Cardinals · Definition

Finite set

set theorycardinals

Before you start you need to know

Finiteness separates sets that can be counted exactly from those that never run out when counted. It is the basis for talking about finite cardinals.

Definition

A set \(A\) is finite if there is a bijection between \(A\) and \(\{1,\dots,n\}\) for some \(n\in\mathbb{N}\), where \(\{1,\dots,0\}=\varnothing\).

\[A\sim\{1,\dots,n\}, \quad |A|=n\]

A set is finite if it can be matched one-to-one with \(\{1,\dots,n\}\), and that \(n\) is unique: it is called the cardinal of \(A\) and written \(|A|\). The empty set is finite with \(|\varnothing|=0\), and a set with \(n\) elements has \(2^n\) subsets.

Basic properties: every subset of a finite set is finite, and if \(A\) and \(B\) are finite and disjoint, \(|A\cup B|=|A|+|B|\). If \(f\colon A\to B\) is injective and \(B\) is finite, then \(A\) is finite and \(|A|\le|B|\), which is the pigeonhole principle.

Worked example: \(\{1,2,\dots,100\}\) is finite with 100 elements, while \(\mathbb{N}\) is not, because \(n\mapsto n+1\) maps \(\mathbb{N}\) onto the proper subset \(\mathbb{N}\setminus\{1\}\). Common mistake: thinking a set is infinite just because it is large; what matters is whether it can be matched with some \(\{1,\dots,n\}\).

Think about it

Why is \(\{1,2,\dots,100\}\) finite but \(\mathbb{N}\) is not?

Because \(\{1,\dots,100\}\) has 100 elements, while \(\mathbb{N}\) is bijective with a proper subset of itself.

Exercises 10

  1. How is it defined that a set \(A\) is finite?
  2. How many elements does the empty set \(\varnothing\) have?
  3. Let \(A=\{a,b,c\}\). How many subsets does \(A\) have?
  4. If \(A\sim\{1,\dots,n\}\) and \(A\sim\{1,\dots,m\}\), what follows?
  5. Is every subset of a finite set also finite?
  6. Which of these sets is finite?
  7. If \(A\) and \(B\) are finite and disjoint, how many elements does \(A\cup B\) have?
  8. If \(f\colon A\to B\) is injective and \(B\) is finite, what follows about \(A\)?
  9. Why is \(\mathbb{N}\) not finite?
  10. If \(1\le k\le n\), how many elements does \(\{1,\dots,n\}\setminus\{k\}\) have?

What comes next

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.