1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Showing Function is Injective/Surjective

  1. Jan 8, 2013 #1
    Show that for any sets [itex]X, Y , Z[/itex], the canonical function:

    [itex]\varphi : (X × Y) × Z \rightarrow X × (Y × Z)[/itex]

    [itex](\varphi((x, y), z) = (x,(y, z)))[/itex]

    is a bijection.


    Solution. We can do this by showing that [itex]\varphi[/itex] is injective and surjective..

    I can do this by showing [itex]\varphi[/itex] has an inverse (isomorphism theorem). But I would like to know how to show that a function involving cartesian products is injective/surjective.
     
  2. jcsd
  3. Jan 8, 2013 #2

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    This should be pretty straightforward. Why not start by writing out the definition of injective and surjective for this particular map, i.e., what is it you would need to show in each case?
     
  4. Jan 8, 2013 #3
    Would this show that it is injective?

    [itex]x, a \in X[/itex]
    [itex]y, b \in Y[/itex]
    [itex]z, c \in Z[/itex]

    [itex]\varphi((x,y),z) = \varphi((a,b),c)[/itex]

    [itex]\varphi : (x,(y,z)) = (a,(b,c))[/itex]

    [itex] x=a, y=b, z=c[/itex]

    End of proof.

    How about surjective? To be honest, I'm not 100% what I need to prove in each case. I know that injective is one-to-one (each element in Y has at MOST one element from X mapped to it) and surjective is onto (each element in Y has at LEAST one element from X mapped to it), but I do not know how that translates into the notation.
     
    Last edited: Jan 8, 2013
  5. Jan 8, 2013 #4
    Sooo..

    [itex]X = \left\{1, 2\right\}[/itex]
    [itex]Y = \left\{A, B\right\}[/itex]
    [itex]Z = \left\{I, J\right\}[/itex]

    [itex]X × (Y × Z) =[/itex]
    [itex]\left\{(1, (A, I)), (1, (A, J)), (1, (B, I)), (1, (B, J)), (2, (A, I)), (2, (A, J)), (2, (B, I)), (2, (B, J))\right\}[/itex]

    Take any element from [itex]X × (Y × Z)[/itex]:
    e.g. [itex](2, (A, I))[/itex]
    Show that there is an element from [itex](X × Y) × Z[/itex] which maps using the function:
    [itex]\varphi((2, A), I) = (2, (A, I))[/itex]

    Therefore [itex]\varphi[/itex] is surjective...? :)
     
    Last edited: Jan 8, 2013
  6. Jan 8, 2013 #5

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Yes, that's pretty much all there is to it. You may want to include "if and only if" between the statements and write some words to explain the conclusion you are drawing, such as:

    [itex]\varphi((x,y),z) = \varphi((a,b),c)[/itex]

    if and only if

    [itex](x,(y,z)) = (a,(b,c))[/itex]

    if and only if

    [itex] x=a, y=b, z=c[/itex]

    if and only if

    [itex]((x,y),z) = ((a,b),c)[/itex]

    Therefore [itex]\varphi((x,y),z) = \varphi((a,b),c)[/itex] implies [itex]((x,y),z) = ((a,b),c)[/itex]. This shows that the function [itex]\varphi[/itex] is injective.
     
  7. Jan 8, 2013 #6

    jbunniii

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    No, this isn't a general proof, because you used specific examples of [itex]X[/itex], [itex]Y[/itex], and [itex]Z[/itex]. To write a general proof, start by taking an arbitrary element of [itex]X \times (Y \times Z)[/itex]. An arbitrary element is of the form [itex](x,(y,z))[/itex], where [itex]x \in X, y \in Y, z \in Z[/itex]. Now you need to find an element of [itex](X \times Y) \times Z[/itex] which is mapped by [itex]\varphi[/itex] to [itex](x,(y,z))[/itex]. That's all there is to it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Showing Function is Injective/Surjective
Loading...