STEP-BY-STEP LESSON · §6.1
Set Theory: Definitions and the Element Method of Proof
Translate set inclusion into a statement about an arbitrary element.
Before you begin
The Language of Sets
A set specifies which objects are included. Listing order and repetition do not change it.
{2,5}={5,2,2}5∈A asks about the number 5. {5}⊆A asks whether every element of {5} belongs to A.
5∈{2,5}; {5}⊆{2,5}Predicates and Quantified Statements I
P(x) is a condition whose truth depends on x. For P(x): x>2, specify allowed values first.
D={1,2,3}∀x∈D P(x) is true when the condition holds for every element of D. One violating element refutes it.
∀x∈D: x>2
∃x∈D P(x) needs at least one witness. For finite D, falsity can be established by checking every element.
∃x∈D: x>2
Direct Proof and Counterexample I: Introduction
Integer n is even iff there is an integer k with n=2k. Evenness gives this representation, and the representation gives evenness.
n even ↔ ∃k∈ℤ: n=2k
For “every odd integer has an odd square”, testing 3,5,7 suggests a pattern but leaves infinitely many cases. Write an arbitrary odd integer as 2k+1 with integer k; no special value is assumed.
n=2k+1; k∈ℤ
Symbols
- ⊆
- subset, possibly equal
- ∩
- intersection: common elements
- ∪
- union: elements in at least one set
- U
- fixed universe containing all sets’ elements under discussion
- Aᶜ
- complement U∖A within the fixed universe U
Definitions and notation for this topic
Subset
⊆
Every element of A is also an element of B.
Equality is allowed: every set is a subset of itself.
Separate glossary example
{1, 2} ⊆ {1, 2, 3}
Empty set
∅
A set containing no elements.
The set {∅} has one element: the empty set itself.
Separate glossary example
|∅| = 0
Union
∪
The set of elements belonging to at least one of the sets.
We list the shared element 2 only once.
Separate glossary example
{1,2} ∪ {2,3} = {1,2,3}
Intersection
∩
The set of elements belonging to both sets.
The number 2 is common to both sets.
Separate glossary example
{1,2} ∩ {2,3} = {2}
Set difference
A ∖ B
The elements of A that are not elements of B.
The order of A and B matters.
Separate glossary example
{1,2} ∖ {2,3} = {1}
Complement
Aᶜ
The elements of a specified universal set U that are outside A.
A complement depends on the chosen universal set.
All complements in a set identity must use the same fixed universe U. A prime mark is a complement only when that convention has been declared.
Separate glossary example
U={1,2,3}, A={1}: Aᶜ={2,3}
Universe and complement laws
Aᶜ=U∖A; (A∪B)ᶜ=Aᶜ∩Bᶜ; (A∩B)ᶜ=Aᶜ∪Bᶜ
Fix a universe U and subsets A,B⊆U. Complement means outside the set but inside U; both De Morgan identities use this same universe.
An element is outside the union exactly when it is outside both sets. Related laws are A∪Aᶜ=U, A∩Aᶜ=∅, and (Aᶜ)ᶜ=A.
Separate glossary example
If U={1,2,3,4}, A={1,2}, B={2,3}, then (A∪B)ᶜ={4}=Aᶜ∩Bᶜ.
Power set
𝒫(A)
The set of all subsets of A.
If A has n elements, its power set has 2ⁿ elements.
If |A|=n for an integer n≥0, then |𝒫(A)|=2^n: each element is either included in a subset or not.
Separate glossary example
𝒫({1}) = {∅,{1}}
Step by step
Step 1 / 6
Distinguish elements from sets
The statement x∈A concerns one object. A⊆B says that every element of A belongs to B.
A⊆B ⇔ ∀x(x∈A ⇒ x∈B)
Inclusion is a universal claim, not a list of a few examples.
Worked example
Prove A∩B⊆A for any sets A,B.
- Choose arbitrary x∈A∩B. Do not assign it a particular number.
- By the definition of intersection, x∈A and x∈B; hence x∈A.
- Thus every element of the intersection belongs to A. If the intersection is empty, inclusion still holds because there is no violating element.
Optional self-check
Prove A⊆A∪B in one chain.
Show answer
Let x∈A. Then x∈A or x∈B, so x∈A∪B by the definition of union.