Results 1 to 3 of 3

Math Help - Set theory help

  1. #1
    Junior Member
    Joined
    Nov 2009
    Posts
    25

    Set theory help

    Hi,

    I have two set theory questions I'm stuck on:

    1) Prove that the following properties of a set are equivalent:
    i) There exists an injective function f : N → X (N is the set of natural numbers (sometimes called omega))
    ii) there exists a function g : X → X which is injective but not surjective.

    Now, I think I can show that ii) implies i) by using the recursion theorem to construct a function, and showing that it is 1-1. (Define f:N → X by recursion:

    f(0)=c, (c in X/ran(f))
    f(n+)= g(f(n))

    f is one-one. Does this look right?)

    However, I'm struggling to show that i) implies ii).

    2) Let A, X and Y be sets such that X≤A. Prove that Y ^X≤Y ^A. Deduce that, for cardinals κ, λ and μ, if κ ≤ λ, then κμ ≤ λμ. (Y^X is the set of functions from Y into X). Now, clearly I have to define some function from Y ^X into Y ^A, but I don't know how to go about this, particularly since the members of Y ^X and Y ^A are themselves functions...

    Any help greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by KSM08 View Post
    Hi,

    I have two set theory questions I'm stuck on:

    1) Prove that the following properties of a set are equivalent:
    i) There exists an injective function f : N → X (N is the set of natural numbers (sometimes called omega))
    ii) there exists a function g : X → X which is injective but not surjective.

    Now, I think I can show that ii) implies i) by using the recursion theorem to construct a function, and showing that it is 1-1. (Define f:N → X by recursion:

    f(0)=c, (c in X/ran(f))
    f(n+)= g(f(n))

    f is one-one. Does this look right?)

    However, I'm struggling to show that i) implies ii).

    2) Let A, X and Y be sets such that X≤A. Prove that Y ^X≤Y ^A. Deduce that, for cardinals κ, λ and μ, if κ ≤ λ, then κμ ≤ λμ. (Y^X is the set of functions from Y into X). Now, clearly I have to define some function from Y ^X into Y ^A, but I don't know how to go about this, particularly since the members of Y ^X and Y ^A are themselves functions...

    Any help greatly appreciated.
    Take the fibers of each element of \mathbb{N} under f and generated the obvious bijection...can you see where to go from there?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,917
    Thanks
    1762
    Awards
    1
    Quote Originally Posted by KSM08 View Post
    I have two set theory questions I'm stuck on:
    1) Prove that the following properties of a set are equivalent:
    i) There exists an injective function f : N → X (N is the set of natural numbers (sometimes called omega))
    ii) there exists a function g : X → X which is injective but not surjective.

    Now, I think I can show that ii) implies i) by using the recursion theorem to construct a function, and showing that it is 1-1. (Define f:N → X by recursion:
    f(0)=c, (c in X/ran(f))
    f(n+)= g(f(n))
    f is one-one. Does this look right?)
    You have a slight typo in part ii) of #1.
    It should be c\in X\setminus ran(g).

    For part i) we have f:\mathbb{N} \mapsto X is an injection.
     \left( {\forall x \in X} \right)\left[ {f^{ - 1} \{ x\} } \right] the set is either empty or it contains exactly one integer call it n_x.
    Now define g:X \mapsto X as g(x) = \left\{ {\begin{array}{rl}   {f(n_x  + 1),} & {f^{ - 1} \{ x\}  \ne \emptyset }  \\   {x,} & {\text{else}}  \\ \end{array} } \right.
    Show that g is injective and f(0) is not an image.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Textbooks on Galois Theory and Algebraic Number Theory
    Posted in the Advanced Algebra Forum
    Replies: 3
    Last Post: July 8th 2011, 07:09 PM
  2. Group Theory - Sylow Theory and simple groups
    Posted in the Advanced Algebra Forum
    Replies: 16
    Last Post: May 16th 2009, 12:10 PM
  3. Problems relating Theory of Automata (Computer Theory)
    Posted in the Advanced Math Topics Forum
    Replies: 0
    Last Post: October 17th 2007, 10:52 AM
  4. Set Theory
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 1st 2007, 07:57 PM
  5. Set Theory
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 27th 2007, 10:22 AM

Search Tags


/mathhelpforum @mathhelpforum