1. (a) Given any two propositions P and Q, prove de Morgan’s laws in propositional logic:

:(P _ Q) = (:P) ^ (:Q);

:(P ^ Q) = (:P) _ (:Q):

(b) Prove de Morgan’s laws in set theory: Given two sets A;B X, show that

(A [ B)c = Ac Bc;

(A B)c = Ac [ Bc:

Recall that the complement of A X is the set Ac := fx 2 X : x =2 Ag.

(c) Explain brie

y how the results of part (a) and (b) are related. Notice that the

symbols _ and ^ can be easily remembered via the symbols (which you may be

more familiar with) in set theory [ and .

2. (a) Suppose p 2 N. Show that if p2 is divisible by 5 then p is also divisible by 5 (Hint:

write p = 5s + r with appropriate conditions for s and r).

(b) Prove that

p

5 is irrational.

(c) Suppose you try the same argument to prove

p

4 is irrational. The proof must fail,

but where exactly does it fail?

3. Consider a function f : X 7! Y and let A X and B X

(a) Show that f(A [ B) = f(A) [ f(B)

(b) Show that f(A B) f(A) f(B)

(c) Prove that the converse statement f(A) f(B) f(A B) is false (Hint: nd a

counterexample)

(d) Give an extra condition on f and prove that with your extra condition we have

f(A) f(B) f(A B)

(e) Consider a function f : X 7! Y . Given a subset C Y , we dene its inverse image

(or preimage) as f 1(C) := fx 2 X : f(x) 2 Cg. Notice that f 1(C) X and that

f 1(C) makes sense even if f does not have an inverse. Let C Y and D Y .

Prove that

f 1(C [ D) = f 1(C) [ f 1(D)

f 1(C D) = f 1(C) f 1(D):

Note that these set equalities above easily generalise to arbitrary (i.e. `innite’)

collections of sets.

4. Use the principle of mathematical induction to prove the following identity:

1 + r + r2 + + rn =

1 rn+1

1 r

for r 6= 1:

5. In class, we saw an axiomatic foundation of N. Making use of the notion of successor, we

can make an appropriate denition of + (i.e. addition behaves as we learnt way back).

Furthermore, we can make sense of m n when m > n. You may assume these two

facts from now on. Now, you will be guided through a foundational construction of Z.

Consider the set N N and the following relation:

(m1; n1) (m2; n2) if m1 + n2 = n1 + m2

(Perhaps after the end of this problem, I recommend coming back and trying to under-

stand why the equivalence relation dened as above would work to construct Z. Try to

draw a picture.)

(a) Show that is an equivalence relation on NN (recall the cancellative law: m+n =

m + `, for m; n; ` 2 N, then n = `)

(b) Show that if (m1; n1) (m2; n2) and (a1; b1) (a2; b2), then (m1 + a1; n1 + b1)

(m2 + a2; n2 + b2)

Call Z the set of equivalence classes in N N with respect to the relation . That

is, Z := f[(m; n)] : (m; n) 2 N Ng. Recall that [(m; n)] denotes the equivalence

class of N. We now identify a copy of N inside of Z. For every n 2 N, we declare

[(n + 1; 1)] to be the corresponding element in Z (i.e. we have set up a bijection from N

to fz 2 Z : z = [(n + 1; 1)] for some n 2 Ng). That is, when we think of the natural

number n as an integer, we use [(n + 1; 1)] 2 Z.

(c) Use part (b) to show the following: if [(m1; n1)] = [(m2; n2)] and [(a1; b1)] =

[(a2; b2)], then [(m1 + a1; n1 + b1)] = [(m2 + a2; n2 + b2)]

Part (c) shows us how to dene addition + on Z as follows: we dene [(m; n)]+[(a; b)] =

[(m + a; n + b)].

(d) Show that for every [(m; n)] 2 Z, we have [(m; n)] + [(1; 1)] = [(m; n)]

Part (d) tells us that [(1; 1)] is the additive identitiy in (Z; +); i.e. it is what we usually

denote by 0.

(e) Show that for every [(m; n)] 2 Z, we have [(m; n)] + [(n;m)] = [(1; 1)]

Part (e) tells us that the additive inverse of [(m; n)] is [(n;m)] and we write [(n;m)] =

[(m; n)]. In particular, we have made sense of what we usually denote by n for n 2 N

(f) Show that every integer [(m; n)] 2 Z is either a natural number (i.e. of the form

[(a; 1)], 0 (i.e. of the form [(a; a)]), or the opposite of a natural number. Hint:

you may nd it useful to distinguish three case: m > n, m = n and m < n.

Furthermore, remember that m n 2 N when m > n, and similarly n m 2 N

when n > m).

Part (f) tells us that Z is nothing but the natural numbers, their negatives, and zero.

That is, Z is what we usually think of as the integers.

6. In Problem 4, we constructed the integers Z. With some work we can dene the multi-

plication on Z. In this exercise, we will assume that we already have a knowledge of Z

together with + and . Our goal is to dene Q. Consider the set Z (Z n f0g) and the

following relation:

(m1; n1) (m2; n2) if m1 n2 = n1 m2:

(Again, try to draw a picture)

(a) Show that is an equivalence relation on Z (Z n f0g)

(b) Show that if (m1; n1) (m2; n2) and (a1; b1) (a2; b2), then

(m1 b1 + a1 n1; n1 b1) (m2 b2 + a2 n2; n2 b2)

and that (m1 a1; n1 b1) (m2 a2; n2 b2)

Call Q the set of equivalence classes in Z (Z n f0g) with respect to the equivalence

relaiton . Notice that the equivalence class [(m; n)] 2 Q is nothing but what we usually

denote by m

n . Part (b) allows us to dene + and on Q: for every [(m; n)]; [(a; b)] 2 Q,

we dene [(m; n)] + [(a; b)] = [(m b + a n; n b)] and [(m; n)] [(a; b)] = [(m a; n b)]

(can you motivate these denitions?)

(c) Now, we want to nd a copy of Z inside Q. For every n 2 Z, determine a rational

number [(a; b)] 2 Q that corresponds to n. (Hint: intuitively, we want to write an

integer as a fraction).

(d) Show that for every [(m; n) 2 Q, we have [(m; n)] + [(0; 1)] = [(m; n)] and [(m; n)]

[(1; 1)] = [(m; n)]

(e) For every [(m; n)] 2 Q, nd [(a; b)] 2 Q such that [(m; n)] + [(a; b)] = [(0; 1)]

(f) For every [(m; n)] 2 Qnf[(0; 1)]g, nd [(a; b)] 2 Q such that [(m; n)][(a; b)] = [(1; 1)]

0 comments