THE UNIVERSITY OF SYDNEY
MATH3066 ALGEBRA AND LOGIC
Semester 1 Week 10 Solutions 2022
1. Let the universe of discourse be the collection of students in the class. Let F (x)
denote “x is fierce”, G(x) denote “x is friendly”, H(x) denote “x is smiling” and
E(x, y) denote “x and y are the same person”. The statements translate into the
following symbolic forms, taking into account the use of the plural in the third
and fourth statements:
(a) (∀x) (F (x) ∨ G(x))
(b) (∀x) (G(x) ⇒ H(x))
(c) (∃x)(∃y) [( ∼ H(x) ∧ ∼ H(y)) ∧ ∼ E(x, y)]
(d) (∃x)(∃y) [(F (x) ∧ F (y)) ∧ ∼ E(x, y)]
To see that (d) follows logically from (a), (b) and (c), we apply the rules of Pred-
icate Calculus and the well-known sequent P ∨Q, ∼ Q ` P , which is a separate
exercise in the Propositional Calculus, and referenced below as (∗):
1 (1) (∀x) (F (x) ∨ G(x)) A
2 (2) (∀x) (G(x) ⇒ H(x)) A
3 (3) (∃x)(∃y) [( ∼ H(x) ∧ ∼ H(y)) ∧ ∼ E(x, y)] A
4 (4) (∃y) [( ∼ H(a) ∧ ∼ H(y)) ∧ ∼ E(a, y)] A
5 (5)
( ∼ H(a) ∧ ∼ H(b)) ∧ ∼ E(a, b) A
1 (6) F (a) ∨G(a) 1 ∀ E
1 (7) F (b) ∨G(b) 1 ∀ E
2 (8) G(a)⇒ H(a) 2 ∀ E
2 (9) G(b)⇒ H(b) 2 ∀ E
5 (10) ∼ H(a) ∧ ∼ H(b) 5 ∧ E
5 (11) ∼ H(a) 10 ∧ E
5 (12) ∼ H(b) 10 ∧ E
2, 5 (13) ∼ G(a) 8, 11 MT
2, 5 (14) ∼ G(b) 9, 12 MT
1, 2, 5 (15) F (a) 6, 13 SI(S)(∗)
1, 2, 5 (16) F (b) 7, 14 SI(S)(∗)
1, 2, 5 (17) F (a) ∧ F (b) 15, 16 ∧ I
5 (18) ∼ E(a, b) 5 ∧ E
1, 2, 5 (19)
(
F (a) ∧ F (b)) ∧ ∼ E(a, b) 17, 18 ∧ I
1, 2, 5 (20) (∃y) [(F (a) ∧ F (y)) ∧ ∼ E(a, y)] 19 ∃ I
1, 2, 5 (21) (∃x)(∃y) [(F (x) ∧ F (y)) ∧ ∼ E(x, y)] 20 ∃ I
1, 2, 4 (22) (∃x)(∃y) [(F (x) ∧ F (y)) ∧ ∼ E(x, y)] 4, 5, 21 ∃ E
1, 2, 3 (23) (∃x)(∃y) [(F (x) ∧ F (y)) ∧ ∼ E(x, y)] 3, 4, 22 ∃ E
*2. (a) Claim: (∃x)(∃y) F (x, y) 6` (∃x) F (x, x)
Proof: Consider the universe of discourse U = {1, 2} and the relation F =
{(1, 2)}. Then (1, 2) ∈ F , but (1, 1), (2, 2) 6∈ F . Thus F (1, 2) is true, so
that (∃x)(∃y) F (x, y) is true, whilst F (1, 1) and F (2, 2) are false, so that
(∃x)F (x, x) is false. By Soundness of the Predicate Calculus, the conclusion
cannot be deduced from the given hypothesis.
Line (4) to line (5) of the given “proof” is invalid, because a appears in (2).
(b) Claim: (∀y)(∃x) F (x, y) 6` (∃x)(∀y) F (x, y)
Proof: Consider again the universe of discourse U = {1, 2} and the relation
F = {(1, 1), (2, 2)}. Then (1, 1), (2, 2) ∈ F , but (1, 2), (2, 1) 6∈ F . Thus F (1, 1)
is true, so that (∃x)F (x, 1) is true, and F (2, 2) is true, so that (∃x)F (x, 2) is
true. Thus (∀y)(∃x)F (x, y) is true. But F (1, 2) is false, so that (∀y)F (1, y) is
false, and F (2, 1) is false, so that (∀y)F (2, y) is false. Hence (∃x)(∀y) F (x, y)
is false. By Soundness of the Predicate Calculus, the conclusion cannot be
deduced from the given hypothesis.
Line (3) to line (4) of the given “proof” is invalid, because a appears in (3).
3. (a) Claim: (∃x) F (x, x) ` (∃x)(∃y) F (x, y)
Proof:
1 (1) (∃x) F (x, x) A
2 (2) F (a, a) A
2 (3) (∃y) F (a, y) 2 ∃ I
2 (4) (∃x)(∃y) F (x, y) 3 ∃ I
1 (5) (∃x)(∃y) F (x, y) 1, 2, 4 ∃ E
(b) Claim: (∀x)(∀y)(∀z) F (x, y, z) ` (∀z)(∀y)(∀x) F (x, z, y)
Proof:
1 (1) (∀x)(∀y)(∀z) F (x, y, z) A
1 (2) (∀y)(∀z) F (a, y, z) 1 ∀ E
1 (3) (∀z) F (a, b, z) 2 ∀ E
1 (4) F (a, b, c) 3 ∀ E
1 (5) (∀x) F (x, b, c) 4 ∀ I
1 (6) (∀y)(∀x) F (x, b, y) 5 ∀ I
1 (7) (∀z)(∀y)(∀x) F (x, z, y) 6 ∀ I
*(c) Claim: (∀x)(∃y)(∀z) F (x, y, z) ` (∀x)(∀y)(∃z) F (x, z, y)
Proof:
1 (1) (∀x)(∃y)(∀z) F (x, y, z) A
1 (2) (∃y)(∀z) F (a, y, z) 1 ∀ E
3 (3) (∀z) F (a, b, z) A
3 (4) F (a, b, c) 3 ∀ E
3 (5) (∃z) F (a, z, c) 4 ∃ I
1 (6) (∃z) F (a, z, c) 2, 3, 5 ∃ E
1 (7) (∀y)(∃z) F (a, z, y) 6 ∀ I
1 (8) (∀x)(∀y)(∃z) F (x, z, y) 7 ∀ I
*4. (a) Let U = Z+, and for all x, y ∈ Z+, interpret R(x, y) to mean x < y. Certainly,
for each x ∈ Z+, x 6< x, so that W1 holds in U . Furthermore, < is transitive,
that is, for all x, y, z ∈ Z+,
x < y < z ⇒ x < z ,
so that W2 holds in U . Finally, for all x, y ∈ Z+, we can take z = max{x, y}+1,
and it is certainly true that
x < z and y < z ,
so that W3 holds in U . This proves that U serves as a model for W1,W2,W3.
(b) Let U be any model for W1,W2,W3. Certainly we can find x1 ∈ U , since U is
nonempty. Because W3 holds in U , taking x = y = x1, we know there exists
x2 ∈ U such that
R(x, x2) and R(y, x2) ,
so that, certainly, R(x1, x2). Note that x1 is different from x2, because W1
holds. This start an inductive process. Suppose, as an inductive hypothesis,
that n ≥ 2 is a positive integer and that we have found elements x1, . . . , xn ∈
U , all distinct, such that
R(x1, x2) , R(x2, x3) , . . . , R(xn−1, xn) .
Because W3 holds in U , taking x = y = xn, we know there exists xn+1 ∈ U
such that
R(x, xn+1) and R(y, xn+1) ,
so that, certainly, R(xn, xn+1). Hence we have
R(x1, x2) , R(x2, x3) , . . . , R(xn−1, xn) , R(xn, xn+1) .
Suppose that xn+1 = xm for some m ≤ n. But we have
R(xm, xm+1) , R(xm+1, xm+2) , . . . , R(xn, xn+1) .
By applying W2 repeatedly, we get R(xm, xn+1), so that
R(xm, xm) ,
which contradicts W1. This proves that x1, . . . , xn+1 are all distinct. By
induction, we have a list of distinct elements
x1 , x2 , . . . , xn , . . .
of U (in fact an injective map from Z+ into U), which proves U is infinite.
Thus no finite model of W1,W2,W3 exists.