Prove that for arbitrary sets A, B, C the following
identities are true. Note that Euler Diagram is not a proof but can
be useful for you to visualize!
(A∩B)⊆(A∩C)∪(B∩C')
Bonus question:
A∪B∩A'∪C∪A∪B''=
=(A∩B∩C)∪(A∩B'∩C)∪(A'∩B∩C)∪(A'∩B∩C')
Prove the following statements!
1. If A and B are sets then
(a) |A ∪ B| = |A| + |B| − |A ∩ B| and
(b) |A × B| = |A||B|.
2. If the function f : A→B is
(a) injective then |A| ≤ |B|.
(b) surjective then |A| ≥ |B|.
3. For each part below, there is a function f : R→R that is
(a) injective and surjective.
(b) injective but not surjective.
(c) surjective but not injective.
(d)...
Bezout’s Theorem and the Fundamental Theorem of Arithmetic
1. Let a, b, c ∈ Z. Prove that c = ma + nb for some m, n ∈ Z if
and only if gcd(a, b)|c.
2. Prove that if c|ab and gcd(a, c) = 1, then c|b.
3. Prove that for all a, b ∈ Z not both zero, gcd(a, b) = 1 if
and only if a and b have no prime factors in common.
A, B and C be sets.
(a) Suppose that A ⊆ B and B ⊆ C. Does this mean that A ⊆ C?
Prove your answer. Hint: to prove that A ⊆ C you must prove the
implication, “for all x, if x ∈ A then x ∈ C.”
(b) Suppose that A ∈ B and B ∈ C. Does this mean that A ∈ C?
Give an example to prove that this does NOT always happen (and
explain why...