Equivalent Sets

Why

We want to talk about the size of a set.

Definition

Two sets are equivalent if there exists a bijection between them. Let $X$ be a set. Then set equivalence as a relation in $\powerset{X}$ is an equivalence relation (see Equivalence Relations).

Notation

If $A$ and $B$ are sets and they are equivalent, then we write $A \sim B$, read aloud as “$A$ is equivalent to $B$.”

Basic result

Every set is equivalent to itself, whether two sets are equivalent does not depend on the order in which we consider them, and if two sets are equivalent to the same set then they are equivalent to each other. These facts can be summarized by the following proposition.

Let $X$ a set. Then $\sim$ is an equivalence relation on $\powerset{X}$.¹

For natural numbers

Every proper subset of a natural number is equivalent to some smaller natural number.²

Equivalence to subsets

It is unusual that a set can be equivalent to a proper subset of itself.

A set may be equivalent to a proper subset of itself.

The example is the set of natural numbers and the function $f(n) = n^+$. It is a bijection from $\omega $ onto $\N $.³

However, this never holds for natural numbers.

If $n \in \omega $ then $n \not\sim x$ for any $x \subset n$ and $x \neq n$.

The proof is direct and will appear in future editions. ↩︎
The proof, which uses induction, will appear in future editions. ↩︎
The account will be expanded in future editions. ↩︎