Thread: 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.

Suppose that then define as
It is clear that must be onto.
Suppose that then by definition that means .
By ordered pairs that means so it is one-to-one.

The second one is false. Let .
There are no onto functions
There are no one-to-one functions

Originally Posted by Plato

Suppose that then define as
It is clear that must be onto.
Suppose that then by definition that means .
By ordered pairs that means so it is one-to-one.

The second one is false. Let .
There are no onto functions
There are no one-to-one functions

The question says D is infinite.

Originally Posted by yaoyao

The question says D is infinite.

Ha. Read too quickly.

Could someone move this thread to the Topology subforum? Thank you.

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?

Yes I need. Not answered yet? Do you have a sol?

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 to the set of injections from E to D. Take arbitrary. Then define 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 to D because and . So therefore, we can view as an injection from E to D itself just by coding elements of 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 . 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.