Welcome guest, is this your first visit? Create Account now to join.

### Welcome to the Online Debate Network.

If this is your first visit, be sure to check out the FAQ by clicking the link above. You may have to register before you can post: click the register link above to proceed.

# Thread: Equinumerous Sets and Bijections

1. ## Equinumerous Sets and Bijections

I. Introduction

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

(DEF 1) The equinumerous relation: EQ S x S where (Si,Sj) EQ A is equinumerous with B

(DEF 2) The cardinality equivalence relation: CE S x S where (A,B) EQ there exists a bijection f:Si Sj

(Lemma 1) CE 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.

(Lemma 2) EQ 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, then EQ(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).

(Lemma 4) If f:A B is a bijection, then there exists a bijection f-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:

Conservation of Elements (CoE): 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.

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) If f:X Y is a bijection, then f 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.  Reply With Quote

2. ## Re: Equinumerous Sets and Bijections

A few typo corrections:

(DEF 1) The equinumerous relation: EQ ⊆ S x S where (Si,Sj) ∈ EQ ⇔ Si is equinumerous with Sj

(DEF 2) The cardinality equivalence relation: CE ⊆ S x S where (Si,Sj) ∈ CE ⇔ there exists a bijection f:Si → Sj  Reply With Quote

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•