<<

p

>p

>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 de ne its inverse image

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

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

Prove that

f1(C [ D) = f1(C) [ f1(D)

f1(C \ D) = f1(C) \ f1(D):

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

collections of sets.

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

1 + r + r2 + + rn =

1 r

n+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 de nition 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 de ned 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 de ne addition + on Z as follows: we de ne [(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 de ne 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 de ne 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 de ne + and on Q: for every [(m; n)]; [(a; b)] 2 Q,

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

(can you motivate these de nitions?)

(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)]

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

-(PVQ) = (-P)^(-Q),

-(PAQ) = (-P) v(Q).

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

(AUB) = An BC,

(An B) = AⓇUB

Recall that the complement of A CX is the set Aº := {1 € X : * & A}.

(c) Explain briefly how the results of part (a) and (b) are related. Notice that the

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

more familiar with) in set theory U and n.

2. (a) Suppose PE N. Show that if p’ 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 V5 is irrational.

(c) Suppose you try the same argument to prove V7 is irrational. The proof must fail,

but where exactly does it fail?

3. Consider a function f :X HY and let ASX and B CX

(a) Show that f(AUB) = f(A) U f(B)

(b) Show that f(An B) Cf(A) n f(B)

(c) Prove that the converse statement f(A) n f(B) Cf(An B) is false (Hint: find a

counterexample)

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

f(A) n f(B) = f(ANB)

(e) Consider a function f : X HY. Given a subset C CY, we define its inverse image

(or preimage) as f-(C):= {r € X : f(x) € C}. Notice that f-1(C) X and that

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

Prove that

f'(CUD) = f-(CUF-‘(D)

f-(COD) = f-‘(C) nf-(D).

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

collections of sets.

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

1 – pp+1

1+r+p2 + … + pelle

for r #1.

1-r

=

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

can make an appropriate definition 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:

(mi, ni) ~ (m2, n2) if mi + n2 = n1 + m2

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

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

draw a picture.)

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

m+l, for m, n, l e N, then n=l)

(b) Show that if (mi, ni) ~(m2, n2) and (a1, bı) ~ (a2, b2), then (mi + a1, n1 +bi) ~

(m2 + a2, n2 + b2)

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

is, Z := {[(m,n)] : (m, n) E N N}. Recall that [(m,n)] denotes the equivalence

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

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

to {z e Z: z= ((n + 1, 1)] for some n e N}). That is, when we think of the natural

number n as an integer, we use ((n +1,1)] e Z.

–

Prove that

f-‘(CUD) = f (C)uf-‘(D)

f-‘(COD) = f-(C) nf-(D).

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

collections of sets.

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

1+r+p? +…+mon

1 – poh+1

for r +1.

1-r

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

can make an appropriate definition 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 x N and the following relation:

(mi, ni) ~ (m2, n2) if mi + n2 = n1 + m2

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

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

draw a picture.)

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

m+l, for m, n, l e N, then n= l)

(b) Show that if (mi, n1) ~ (m2, n2) and (a1, b1) ~ (a2, b2), then (mi + 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:= {[(m, n)] : (m,n) E N N}. Recall that [(m, n) denotes the equivalence

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

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

to {z e Z: z = [(n +1,1)] for some n e N}). That is, when we think of the natural

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

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

[(az, b2)], then [(mi + a1, ni+b1)] = [(m2 +22, N2 + b2)]

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

[(m+a,n+b)]

(d) Show that for every [(m, n)] = 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) € 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 EN

(f) Show that every integer [(m, n)] € 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 find it useful to distinguish three case: m > n, m = n and m n, and similarly n – mEN

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 define 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 define Q. Consider the set Zx (Z\{0}) and the

following relation:

(m1, nu) ~ (m2, n2) if min2 = n1m2.

(Again, try to draw a picture)

(a) Show that is an equivalence relation on Zx (Z {0})

(b) Show that if (mi, ni) ~ (m2, n2) and (ai, bı) ~ (a2, b2), then

(m1.b1+a1.n1, N1.b) ~(m2.b2 + 22. n2, n. 62)

and that (m1.21,n1.b) ~(m2.09, n2 · 62)

Call Q the set of equivalence classes in Zx (Z\{0}) with respect to the equivalence

relaiton ~. Notice that the equivalence class [(m, n)) € Q is nothing but what we usually

denote by . Part (b) allows us to define + and · on Q: for every [(m, n)], [(a,b)] E Q,

we define [(m, n)] + [(a,b)] = [(m·b+an, n – b)] and [(m, n)] · [(a,b)] = [(m·a, n- b)]

(can you motivate these definitions?)

(C) Now, we want to find a copy of Z inside Q. For every n e Z, determine a rational

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

integer as a fraction).

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

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

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

plication on

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

together with + and .. Our goal is to define Q. Consider the set Zx (Z\{0}) and the

following relation:

(m1, nu) ~ (m2, n2) if mi.n2 = n1.m2.

(Again, try to draw a picture)

(a) Show that is an equivalence relation on Zx (Z {0})

(b) Show that if (mi, ni)~ (m2, n2) and (ai, bı) ~ (a2, b2), then

(m1.b1+a1.n1, N1.b) ~(m2.b2 + 22. n2, n. 62)

and that (m1.01, n. b) ~(m2.12, 12 · 62)

Call Q the set of equivalence classes in Zx (Z\{0}) with respect to the equivalence

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

denote by m Part (b) allows us to define + and on Q: for every [(m, n)], [(a,b)] E Q,

we define (m, n)] + [(a,b)] = [(m.b+a.n, n.b)] and [(m, n)] · [(a,b)] = [(m.a,n. b)]

(can you motivate these definitions?)

(C) Now, we want to find a copy of Z inside Q. For every n e Z, determine a rational

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

integer as a fraction).

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

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

(e) For every [(m, n)] € Q, find [(a,b)] € Q such that [(m, n)] + [(a, b)] = [(0,1)]

(f) For every [(m, n)] € Q\{[(0,1)]}, find [(a,b)) € Q such that [(m, n)]-[(a,b)] = [(1,1)]