Prove one the two following theorems of Cantor The set of ra

Prove one the two following theorems of Cantor: The set of rational numbers is a countable set; The set of real numbers is an uncountable set. Prove one of the two Laws of De Morgan from set theory: Give the Masse diagram for the divisors of each number: 51; 256. Use the Euclidean algorithm to find the greatest common divisor of the pair of numbers and write the greatest common divisor as an integral linear combination of the integers. (175.343); (756, 210). Express the logic statement in disjunctive normal form: Solve the system of linear congruences: {x equivalence 1 mod 4 x equivalence mod 9}

Solution

2nd question:

a. (A B)\' = A\' U B\'

Let M = (A B)\' and N = A\' U B\'

Let x be an arbitrary element of M then x M x (A B)\'

x (A B)

x A or x B

x A\' or x B\'

x A\' U B\'

x N

Therefore, M N …………….. (i)

Again, let y be an arbitrary element of N then y N y A\' U B\'

y A\' or y B\'

y A or y B

y (A B)

y (A B)\'

y M

Therefore, N M …………….. (ii)

Now combine (i) and (ii) we get; M = N i.e. (A B)\' = A\' U B\'

b) (A U B)\' = A\' B\'

Let P = (A U B)\' and Q = A\' B\'

Let x be an arbitrary element of P then x P x (A U B)\'

x (A U B)

x A and x B

x A\' and x B\'

x A\' B\'

x Q

Therefore, P Q …………….. (i)

Again, let y be an arbitrary element of Q then y Q y A\' B\'

y A\' and y B\'

y A and y B

y (A U B)

y (A U B)\'

y P

Therefore, Q P …………….. (ii)

Now combine (i) and (ii) we get; P = Q i.e. (A U B)\' = A\' B\'

Question 6:

x= 1 mod 4

so lets say x=1+4t

x=8 mod 9 ===> 1+4t=8 mod 9

===> 4t= 7 mod 9

====> 4t= (9+7) mod 9

=====> 4t=16 mod 9

=====> t= 4 mod 9

======> t= 4+9s

since x=1+4t

====> x=1+4(4+9s)

====> x=1+16+36s

====> x=17+36 s where s is an integer

so solution is x= 17+36 s