Set Operations

Once we have sets, we have set operations:

• Equality $A \equiv B$: $\forall x. x \in A \Leftrightarrow x \in B$.
• Subset $A \subseteq B$: $\forall x. x \in A \Rightarrow x \in B$.
• Proper subset $A \subset B$: $A \subseteq B \land A \neq B$.
• Union $A \cup B$: $\{x \mid x \in A \lor x \in B\}$.
• Intersection $A \cap B$: $\{x \mid x \in A \land x \in B\}$.
• Difference $A \setminus B$: $\{x \mid x \in A \land x \notin B\}$.
• Power set $\mathcal{P}(A)$: the set of all subsets of $A$.
• Empty set $\emptyset$: $\forall x. x \notin \emptyset$.
• Cartesian product $A \times B$: $\{(a, b) \mid a \in A \land b \in B\}$.
• Size $\#(A)$: number of elements.

Key fact: $\#(\mathcal{P}(A)) = 2^{\#(A)}$.

A proof by authority is the fallacy of accepting a statement because an authority figure asserted it, without checking the argument itself. In mathematics this is not a valid proof — only the argument matters, not who said it.

Examples to refuse:
- 'It must be true, Professor X said so.'
- 'It was proved in a famous paper, so I won't reproduce it.'

Even correct theorems require a proof. Appeal to authority outside mathematics (e.g. 'the priest says so') is irrelevant; appeal to authority inside mathematics still requires the actual argument. The reason: mathematics is self-certifying — proofs can be mechanically checked.

Fact. $\#\emptyset = 0$ — the empty set has zero elements.

Fact. $\#\mathcal{P}(X) = 2^{\#X}$ — the powerset of a finite set has $2^n$ elements.

Worked example. Compute $\#\mathcal{P}(\mathcal{P}(\emptyset))$:
1. $\#\emptyset = 0$.
2. $\#\mathcal{P}(\emptyset) = 2^0 = 1$ (only the empty set itself).
3. $\#\mathcal{P}(\mathcal{P}(\emptyset)) = 2^1 = 2$.

The two elements are: $\emptyset$ and $\{\emptyset\}$.

Why no function $f: \emptyset \to \emptyset$? A function is a relation. The empty set IS a valid function (with empty graph). The unique function $\emptyset \to \emptyset$ exists.

Why no function $\emptyset \to \{a\}$? None exists — for $f$ to be total, every element of the domain must map somewhere. The empty set has no elements, so this is fine! Wait — actually the empty function $\emptyset \to \{a\}$ does exist (it has an empty graph).

Theorem. For any set $X$, there is exactly one function $\emptyset \to X$ (the empty function).

Theorem (no injection from $\{0, 1\}$ into $\emptyset$). Such an $f$ would need $f(0)$ and $f(1)$ both in $\emptyset$, but $\emptyset$ has no elements. So no injection exists — confirming $\#\{0,1\} > \#\emptyset$.