A={x:x∈N and 7∣x}
This set has form A={x:P(x)} where P(x) is the open sentence (x∈N)∧(7∣x). Thus 21∈A because P(21) is true. Similarly, 7,14,28,35 etc are all elements of A. But 8∈/A for example because P(8) is false. Likewise, −14∈/A because P(−14) is false.
A={X∈P(N):∣X∣=3}
We know that {4,13,45}∈A because {4,13,45}∈P(N) and ∣{4,13,45}∣=3.
However, {1,2,3,4}∈/A because ∣{1,2,3,4}∣=3
B={(x,y)∈Z×Z:x≡y(mod5)}
(8,23)∈B because (8,23)∈Z×Z and 8≡23(mod5).
Likewise, (100,75)∈B, (102,77)∈B etc., but (6,10)∈/B
Suppose n∈Z and consider the ordered pair (4n+3,9n−2). Does this ordered pair belong in B? To answer this, we observe that (4n+3,9n−2)∈Z×Z. Next, we observe (4n+3)−(9n−2)=−5n+5=5(1−n), so 5∣((4n+3)−(9n−2)), which means (4n+3)≡(9n−2)(mod5). Therefore we have established that (4n+3,9n−2) meets the requirements for belonging to B, so (4n+3,9n−2)∈B for every n∈Z.
C={3x3+2:x∈Z}
Elements of this set consist of all the values 3x3+2 where x is an integer. Thus −22∈C because −22=3(−2)3+2. You can confirm −1∈C and 5∈C. 0∈/C and 21∈/C etc.
To prove A⊆B, we need to prove
a∈A⟶a∈B
This can be proved directly, assuming a∈A and deducing a∈B.
The contrapositive approach is another option: Assume a∈/B and deduce a∈/A.
If A and B are sets, then P(A)∪P(B)⊆P(A∪B).
A small example of this...
P(A)∪P(B)={∅,{1},{2},{1,2}}∪{∅,{2},{3},{2,3}}={∅,{1},{2},{3},{1,2},{2,3}}.
Also P(A∪B)=P({1,2,3})={∅,{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}. So even though P(A)∪P(B)=P(A∪B), it is true that P(A)∪P(B)⊆P(A∪B) for this particular A and B.
Prove that {x∈Z:18∣x}⊆{x∈Z:6∣x}
(Prove the set of integers that are divisible by 18 is a subset of the set of integers that are divisible by 6)
Proof:
-
Suppose a∈{x∈Z:18∣x}.
(Our supposition)
-
This means that a∈Z and 18∣a.
(Subsitute in a for x in the notation for the set).
-
By definition of divisibility, there is an integer c for which a=18c.
-
Consequently, a=6(3c), and from this we deduce 6∣a.
-
Therefore a is one of the integers that 6 divides, so a∈{x∈Z:6∣x}.
-
We've shown a∈{x∈Z:18∣x} implies a∈{x∈Z:6∣x}, so it follows that {x∈Z:18∣x}⊆{x∈Z:6∣x}. ■
Prove that {x∈Z:2∣x}∩{x∈Z:9∣x}⊆{x∈Z:6∣x}
(Prove the intersection between the set of all integers divisibly by 2 and integers divisible by 9 is the subset of all integers divisible by 6)
Proof:
-
Suppose a∈{x∈Z:2∣x}∩{x∈Z:9∣x}
(Suppose a is in the intersection between two sets.. ints divis by 2 and ints divis by 9)
-
By definition of intersection, this means a∈{x∈Z:2∣x} and a∈{x∈Z:9∣x}.
(Use definition of intersection to establish a is in both sets of integers)
-
Since a∈{x∈Z:2∣x} we know 2∣a, so a=2c for some c∈Z. Thus a is even.
(Use a's membership to this particular set to establish some more information about a)
-
Since a∈{x∈Z:9∣x} we know 9∣a, so a=9d for some d∈Z.
(Same as 3, more information about a)
-
As a is even, a=9d implies d is even.
(More logical insights about a)
-
Then d=2e for some integer e, and we have a=9d=9(2e)=6(3e).
(Use insights from previous steps to establish a is also a multiple of 6)
-
From a=6(3e), we conclude 6∣a, and this means a∈{x∈Z:6∣x}.
( Since a is divisible by 6 it must also by in the set of all ints divis by 6 )
-
We have shown that a∈{x∈Z:2∣x}∩{x∈Z:9∣x} implies a∈{x∈Z:6∣x}, so it follows that {x∈Z:2∣x}∩{x∈Z:9∣x}⊆{x∈Z:6∣x}. ■
Prove that {(x,y)∈Z×Z:x≡y(mod6)}⊆{(x,y)∈Z×Z:x≡y(mod3)}
(Prove the set of ordered pairs that have the same remainder for modulo 6 is the subset of ordered pairs that have the same remainder for modulo 3)
Proof:
- Suppose (a,b)∈{(x,y)∈Z×Z:x≡y(mod6)}
- This means that (a,b)∈Z×Z and a≡b(mod6).
- Consequently 6∣(a−b), so a−b=6c for some integer c.
- It follows that a−b=3(2c), and this means that 3∣(a−b), so a≡b(mod3).
- Thus (a,b)∈{(x,y)∈Z×Z:x≡y(mod3)}.
- We've now seen that (a,b)∈{(x,y)∈Z×Z:x≡y(mod6)} implies (a,b)∈{(x,y)∈Z×Z:x≡y(mod3)}, so it follows that {(x,y)∈Z×Z:x≡y(mod6)}⊆{(x,y)∈Z×Z:x≡y(mod3)} ■
¶ Example 4: Prove that if A and B are sets, then P(A)∪P(B)⊆P(A∪B)
Theorem: If A and B are sets, then P(A)∪P(B)⊆P(A∪B)
Proof:
-
Suppose X∈P(A)∪P(B).
-
By definition of union, this means X∈P(A) or X∈P(B).
-
Therefore X⊆A or X⊆B (by definition of power sets). We consider cases.
-
Case 1: Suppose X⊆A. Then X⊆A∪B, and this means X∈P(A∪B).
-
Case 2: Suppose X⊆B. Then X⊆A∪B, and this means X∈P(A∪B).
-
(We do not need to consider the case where X⊆A and X⊆B because that is taken care of by either of our cases). The above cases show X∈P(A∪B).
-
Thus we've shown that X∈P(A)∪P(B) implies X∈P(A∪B), and this completes the proof that P(A)∪P(B)⊆P(A∪B) ■
Theorem: Suppose A and B are sets. If P(A)⊆P(B) then A⊆B.
Proof:
- We use direct proof. Assume P(A)⊆P(B)
- Based on this assumption, we must now show A⊆B.
- To show A⊆B, suppose that a∈A.
- Then the one-element set {a} is a subset of A, so {a}∈P(A)
- But then, since P(A)⊆P(B), it follows that {a}∈P(B).
- This means that {a}⊆B, hence a∈B.
- We've shown that a∈A implies a∈B, so therefore A⊆B. ■
Prove that both A⊆B and B⊆A.
Theorem: {n∈Z:35∣n}={n∈Z:5∣n}∩{n∈Z:7∣n}
Proof:
- First we show {n∈Z:35∣n}⊆{n∈Z:5∣n}∩{n∈Z:7∣n}.
- Suppose a∈{n∈Z:35∣n}.
- This means that 35∣a, so a=35c for some c∈Z. Thus a=5(7c) and a=7(5c).
- From a=5(7c) it follows that 5∣a, so a∈{n∈Z:5∣n}.
- From a=7(5c) it follows that 7∣a, so a∈{n∈Z:7∣n}.
- As a belongs to both {n∈Z:5∣n} and {n∈Z:7∣n}, we get a∈{n∈Z:5∣n}∩{n∈Z:7∣n}. Thus we've shown that {n∈Z:35∣n}⊆{n∈Z:5∣n}∩{n∈Z:7∣n}.
- Next we show {n∈Z:5∣n}∩{n∈Z:7∣n}⊆{n∈Z:35∣n}
- Suppose a∈{n∈Z:5∣n}∩{n∈Z:7∣n}.
- By definition of intersection, this means that a∈{n∈Z:5∣n} and a∈{n∈Z:7∣n}
- Therefore it follows that 5∣a and 7∣a.
- By definition of divisibility, there are integers c and d where a=5c and a=7d.
- Then a has both 5 and 7 as prime factors, so the prime factorization of a must include factors of 5 and 7. Hence 5⋅7=35 divides a, so a∈{n∈Z:35∣n}.
- We've now shown that {n∈Z:5∣n}∩{n∈Z:7∣n}⊆{n∈Z:35∣n}.
- At this point we've shown that {n∈Z:35∣n}⊆{n∈Z:5∣n}∩{n∈Z:7∣n} and {n∈Z:5∣n}∩{n∈Z:7∣n}⊆{n∈Z:35∣n}, so we've proved {n∈Z:35∣n}={n∈Z:5∣n}∩{n∈Z:7∣n}. ■
This example shows that, similar to algebra, if c=0 and ac=bc, then a=b. This holds for sets, if C=∅.
Theorem: For sets A, B, and C, C=∅; If A×C=B×C, then A=B
Proof:
- Suppose A×C=B×C. We must show that A=B
(First major half of proof)
-
First we will show A⊆B
-
Suppose a∈A
-
Since C=∅, there exists an element c∈C.
-
Thus, since a∈A and c∈C, we have (a,c)∈A×C by definition of the Cartesian Product.
-
Since A×C=B×C, it follows that (a,c)∈B×C.
-
But (a,c)∈B×C means a∈B, by definition of the Cartesian product.
-
We have shown that a∈A implies a∈B, so a⊆B.
(Second major half of proof. It is just the previous lines 3-8 with the roles of A and B reversed.)
-
Next we will show B⊆A.
-
Suppose a∈B
-
Since C=∅, there exists an element c∈C.
-
Thus, since a∈B and c∈C, we have (a,c)∈B×C by definition of the Cartesian Product.
-
Since B×C=A×C, we have (a,c)∈A×C
-
It follows that a∈A
-
We have shown a∈B implies a∈A, so B⊆A.
(Conclusion of Proof)
- We have shown A⊆B and B⊆A, so A=B. In summary, we have shown that if A×C=B×C, then A=B. This completes the proof. ■
This example shows another way set operations are similar to operations on numbers. The distributive property a⋅(b+c)=a⋅b+a⋅c works with sets. Just replace variables with sets. Replace ⋅ with × (Cartesian Product) and + with ∪ (intersection).
Theorem: A×(B∩C)=(A×B)∩(A×C) for all sets A, B, and C
Proof:
Part 1: Show that A×(B∩C)⊆(A×B)∩(A×C)
- Suppose (a,b)∈A×(B∩C)
- a∈A and b∈B∩C
(Definition of Cartesian Product)
- It follows that b∈B and b∈C
(Definition of intersection)
- Since a∈A and b∈B, it follows that (a,b)∈A×B
(Definition of Cartesian Product)
- Also since a∈A and b∈C, it follows that (a,b)∈A×C
(Definition of Cartesian Product)
- Now we have (a,b)∈A×B and (a,b)∈A×C, so (a,b)∈(A×B)∩(A×C)
- We've shown that (a,b)∈A×(B∩C) implies (a,b)∈(A×B)∩(A×C), so we have A×(B∩C)⊆(A×B)∩(A×C)
Part 2: Show that (A×B)∩(A×C)⊆A×(B∩C)
- Suppose (a,b)∈(A×B)∩(A×C)
- This means (a,b)∈A×B and (a,b)∈A×C
(Definition of Intersection)
- (a,b)∈A×B means a∈A and b∈B
(Definition of Cartesian Product)
- (a,b)∈A×C means a∈A and b∈C
(Definitiion of Cartesian Product)
- We now have b∈B and b∈C, so b∈B∩C
(By definition of intersection)
- Thus we've deduced that a∈A and b∈B∩C, so (a,b)∈A×(B∩C)
conc?
-
In summary, we've shown that (a,b)∈(A×B)∩(A×C) implies (a,b)∈A×(B∩C) so we have (A×B)∩(A×C)⊆A×(B∩C).
-
We have shown that A×(B∩C)⊆(A×B)∩(A×C) and (A×B)∩(A×C)⊆A×(B∩C), so it follows that (A×B)∩(A×C)=A×(B∩C)
■