Cardinals · Definition

Equipotence

set theorycardinals

Before you start you need to know

Equipotence compares sets by size without needing to count them. It is the tool that also lets us compare infinite sets.

Definition

Two sets \(A\) and \(B\) are equipotent if there is a bijection \(f\colon A\to B\). It is written \(A\sim B\).

\[A\sim B \iff \exists\, f\colon A\to B\ \text{biyectiva}\]

Equipotence is an equivalence relation: it is reflexive, because the identity is a bijection; symmetric, because the inverse of a bijection is a bijection; and transitive, because the composition of bijections is a bijection. It therefore splits sets into classes, and each class groups sets of the same size.

Examples: \(\{a,b,c\}\sim\{1,2,3\}\) via \(a\mapsto1,\ b\mapsto2,\ c\mapsto3\). Among infinite sets, \(\mathbb{N}\sim\{0,2,4,\dots\}\) via \(n\mapsto 2n\), even though the evens are a proper part of \(\mathbb{N}\). And \(\mathbb{N}\sim\mathbb{Z}\) via \(0\mapsto0,\ 1\mapsto1,\ 2\mapsto-1,\ 3\mapsto2,\dots\), which alternates signs.

Typical mistakes: confusing equipotence with equality, since \(\{1,2\}\) and \(\{a,b\}\) are equipotent without being equal. And believing that an injection between two sets is enough: \(\mathbb{N}\subseteq\mathbb{R}\) is injective, yet \(\mathbb{N}\not\sim\mathbb{R}\).

Think about it

Is \(\mathbb{N}\) equipotent to \(\mathbb{Q}\)?

Yes: the rationals are countable, so there is a bijection with \(\mathbb{N}\).

Exercises 10

  1. What is needed for two sets \(A\) and \(B\) to be equipotent?
  2. Is \(\{a,b,c\}\) equipotent to \(\{1,2,3\}\)?
  3. Which of these properties does equipotence satisfy?
  4. Let \(\mathbb{N}=\{0,1,2,\dots\}\). Is \(\mathbb{N}\) equipotent to \(\{0,2,4,\dots\}\)?
  5. Which statement about \(\mathbb{N}\) and \(\mathbb{Z}\) is correct?
  6. How is it written that the sets \(A\) and \(B\) are equipotent?
  7. Is \(\{1,2\}\) equipotent to \(\{1,2,3\}\)?
  8. What do you get when composing two bijections \(f\colon A\to B\) and \(g\colon B\to C\)?
  9. The inclusion of \(\mathbb{N}\) in \(\mathbb{R}\) is an injective function. Why does it not prove that \(\mathbb{N}\sim\mathbb{R}\)?
  10. Let \(f\colon A\to B\) be a bijection, with \(A\) finite. Why is \(B\) also finite?

References

  • Herbert B. Enderton, Elements of Set Theory, 1st edition, Academic Press, 1977.
  • Thomas Jech, Set Theory (The Third Millennium Edition), 3rd millennium edition, Springer, 2003.