# Set theory/ Cardinal Help

• Feb 14th 2010, 12:32 PM
yaoyao
Set theory/ Cardinal Help
If f : A-B is the given function, the graph f is the subset of AcrossB consisting of all (a,f(a)).
1. Prove that a-(a,f(a)) is a one-to-one map of A onto the graph of f.

2. Let D and E be sets with cardinal numbers d and e. Suppose d is infinite and that e<=d. Prove that d^e is the number of one-to-one maps of E into D.(Hint: of course d^e is an upper bound. To get the reverse inequality, use part(a))

I am OK with question 1.
Here is my trial on Q2

H(E,D) is the set of all functions from E to D. |H(E,D)| = d^e
H'(E,D) is the set of all one-to-one functions from E to D. |H'(E,D)|= n

n <= d^e since H'(E,D) is a subset of H(E,D)

Construct a map F(H(E,D), H'(E,D)) making every function in H(E,D) be a one-to-one function. Then the graph of F is a subset of
H(E,D)crossH'(E,D). Suppose the set of graph F is with cardinal t.

Then, H(E,D) - (H(E,D), H'(E,D)) is a one-to-one map of H(E,D) onto the graph F.

Then we have d^e = t <= d^e * n

I am stuck here. Can we now conclude d^e <= n ? I guess no. But do you guys have any other solutions? Thank you.
• Feb 14th 2010, 01:18 PM
Plato
Suppose that $\displaystyle \mathbb{G} = \left\{ {(a,f(a):a \in A} \right\}$ then define $\displaystyle \phi:A\mapsto \mathbb{G}$ as $\displaystyle \phi(a)=(a,fa)$
It is clear that $\displaystyle \phi$ must be onto.
Suppose that $\displaystyle \phi (b)= \phi (c)$ then by definition that means $\displaystyle (b,f(b))=(c,f(c))$.
By ordered pairs that means $\displaystyle c=b$ so it is one-to-one.

The second one is false. Let $\displaystyle D=\{a,b,c\}~\&~E=\{0,1\}$.
There are no onto functions $\displaystyle E\mapsto D$
There are no one-to-one functions $\displaystyle D\mapsto E$
• Feb 14th 2010, 01:36 PM
yaoyao
Quote:

Originally Posted by Plato
Suppose that $\displaystyle \mathbb{G} = \left\{ {(a,f(a):a \in A} \right\}$ then define $\displaystyle \phi:A\mapsto \mathbb{G}$ as $\displaystyle \phi(a)=(a,fa)$
It is clear that $\displaystyle \phi$ must be onto.
Suppose that $\displaystyle \phi (b)= \phi (c)$ then by definition that means $\displaystyle (b,f(b))=(c,f(c))$.
By ordered pairs that means $\displaystyle c=b$ so it is one-to-one.

The second one is false. Let $\displaystyle D=\{a,b,c\}~\&~E=\{0,1\}$.
There are no onto functions $\displaystyle E\mapsto D$
There are no one-to-one functions $\displaystyle D\mapsto E$

The question says D is infinite.(Happy)
• Feb 14th 2010, 01:49 PM
Plato
Quote:

Originally Posted by yaoyao
The question says D is infinite.(Happy)

Ha. Read too quickly.
• Feb 16th 2010, 02:26 PM
yaoyao
Could someone move this thread to the Topology subforum? Thank you.
• Feb 16th 2010, 02:29 PM
Drexel28
Quote:

Originally Posted by yaoyao
Could someone move this thread to the Topology subforum? Thank you.

Why? This isn't topology. Also, do you still need help for number two?
• Feb 16th 2010, 02:31 PM
yaoyao
Yes I need. Not answered yet? Do you have a sol?
• Feb 16th 2010, 08:02 PM
wgunther
Ha. So I just saw this on yahoo answers and answered it there, and I remembered I saw it here and was going to answer it, but ran out of time. Here's the solution, but properly formatted.
---------------------
This is trivial with observation in part 1.

Firstly, it's silly a lot of times to think of the graph of a function to be different than the function itself, because the general set theoretic definition of a function is the set of ordered pairs, ie the graph. This is one times where thinking about the graph of a function is actually very very useful.

So, what do we need to show? We need to show there is an injection $\displaystyle K:E\to D$ to the set of injections from E to D. Take $\displaystyle f:E\to D$ arbitrary. Then define $\displaystyle k_f:E\to E\times D$ to be the injection from defined in part 1.
NOTE: Here is where we will use all of our assumptions. there is a natural bijection between $\displaystyle E\times D$ to D because $\displaystyle |D|\geq\aleph_0$ and $\displaystyle |E|\leq|D|$. So therefore, we can view $\displaystyle k_f$ as an injection from E to D itself just by coding elements of $\displaystyle E\times D$ into elements of D. This is actually the only place where this proof uses AC as well. But it's very essential, without AC this theorem will most def. fail violently.

Then define the map K as $\displaystyle f\mapsto k_f$. This map is clearly an injection (as a function is completely determined by it's graph) and this, we are done, as K is an injective map from the set of functions from E to D to the set of injections between E and D.