SOLUTIONS FOR ASSIGNMENT 1
(1) (a) (i) [? 4 points ?] Claim: P ⇒ Q, Q⇒ R ` P ⇒ R
Proof.
1 (1) P ⇒ Q A
2 (2) Q⇒ R A
3 (3) P A
1,3 (4) Q MP 1,3
1,2,3 (5) R MP 2,4
1,2 (6) P ⇒ R CP 3,5

(ii) [? 4 points ?]Claim: P, P ⇔ Q ` Q
Proof.
1 (1) P A
2 (2) P ⇔ Q A
2 (3) (P ⇒ Q) ∧ (Q⇒ P ) Def 2
2 (4) P ⇒ Q ∧ E 3
1,2 (5) Q MP 1,4

(iii) [? 4 points ?]Claim: P, ∼ (P ∧Q) ` ∼ Q
Proof.
1 (1) P A
2 (2) ∼ (P ∧Q) A
3 (3) Q A
1,3 (4) P ∧Q ∧ I 1,3
1,2,3 (5) (P ∧Q) ∧ (∼ (P ∧Q)) ∧ I 2,4
1,2 (6) ∼ Q RAA 3,5

(iv) [? 4 points ?]Claim: P ∧ (Q ∨R) ` (P ∧Q) ∨ (P ∧R)
Proof.
1 (1) P ∧ (Q ∨R) A
1 (2) P ∧E 1
1 (3) Q ∨R ∧E 1
4 (4) Q A
1,4 (5) P ∧Q ∧I 2,4
1,4 (6) (P ∧Q) ∨ (P ∧R) ∨I 5
7 (7) R A
1,7 (8) P ∧R ∧I 2,7
1,7 (9) (P ∧Q) ∨ (P ∧R) ∨I 8
1 (10) (P ∧Q) ∨ (P ∧R) ∨E 3,4,6,7,9

1
2 SOLUTIONS FOR ASSIGNMENT 1
(b) (i) [? 2 points ?]
P Q ∼ P P ⇒ Q (∼ P )⇒ (P ⇒ Q)
T T F T T
T F F F T
F T T T T
F F F T T
(ii) [? 2 points ?]
P Q R P ∧Q ∼ R P ∧ (∼ R) (P ∧Q) ∨ (P ∧ (∼ R))
T T T T F F T
T T F T T T T
T F T F F F F
T F F F T T T
F T T F F F F
F T F F T F F
F F T F F F F
F F F F T F F
(c) (i) [? 4 points ?]
(∼ Q) ⇒ (P ⇒ (Q ⇒ R))
T F F T F T F F
2 8 1 4 3 6 5 7
Comparing steps 6 and 8 we reach a contradiction, hence it’s a theorem.
(ii) [? 4 points ?]
(P ⇒ R) ⇒ ((Q ⇒ R) ⇒ ((P ∨Q) ⇒ R))
F T F F F T F F T F F
11 2 9 1 10 4 8 3 6 5 7
Comparing steps 6,10 and 11 we reach a contradiction, hence it’s a theorem.
(2) (a) (i) [? 3 points ?] Suppose the sequent (P ⇒ Q)⇒ (∼ P ), P ⇒ Q ` P is valid. Then
by the Soundness Theorem (P ⇒ Q) ⇒ (∼ P ), P ⇒ Q ( P is valid as well.
But suppose that V (P ) = F . Then we would have that V (P ⇒ Q) = T and
V ((P ⇒ Q) ⇒ (∼ P )) = T . This shows that (P ⇒ Q) ⇒ (∼ P ), P ⇒ Q * P .
This is a contradiction, and hence the sequent cannot be valid.
(ii) [? 3 points ?] We apply the same idea as part (i) above. This time, we take
V (P ) = F and V (Q) = T . Then V ((P ⇒ Q) ⇒ (Q ⇒ P )) = F . This shows
that * (P ⇒ Q) ⇒ (Q ⇒ P ), so by the Soundness Theorem it follows that the
sequence ` (P ⇒ Q)⇒ (Q⇒ P ) is not valid.
(b) [? 4 points ?] Consider the sequent S : W1, ...,Wn ` W . We let N ≥ 1 and suppose
the Soundness Theorem holds for any sequent which has a proof in at most N lines.
Suppose S has a proof in N + 1 lines, and the last line is an application of DN . Then
SOLUTIONS FOR ASSIGNMENT 1 3
the proof looks like:
...
A (r) X · · ·
...
A (N + 1) W DN, r
Here X is a wff and A is a set of assumptions. Note that since this is a valid proof of
W we must have that A ⊂ {W1, ...,Wn}.
The first r lines of this proof prove that the sequent W1, ...,Wn ` X is valid. Since
r ≤ N the inductive hypothesis applies to this sequent, and we can deduce that
W1, ...,Wn ( X holds. Now since we are applying DN we must have that either
X =∼ (∼W ) or W =∼ (∼ X).
We want to show that W1, ...,Wn (W holds. To this end, suppose that V (W1) = · · · =
V (Wn) = T . Then V (X) = T since W1, ...,Wn ( X. In either case (X =∼ (∼ W ) or
W =∼ (∼ X)) this implies that V (W ) = T as well, completing this proof.
(c) Suppose W is built out of propositional variables P1, ..., Pn. Fix a choice of truth values
V (P1), ..., V (Pn) ∈ {T, F}. Recall that from this choice we define
Wi =
{
Pi if V (Pi) = T, and
∼ Pi if V (Pi) = F,
and the Key Lemma states: V (W ) = T ⇒ W1, ...,Wn ` W , and V (W ) = F ⇒
W1, ...,Wn ` ∼W .
(i) [? 6 points ?] Now suppose that W = X ∨ Y where X,Y are some wffs. Note
that necessarily X,Y are also built out of P1, ..., Pn and `(X), `(Y ) ≤ N . Hence
the Key Lemma holds for X and Y .
If V (W ) = T then V (X) = T or V (Y ) = T . In the case V (X) = T the
Key Lemma implies that S1 : W1, ...,Wn ` X is valid. Here is a proof that
W1, ...,Wn `W :
1 (1) W1 A
...
n (n) Wn A
1, ..., n (n + 1) X SI(S1) 1, ..., n
1, ..., n (n + 2) X ∨ Y ∨I n + 1
1, ..., n (n + 3) W Def n + 2
The case V (Y ) = T is the same, except the roles of X and Y are interchanged
in the above proof.
If V (W ) = F then V (X) = V (Y ) = F . Since `(X), `(Y ) ≤ N we can use the
Key Lemma to deduce that S2 : W1, ...,Wn `∼ X and S3 : W1, ...,Wn `∼ Y are
both valid. We’d like to prove that W1, ...,Wn ` ∼W is valid.
Before doing so, we need to a lemma, which is essentially a part of de Morgan’s
laws in syntactic form. Recall that in lecture we proved the from a contradiction
one can prove anything, i.e. that the sequent S4 : S ∧ (∼ S) ` T is valid, where
S, T are any wffs.
4 SOLUTIONS FOR ASSIGNMENT 1
Now we will prove the following sequent is valid
S5 : (∼ X) ∧ (∼ Y ) `∼ (X ∨ Y )
1 (1) (∼ X) ∧ (∼ Y ) A
1 (2) ∼ X ∧E 1
1 (3) ∼ Y ∧E 1
4 (4) X ∨ Y A
5 (5) X A
1,5 (6) X ∧ (∼ X) ∧I 1, 5
7 (7) Y A
1,7 (8) Y ∧ (∼ Y ) ∧I 3, 7
1,7 (9) X ∧ (∼ X) SI(S4) 8
1,4 (10) X ∧ (∼ X) ∨E 4, 5, 6, 7, 9
1 (11) ∼ (X ∨ Y ) RAA 4, 10
Note that in line (9), we are applying sequent introduction with substitution,
where we substitute S = Y and T = X ∧ (∼ X).
Now we are ready to prove that W1, ...,Wn ` ∼W is valid:
1 (1) W1 A
...
n (n) Wn A
1, ..., n (n + 1) ∼ X SI(S2) 1, ..., n
1, ..., n (n + 2) ∼ Y SI(S3) 1, ..., n
1, ..., n (n + 3) (∼ X) ∧ (∼ Y ) ∧I n + 1, n + 2
1, ..., n (n + 4) ∼ (X ∨ Y ) SI(S5) n + 3
1, ..., n (n + 5) ∼W Def n + 4
(ii) [? 6 points ?] In preparation for this case we need two sequents. The first is:
S6 : (∼ X) ∨ Y ` X ⇒ Y
1 (1) (∼ X) ∨ Y A
2 (2) X A
3 (3) ∼ X A
2,3 (4) X ∧ (∼ X) ∧I 2,3
2,3 (5) Y SI(S4) 4
6 (6) Y A
1,2 (7) Y ∨E 1,3,5,6,6
1 (8) X ⇒ Y CP 2, 7
Before we prove the second sequent, we note an easy theorem. Suppose S, T are
wffs. Then
S ` T =⇒ ∼ T ` ∼ S (0.1)
Indeed, suppose S7 : S ` T is valid. There here’s a proof of ∼ T ` ∼ S:
1 (1) ∼ T A
2 (2) S A
2 (3) T SI(S7) 2
1,2 (4) T ∧ (∼ T ) ∧I 1,3
2,4 (5) ∼ S RAA 2, 4
SOLUTIONS FOR ASSIGNMENT 1 5
Now, the second sequent we want to prove is S8 : ∼ ((∼ X) ∨ Y ) ` ∼ (X ⇒ Y ).
By (0.1) this will follow if we prove S9 : X ⇒ Y ` (∼ X) ∨ Y . Here’s a proof of
S9:
1 (1) X ⇒ Y A
(2) X ∨ (∼ X) TI
3 (3) X A
1,3 (4) Y MP 1, 3
1,3 (5) (∼ X) ∨ Y ∨I 4
6 (6) ∼ X A
6 (7) (∼ X) ∨ Y ∨I 6
1 (8) (∼ X) ∨ Y ∨E 2, 3, 5, 6, 7
This proves S9 and hence also S8.
Now we suppose that W = X ⇒ Y . Since `(X), `(Y ) ≤ N the Key Lemma
applies to X,Y . If V (W ) = T we have that either V (X) = F or V (X) =
V (Y ) = T .
If V (X) = F then we get that S2 is valid. Here’s a proof that W1, ...,Wn `W is
valid:
1 (1) W1 A
...
n (n) Wn A
1, ..., n (n + 1) ∼ X SI(S2) 1, ..., n
1, ..., n (n + 2) (∼ X) ∨ Y ∨I n + 1
1, ..., n (n + 3) X ⇒ Y SI(S6) n + 2
1, ..., n (n + 4) W Def n + 3
If V (X) = V (Y ) = T then in particular we get that S10 : W1, ...,Wn ` Y is
valid. Then the proof of W1, ...,Wn ` W is the same as the above one, except
we replace the n + 1-th line by
1, ..., n (n + 1) Y SI(S10) 1, ..., n
If V (W ) = F then V (X) = T and V (Y ) = F . Hence we get that S1 and S3 are
valid. Here’s a proof that W1, ...,Wn ` ∼W is valid:
1 (1) W1 A
...
n (n) Wn A
1, ..., n (n + 1) X SI(S1) 1, ..., n
1, ..., n (n + 2) ∼ Y SI(S3) 1, ..., n
1, ..., n (n + 3) ∼ (∼ X) DN n + 1
1, ..., n (n + 4) ∼ (∼ X) ∧ (∼ Y ) ∧I n + 2, n + 3
1, ..., n (n + 5) ∼ ((∼ X) ∨ Y ) SI(S5) n + 4
1, ..., n (n + 6) ∼ (X ⇒ Y ) SI(S8) n + 5
1, ..., n (n + 7) ∼W Def n + 6
(3) (a) [? 5 points ?] First we note the following two computations:
25 ≡ 4 (mod 7)
42 ≡ 2 (mod 7) =⇒ 44 ≡ 4 (mod 7)
6 SOLUTIONS FOR ASSIGNMENT 1
Using these computations we proceed as follows:
2525 ≡ 425 (mod 7)
≡ 4244 (mod 7)
≡ (44)64 (mod 7)
≡ 464 (mod 7)
≡ 4443 (mod 7)
≡ 4(43) (mod 7)
≡ 44 (mod 7)
≡ 4 (mod 7)
Hence if today is Monday in 2525 days it will be Friday.
(b) (i) [? 5 points ?]First we note that we have x = dk(10
k−1) + dk−1(10k−2) + · · · +
d2(10) + d1. Observe that:
10 ≡ 1 (mod 9)
10 ≡ 1 (mod 3)
10 ≡ −1 (mod 11)
Therefore we have that
x ≡ dk(10k−1) + dk−1(10k−2) + · · ·+ d2(10) + d1 (mod 9)
≡ dk(1k−1) + dk−1(1k−2) + · · ·+ d2(1) + d1 (mod 9)
≡ dk + dk−1 + · · ·+ d2 + d1 (mod 9)
Replacing 9 by 3 above we also get that x ≡ dk + dk−1 + · · ·+ d2 + d1 (mod 3).
We also have that
x ≡ dk(10k−1) + dk−1(10k−2) + · · ·+ d2(10) + d1 (mod 11)
≡ dk(−1)k−1 + dk−1(−1)k−2 + · · ·+ d2(−1) + d1 (mod 11)
≡ d1 − d2 + d3 − · · ·+ (−1)k−1dk (mod 11)
(ii) [? 4 points. Some people may have interpreted this question as asking to apply
the divisibility test on four separate 3 digit numbers. That’s ok - no penalty for
my ambiguously phrased question. ?]We can use to define easy divisibility tests
for any number. For instance, to check if a number is divisible by 9, we just add
all its digits and check if the result is divisible by 9. The same would hold if 9
is replaced by 3. To check if a number is divisible by 11 we take the alternating
sum of all its digits and check if that is divisible by 11.
For instance, the sum of the digits of x = 911, 219, 186, 429 is 53 which is not
divisible by 3 nor 9. Hence x is not divisible by 3 nor 9. The alternating sum of
the digits of x is 9− 2 + 4− 6 + 8− 1 + 9− 1 + 2− 1 + 1− 9 = 13 which is not
divisible by 11. Hence x is also not divisible by 11.
SOLUTIONS FOR ASSIGNMENT 1 7
(4) (a) [? 6 points ?] As sets we have R = {I, 1 + I, x + I, x + 1 + I} and S = {J, 1 + J, x +
J, x + 1 + J}. Here is the addition table for R:
I 1 + I x + I x + 1 + I
I I 1 + I x + I x + 1 + I
1 + I 1 + I I x + 1 + I x + I
x + I x + I x + 1 + I I 1 + I
x + 1 + I x + 1 + I x + I 1 + I I
The addition table for S is the same, except every instance of I should be replaced by
a J .
Here is the multiplication table for R:
R I 1 + I x + I x + 1 + I
I I I I I
1 + I I 1 + I x + I x + 1 + I
x + I I x + I 1 + I x + 1 + I
x + 1 + I I x + 1 + I x + 1 + I I
Here is the multiplication table for S:
S J 1 + J x + J x + 1 + J
J J J J J
1 + J J 1 + J x + J x + 1 + J
x + J J x + J x + J J
x + 1 + J J x + 1 + J J x + 1 + J
(b) [? 6 points ?] We claim that R and S are not isomorphic. Indeed, suppose we have an
isomorphism f : R→ S. Since we must have that f(I) = J , i.e. f maps the zero in R
to the zero in S, it follows that f induces a bijection between the nonzero elements of
R to the nonzero elements of S. Therefore
f((1 + I)(x + I)(x + 1 + I)) = f(1 + I)f(x + I)f(x + 1 + I) (0.2)
= (1 + J)(x + J)(x + 1 + J) (0.3)
This implies that f(x + 1 + I) = J , a contradiction since the isomorphism can’t map
a nonzero element of R to the zero element of S.
Note that in (0.3) we are not claiming that f(1+I) = 1+J, f(x+I) = x+J, f(x+1+I) =
x + 1 + J . We are using the fact that
{f(1 + I), f(x + I), f(x + 1 + I)} = {1 + J, x + J, x + 1 + J}
(5) (a) [? 6 points ?]First we show that ∼ is an equivalence relation. For x, y, z ∈ X we have:
x ∼ x since f(x) = f(x) (reflexivity), x ∼ y =⇒ f(x) = f(y) =⇒ f(y) = f(x) =⇒ y ∼
x (symmetry), and (x ∼ y) ∧ (y ∼ z) =⇒ (f(x) = f(y)) ∧ (f(y) = f(z)) =⇒ f(x) =
f(z) =⇒ x ∼ z (transitivity).
Define ϕ : X/∼ → im(f) by ϕ([x]) = f(x). We claim that ϕ is a well-defined function.
Suppose that [x] = [y]; we need to show that ϕ([x]) = ϕ([y]). Indeed,
[x] = [y] =⇒ x ∼ y =⇒ f(x) = f(y) =⇒ ϕ([x]) = ϕ([y])
Now we’ll show that ϕ is a bijection. To prove injectivity, suppose that ϕ([x]) = ϕ([y])
for [x], [y] ∈ X/∼. Then f(x) = f(y), so x ∼ y, and hence [x] = [y]. To prove
surjectivity, let z ∈ im(f). Then z = f(x) for some x ∈ X, and hence ϕ([x]) = z.
8 SOLUTIONS FOR ASSIGNMENT 1
(b) [? 6 points ?]We define ϕ : Z[x]→ Z[i] by ϕ(p(x)) = p(i). This is a ring homomorphism
since if p(x), q(x) ∈ Z[x] then
ϕ(p(x)) + ϕ(q(x)) = p(i) + q(i) = ϕ(p(x) + q(x))
ϕ(p(x))ϕ(q(x)) = p(i)q(i) = ϕ(p(x)q(x)).
Given a + bi ∈ Z[x] we have that ϕ(a + bx) = a + bi, proving that ϕ is surjective, i.e.
im(ϕ) = Z[i]. Next, we claim that ker(ϕ) = I. Indeed, I ⊂ ker(ϕ) since if p(x) ∈ I
then p(x) = (x2 + 1)q(x) for some q(x) ∈ Z[x]. Hence p(i) = (i2 + 1)q(i) = 0, so
p(x) ∈ ker(ϕ). Conversely, if p(x) ∈ ker(ϕ) then p(i) = 0. By the fact in the statement
of the problem, this implies that x2 + 1 divides p(x), i.e. p(x) ∈ I. This shows that
ker(ϕ) = I. By the First Isomorphism Theorem we conclude that Z[x]/I ∼= Z[i].
(6) (a) [? 6 points ?] Let x + ay, x′ + ay′ ∈ J . Then
(x + ay) + (x′ + ay′) = (x + x′) = a(y + y′) ∈ J
since x+ x′ ∈ I. Moreover, if z ∈ R then (x+ ay)z = xz + ayz ∈ J since xz ∈ I. This
shows that J is an ideal. We have that I ⊂ J since for any x ∈ I, x = x + a0 ∈ J .
(b) [? 6 points ?] Let a + I ∈ R/I be a nonzero element. To show that R/I is a field we
need to show that a + I has a multiplicative inverse. Since a + I is nonzero we have
that a /∈ I. Consider J = I + aR as in part (a). By (a), J is an ideal of R containing
I. Moreover, since a ∈ J and a /∈ I we have that I 6= J . Since I is large we must have
that J = R. In particular, this implies that 1 ∈ J , i.e. 1 = x + ay for some elements
y ∈ R, x ∈ I. Hence we get that
(a + I)(y + I) = ay + I
= ay + x + I
= 1 + I
Note that the second equality follows since (ay + x)− (ay) ∈ I. This shows that y + I
is the multiplicative inverse of a + I, and hence we conclude that R/I is a field.






























































































































































































































































































































学霸联盟