Results 1 to 10 of 10

Math Help - How can you proof this?

  1. #1
    Junior Member
    Joined
    Oct 2009
    From
    UK
    Posts
    31

    Question How can you proof this?

    Okey hi!
    I have a question. I have to prove that:
    g has bijectivity <-> g has injectivity <-> g has surjetivity.

    I know that the map is g: X -> Y. X and Y are both finite sets, and you know that the cardinality of X is the same as the cardinality of Y.

    How do you proof this statement?
    I don't know how to start, what to do, what to use...

    Thanks for any help!
    Mary
    Last edited by mr fantastic; November 14th 2009 at 03:17 AM. Reason: Restored deleted question.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    Quote Originally Posted by MaryB View Post
    Okey hi!
    I have a question. I have to prove that:
    g has bijectivity <-> g has injectivity <-> g has surjetivity.

    I know that the map is g: X -> Y. X and Y are both finite sets, and you know that the cardinality of X is the same as the cardinality of Y.

    How do you proof this statement?
    I don't know how to start, what to do, what to use...
    Actually I have no idea what you are asking.
    A mapping is a bijection if and only if it is both injective and surjective.

    Now what is the exact statement of the question you have been given?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Plato View Post
    Actually I have no idea what you are asking.
    A mapping is a bijection if and only if it is both injective and surjective.

    Now what is the exact statement of the question you have been given?
    I think the question is the following: If X and Y are both finite and have the same cardinality, i.e. |X|=|Y|, then g:X->Y is bijective if and only if it is injective (and if and only if it is surjective).
    So, under these particular assumptions (X,Y finite and of the same cardinality) being bijective, being injective, and being surjective are all equivalent. It sounds true, doesn't it?
    Now to prove this I suggest showing, first, that from g:X->Y being injective it follows that g is also surjective, and, second, that from g being surjective it follows that g ia also injective. (Under the given assumptions, the first statement follows, because the image of X under g is a subset of the finite set Y, is contained in Y, and has the same number of elements as Y. The second statement follows, because if g is surjective and X and Y have the same cardinality, it is not possible that the inverse image of some element of Y contains more than one element of X, because otherwise the cardinality of the image of X under g would be less than the cardinality of Y, contradicting the assumed surjectivity of g.)
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Member
    Joined
    Oct 2009
    Posts
    95
    Quote Originally Posted by MaryB View Post
    Okey hi!
    I have a question. I have to prove that:
    g has bijectivity <-> g has injectivity <-> g has surjetivity.

    I know that the map is g: X -> Y. X and Y are both finite sets, and you know that the cardinality of X is the same as the cardinality of Y.

    How do you proof this statement?
    I don't know how to start, what to do, what to use...

    Thanks for any help!
    Mary
    If X and Y have both finite cardinality and |X|=|Y| this is true. Note that the way you stated your questions is backwards, you should of said, let g be a map g:X->Y where X and Y have finite (and same) cardinality, then ....


    But anyhow, the standard trick to proving this is based on the pigeon hole principle.

    I'm going to label the statements in your proof:

    1<=> 2<=> 3
    g has bijectivity <=> g has injectivity <=> g has surjetivity.


    It suffices to show 2 => 3 and 3=>2 because by definition (2 and 3) <=> 1

    Let R=\{g(x) \in Y : x \in X\}

    So suppose that g is injective. Now in order to come to a contradiction suppose that g is not surjective. Then there exists a y \in Y such that  y \notin R. This means that |R|<|Y|=|X| which means by the pigeon hole principle there exist x,y\in X such that  x \neq y and g(x)=g(y) which contradicts injectivity.


    For the other direction, suppose that g is surjective. Then Y=R and furthermore |Y|=|R|. Suppose that g is not injective. Then |X|>|R|=|Y| a contradiction.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,605
    Thanks
    1573
    Awards
    1
    I have questions for both Failure & gmatt.
    The original question is so garbled, how do you read it?
    It is clearly about finite sets.
    But you don’t which of the two standard definitions of finite is being used.
    Some texts say that a set is finite if it bijects with \{1,2,3,\cdots,n\} for some positive integer n.
    If that is the case then this is a trivial question.

    On the other hand, the second way to define finite set is to say that ‘A set is finite if it is not infinite’.
    This is often called Dedekind finite. A set is Dedekind infinite if it bijects with a proper subset of itself.

    Now unless you know the setting of the question, I think it is hard to give a correct answer.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Plato View Post
    I have questions for both Failure & gmatt.
    The original question is so garbled, how do you read it?
    Call it "instinct", or rather "searching for a charitable interpretation of the question". Also, you get plenty of exercise decoding garbled language in everyday life (outside the context of studying and discussing mathematics).

    It is clearly about finite sets.
    But you don’t which of the two standard definitions of finite is being used.
    Some texts say that a set is finite if it bijects with \{1,2,3,\cdots,n\} for some positive integer n.
    If that is the case then this is a trivial question.

    On the other hand, the second way to define finite set is to say that ‘A set is finite if it is not infinite’.
    This is often called Dedekind finite. A set is Dedekind infinite if it bijects with a proper subset of itself.
    If you know for a certainty (preferably with a proof) that these two definitions of "finite" are equivalent, then using Dedekind's definition of "finite" would not be any more problematic. - If, on the other hand, you don't know whether these two definitions are equivalent, then you have a problem at hand that is perhaps more difficult to solve than the exercise itself (after you have solved the primary problem of showing the two definitions to be equivalent).

    Now unless you know the setting of the question, I think it is hard to give a correct answer.
    I tend to follow Yogi Berra's advice: "When you come to a fork in the road, take it."
    So if I have the option of choosing a (quite common) definition of finite (originally given by Bertrand Russell, I believe), that makes the exercise trivial to solve: I'll choose that definition, of course.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Junior Member
    Joined
    Oct 2009
    From
    UK
    Posts
    31
    Sorry to read that I caused so much troubles!
    But I can´t help it, the assignments I get are like this, I can´t make it any easier or better to read.

    `Proof the following: a map g has bijectivity iff g has injectivity iff g has surjectivity. Map g is defined g: X -> Y.
    X and Y are both finite sets, and you know that X and Y have the same cardinality.'

    This is what it says...

    Mary
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by Plato View Post
    On the other hand, the second way to define finite set is to say that ‘A set is finite if it is not infinite’.
    This is often called Dedekind finite. A set is Dedekind infinite if it bijects with a proper subset of itself.
    To show that a proof of the statement is not any less "trivial" for Dedekind's definition of "finite", let me show that g injective implies g surjective, and that g surjective implies g injective (assuming the axiom of choice).

    Since we are told that X and Y have the same cardinality, we are allowed to assume that a bijective mapping b:X->Y of X onto Y exists.

    Proof of g injective \Rightarrow g surjective: (indirect) assume g were not surjective, then the inverse of g restricted to the image of X under g, combined with b would give a bijective mapping of Y onto a proper subset of itself, contradicting the (Dedekind) finiteness of Y.

    Proof of g surjective \Rightarrow g injective: (indirect) if g is surjective then, by the axiom of choice, there exists a mapping g* that maps every y of Y to a single x of the inverse image of y under g. If g were not injective, then the combination of g with g* would yield a bijective mapping of a proper subset of X onto X, contradicting the (Dedekind) finiteness of X.

    Edit: Come to think of it: talk of the axiom of choice, in the context of finite sets, is a bit of overkill here. However, if you are not shy about the axiom of choice, there is no problem. - I suppose, someone using Dedekind's definition of finiteness is likely not to be shy about the axiom of choice.
    Last edited by Failure; October 30th 2009 at 10:07 AM.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    241
    Quote Originally Posted by Failure View Post
    To show that a proof of the statement is not any less "trivial" for Dedekind's definition of "finite", let me show that g injective implies g surjective, and that g surjective implies g injective (assuming the axiom of choice).

    Since we are told that X and Y have the same cardinality, we are allowed to assume that a bijective mapping b:X->Y of X onto Y exists.

    Proof of g injective \Rightarrow g surjective: (indirect) assume g were not surjective, then the inverse of g restricted to the image of X under g, combined with b would give a bijective mapping of Y onto a proper subset of itself, contradicting the (Dedekind) finiteness of Y.

    Proof of g surjective \Rightarrow g injective: (indirect) if g is surjective then, by the axiom of choice, there exists a mapping g* that maps every y of Y to a single x of the inverse image of y under g. If g were not injective, then the combination of g with g* would yield a bijective mapping of a proper subset of X onto X, contradicting the (Dedekind) finiteness of X.

    Edit: Come to think of it: talk of the axiom of choice, in the context of finite sets, is a bit of overkill here. However, if you are not shy about the axiom of choice, there is no problem. - I suppose, someone using Dedekind's definition of finiteness is likely not to be shy about the axiom of choice.
    Please be kind to the old dog trying to learn new tricks!?

    I find this fascinating, and we've just covered similar material in my class.

    I follow everything up to where you combine the inverse of g with b to get a bijective map of Y to a proper subset of itself. Since g is not necessarily a bijective map, how does it follow that you get a bijective map of Y to a proper subset of itself?

    Thanks
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by oldguynewstudent View Post
    Please be kind to the old dog trying to learn new tricks!?

    I find this fascinating, and we've just covered similar material in my class.

    I follow everything up to where you combine the inverse of g with b to get a bijective map of Y to a proper subset of itself. Since g is not necessarily a bijective map, how does it follow that you get a bijective map of Y to a proper subset of itself?

    Thanks
    Well, assuming g: X->Y is injective, then g: X->g(X) is a bijective mapping of X onto the subset g(X) of Y, where g(X) is the image of X under g. If g were not surjective, then g(X) would be a proper subset of Y. Now you can use the inverse of g to map g(X) bijectively onto X and then map X bijectively onto Y, using the bijective mapping b: X->Y that we are allowed to assume exists, because we are told that |X|=|Y| holds. Thus, the bijective map h:g(X)->Y, defined as h := b\circ g^{-1}\ would do the job of mapping a proper subset of Y, namely g(X), onto Y. But since we are told that Y is (Dedekind) finite, this is a contradiction.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 15
    Last Post: June 8th 2011, 11:13 AM
  2. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  3. [SOLVED] direct proof and proof by contradiction
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: February 27th 2010, 10:07 PM
  4. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: April 14th 2008, 04:07 PM

Search Tags


/mathhelpforum @mathhelpforum