Scribd
Upload
14 views3 pages

Week 2 Set Theory Solutions

The document contains solutions to various set theory problems, including operations on sets A and B, cardinalities, and proofs of set identities. It provides specific examples of unions, intersections, and subsets, along with detailed explanations of the reasoning behind each solution. The document also addresses conditions under which two sets can be concluded to be equal and includes proofs of fundamental set properties.

Uploaded by

Vibhas Sharma
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views3 pages

Week 2 Set Theory Solutions

The document contains solutions to various set theory problems, including operations on sets A and B, cardinalities, and proofs of set identities. It provides specific examples of unions, intersections, and subsets, along with detailed explanations of the reasoning behind each solution. The document also addresses conditions under which two sets can be concluded to be equal and includes proofs of fundamental set properties.

Uploaded by

Vibhas Sharma
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

T HE U NIVERSITY OF S YDNEY

S CHOOL OF M ATHEMATICS AND S TATISTICS

Solutions to Sets – Week 2 Tutorials

1. Let A = {a, b, c, {a, d}}. Determine each of the sets Ak and its cardinality |Ak |.
(a) A1 = A ∪ {b, d, e}.
Solution: A1 = A ∪ {b, d, e} = {a, b, c, d, e, {a, d}} and |A1 | = 6.
(b) A2 = A ∩ {b, d, e}.
Solution: A2 = A ∩ {b, d, e} = {b} and |A2 | = 1.
(c) A3 = A \ {a, b}.
Solution: A3 = A \ {a, b} = {c, {a, d}} and |A3 | = 2.
(d) A4 = A \ {c, d}.
Solution: A4 = A \ {c, d} = {a, b, {a, d}} and |A4 | = 3.
(e) A5 = A \ {{a, d}}.
Solution: A5 = A \ {{a, d}} = {a, b, c} and |A5 | = 3.
(f) A6 = A \ {a, {a, d}}.
Solution: A6 = A \ {a, {a, d}} = {b, c} and |A6 | = 2.

2. List the elements in each of the six sets P, Q, P ∪ Q, P ∩ Q, P \ Q and Q \ P, where

P = {x | x ∈ Z and 4 ≤ x ≤ 10},
y
Q = {y | y ∈ Z and ∈ Z and 0 ≤ y2 ≤ 50}.
2

Solution: The answers are:

P = {4, 5, 6, 7, 8, 9, 10}, Q = {−6, −4, −2, 0, 2, 4, 6},


P ∪ Q = {−6, −4, −2, 0, 2, 4, 5, 6, 7, 8, 9, 10}, P ∩ Q = {4, 6},
P \ Q = {5, 7, 8, 9, 10}, Q \ P = {−6, −4, −2, 0, 2}.

3. Let A = {a, b, c, d}. Write down all the subsets of A. How many are there?
Solution: The subsets of A are

/ {a}, {b}, {c}, {d},


0,
{a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d},
{a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b, c, d}.

There are 16 subsets of A.

Copyright © 2024 The University of Sydney


4. Can you conclude that A = B if A, B, and C are sets such that
(a) A ∪C = B ∪C? (b) A ∩C = B ∩C? (c) A ∪C = B ∪C and A ∩C = B ∩C?
Solution: No. To see this note that the above equation is satisfied by A = C and B = 0.
/
Solution: No. Set C = 0/ then the above equation is satisfied for all choices of A and B.
Solution: Yes. To prove this, first note that the statement is symmetric in A and B. It
follows that it is enough to show that A ⊆ B.
Take an element a ∈ A. We must show that a ∈ B.
Because A ∪C = B ∪C we have a ∈ B ∪C. Hence, a is either in B or in C (or both).
If a ∈ B we are done.
If a ∈ C, then, by assumption, a ∈ A ∩C and since A ∩C = B ∩C we have that a ∈ B ∩C.
In particular, a ∈ B.
Give a proof if you can conclude that A = B. Otherwise, give a counterexample.

5. Let A, B, and C be sets. Show that


(a) (A ∪ B) ⊆ (A ∪ B ∪C). (b) (A ∩ B ∩C) ⊆ (A ∩ B). (c) (A \C) ∩ (C \ B) = 0.
/
Solution: Take x ∈ A ∪ B. Hence, x ∈ A or x ∈ B. In both cases we have that x ∈
A ∪ B ∪C.
Solution: Take x ∈ A ∩ B ∩ C. Hence, x ∈ A and x ∈ B and x ∈ C. This means, in
particular, that x ∈ A ∩ B.
Solution: Suppose that (A \ C) ∩ (C \ B) 6= 0.
/ Then there exists an element x ∈ (A \
C) ∩ (C \ B). Hence x ∈ A \ C and so x 6∈ C. But also x ∈ C \ B and hence x ∈ C. A
contradiction.
It follows that (A \C) ∩ (C \ B) = 0.
/

6. If A and B are subsets of a set X, prove that

X \ (A ∩ B) = (X \ A) ∪ (X \ B).

Solution: Before we start this proof we need to know a couple of things.

• We need to know that if x ∈ / A ∩ B, then either x ∈


/ A or x ∈ / B (or both). This
follows from our laws of logic, using the contrapositive: If both x ∈ A and x ∈ B,
then x ∈ A ∩ B.
• We also need to know that if x ∈ / A then x ∈
/ A ∩ B. Again, this follows from our
laws of logic; since x ∈ A ∩ B means both x ∈ A and x ∈ B, so if x ∈
/ A then certainly
x∈/ A ∩ B.

Proof, Part 1. Suppose that x ∈ X \ (A ∩ B).


Then x ∈ X and x ∈ / A ∩ B. Since x ∈
/ A ∩ B, x ∈
/ A or x ∈
/ B.
Suppose that x ∈ / A. Since we know x ∈ X, then x ∈ X \ A.
Similarly, if x ∈
/ B then x ∈ X \ B.
Since x ∈
/ A or x ∈
/ B, at least one of x ∈ X \ A, x ∈ X \ B is true.
Thus x ∈ (X \ A) ∪ (X \ B).
This first part of the proof shows that X \ (A ∩ B) ⊆ (X \ A) ∪ (X \ B).

Proof, Part 2. Suppose that x ∈ (X \ A) ∪ (X \ B).


Then x ∈ X \ A or x ∈ X \ B.
If x ∈ X \ A then x ∈ X and x ∈/ A.
Since x ∈/ A, certainly x ∈
/ A ∩ B, and so x ∈ X \ (A ∩ B).
Similarly if x ∈ X \ B then x ∈ X \ (A ∩ B).
So in either case x ∈ X \ (A ∩ B).
This second part of the proof shows that (X \ A) ∪ (X \ B) ⊆ X \ (A ∩ B).

The two parts of the proof together show that X \ (A ∩ B) = (X \ A) ∪ (X \ B).


This proof is written out with a lot of English words. In advanced work, proofs do tend to
be written out with quite a lot of English words; symbols like ∴ are not used. However,
the more advanced the work, the bigger the jumps that the reader has to fill in!

Common questions

Powered by AI

The union P∪Q of sets P = {4,5,6,7,8,9,10} and Q = {-6,-4,-2,0,2,4,6} results in {−6,−4,−2,0,2,4,5,6,7,8,9,10}. The intersection P∩Q results in {4,6} .

Considered independently, neither A∪C = B∪C nor A∩C = B∩C implies A = B. For instance, A = C and B = ∅ satisfies both A∪C = B∪C and A∩C = B∩C independently without A being equal to B .

The given conditions imply that A = B if A∪C = B∪C and A∩C = B∩C. To prove this, assume A ⊆ B. Take any element a in A; since A∪C = B∪C, a must be in B or C. If it's not in B, it must be in A∩C, therefore it needs to be in B∩C, and thus, in B. By symmetry in A and B, B ⊆ A, so A = B .

The inclusion property is shown by noting that for any sets A and B, if A ⊆ B, every element in A is also in B. For example, take A∩B∩C ⊆ A∩B, as any x in A∩B∩C is also in A∩B due to satisfying x in A and x in B .

A set with four elements has 16 subsets. This is calculated using the formula 2^n, where n is the number of elements in the set. Here, 2^4 = 16, listing all possible combinations of elements .

For sets A and B to be equal given any set C, it is necessary that both A∪C = B∪C and A∩C = B∩C hold true. This ensures every element behaves identically with set C between A and B, meaning each element in A must be in B and vice versa, confirming A = B .

To derive all subsets of a set, systematically list all combinations of its elements, starting from the empty set to the full set. Using a power set formula, 2^n, helps ensure comprehensiveness, where n is the number of set elements. For four elements, list: ∅, {a}, {b}, {c}, {d}, {a,b}, {a,c}, {a,d}, {b,c}, {b,d}, {c,d}, {a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}, and {a,b,c,d} .

To show (A\C) ∩ (C\B) = ∅, assume there exists an element x in this intersection. Then, x should be in A but not in C (A\C) and simultaneously in C but not in B (C\B). This creates a contradiction, as x cannot be both in and not in C. Thus, the intersection is empty .

The proof demonstrates De Morgan's Law for set complements and unions, showing that the complement of an intersection is equal to the union of the complements. Specifically, any element not in both A and B (not in A∩B) must be outside A, outside B, or both, thus in (X \A)∪(X \B) and vice versa .

The cardinality of a set resulting from set operations can differ based on the operation. Union (A∪B) adds elements from both, possibly increasing size unless sets overlap significantly. Intersection (A∩B) only counts shared elements, reducing cardinality generally unless identical. Difference (A\B) reduces size by excluding elements in B, affecting cardinality based on overlap extent .

You might also like