CM1020 Topic: Sets
Rosen Reading: Section 2.1
Key Concepts: Empty Set, Subset, Vacuous Proof
One of the first theorems encountered in set theory states that the empty set is a subset of every set.
$$\emptyset \subseteq S$$
for every set \(S\).
Although this statement may appear obvious, it provides an important introduction to mathematical definitions, logical implication, and a proof technique known as a vacuous proof.
Theorem
For every set \(S\):
$$ (i)\ \emptyset \subseteq S $$
and
$$ (ii)\ S \subseteq S $$
This note focuses on proving part (i).
Definition of a Subset
A set \(A\) is a subset of a set \(B\) if every element of \(A\) is also an element of \(B\).
In mathematical notation:
$$ A \subseteq B \iff \forall x(x \in A \rightarrow x \in B) $$
Therefore, to prove that:
$$ \emptyset \subseteq S $$
it is sufficient to show that:
$$ \forall x(x \in \emptyset \rightarrow x \in S) $$
is true.
Key Observation
The empty set contains no elements.
Therefore:
$$ x \in \emptyset $$
is always false.
There is no object \(x\) that belongs to the empty set.
The Logical Argument
The statement under consideration is:
$$ x \in \emptyset \rightarrow x \in S $$
In propositional logic, an implication is considered true whenever its hypothesis is false.
Since:
$$ x \in \emptyset $$
is always false, the implication is always true.
Therefore:
$$ \forall x(x \in \emptyset \rightarrow x \in S) $$
is true.
It follows that:
$$ \emptyset \subseteq S $$
for every set \(S\).
What Is a Vacuous Proof?
A vacuous proof proves a statement because its hypothesis can never be satisfied.
The general form is:
$$ P \rightarrow Q $$
If \(P\) is always false, then the implication is automatically true regardless of \(Q\).
In this theorem, the hypothesis is:
$$ x \in \emptyset $$
which is always false because the empty set contains no elements.
Therefore, the proof that:
$$ \emptyset \subseteq S $$
is an example of a vacuous proof.
Important Symbols
| Symbol | Meaning |
|---|---|
| ∅ | Empty set |
| ⊆ | Subset of |
| ∈ | Element of |
| ∀ | For all |
| ∃ | There exists |
| → | Implies |
| ⇔ | If and only if |
| ¬ | Not |
| ∧ | And |
| ∨ | Or |
Summary
- The empty set is a subset of every set.
- A subset statement can be rewritten as a logical implication.
- The statement \(x \in \emptyset\) is always false.
- An implication with a false hypothesis is true.
- This type of argument is called a vacuous proof.
This theorem is often a student's first encounter with formal mathematical proof and demonstrates how set theory and logic are closely connected in discrete mathematics.
Things to Remember for the Exam
- Always start a subset proof from the definition of a subset.
- Remember that \(A \subseteq B\) means every element of \(A\) is also an element of \(B\).
- The empty set contains no elements.
- A conditional statement with a false hypothesis is true.
- Know the definition of a vacuous proof and be able to recognize one.
0 comments