Gödel's Incompleteness TheoremsWhat is the limit of mathematical knowledge?

[bobby2k]

Homework Statement

Let K be any set and let F* be the set of all functions with domain K. Prove that card K < card F*.

The Attempt at a Solution

I am first able to show that card K <= card F*, by creating an invertible function from K into F*.
let f: K -> F*
be defined so that if k is an element of K, then f(k) = {(i,k): i is an element of K}.
Basically we create a function with function value of k in all points.

But this only shows <= , I am not sure of to prove <. Then I think I must assume that there is a bijection, but that this leads to a contradiction. How do I do that?

 

[pasmith]

Homework Statement

Let K be any set and let F* be the set of all functions with domain K. Prove that card K < card F*.

The Attempt at a Solution

I am first able to show that card K <= card F*, by creating an invertible function from K into F*.
let f: K -> F*
be defined so that if k is an element of K, then f(k) = {(i,k): i is an element of K}.
Basically we create a function with function value of k in all points.

But this only shows <= , I am not sure of to prove <. Then I think I must assume that there is a bijection, but that this leads to a contradiction. How do I do that?

You don't need to use a proof by contradiction.

Show that there exists a bijection from the power set of [itex]K[/itex] to the set of functions from [itex]K[/itex] to [itex]\{0,1\}[/itex]. This set is a proper subset of [itex]F^{*}[/itex], since the codomain of a function in [itex]F^{*}[/itex] can be any non-empty set.

Why does this imply that there is no bijection from [itex]K[/itex] to [itex]F^{*}[/itex]?

 

[bobby2k]

You don't need to use a proof by contradiction.

Show that there exists a bijection from the power set of [itex]K[/itex] to the set of functions from [itex]K[/itex] to [itex]\{0,1\}[/itex]. This set is a proper subset of [itex]F^{*}[/itex], since the codomain of a function in [itex]F^{*}[/itex] can be any non-empty set.

Why does this imply that there is no bijection from [itex]K[/itex] to [itex]F^{*}[/itex]?

Ok, I'll try, I was not able to find an bijection from P(K) to the functions, but an injection, but I think it still works.

Lemma: card (P(K)) <= card L
L is the set of functions with codomain {0,1}, and domain K.
Define F2: P(K)-> L
F2(K') = {(i,j) : i is an element of K: j = 1 if i is an element of K', else j = 0}
K' is a subset of K.
F2 gives a function which has domain K, and this new function is 1 only if it is evaluated in K'.
it is must be invertible because if F2(K')=F2(K''), then K'=K''.Now we have that:

Card K < Card(P(K)) <= card(L) <= card(F*), since L is a subset of F*.
We can't have a bijection from K to F*, because then we could create an injection from P(K) to K, which is impossible.

Out of curiosity, how would you make the F2 function also surjective?

EDIT:
Haha, I see that the function I defined is actually surjective. Thanks for the help, it was a very smart trick!