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, an
d 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.