Results 1 to 12 of 12

Math Help - relationship help

  1. #1
    Newbie
    Joined
    Sep 2009
    Posts
    8

    relationship help

    Just wondering if I could have some help proving that there is an injection from the set of all integers to the set of all reals. I think I need to use the identity function but not too sure

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by garrett12 View Post
    Just wondering if I could have some help proving that there is an injection from the set of all integers to the set of all reals. I think I need to use the identity function but not too sure

    Thanks!
    Is the identity function an injection? Well, there you go.

    Tonio
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Sep 2009
    Posts
    8
    Thanks for the reply. I get how the identity function is an injection, but I don't quite get the formal way to write a proof saying that the injection exists between Z and R. Any hints on the formal definition?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by garrett12 View Post
    Thanks for the reply. I get how the identity function is an injection, but I don't quite get the formal way to write a proof saying that the injection exists between Z and R. Any hints on the formal definition?
    f:\mathbb{Z} \to \mathbb{R} is an injection if \forall x,y \in \mathbb{Z} , f(x) = f(y) \Rightarrow x = y

    Let f(x) = x, the identity function. Let x_0, y_0 \in \mathbb{Z} such that x_0 \neq y_0. Then, obviously, f(x_0) \neq f(y_0) and so f(x) is an injection.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Sep 2009
    Posts
    8
    Thanks Defunkt, that was what I was looking for. Just another quick question, along the same lines. If I'm asked to prove that the injection relationship is reflexive and transitive - but i'm not given a domain or range with it - how would i go about proving this? Can I just make up my own domain and range that it works for and then prove that?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by garrett12 View Post
    Thanks Defunkt, that was what I was looking for. Just another quick question, along the same lines. If I'm asked to prove that the injection relationship is reflexive and transitive - but i'm not given a domain or range with it - how would i go about proving this? Can I just make up my own domain and range that it works for and then prove that?

    Thanks
    You don't "make up" your domain and range -- you have to show that it holds for any domain and range, ie. that:

    if there exist injections f:X \to Y , g: Y \to Z then there exists an injection h:X \to Z (this is transitivity).

    and that for any set X, there exists an injection f:X \to X

    Can you finish from here?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Sep 2009
    Posts
    8
    Quote Originally Posted by Defunkt View Post
    You don't "make up" your domain and range -- you have to show that it holds for any domain and range, ie. that:

    if there exist injections f:X \to Y , g: Y \to Z then there exists an injection h:X \to Z (this is transitivity).

    and that for any set X, there exists an injection f:X \to X

    Can you finish from here?
    I have trouble coming up with the formal ways of explaining it..

    For transitivity:

    If f:X->Y and g:Y->Z are injections..
    For all x in X, y in Y and z in Z s.t f(x) = y and f(y) = z, ???

    I get that xRz as no other unique value from X can relate to z but can't explain it


    For symmetric:

    Should the identity function be used again here? Seems like it should be
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by garrett12 View Post
    I have trouble coming up with the formal ways of explaining it..

    For transitivity:

    If f:X->Y and g:Y->Z are injections..
    For all x in X, y in Y and z in Z s.t f(x) = y and f(y) = z, ???

    I get that xRz as no other unique value from X can relate to z but can't explain it


    For symmetric:

    Should the identity function be used again here? Seems like it should be
    To show transitivity, you need to show that given that there are injections f:X \to Y \ , g: Y \to Z, there is an injection h:X \to Z.

    Easily enough, let h = g \circ f, then h:X \to Z. Can you show that h is an injection?

    For reflexivity: The identity function is an injection from X to X.

    The relation is not symmetric, though. Can you see why?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Newbie
    Joined
    Sep 2009
    Posts
    8
    Quote Originally Posted by Defunkt View Post
    To show transitivity, you need to show that given that there are injections f:X \to Y \ , g: Y \to Z, there is an injection h:X \to Z.

    Easily enough, let h = g \circ f, then h:X \to Z. Can you show that h is an injection?

    For reflexivity: The identity function is an injection from X to X.

    The relation is not symmetric, though. Can you see why?
    Could I use the counterexample of X={1,2,3} Y={7,8,9} and say that (1,3) is in the relation, but (3,1) is not?

    And would a correct counterexample for antisymmetry be X={1,2,3} Y={1,2,3,4} and say that (1,2) is in the relation and (2,1) is in the relation but 2 != 1?
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by garrett12 View Post
    Could I use the counterexample of X={1,2,3} Y={7,8,9} and say that (1,3) is in the relation, but (3,1) is not?

    And would a correct counterexample for antisymmetry be X={1,2,3} Y={1,2,3,4} and say that (1,2) is in the relation and (2,1) is in the relation but 2 != 1?
    No, that is incorrect. The relation is between whole sets, ie. if X = \left\{1,2,3\right\}, Y = \left\{7,8,9\right\} then (X,Y) is in the relation and so is (Y,X) since there is an injection from X to Y and also an injection from Y to X.

    A proper counterexample to symmetry would be X = \{1\}, Y = \{1,2\}. Obviously, there is an injection from X to Y however there is no injection from Y to X, and so (X,Y) would be in the relation but (Y,X) would not be.

    Can you come up with an example to anti-symmetry now?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie
    Joined
    Sep 2009
    Posts
    8
    Quote Originally Posted by Defunkt View Post
    No, that is incorrect. The relation is between whole sets, ie. if X = \left\{1,2,3\right\}, Y = \left\{7,8,9\right\} then (X,Y) is in the relation and so is (Y,X) since there is an injection from X to Y and also an injection from Y to X.

    A proper counterexample to symmetry would be X = \{1\}, Y = \{1,2\}. Obviously, there is an injection from X to Y however there is no injection from Y to X, and so (X,Y) would be in the relation but (Y,X) would not be.

    Can you come up with an example to anti-symmetry now?
    Right, well for anti-symmetry I think that you just need the two sets to have the same cardinality and different elements to prove that it is not antisymmetric.

    E.g X = {1,2,3}, Y={4,5,6}

    There exists an injection from X->Y and Y->X, however X != Y. Hence the relation is not antisymmetric.

    ?
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Super Member
    Joined
    Aug 2009
    From
    Israel
    Posts
    976
    Quote Originally Posted by garrett12 View Post
    Right, well for anti-symmetry I think that you just need the two sets to have the same cardinality and different elements to prove that it is not antisymmetric.

    E.g X = {1,2,3}, Y={4,5,6}

    There exists an injection from X->Y and Y->X, however X != Y. Hence the relation is not antisymmetric.

    ?
    Yep, that is correct!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Relationship
    Posted in the Algebra Forum
    Replies: 17
    Last Post: March 1st 2010, 06:55 PM
  2. relationship between a,b and c
    Posted in the Calculus Forum
    Replies: 1
    Last Post: August 15th 2009, 02:37 AM
  3. Replies: 2
    Last Post: April 18th 2009, 07:27 AM
  4. Relationship between f's
    Posted in the Calculus Forum
    Replies: 2
    Last Post: October 6th 2008, 09:41 PM
  5. Relationship between ln2, ln3, ln6
    Posted in the Algebra Forum
    Replies: 3
    Last Post: March 24th 2008, 04:50 PM

Search Tags


/mathhelpforum @mathhelpforum