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

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.

Results 1 to 2 of 2
  1. #1
    ODN Community Regular

    Join Date
    Aug 2004
    Location
    Wheaton, IL
    Posts
    13,845
    Post Thanks / Like

    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.
    Last edited by CliveStaples; August 28th, 2015 at 12:33 PM.
    If I am capable of grasping God objectively, I do not believe, but precisely because I cannot do this I must believe. - Soren Kierkegaard
    **** you, I won't do what you tell me

    HOLY CRAP MY BLOG IS AWESOME

  2. #2
    ODN Community Regular

    Join Date
    Aug 2004
    Location
    Wheaton, IL
    Posts
    13,845
    Post Thanks / Like

    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
    If I am capable of grasping God objectively, I do not believe, but precisely because I cannot do this I must believe. - Soren Kierkegaard
    **** you, I won't do what you tell me

    HOLY CRAP MY BLOG IS AWESOME

 

 

Similar Threads

  1. Sets and Orders
    By CliveStaples in forum Logical Riddles & Puzzles
    Replies: 3
    Last Post: April 22nd, 2014, 08:39 AM
  2. STATE OF EMERGENCY? G.O.P. Sets Aside Work on Immigration
    By cat's meow in forum Current Events
    Replies: 13
    Last Post: September 24th, 2007, 10:44 PM

Bookmarks

Posting Permissions

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