\( \newcommand{\matr}[1] {\mathbf{#1}} \newcommand{\vertbar} {\rule[-1ex]{0.5pt}{2.5ex}} \newcommand{\horzbar} {\rule[.5ex]{2.5ex}{0.5pt}} \)
deepdream of
          a sidewalk
Show Question
\( \newcommand{\cat}[1] {\mathrm{#1}} \newcommand{\catobj}[1] {\operatorname{Obj}(\mathrm{#1})} \newcommand{\cathom}[1] {\operatorname{Hom}_{\cat{#1}}} \newcommand{\multiBetaReduction}[0] {\twoheadrightarrow_{\beta}} \newcommand{\betaReduction}[0] {\rightarrow_{\beta}} \newcommand{\betaEq}[0] {=_{\beta}} \newcommand{\string}[1] {\texttt{"}\mathtt{#1}\texttt{"}} \newcommand{\symbolq}[1] {\texttt{`}\mathtt{#1}\texttt{'}} \)
Math and science::Analysis::Tao::03: Set theory

Cardinality of sets

Equal cardinality

We say that two sets \( X \) and \( Y \) have equal cardinality iff there exists a bijection \( f : X \rightarrow Y \) from \( X \) to \( Y \).

Cardinality n

Let \( n \) be a natural number. A set \( X \) is said to have cardinality n if it has equal cardinality with the set \( \{i \in \mathbb{N} : 1 \ge i \ge n \} \). We also say that such a set has \( n \) elements.

Finite sets

A set is finite iff it has cardinality \( n \) for some natural number \( n \); otherwise, the set is called infinite.

Notation: if \( X \) is a finite set, we use \( \#(X) \) to denote the cardinality of \( X \).


The set of natural numbers is infinite.

Sets with equal cardinality can have one contain the other. For example, there is a bijection between the set of natural numbers and the set of even natural numbers, \( f: X \rightarrow Y\), \( f(n) := 2n \).