I. Introduction

Given a family of sets S = {S_{i}}, we have the following relations:

(DEF 1) Theequinumerousrelation: EQ ⊆ S x S where (S_{i},S_{j}) ∈ EQ ⇔ A is equinumerous with B

(DEF 2) Thecardinality equivalencerelation: CE ⊆ S x S where (A,B) ∈ EQ ⇔ there exists a bijection f:S_{i}→ S_{j }

CE(Lemma 1)is an equivalence relation

Proof:

(1) (Reflexive) CE(X,X), since the identity map is a bijection

(2) (Symmetric) CE(X,Y) ⇒ CE(Y,X), since bijective functions have inverses that are also bijections

(3) (Transitive) CE(X,Y) and CE(Y,Z) ⇒ CE(X,Z), since a composition of bijections is a bijection.

EQ(Lemma 2)is an equivalence relation

Proof:(1) (Reflexive) EQ(X,X), since every set is equinumerous with itself.

(2) (Euclidean) EQ(Y,X) and EQ(Z,X) ⇒ EQ(Y,Z): if Y is equinumerous with X and Z is equinumerous with X, then Y is equinumerous with Z. [As Euclid stated: "Things which are equal to the same thing also equal one another."]

Reflexive Euclidean relations are equivalence relations (proof), so EQ is an equivalence relation.

(Lemma 3)If A = B, thenEQ(A,B)

Proof:

By substitution, EQ(A,B) ⇔ EQ (B,B) since A = B. Since EQ is reflexive, we have EQ(B,B), and thus EQ(A,B).

If f:A → B is a bijection, then there exists a bijection f(Lemma 4)^{-1}: B → A such that for all a ∈ A and b ∈ B: f(f^{-1}(b)) = b and f^{-1}(f(a)) = a.

Proof:

Omitted.

If f:X → Y is a function, then define:

(DEF 3) X ⊕ f := {(x,f(x)) | x ∈ X} [⊆ X x Y]

(DEF 4) f ⊕ X := {(f(x), x) | x ∈ X} [⊆ Y x X]

II. Problem statement

We have:

EQ(X,Y) ⇒ CE(X,Y)

That is, if two sets are equinumerous, then their elements can be put into a 1:1 correspondence. I take this statement to be non-controversial and it is therefore offered without proof.

I wish to show:

CE(X,Y) ⇒ EQ(X,Y)

I.e. that if two sets can be put into a 1:1 correspondence then they are equinumerous with one another.

I will make use of the following principle:

: If a process, operation, or modification of a set neither creates or destroys any elements of that set, then the number of elements doesn't change.Conservation of Elements (CoE)

Examples:

Prepending a "c" symbol to each natural number: {c0, c1, c2, c3, ...}. No elements of N are created or destroyed, so by CoE this set is equinumerous with N.

Adding c to the set of natural numbers: {c,0,1,2,3,...}. A new element, c, has been created and added to N. CoE does not apply.

Removing 0 from the set of natural numbers: {1,2,3,...}. An element, 0, has been destroyed. CoE does not apply.

III. Proof

We will need the following lemma.

(Lemma 5)Iff:X → Yis a bijection, thenf ⊕ X = Y ⊕ f^{-1}

Proof:(⊆)

Let a ∈f ⊕ X. Then a = (f(x), x) for some x ∈ X. Since f:X → Y, f(x) ∈ Y, say f(x) = y. We have f^{-1}(y) = f^{-1}(f(x)) = x. Since y is in Y, (y, f^{-1}(y)) ∈ Y ⊕ f^{-1}. But (y, f^{-1}(y)) = (f(x), x) = a. So a ∈ Y ⊕ f^{-1}.

(⊇)

Let c ∈ Y ⊕ f^{-1}. Then c = (y, f^{-1}(y)) for some y ∈ Y. We have f^{-1}(y) ∈ X, since f-1:Y → X. Also, f(f^{-1}(y)) = y. So c = (y, f^{-1}(y)) = (f(f^{-1}(y)), f^{-1}(y)) ∈ f ⊕ X.

Suppose CE(X,Y). Then there exists a bijection f:X → Y, and likewise a bijection f^{-1}:Y → X.

(1) The process of post- or pre-pending f(x) to each x in X neither creates new elements in X or destroys elements of X. Therefore, by CoE, EQ(X, X ⊕ f).

(2) The process of flipping each (x,f(x)) pair doesn't create or destroy any pairs. Therefore, by CoE, EQ(f ⊕ X, X ⊕ f).

(3) The process of post- or pre-pending f^{-1}(y) to each y in Y neither creates new elements in Y or destroys elements of Y. Therefore, by CoE, EQ(Y ⊕ f^{-1}, Y).

(4) By Lemmas 5 and 3, EQ(f ⊕ X, Y ⊕ f^{-1}).

(5) We have EQ(X, X ⊕ f) [from (1)], EQ(X ⊕ f, f ⊕ X) [from (2) and symmetry of EQ], EQ(f ⊕ X, Y ⊕ f^{-1}) [from (4)], EQ(Y ⊕ f^{-1}, Y) [from (3)]. Since EQ is transitive, we have EQ(X,Y).

QED.

## Bookmarks