THE UNIVERSITY OF SYDNEY
MATH3066 ALGEBRA AND LOGIC
Semester 1 Week 9 Solutions 2022
1. Let the universe of discourse be the collection of people. Let A(x) denote “x is
from Australia”, E(x) denote “x is from Europe” and S(x) denote “x is from
the Southern Hemisphere”. The statements translate loosely into the following
symbolic forms:
(a) (∀x) (A(x) ⇒ S(x))
(b) (∀x) (E(x) ⇒ ∼ S(x))
(c) (∀x) (A(x) ⇒ ∼ E(x))
To see that (c) follows logically from (a), (b), we apply the rules of Predicate
Calculus:
1 (1) (∀x) (A(x) ⇒ S(x)) A
2 (2) (∀x) (E(x) ⇒ ∼ S(x)) A
3 (3) A(b) A
1 (4) A(b)⇒ S(b) 1 ∀ E
2 (5) E(b)⇒ ∼ S(b) 2 ∀ E
1, 3 (6) S(b) 3, 4 MP
1, 3 (7) ∼∼ S(b) 6 DN
1, 2, 3 (8) ∼ E(b) 5, 7 MT
1, 2 (9) A(b) ⇒ ∼ E(b) 2, 8 CP
1, 2 (10) (∀x) (A(x) ⇒ ∼ E(x)) 9 ∀ I
The statement “No Australian lives in Europe” is clearly false, so either our loose
translation into symbolism has an error, or perhaps one of the hypotheses (a) or
(b) is faulty. In fact “being from” is not the same predicate as “living in”, so the
fault is in the looseness of the translation.
*2. Let P be the set of people and T be the set of all possible times. Let F (x, t) mean
“x is fooled at time t”. (The relation F is a subset of P × T .) The statements
may be translated into the following:
(a) (∃x ∈ P )(∀t ∈ T ) F (x, t)
(b) (∃t ∈ T )(∀x ∈ P ) F (x, t)
(c) ∼ [(∀x ∈ P )(∀t ∈ T ) F (x, t)]
One could take a literal translation of the words of (b) to get the following weaker
symbolic statement:
(b)′ (∀x ∈ P )(∃t ∈ T ) F (x, t)
which is probably not what Abraham Lincoln intended. In any case, if (a), (b)
and (c) are consistent, then certainly (a), (b)′ and (c) are consistent (because (b)
implies (b)′). To see consistency, it suffices to construct a model in which they are
all true. Let P = {x1, x2} and T = {t1, t2}, where there are exactly two people x1
and x2 and exactly two times t1 and t2. Now put
F = {(x1, t1), (x2, t2), (x1, t2)} .
Observe that (x1, t1), (x1, t2) ∈ F , which translates to “F (x1, t) is true for all t.”
Thus x1 is fooled all the time, so (a) is true. Observe also that (x1, t2), (x2, t2) ∈ F ,
which translates to “F (x, t2) is true for all x.” Thus at time t2, all of the people
are fooled, so (b) is true. Finally, observe that (x2, t1) 6∈ F , which translates to
“F (x2, t1) is false”, so not everyone is fooled all of the time, so (c) is true. Hence
(a), (b), (c) are consistent.
3. (a) Claim: (∀x)(F (x)⇒ G(x)) ` (∀x)F (x) ⇒ (∀x)G(x)
Proof:
1 (1) (∀x) (F (x) ⇒ G(x)) A
2 (2) (∀x) F (x) A
1 (3) F (a)⇒ G(a) 1 ∀ E
2 (4) F (a) 2 ∀ E
1, 2 (5) G(a) 3, 4 MP
1, 2 (6) (∀x)G(x) 5 ∀ I
1 (7) (∀x) F (x) ⇒ (∀x)G(x) 2, 6 CP
(b) Claim: (∀x)(F (x)⇒∼ G(x)), (∀x)(H(x)⇒ G(x)) ` (∀x)(F (x)⇒∼ H(x))
Proof:
1 (1) (∀x) (F (x) ⇒ ∼ G(x)) A
2 (2) (∀x) H(x)⇒ G(x) A
3 (3) F (a) A
1 (4) F (a)⇒∼ G(a) 1 ∀ E
2 (5) H(a)⇒ G(a) 2 ∀ E
1, 3 (6) ∼ G(a) 3, 4 MP
1, 2, 3 (7) ∼ H(a) 5, 6 MT
1, 2 (8) F (a)⇒∼ H(a) 3, 7 CP
1, 2 (9) (∀x)(F (x)⇒∼ H(x)) 8 ∀ I
*(c) Claim: (∀x)((F (x) ∨G(x))⇒ H(x)) , (∀x) ∼ H(x) ` (∀x) ∼ F (x)
Proof:
1 (1) (∀x)((F (x) ∨G(x))⇒ H(x)) A
2 (2) (∀x) ∼ H(x) A
3 (3) F (a) A
1 (4) (F (a) ∨G(a))⇒ H(a) 1 ∀ E
2 (5) ∼ H(a) 2 ∀ E
1, 2 (6) ∼ (F (a) ∨G(a)) 4, 5 MT
3 (7) F (a) ∨G(a) 3 ∨ I
1, 2, 3 (8) (F (a) ∨G(a))∧ ∼ (F (a) ∨G(a)) 6, 7 ∧ I
1, 2 (9) ∼ F (a) 3, 8 RAA
1, 2 (10) (∀x) ∼ F (x) 9 ∀ I
*(d) Claim: (∀x)(G(x)⇒ H(x)) , (∃x)(G(x) ∧ F (x)) ` (∃x)(F (x) ∧H(x))
Proof:
1 (1) (∀x)(G(x)⇒ H(x)) A
2 (2) (∃x)(G(x) ∧ F (x)) A
3 (3) G(a) ∧ F (a) A
1 (4) G(a)⇒ H(a) 1 ∀ E
3 (5) G(a) 3 ∧ E
1, 3 (6) H(a) 4, 5 MP
3 (7) F (a) 3 ∧ E
1, 3 (8) F (a) ∧H(a) 6, 7 ∧ I
1, 3 (9) (∃x)(F (x) ∧H(x)) 8 ∃ I
1, 2 (10) (∃x)(F (x) ∧H(x)) 2, 3, 9 ∃ E
*(e) Claim: (∃x)(G(x)∧ ∼ H(x)), (∀x)(G(x)⇒ F (x)) ` (∃x)(F (x)∧ ∼ H(x))
Proof:
1 (1) (∃x)(G(x)∧ ∼ H(x)) A
2 (2) (∀x)(G(x)⇒ F (x)) A
3 (3) G(a)∧ ∼ H(a) A
2 (4) G(a)⇒ F (a) 2 ∀ E
3 (5) G(a) 3 ∧ E
2, 3 (6) F (a) 4, 5 MP
3 (7) ∼ H(a) 3 ∧ E
2, 3 (8) F (a)∧ ∼ H(a) 6, 7 ∧ I
2, 3 (9) (∃x)(F (x)∧ ∼ H(x)) 8 ∃ I
1, 2 (10) (∃x)(F (x)∧ ∼ H(x)) 1, 3, 9 ∃ E
(f) Claim: (∀x)(F (x) ∧G(x)) ` (∀x)F (x) ∧ (∀x)G(x)
Proof:
1 (1) (∀x)(F (x) ∧G(x)) A
1 (2) F (a) ∧G(a) 1 ∀ E
1 (3) F (a) 2 ∧ E
1 (4) (∀x)F (x) 3 ∀ I
1 (5) G(a) 2 ∧ E
1 (6) (∀x)G(x) 5 ∀ I
1 (7) (∀x)F (x) ∧ (∀x)G(x) 4, 6 ∧ I
(g) Claim: (∀x)F (x) ∧ (∀x)G(x) ` (∀x)(F (x) ∧G(x))
Proof:
1 (1) (∀x)F (x) ∧ (∀x)G(x) A
1 (2) (∀x)F (x) 1 ∧ E
1 (3) F (a) 2 ∀ E
1 (4) (∀x)G(x) 1 ∧ E
1 (5) G(a) 4 ∀ I
1 (6) F (a) ∧G(a) 3, 5 ∧ I
1 (7) (∀x)(F (x) ∧G(x)) 6 ∀ I
*(h) Claim: (∃x)(F (x) ∨G(x)) ` (∃x)F (x) ∨ (∃x)G(x)
Proof:
1 (1) (∃x)(F (x) ∨G(x)) A
2 (2) F (a) ∨G(a) A
3 (3) F (a) A
3 (4) (∃x)F (x) 3 ∃ I
3 (5) (∃x)F (x) ∨ (∃x)G(x) 4 ∨ I
6 (6) G(a) A
6 (7) (∃x)G(x) 6 ∃ I
6 (8) (∃x)F (x) ∨ (∃x)G(x) 7 ∨ I
2 (9) (∃x)F (x) ∨ (∃x)G(x) 2, 3, 5, 6, 8 ∨ E
1 (10) (∃x)F (x) ∨ (∃x)G(x) 1, 2, 9 ∃ E
*(i) Claim: (∃x)F (x) ∨ (∃x)G(x) ` (∃x)(F (x) ∨G(x))
Proof:
1 (1) (∃x)F (x) ∨ (∃x)G(x) A
2 (2) (∃x)F (x) A
3 (3) F (a) A
3 (4) F (a) ∨G(a) 3 ∨ I
3 (5) (∃x)(F (x) ∨G(x)) 4 ∃ I
2 (6) (∃x)(F (x) ∨G(x)) 2, 3, 5 ∃ E
7 (7) (∃x)G(x) A
8 (8) G(a) A
8 (9) F (a) ∨G(a) 8 ∨ I
8 (10) (∃x)(F (x) ∨G(x)) 9 ∃ I
7 (11) (∃x)(F (x) ∨G(x)) 7, 8, 10 ∃ E
1 (12) (∃x)(F (x) ∨G(x)) 1, 2, 6, 7, 11 ∨ E
*(j) Claim: (∀x)F (x) ∨ (∀x)G(x) ` (∀x)(F (x) ∨G(x))
Proof:
1 (1) (∀x)F (x) ∨ (∀x)G(x) A
2 (2) (∀x)F (x) A
2 (3) F (a) 2 ∀ E
2 (4) F (a) ∨G(a) 3 ∨ I
2 (5) (∀x)(F (x) ∨G(x)) 4 ∀ I
6 (6) (∀x)G(x) A
6 (7) G(a) 6 ∀ E
6 (8) F (a) ∨G(a) 7 ∨ I
6 (9) (∀x)(F (x) ∨G(x)) 8 ∀ I
1 (10) (∃x)(F (x) ∨G(x)) 1, 2, 5, 6, 9 ∨ E
*4. Let U = {1, 2}, a two element universe of discourse with distinct objects 1 and 2.
Suppose that F (x) means “x = 1” and G(x) means “x = 2”. Then
(∀x)(F (x) ∨G(x)) is true,
because, for each x ∈ U , either x = 1 or x = 2. However,
F (2) is false,
so that
(∀x)F (x) is false.
Similarly,
G(1) is false,
so that
(∀x)G(x) is false.
Hence
(∀x)F (x) ∨ (∀x)G(x) is false,
whilst
(∀x)F (x) ⇒ (∀x)G(x) is trivially true.
Note further that
F (1) is true
so that
F (1) ⇒ G(1) is false,
so that
(∀x)(F (x) ⇒ G(x)) is false.
Hence the sequents
(∀x)F (x) ⇒ (∀x)G(x) ` (∀x)(F (x)⇒ G(x))
and
(∀x)(F (x) ∨G(x)) ` (∀x)F (x) ∨ (∀x)G(x)
cannot be proved using the rules of Predicate Calculus, for otherwise, in each case,
you would have a false conclusion following from a true premise, contradicting
Soundness.