1 Question

(a)

i) Write the negation of:

(P) ∀x∀y(x < y → ∃z(x < z < y))

without using the connective ¬. You may however use ≤.

ii) Determine whether or not P is true if the universe of discourse is Z.

(b) Show that S does not logically imply Q where

(S) ∀x∃y(f(y) = x)

(Q) ∀w∃z(f(g(z)) = w)

by finding a non-empty domain and definitions of functions f and g which make S true and Q false.

(c) Express the following two of Hilbert’s axioms for Euclidean plane geometry into formal logic notation:

i) Every line has at least two distinct points.

ii) There are at least three points not on the same line. You may use the following definitions: P = set of points L = set of lines for l ∈ L, x ∈ P, l(x) denotes that point x lies on line l.

2 Solution

(a)

i) ∃x∃y((x < y) ∧ ∀z((z ≤ x) ∨ (y ≤ z)))

ii) False. Take x=3, y=4.

(b) D = {0, 1}, f(x) = x ∀x ∈ D, g(x) = 0 ∀x ∈ D, then S is true and Q is false [let w=1, then 1 ≠ 0 = f(g(0)) and 1 ≠ 0 = f(g(1))] (c)

(i) ∀l ∈ L∃x ∈ P ∃y ∈ P (x ≠ y ∧ l(x) ∧ l(y))

(ii) ∃x ∈ P ∃y ∈ P ∃z ∈ P (x ≠ y ∧ x ≠ z ∧ y ≠ z ∧ ∀l ∈ L(l(x) ∧ l(y) → ¬l(z)))