Results 1 to 7 of 7

Math Help - Yes or No? If f : S → N is injective but NOT surjective, is S finite?

  1. #1
    Newbie
    Joined
    May 2012
    From
    Los Angeles
    Posts
    13

    Yes or No? If f : S → N is injective but NOT surjective, is S finite?

    For set S, the set of naturals N, and a function f, if f : S → N is injective, but NOT surjective, is S finite?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member girdav's Avatar
    Joined
    Jul 2009
    From
    Rouen, France
    Posts
    675
    Thanks
    32

    Re: Yes or No? If f : S → N is injective but NOT surjective, is S finite?

    Not necessarily, for example if S is the set of natural numbers and f(n)=2n.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    May 2012
    From
    Los Angeles
    Posts
    13

    Re: Yes or No? If f : S → N is injective but NOT surjective, is S finite?

    Thanks for the response. I meant to ask: for some set S and any countable set A, if f : S → A is injective but not surjective, is S finite? I see that B = {1, 3, 5, 7,...} can inject into the naturals, but it is not surjective as 6 is unmapped. However, B is infinite. Is this right? Thanks, again.
    Last edited by mpitluk; May 6th 2012 at 10:34 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2012
    From
    Los Angeles
    Posts
    13

    Re: Yes or No? If f : S → N is injective but NOT surjective, is S finite?

    I can see that is wrong as well for the same reason. I am just trying to say that S is finite using the terms "bijective" "injective" and/or "surjective," so far, to no avail. I'm taking a grad-level math-logic class as a mere philosophy undergrad (in order to apply for departmental honors) and so, I'm just trying to make connections between the terms.

    Might this be right: For any set S, the set of naturals N, and for EVERY mapping f between S and N, if f : S → N is not surjective, then S is finite?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,395
    Thanks
    1481
    Awards
    1

    Re: Yes or No? If f : S → N is injective but NOT surjective, is S finite?

    Quote Originally Posted by mpitluk View Post
    Might this be right: For any set S, the set of naturals N, and for EVERY mapping f between S and N, if f : S → N is not surjective, then S is finite?
    No that does not work.
    One way to define infinite is called Dedekind infinite
    A set S is infinite if there is a non-surjective injection mapping S\to S.
    So S is finte if every injection S\to S is also an surjection.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2012
    From
    Los Angeles
    Posts
    13

    Re: Yes or No? If f : S → N is injective but NOT surjective, is S finite?

    Plato, can you clarify a little? I understand a set S to be Dedekind infinite iff some proper subset of S has the same cardinality as S, i.e., there is some f : A ⊂ S → S such that f is bijective. Maybe what you're saying is the same...?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Yes or No? If f : S → N is injective but NOT surjective, is S finite?

    Quote Originally Posted by mpitluk View Post
    I understand a set S to be Dedekind infinite iff some proper subset of S has the same cardinality as S, i.e., there is some f : A ⊂ S → S such that f is bijective. Maybe what you're saying is the same...?
    Yes, this is the same. Plato says that S is infinite iff there exists an f : S -> S such that f is an injection and f is not a surjection. Let A be the image of f; then A ⊂ S and f is a bijection between S and A.

    Quote Originally Posted by mpitluk View Post
    Might this be right: For any set S, the set of naturals N, and for EVERY mapping f between S and N, if f : S → N is not surjective, then S is finite?
    The natural interpretation of this statement is

    ∀S ∀f: S -> N. (f is not surjective => S is finite).

    This is false. However, the following statement:

    ∀S. (∀f : S -> N. f is not surjective) => S is finite

    is true. It can be expressed in English as: "For every S, if every function f: S -> N is not surjective, then S is finite. Note that "if" is located before "every" implying that the universal quantifier over f is in the assumption.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Injective, Surjective
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: February 14th 2011, 07:47 AM
  2. Injective, surjective map!
    Posted in the Advanced Algebra Forum
    Replies: 13
    Last Post: December 14th 2010, 12:49 AM
  3. [SOLVED] Injective and Surjective
    Posted in the Calculus Forum
    Replies: 11
    Last Post: September 29th 2010, 02:16 PM
  4. Injective and Surjective
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 9th 2009, 08:04 AM
  5. Injective and surjective
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 13th 2008, 07:35 PM

Search Tags


/mathhelpforum @mathhelpforum