xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

数学代写-IGNMENT 1

时间：2021-04-12

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.

学霸联盟

(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.

学霸联盟