Naive Set Theory: Cardinality
Cardinality
A Working Definition
The size of a set is called its cardinality, which is given by a cardinal number. A cardinal number is a special kind of "number" that can be used to count the number of elements in set, even an infinite one. Unfortunately, a robust, general definition of cardinality requires a great deal more logical rigor than we have developed so far. However, a working definition of cardinality that covers a few key concepts provides a big bang for the buck. Our working definition will therefore be in terms of key properties of cardinality, with the definition of cardinality itself left to a deeper dive into set theory.
Cardinality
The cardinality of a set $A$ is written $|A|$. As this notation is often used to denote other concepts, such as the absolute value of a number, cardinality is also written as $\text{card}(A)$ to remove any ambiguity. Cardinal numbers have several properties, which we list here.
-
$|A| = |B|$ if and only if $A$ is equinumerous to $B$.
-
Addition: $|A| + |B| = |A \cup B|$ if $A \cap B = \varnothing$. Addition is commutative and associative.
-
Multiplication: $|A| \cdot |B| = |A \times B|$. Multiplication is commutative and associative.
Finite Sets
A set $A$ is finite if it is equinumerous to some natural number $n$, and its cardinality is $|A| = n$. For example, if $A = \{a, b, c, d\}$, then $|A| = 4$. This means that natural numbers are cardinal numbers. However, as we'll see, not all cardinal numbers are natural numbers.
Countable Sets
A set is countable if it is equinumerous to a subset of $\mathbb{N}$. Finite sets are countable by definition. However, countable sets need not be finite, as the set of all even natural numbers $\{0, 2, 4, 6, \ldots\}$ is also countable.
Infinite Sets
A set is infinite if it is not finite. That is, a set $A$ is infinite if there exists no $n \in \mathbb{N}$ such that $A \approx n$. A set is countably infinite if it is countable and infinite. For example, the set of even natural numbers referenced above is countably infinite. A set is uncountably infinite or simply uncountable if it is infinite and not equinumerous to some subset of $\mathbb{N}$. For example, the set of real numbers is uncountable.
Sneak Peak: Axiomatic Set Theory
We've directly defined the cardinality of finite sets, but what about infinite sets? As an appetizer, we mention a special infinite cardinal.
The cardinality of $\mathbb{N}$ has a special symbol, $\aleph_0$. $\aleph$ is the first letter of the Hebrew alphabet, and is transliterated as "aleph." The subscript is a zero, but in this particular instance is pronounced "null." Thus, $\aleph_0$ is spoken aloud as "aleph null." The subscript $0$ comes from the fact that $\aleph_0$ is the first infinite cardinal number. The study of infinite cardinals such as $\aleph_0$ is in fact one of the major motivations for the development of axiomatic set theory.
Axiomatic set theory starts with first order logic (which covers concepts such as and, or, and implication), lays out several axioms about sets, and builds everything up from there. These axioms are simple but precisely denoted statements about sets which we take to be true by definition. Most axioms are fairly straightforward, such as the axiom of union, which in simple terms says that if two sets exist, then a third set exists containing the elements of both. As a result, we can appeal to intuition to get the same point across in a less rigorous study of set theory, without really losing that much rigor in the end. However, several axioms are more intricate, such as the axiom of regularity and the axiom of choice, two less intuitive axioms required by the full definition of cardinal numbers.
The proper definition of a cardinal number of a set is that it is the least ordinal number to which the set is equinumerous. The ordinal numbers in turn require concepts such as epsilon images and transfinite recursion, which in turn require the aforementioned axioms of regularity and choice.. The ordinal numbers include the natural numbers, so we are on firm footing by saying that $|\{a, b, c, d\}| = 4$ as we did above. However, ordinal numbers "go beyond" the natural numbers and allow us to define cardinal numbers for infinite sets.
Axiomatic set theory also allows us to avoid paradoxes that less formal language does not protect us from. Consider the set of all sets that do not contain themselves - does it contain itself? If it does not, then it does, and if it does not, then it does. Axiomatic set theory avoid paradoxes like these by not allowing such sets to be defined in the first place.
If subjects such as ordinal numbers, infinite cardinals, and formal logic sound interesting, then axiomatic set theory will be interesting to you. Axiomatic set theory is also a gateway drug to subjects like model theory, which studies the properties of formal logical systems in general. However, if you are more interested in geometry, differential equations, vector spaces, prime numbers, cryptography, algebra, and other more recognizably "mathematical" concepts, then you by now surely have enough set theory under your belt to study those subjects to your heart's content.
Problems
Show that no finite set is equinumerous to a proper subset of itself.
Proof by contradiction. Let $A$ be a finite set. Then it is equinumerous to some natural number $n$, and there is a bijection, call it $f$, from $A$ into $n$. Suppose that there is a bijection $g$ from $A$ to a proper subset of itself, $A'$. Then there is some $a \in A - g(A)$, since $g(A)=A'$ is a proper subset of $A$. Therefore $f(g(a)) \notin f(A)$, so $f(A)$ is a proper subset of $n$. However, the composition $g^{-1} \circ f \circ g$ therefore maps $n$ into a proper subset of itself. But this contradicts the Pigeonhole Principle. Therefore $A$ was not equinumerous to $A'$ after all.
Show that if a set is equinumerous to a subset of itself, then it is infinite.
The result follows directly from the preceding theorem. Since no finite set is equinumerous to a subset of itself, a set that is equinumerous to a subset of itself cannot be finite, thus it must be infinite.
Prove that $\mathbb{N}$ is infinite.
Let the function $f : \mathbb{N} \rightarrow \mathbb{N} - \{0\}$ be defined as $f(x) = x +1$. Clearly $f$ is bijective, and $\mathbb{N} - \{0\}$ is a proper subset of $\mathbb{N}$, so $\mathbb{N}$ is infinite.
Show that every finite set is equinumerous to a unique natural number.
Let $A$ be a set, and suppose it is equinumerous to two natural numbers, $n$ and $m$. Then there exists a bijection $f : A \rightarrow n$ and a bijection $g : A \rightarrow m$. Then $f \circ g^{-1}$ is a bijection from $m$ to $n$. By trichotomy, either $m < n$, $m = n$, or $m > n$. If $m < n$, then $m \in n$, and so by transitivity, $m \subset n$. But this contradicts the Pigeonhole Principle, so it must be that $m \geq n$. However, the same logic shows that $n \nless m$. Thus we conclude that $m = n$.
Show that if $A \subset n$ for some $n \in \mathbb{N}$, then $A$ is equinumerous to some $m < n$.
Proof by induction. Let
$$S = \{ n \in \mathbb{N} : \text{ every proper subset of } n \text{ is equinumerous to some } m \in n \}.$$
We can see that $0 \in S$ vacuously, as $0$ has no proper subsets. For the inductive case, we assume $n \in S$ and consider a proper subset $P \subset n^+$. There are three possible cases to consider:
-
$n = P$. Then by the inductive hypothesis $P \approx n \in n^+$.
-
$P \subset n$. Then since $k \in S$, there is some $m$ such that $P \approx m \in n \in n^+$.
-
$n \in P$. Then $P = (P \cap n) \cup \{ n \}$. Then $P \cap n$ is a proper subset of $n$. Because $n \in S$, there is an $m \in n$ such that $P \cap n \approx m$. Let $f$ be a bijection between $P \cap n$ and $m$. We can construct $g = f \cup \{(n, m)\}$ and note that it is a bijection between $P$ and $m^+$, and so $P \approx m^+$. Because $m \in n$, it follows that $m^+ \in n^+$. Therefore $n^+ \in S$.
The result follows by induction.
-
Show that the subset of a finite set is finite.
Let $A$ be a finite set, let $B \subseteq A$, and let $f$ be a bijection from $A$ to some natural number $n$. Then $B \approx f(B) \subseteq n$. By the previous proof, $f(B) \approx m$ for some $m < n$. Since $m \in \mathbb{N}$, it follows that $B$ is finite.