Set Theory: Subsets, Complements, and Counting Subsets

Universe, Sets, and Elements

Universe (U): the universal set that contains all objects under discussion.
A set is a collection of elements drawn from the universe.
Finite vs infinite sets:
- Example of infinite: the even counting numbers starting from 2 (i.e., {2, 4, 6, 8, 10, …}) — infinite in size.
- A finite set example mentioned: a set with a small finite list or a set like {5, 6} (Lemma: finite with 2 elements).
Notation recap:
- A ⊆ B means A is a subset of B (every element of A is in B).
- A ⊊ B (or A ⊂ B) means A is a proper subset of B (A ⊆ B and A ≠ B).
- A = B means A and B have exactly the same elements.
- ∅ denotes the empty set (contains no elements).
Complements and diagrams:
- Complement of a set M, written M^c or
  A^c, is the set of all elements in the universe not in M: M^c = U \ M.
- Venn diagrams use a rectangle for the universe and shapes for sets; complements appear as the region outside the set inside the universe.

Subset definition: A ⊆ B if every element of A is also an element of B.
Equality through mutual containment: A = B iff A ⊆ B and B ⊆ A (every element of A is in B and vice versa).
Proper subset definition: A ⊊ B iff A ⊆ B and A ≠ B (A is contained in B but not equal to B).
Examples from transcript:
- If A = {5, 6} and B = {4, 5, 6}, then A ⊆ B and A ≠ B, so A ⊊ B.
- If A = {8, 9, 10, 11} and B = {7, 8, 9, 10, 11, 12}, then A ⊆ B and A ≠ B, so A ⊊ B.
- If A = {1, 2, 3} and B = {1, 2, 3}, then A ⊆ B but A ≠ B is false; A = B, so A ⊆ B but not a proper subset.
How to tell if A is a subset of B:
- Read left to right: every element on the left must appear on the right.
- If some element on the left is missing from the right, A ⊄ B (not a subset).
How to tell if A is a proper subset of B:
- In addition to A ⊆ B, there must be at least one element in B that is not in A (A ≠ B).

Complement of a set M (with respect to the universe U):
- M^c = U \ M (the elements in U not in M).
Examples:
- If U = {1, 2, 3, 4, 5, 6} and M = {5, 6}, then M^c = {1, 2, 3, 4}.
Intersection:
- A ∩ B = {x : x ∈ A and x ∈ B}.
- Example: If A = {1, 3, 5, 7, 9} and B = {1, 2, 3, 4, 5, 6}, then A ∩ B = {1, 3, 5}.
Empty intersection: It is possible that A ∩ B = ∅ (no elements in common).
Union and other operations (brief note): A ∪ B contains all elements that are in A or B or both; not elaborated in transcript but commonly used with these concepts.

How many subsets does an n-element set have?
- Number of subsets of an n-element set = 2^{n}.
How many proper subsets does an n-element set have?
- Number of proper subsets = 2^{n} - 1 (provided n > 0).
- Edge case: for the empty set (n = 0), the only subset is ∅ itself, and there are 0 proper subsets: 2^{0} - 1 = 0.
Examples:
- A set with 2 elements has 2^2 = 4 subsets: ∅, {a}, {b}, {a,b}.
- Proper subsets: ∅, {a}, {b} (3 proper subsets).
- A set with 3 elements has 2^3 = 8 subsets, and 7 proper subsets.
- A set with 6 elements has 2^6 = 64 subsets, and 63 proper subsets.
Systematic enumeration methods:
- Manual listing (good for small n).
- Tree diagram approach: consider each element as either in or out of a subset; branch by including or excluding elements to build all subsets.
- For larger n, use the formula to avoid listing.
Zero and the empty set:
- The empty set ∅ is a subset of every set (∅ ⊆ A for any A).
- ∅ is a proper subset of every nonempty set (∅ ⊊ A if A ≠ ∅).
Practical test-taking note:
- If asked for all subsets, list or identify 2^n possibilities.
- If asked for all proper subsets, count 2^n − 1 and be mindful of whether the full set is included.

Power set concept: the set of all subsets of a given set; its size is 2^n for a set with n elements.
Real-world example (days of the week):
- Days = {Mon, Tue, Wed, Thu, Fri, Sat, Sun} has n = 7 elements.
- Total subsets = 2^{7} = 128.
- Total proper subsets = 2^{7} - 1 = 127.
Another practical example (group members with initials):
- Given six people with initials a, b, c, d, e, f, the number of possible subsets is 2^6 = 64; proper subsets are 63.
Word problem illustration from transcript:
- A problem asks for the sets of a group where five specific individuals show up; you count combinations or list all subsets of size 5, not necessarily all subsets. This is about choosing a subset rather than listing every subset.

Venn diagram setup:
- Universe is the rectangle; each set is a region inside the universe.
Subset questions using diagrams:
- If Set A lies entirely inside Set B (A ⊆ B), then A is a subset of B.
- If A lies inside B but A ≠ B, then A ⊊ B (proper subset).
- If A and B have elements that are not in the other, A is not a subset of B, i.e., A ⊄ B.
- If A = B (exactly the same elements), then A ⊆ B and B ⊆ A (equal sets).
Some examples from the transcript:
- Sunday and Thursday example: determine if one set is a subset of another; discussion illustrates reading from left to right and checking elements.
- A left-hand set {L, M, N} and a right-hand set {L, M, N, P} typically yields A ⊆ B but not A = B, hence A ⊊ B.
- If the left is {L, M, N} and the right is {L, M, N, P, Q}, then A ⊊ B as long as the right contains at least one extra element.
If a problem asks for the answer “both” for subset and proper subset, this occurs when A ⊆ B and A ≠ B (i.e., A ⊊ B).

Intersection definition: A ∩ B = {x | x ∈ A and x ∈ B}.
Example from transcript:
- A = {1, 3, 5, 7, 9}, B = {1, 2, 3, 4, 5, 6}
- A ∩ B = {1, 3, 5}.
A note: The intersection of A with the empty set is empty: A ∩ ∅ = ∅.

Problem A: Let A = {3, 4} and B = {3, 4, 5}. Is A a subset of B? Is A a proper subset of B?
- A ⊆ B is true; A ⊊ B is true.
Problem B: Let U = {1, 2, 3, 4, 5, 6} and A = {5, 6}. Find A^c.
- A^c = {1, 2, 3, 4}.
Problem C (counting): A set has n = 3 elements. How many subsets does it have? How many proper subsets?
- Subsets: 2^{3} = 8; Proper subsets: 2^{3} - 1 = 7.
Problem D (empty set): Is ∅ a subset or proper subset of {a, b}? Explain.
- ∅ ⊆ {a, b} (subset), and ∅ ⊊ {a, b} (proper subset) since {a, b} ≠ ∅.
Problem E (word problem continued): A group of 7 people (days of the week example) yields 128 total subsets and 127 proper subsets.
Problem F (intersection): If A = {1, 3, 5} and B = {5, 6, 7}, what is A ∩ B?
- A ∩ B = {5}.

Number of subsets of an n-element set: 2^{n}
Number of proper subsets of an n-element set: 2^{n} - 1
Complement relative to universal set U: A^{c} = U \ A
Intersection: A \,\cap\, B = {x \,|\, x \in A \,\text{and}\, x \in B}
Empty set properties:
- \emptyset \subseteq A\quad \text{for any } A
- If A \neq \emptyset then \emptyset \subsetneq A
Subset relationships:
- A \subseteq B means every element of A is in B.
- A \subsetneq B means A is a proper subset of B (A ⊆ B and A ≠ B).
Power set concept: the set of all subsets of a given set; size is 2^{n} for an n-element set.
Note on test strategy:
- Distinguish between subset vs proper subset unless the problem explicitly says both.
- Use the power-set counting when listing all subsets is impractical.
- For Venn diagram questions, identify the universe, known sets, and the region types (inside, outside, overlap) to determine subset relations.