Results 1 to 3 of 3

Math Help - Finite function question

  1. #1
    Member
    Joined
    Jan 2008
    Posts
    78

    Finite function question

    Suppose that f : X --> Y is given.

    If X is finite, show that f(X) is also finite. Similarly, if X is countable,
    show that f(X) is also countable.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    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
    Hello,
    Quote Originally Posted by flaming View Post
    Suppose that f : X --> Y is given.

    If X is finite, show that f(X) is also finite. Similarly, if X is countable,
    show that f(X) is also countable.
    (talking about Y is an extraneous information)

    The solution lies in the definition of f(X)

    f(X)=\{f(x) ~:~ x \in X\}

    For any x \in X, there is at least one element y \in f(X) such that y=f(x)

    It also means that for any y \in f(X), there is at least one x \in X such that y=f(x)
    You can see that this sentence is exactly the definition of a surjection.

    Hence f ~:~ X \to f(X) is a surjection. By Cantor-Bernstein theorem (I think it's this one), we have \text{Card}(X) \ge \text{Card}(f(X))

    If X is finite, then \text{Card}(X) < \text{Card}(\mathbb{N}). So we have {\color{red}\text{Card}(f(X))} \le \text{Card}(X) < {\color{red}\text{Card}(\mathbb{N})}. Thus f(X) is finite.

    If X is countable, then \text{Card}(X) \le \text{Card}(\mathbb{N}), etc...


    If you see any mistake, tell me, I'm learning this stuff too
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,792
    Thanks
    1687
    Awards
    1
    Here are some remarks to clear up some questions raised by the above posts.
    DEFINITION: card(A) \leqslant card(B) \Leftrightarrow \,\exists \, g:A \mapsto B is an injection

    Here is a most important theorem in many texts that deal with this material.
    There is an injection F:A \mapsto B if and only if there exists a surjection <br />
G:B \mapsto A.
    As noted above there is a surjection f:X \mapsto f(X).
    So by that theorem we must have an injection g:f(X) \mapsto X
    Now apply the definition.

    BTW: I do not see how the Cantor-Schroder-Bernstein theorem applies

    Also recall that a function f:A \mapsto B is simply a subset of A \times B.
    Where A is the set of all first terms of the pairs and f(A) is the set of second terms in the pairs.
    So there is a natural expectation that the card(f(A)) \leqslant card(A).
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: May 21st 2011, 04:17 AM
  2. Replies: 1
    Last Post: September 30th 2010, 01:49 PM
  3. Determining a function based on finite sequences
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: August 29th 2010, 07:51 PM
  4. Please help me with this finite question
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 11th 2009, 04:44 AM
  5. what is the finite variation function?
    Posted in the Calculus Forum
    Replies: 2
    Last Post: January 30th 2007, 04:24 AM

Search Tags


/mathhelpforum @mathhelpforum