Cardinality, An Introduction

Introduction

If the members of x and y can be placed in 1-1 correspondence, the sets have the same size or cardinality. If x is the same size as y, is the same size as z, then x is the same size as z. As you might guess, we are building an equivalence relation.

Recall that a bijection is a function that is invertible and covers the entire range. Build a relation as follows. SameSize(x,y) iff there is a bijection between x and y. Since the domain and range are always sets, There is no distinction between a bijection implemented as a formula and a bijection implemented as a set. Either can be transformed into the other.

Invert and compose bijections to show this relation is reflexive, symmetric, and transitive. Thus SameSize() partitions the universe of sets into equivalence classes. Intuitively, all the sets in a given class are the same size. After all, their members can be placed in 1-1 correspondence.

Each equivalence class is called a cardinal class. A special representative of each cardinal class is called the cardinal number, or simply the cardinal. The cardinal establishes the size of the sets in that class. More on this later.

One must be a bit careful here. Our equivalence relation SameSize() is implemented as a formula with two free variables, rather than a subset of a cross product. If this relation were a set then its domain would be a set, which is the set of all sets, which is impossible. Thus SameSize() will always be a formula and never a set.