Definition 1.5.1. Two sets \(A\) and \(B\) have the same cardinality if there is a bijection between them, denoted by
\[|A|=|B|.\]If there is an injection from \(A\) to \(B,\) then \(A\) has smaller cardinality than \(B,\) denoted by
\[|A|\le |B|.\]If this holds, and if \(A\) and \(B\) do not have the same cardinality, then \(A\) has strictly smaller cardinality than \(B,\) denoted by
\[|A|< |B|.\]Theorem 1.5.2 (Schröder-Bernstein theorem). Let \(A\) and \(B\) be sets. Then
\[\left(|A|\le |B| \land |B|\le |A|\right) \Rightarrow |A|=|B|.\]Theorem 1.5.3 (Cantor’s theorem). If \(A\) is a set and \(\mathcal P(A)\) is the power set of \(A,\) then
\[|A|<|\mathcal P(A)|.\]Definition 1.5.4. (von Neumann ordinals). We define the zero and successor operation by
\[0=\varnothing, \qquad S(x)=x\cup\{x\}.\]This gives
\[\begin{aligned} 0&=\varnothing,\\ 1&=S(0)=\{\varnothing\},\\ 2&=S(1)=\{\varnothing,\{\varnothing\}\},\\ \end{aligned}\]and so on. In general, the natural number \(n\) is defined by
\[n=\{0,1,\ldots,n-1\}.\]The set of all natural numbers \(\lbrace 0,1,2,\dots\rbrace\) is denoted by \(\mathbb N.\)
Definition 1.5.5. A set \(A\) is finite if there is \(n\in \mathbb N\) such that \(|A|=|n|.\) Otherwise, \(A\) is infinite. If \(A\) is finite and \(|A|=|n|,\) then \(A\) is said to have \(n\) elements.
References
- Cameron, P. J. (1998). Sets, logic and categories. Springer. https://doi.org/10.1007/978-1-4471-0589-3