Submitted by: Razel C. Soriano M.S.

Ed Teaching Mathematics
Problem Set: SET THEORY Submitted to: Charles B. Montero, Ph.D.

1. Prove the following using the indicated method.

a. If x
2
is divisible by 3 then x is divisible by 3.

Suppose x
2
is divisible by 3, note that when integer x when divided by 3, the remainders are 2, 1, or
0, thus x = 3n or x = 3n + 1 or x = 3n + 2.
If x = 3n then x
2
is 9n
2
which is divisible by 3.
If x = 3n +1 then x
2
= 9n
2
+ 6n + 1 is not divisible by 3
If x = 3n + 2 then x
2
= 9n
2
+ 12n + 4 is not divisible by 3
Since x
2
is divisible by 3 from supposition, it follows x
2
= 9n
2
.hence x = 3n for some integers,
thus x is divisible by 3.


b. CASE 1: 3 is not rational (indirect method)

Suppose 3 is rational, then there exist an integers p and q such that 3 =
q
p
, q 0 = ,
p and q express in lowest term.

q
p
= 3 ,

2
|
|
.
|

\
|
q
p
= ( )
2
3

3
2
2
=
q
p


p
2
= 3q
2


p
2
has a factor of 3, thus, p
2
is divisible by 3, therefore p can be expressed in p = 3k, ke Z.

Substitute:
p
2
= 3q
2
( )
2
3k = 3q
2


3
3
3
9
2 2
q k
=
3k
2
= q
2


Therefore, q
2
is divisible by 3, then q is divisible by 3. p = 3k and q = 3m, me Z.



Note:
q
p
is in the lowest term, thus the assumption is false! Therefore


3 is irrational.
CASE 2:




Prove that 3 is an irrational number.
Solution:
The number, 3 , is irrational, ie., it cannot be expressed as a ratio of integers a
and b. To prove that this statement is true, let us assume that 3 is rational so that
we may write
3 = a/b
1.
for a and b = any two integers. We must then show that no two such integers can
be found. We begin by squaring both sides of eq. 1:
3 = a
2
/b
2
2.

or 3b
2
= a
2
2a.
If b is odd, then b
2
is odd; in this case, a
2
and a are also odd. Similarly, if b is even,
then b
2
, a
2
, and a are even. Since any choice of even values of a and b leads to a
ratio a/b that can be reduced by cancelling a common factor of 2, we must assume
that a and b are odd, and that the ratio a/b is already reduced to smallest possible
terms. With a and b both odd, we may write
a = 2m + 1 3.

and b = 2n +1 4.
where we require m and n to be integers (to ensure integer values of a and b).
When these expressions are substituted into eq. 2a, we obtain
3(4n
2
+ 4n + 1) = 4m
2
+ 4m + 1 5.
Upon performing some algebra, we acquire the further expression
6n
2
+ 6n + 1 = 2(m
2
+ m) 6.
The Left Hand Side of eq. 6 is an odd integer. The Right Hand Side, on the other
hand, is an even integer. There are no solutions for eq. 6. Therefore, integer values
of a and b which satisfy the relationship 3 = a/b cannot be found. We are forced
to conclude that 3 is irrational.

c.
{ } 1 5 : 4 , 3 , 2 , 1
2

n
n is divisible by 4. (Enumeration).

Proof: case 1:
If x = 1
5
2(1)
1 = 5
2
1 = 25 1 = 24 is div. by 3.
If x = 2
5
2(2)
1 = 5
4
1 = 625 1 = 624 is div. by 3.
If x = 3
5
2(3)
1 = 5
6
1 = 15625 1 = 15624 is div. by 3.
If x = 4
5
2(4)
1 = 5
8
1 = 390625 1 = 390624 is div. by 3.
.
.
.

d. ( )
3
4
1 2 3 1 :
3
2 2 2
n n
n n

= + + + N e
Proof:
i. Show that P (n) is true for n = 1
1
2
+ 3
2
+ + (2n 1)
2
=
3
4
3
n n


1
2
+ 3
2
+ + (2(1) 1)
2
=
3
) 1 ( ) 1 ( 4
3

( 2 1)
2
=
3
1 4

1
2
=
3
3


1 = 1
Therefore P(1) is true.

ii. Assume the P(n) is true for n = k

Show that P(n) is true for n = k + 1.

Assume: P (k): 1
2
+ 3
2
+ + (2k 1)
2
=
3
4
3
k k


Show: P (k+1): 1
2
+ 3
2
+ + ( ) | |
2
1 1 2 + k =
3
) 1 ( ) 1 ( 4
3
+ + k k


Note:
P(k+1): 1
2
+ 3
2
+ + (2k 1)
2
+ ( ) | |
2
1 1 2 + k =
3
) 1 ( ) 1 ( 4
3
+ + k k


From the hypothesis and both side by ( ) | |
2
1 1 2 + k

1
2
+ 3
2
+ + (2k 1)
2
+ ( ) | |
2
1 1 2 + k =
3
4
3
k k
+
3
) 1 ( ) 1 ( 4
3
+ + k k




=
3
1 ) 1 ( 4 4
3 3
+ + k k k k


=
3
1 ) 1 3 3 ( 4 4
2 3 3
+ + + + k k k k k k


=
3
1 1 12 12 4 4
2 3 3
+ + + + k k k k k k


=
3
10 12 8
2 3
k k k + +


( ) | |
2
1 1 2 + k =
3
) 5 6 4 ( 2
2
+ + k k k


=
3
4
3
k k
+
3
) 1 ( ) 1 ( 4
3
+ + k k


=
3
1 ) 1 ( 4 4
3 3
+ + k k k k


=
3
) 1 ( ) 1 ( 4 ) 1 4 (
3 2
+ + + k k k k


=
| |
3
1 ) 1 ( 4 ) 1 ( ) 1 4 (
2 2
+ + + k k k k




II.

) ( .
) ( .
) (
B C A if B A ii
B A if B C A i
B A iff B C A
_ =
= _
= _
|
|
|


i. Suppose AB = |
Let xeA then xeB

=> x eB Since A_C it follows that xeC
=> x eB and xeC
=> x e(C B)
Thus, A_(C B)

ii. Suppose xeA then x e C B
=> x e CB`
=> x e C and x e B`
=> x e C and x e B
=> AB = |
3. The relation of Z defined by a ~ b iff a b is divisible by 5 is an equivalence relation.

Let r = { } 5 , : ) , ( by divisible and b a b a Z e
Show: r is an equivalence relation.

Proof:
i. Reflexive: since a a = 0 is divisible by 5. Therefore (a , a) e r , for every aeZ.

ii. Symmetric: if (a,b) e r, then a b is divisible by 5.
a b = 5n, for some n e Z
1 (a b) = 5 n
b a = 5 (n)
b a is divisible by 5.
( b a ) e n.

iii. Transitive
If (a , b) er and (b , c) e r then a b is divisible by 5 & b c is divisible by 5.
a b = 5n and b c = 5m for some n, n e Z.
(a b) + (b c) = 5n + 5m
a c = 5 (n + m) e Z
a c is divisible by 5
(a , c) er.

Give the partition of Z induced by the equivalence relation in above # 3.

[0] = { aeZ: (a ,0) er}
= { aeZ: a 0 is divisible by 5}
= { aeZ: a = 5n, n eZ}
= { 5n, n eZ}
= { , -15, -10, -5, 0 , 5, 10, 15, }

[1] = { aeZ: (a ,1) er}
= { aeZ: a 1 is divisible by 5}
= { aeZ: a 1 = 5n, n eZ}
= { 5n + 1, n eZ}
= { , -14, - 9, -4, 1 , 6, 11, 16, }

[2] = { aeZ: (a ,2) er}
= { aeZ: a 2 is divisible by 5}
= { aeZ: a 2 = 5n, n eZ}
= { 5n + 2, n eZ}
= { , -13, - 8, -3, 2 , 7, 12, 17, }

[3] = { aeZ: (a ,3) er}
= { aeZ: a 3 is divisible by 5}
= { aeZ: a 3 = 5n, n eZ}
= { 5n + 3, n eZ}
= { , -12, - 7, -2, 3 , 8, 13, 18, }

[4] = { aeZ: (a ,4) er}
= { aeZ: a 4 is divisible by 5}
= { aeZ: a 4 = 5n, n eZ}
= { 5n + 4, n eZ}
= { , -11, - 6, -1, 4 , 9, 14, 19, }

[5] = { aeZ: (a ,5) er}
= { aeZ: a 5 is divisible by 5}
= { aeZ: a 5 = 5n, n eZ}
= { 5n + 5, n eZ}
= { , -10, - 5, 0, 5 , 10, 15, }




[6] = { aeZ: (a ,6) er}
= { aeZ: a 6 is divisible by 5}
= { aeZ: a 6 = 5n, n eZ}
= { 5n + 6, n eZ}
= { , -9, - 4, 1, 6 , 11, 16, 21 }


[5] = [0]
[6] = [1]

{ } ] 4 [ ], 3 [ ], 2 [ ], 1 [ ], 0 [ = , is a partition of Z.
Note:
i. [0],[1][2],[3],[4] |

ii. [0] [1] = |
[0] [2] = |
[0] [3] = |
[0] [4] = |

iii. [0] [1] [2] [3] [4] = Z