Difficulty: Introductory to Intermediate | Prerequisites: Basic set notation (curly braces, ∈, ⊆)
This material sits at the foundation of CS 182 and underpins everything that follows: functions, relations, proof techniques, and combinatorics all rely on fluent set reasoning. If you are coming in cold, you need to be comfortable reading set-builder notation and knowing what "element of" versus "subset of" means before this will click. These concepts recur on virtually every exam in the course.
Sets are unordered collections of distinct objects. The power set of a set S is the set of all subsets of S (including the empty set and S itself). Set identities let you prove that two set expressions are equivalent using algebraic laws, without relying on Venn diagrams.
Set
A well-defined collection of distinct objects, called elements or members. Order does not matter, and duplicates are ignored.
In simple terms, think of it as a bag of unique items where you only care about what is in the bag, not the order you put things in.
Element (∈)
An object that belongs to a set. We write x ∈ S to mean "x is an element of S."
In simple terms, this is the "is in" relationship: 2 ∈ {1, 2, 3} because 2 is in that set.
Subset (⊆)
A set A is a subset of B if every element of A is also an element of B. Written A ⊆ B.
In simple terms, A fits entirely inside B. Every set is a subset of itself, and the empty set is a subset of every set.
Power set (2^S)
The set of all subsets of a set S. If S has n elements, then 2^S has 2^n elements.
In simple terms, it is every possible combination of elements you could pick from S, including picking nothing (the empty set) and picking everything (S itself).
Set difference (B − A)
The set of elements that are in B but not in A.
In simple terms, start with B and remove anything that also appears in A.
Cartesian product (A × C)
The set of all ordered pairs (a, c) where the first element comes from A and the second from C.
In simple terms, pair every item in A with every item in C. Unlike a plain set, order matters here: (1, 2) and (2, 1) are different pairs.
Complement (Ā or A^c)
The set of all elements in the universal set that are not in A.
In simple terms, everything outside A.
Empty set (∅ or {})
The set with no elements. It is a subset of every set and an element of every power set.
When asked whether a statement about sets is true or false, the key is matching the operation to its definition precisely.
Given A = {1, 2, 3}, B = {2, {3}}, C = {1, {2}, 2^A}:
2 ∈ B: True. 2 is listed as an element of B.
3 ∈ B − A: False. B − A contains elements in B but not in A. Since 3 is not in B at all, it cannot be in B − A.
{} ∈ 2^B: True. The empty set is a subset of every set, so it appears as an element of every power set.
A ⊆ C: True. Every element of A (1, 2, and 3) is also in C. (Note: 3 is in C because 2^A = the power set of {1,2,3}, and you need to check whether 3 itself is an element of C or whether it appears through some nested structure. In this problem, C is defined so that all of 1, 2, 3 are present.)
{1, {2}} ∈ A × C: False. Elements of A × C are ordered pairs (a, c). The notation {1, {2}} is a set, not an ordered pair.
{3} ⊆ B: False. For {3} to be a subset of B, every element of {3} must be in B. The element 3 is not in B (B contains {3} as an element, but that is the set containing 3, not the number 3 itself).
|2^(A×B)| = 64: False. |A| = 3 and |B| = 2, so |A × B| = 6, and |2^(A×B)| = 2^6 = 64. However, the original problem asks about |2^A × B|, not |2^(A×B)|. |2^A| = 8 and |B| = 2, giving |2^A × B| = 16.
{1} ∈ 2^C: True. {1} is a subset of C (since 1 ∈ C), so {1} is an element of the power set of C.
{{{2}, 2^A}, {1}} ⊆ 2^C: False. For this to hold, every element of the outer set must be an element of 2^C (i.e., a subset of C). The element {{2}, 2^A} is not a subset of C, so the statement fails.
Element versus subset confusion. 3 ∈ {3} is true, but 3 ⊆ {3} is meaningless unless 3 is itself a set. Meanwhile {3} ⊆ {3} is true and {3} ∈ {3} is false (unless {3} contains itself, which it does not here).
Nested braces. {3} and 3 are different objects. B = {2, {3}} has exactly two elements: the number 2 and the set {3}.
Power set size. Always compute |2^S| = 2^|S|. Do not confuse |2^A × B| with |2^(A×B)|.
The goal is to transform one side of the equation into the other using named laws, with no Venn diagram shortcuts.
Key laws to know:
Distributive: A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Complement: A ∩ Ā = ∅ and A ∪ Ā = U (universal set)
Identity: A ∪ ∅ = A and A ∩ U = A
De Morgan's: (A ∪ B)^c = A^c ∩ B^c and (A ∩ B)^c = A^c ∪ B^c
Commutative, associative, idempotent laws
Worked example: Prove ((Ā ∪ B) ∩ A) ∪ (A ∩ B̄) = A
Start with the left-hand side:
Distribute A across (Ā ∪ B): (A ∩ Ā) ∪ (A ∩ B) ∪ (A ∩ B̄)
A ∩ Ā = ∅ (complement law): ∅ ∪ (A ∩ B) ∪ (A ∩ B̄)
∅ ∪ X = X (identity law): (A ∩ B) ∪ (A ∩ B̄)
Factor out A (reverse distributive law over B ∪ B̄): A ∩ (B ∪ B̄)
B ∪ B̄ = U (complement law): A ∩ U = A
Each step cites a named law. This is the standard expected on exams.
To disprove that an equation has positive integer solutions, you can bound the variables and test every candidate.
Example: Show 6x² + 5y² = 100 has no positive integer solutions.
From 6x² ≤ 100, we get x ≤ √(50/3) ≈ 4.08, so x ∈ {1, 2, 3, 4}.
For each x, solve y = √((100 − 6x²)/5) and check whether y is a positive integer.
x = 1: y = √(18.8), not an integer.
x = 2: y = √(15.2), not an integer.
x = 3: y = √(9.2), not an integer.
x = 4: y = √(0.8), not an integer.
All candidates are exhausted. No positive integer solution exists.
This technique works whenever the search space is finite and small.
Set operations appear everywhere in databases (SQL joins are set intersections and unions), access control (permission sets), and networking (IP address ranges). Power sets model all possible configurations of a system. If you have five feature flags, the power set gives you all 32 possible on/off combinations.
Students often think {3} ∈ B and 3 ∈ B are the same thing. They are not. One asks whether a set is an element; the other asks whether a number is.
Students often confuse ⊆ (subset) with ∈ (element of). A subset relationship compares two sets. Membership relates an element to a set.
Students often think |2^A × B| equals 2^(|A|·|B|). It does not. 2^A × B is the Cartesian product of the power set of A with B, so its size is 2^|A| · |B|.
Students often think exhaustive search is not a valid proof technique. For finite domains, checking every case is a complete and rigorous proof.
⚠️ True/false set membership questions appear on nearly every CS 182 exam. The trick is always careful attention to braces and the distinction between ∈ and ⊆.
⚠️ Set identity proofs must cite laws by name. Unlabelled steps or Venn diagram arguments may receive zero marks.
⚠️ Power set cardinality (2^n) is a common calculation target, especially when nested inside Cartesian products.
True or false: The empty set is a subset of every set. True.
True or false: {1, 2} ∈ {1, 2, 3}. False. {1, 2} is a subset of {1, 2, 3}, not an element of it.
Fill in the blank: If |S| = 4, then |2^S| = ___. 16.
True or false: A ∩ Ā = U. False. A ∩ Ā = ∅. It is A ∪ Ā that equals U.
Q: Let X = {a, b} and Y = {1, 2, 3}. How many elements does 2^(X × Y) have?
A: |X × Y| = 2 · 3 = 6. Therefore |2^(X × Y)| = 2^6 = 64.
Q: Prove using set laws that A ∪ (A ∩ B) = A.
A: A ∪ (A ∩ B) = (A ∩ U) ∪ (A ∩ B) = A ∩ (U ∪ B) = A ∩ U = A. (Uses identity law, reverse distribution, and identity law again.) This is also known as the absorption law.
Q: Is ∅ ∈ 2^∅ true or false?
A: True. 2^∅ = {∅}, and ∅ is an element of {∅}.
Q: If A = {1, {2}}, is {2} ∈ A true?
A: Yes. {2} is listed as one of the two elements of A.
This material connects directly to functions and relations (covered next), because functions are defined as subsets of Cartesian products. Understanding when (a, b) is an element of A × B is essential for determining whether a relation is well-defined.
Set identity proofs also build the foundation for Boolean algebra and logic gate simplification, which appears later in digital systems courses.
Power set reasoning recurs in combinatorics: counting subsets, combinations, and the binomial theorem all rely on the same 2^n structure.
Tags: sets, set theory, power set, subset, element, membership, Cartesian product, set difference, complement, set identity, set laws, distributive law, De Morgan's law, exhaustive search, disproof, CS 182, Purdue, discrete mathematics, foundations of computer science