Results 1 to 7 of 7

Math Help - bijection and cardinality

  1. #1
    Member
    Joined
    Nov 2006
    Posts
    142

    bijection and cardinality

    I have to prove that if the cardinality of A = the cardinality of B AND the cardinality of C = the cardinality of D then the cardinality of (A x C) = the cardinality of (B x D) with sets A,B,C,D and x denoting the cartesian product.

    I know that there exists a bijection f: A to B and a bijection g: C to D. But how do I proceed using this idea of bijections?

    Thanks for your help in advance.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Global Moderator

    Joined
    Nov 2005
    From
    New York City
    Posts
    10,616
    Thanks
    9
    Quote Originally Posted by PvtBillPilgrim View Post
    I have to prove that if the cardinality of A = the cardinality of B AND the cardinality of C = the cardinality of D then the cardinality of (A x C) = the cardinality of (B x D) with sets A,B,C,D and x denoting the cartesian product.

    I know that there exists a bijection f: A to B and a bijection g: C to D. But how do I proceed using this idea of bijections?

    Thanks for your help in advance.
    Let f:A\to B and g:C\to D be bijections.
    Define h:A\times C\to B\times D by h(a,c) = (f(a),g(c)).
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Nov 2006
    Posts
    142
    Can I say this?

    I know that there is a function f: A to B that is injective, a function g: B to A that is injective, a function h: C to D that is injective, and a function j: D to C that is injective (since the cardinality of X <= the cardinality of Y if there exists an injective function from X to Y).

    Define the function k: (A x C) to (B x D).
    Do the statements above imply that a function l: (A x C) to (B x D) is injective with l(a,c) = (a,c) and a function m: (B x D) to (A x C) is injective with m(b,d) = (b,d). Then by the Cantor-Bernstein Theorem, the cardinality of (A x C) is equal to the cardinality of (B x D).
    .
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,786
    Thanks
    1683
    Awards
    1
    PvtBillPilgrim, did you read the first reply by TPH?
    Why would you go to the lengths you have tried? I cannot follow them.
    Look, we are given that A & B have the same cardinality so the is a bijection between them. Same statement for C & D. As was pointed out by THP it is simple to show that \Phi :A \times C \leftrightarrow B \times D,\quad \Phi (a,c) = \left( {f(a),g(c)} \right) is a bijection.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2006
    Posts
    142
    Well I don't understand exactly what that means.

    Is that the proof or do I need to show that the function h in his post is a bijection? I understand if it's a bijection, then the cardinality is the same, but I don't see why it's a bijection. Is it just obvious?

    Basically, how do I prove that the function h defined by h(a,b) = (f(a),g(b)) is a bijection?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Moo
    Moo is offline
    A Cute Angle Moo's Avatar
    Joined
    Mar 2008
    From
    P(I'm here)=1/3, P(I'm there)=t+1/3
    Posts
    5,618
    Thanks
    6
    Quote Originally Posted by PvtBillPilgrim View Post
    Well I don't understand exactly what that means.

    Is that the proof or do I need to show that the function h in his post is a bijection? I understand if it's a bijection, then the cardinality is the same, but I don't see why it's a bijection. Is it just obvious?

    Basically, how do I prove that the function h defined by h(a,b) = (f(a),g(b)) is a bijection?
    Yup, you have to prove it.

    If h(a,b)=h(a',b'), it means that (f(a),g(b))=(f(a'),g(b')) --> f(a)=f(a') and g(b)=g(b'). Since f and g are bijections, a=a' and b=b'. Thus h is an injection.

    Let y in B \times D. To prove it's a surjection, you have to prove that there exist a and b in A \times C such that h(a,b)=y.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,786
    Thanks
    1683
    Awards
    1
    If h(p,q) = h\left( {r,s} \right) \Rightarrow \left( {f(p),g(q)} \right) = \left( {f(r),g(s)} \right) then by ordered pairs f(p) = f(r)\,\& \,g(q) = g(s).
    As both are injections we have p = r\,\& \,q = s. That proves h is injective.

    Suppose that (j,k) \in B \times D \Rightarrow \quad j \in B \wedge k \in D.
    Because the junctions are both surjections we get:
    \left( {\exists a \in A} \right)\left[ {f(a) = j} \right]\,\& \,\left( {\exists c \in C} \right)\left[ {g(c) = k} \right] \Rightarrow \quad h(a,c) = \left( {j,k} \right).
    That shows that h is a surjection.
    Or h is a bijection!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. bijection of e^x * ln x
    Posted in the Calculus Forum
    Replies: 8
    Last Post: January 20th 2010, 12:46 PM
  2. Bijection
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: January 7th 2010, 06:24 AM
  3. Cardinality and Bijection
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: November 4th 2009, 08:51 PM
  4. Bijection
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: September 15th 2009, 12:55 PM
  5. bijection help
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 12th 2009, 07:59 PM

Search Tags


/mathhelpforum @mathhelpforum