# Set theory help

• Feb 20th 2010, 07:10 AM
KSM08
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.
• Feb 20th 2010, 09:17 AM
Drexel28
Quote:

Originally Posted by KSM08
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?
• Feb 20th 2010, 12:29 PM
Plato
Quote:

Originally Posted by KSM08
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.