Homework Help: I am getting frustrated with this question ( Real analysis)

1. Sep 27, 2010

╔(σ_σ)╝

1. The problem statement, all variables and given/known data

Let $$A$$ be the set of all real-valued functions on [0,1]. Show that there does not exist a function from [0,1] onto $$A$$.

I spent half of my Saturday trying to prove this proposition and I couldn't make headway.

2. Relevant equations

3. The attempt at a solution

Well it only makes sense that the proof should be by contradiction.

I have a feeling that I may be able to use the axiom of choice.

I also have a feeling that the same technique used to show that a set S and P(S) ( power set of S) do not have the same cardinality can be used in my proof.

That is, I could assume that my function $$E : [0,1] \rightarrow A$$ [ E for exotic :) ] was unto then make some crazy set B whose argument involves E such that if E is unto then we get a contradiction within/with B.

Sort of like the proof here : https://www.physicsforums.com/showthread.php?t=420921

Please DO NOT ,on any account, give me the solution or hints that are pretty much THE solutions.

I want to solve this problem on my own so if you want to give me a hint propose statements that make ME come up or deduce the hints ( Hopefully, you guys understand what I mean and where I am coming from ).

I want to develop some sort of mathematical maturity.

2. Sep 27, 2010

Newtime

I haven't solved in but at first glance, I would go with this idea. It seems like the cardinality of A is larger than the cardinality of the unit interval.

Disclaimer: I'm still new to analysis, so this is not just a first idea, but a rookie's first idea.

3. Sep 27, 2010

╔(σ_σ)╝

I have tried that approach numerous times (4 times if I recall right). I have a feeling it will work but I am having a difficult time coming up with a contradiction.

The problem is that the elements of A and [0,1] are far disconnected. I mean A has functions as elements and [0,1] has real numbers .

The power set approach works great because of the relation between P(S) and S; they are sets and S is a subset of P(S). This is not the case here.

If E existed it would do some crazy black-box magic with x in [0,1] and the spit out a function. There is almost no "relation" between E(x) and x.

I am new to analysis too. This is my first course and to make it worse engineering math did not prepare me for this. This is my first taste of pure mathematics.

4. Sep 27, 2010

Newtime

Yes the elements of A and the unit interval are different but how can we reconcile that? A function is uniquely determinded by where it maps each element of the domain. Since A is the set of all real valued functions on the unit interval, for each x, f(x) where f is in A has how many choices?

5. Sep 27, 2010

╔(σ_σ)╝

Well I did not assume E was one to one; so I am not sure what you mean. However, since it was assumed that E is onto for any x in [0,1] and f(x) in A there is at least 1 choice of x.

6. Sep 27, 2010

Newtime

I'm saying that any function, almost by definition, is determined by where it takes the domain. If our domain is the unit interval, than any f can be described by describing where it takes the unit interval. So in particular, for each x in the unit interval, f(x) can by any element of the reals. Thus, we have uncountably many choices for the image under f for each element of the unit interval. So what can we conclude about the cardinality of A?

7. Sep 27, 2010

╔(σ_σ)╝

I am seriously misunderstading what you are trying to say to me; correct me if I am wrong but are you saying....

E(x) = f [Where E is my map from the unit interval to a funtion of the unit interval]

f(x) can also take take on all values in R.

I was confused about what f you were referring to. I am assuming f is a funtion from E([0,1]).

EDIT

Sure the image of [0,1] under f is of the cardinality continuum . But I don't see how I can conclude anything about A that is logically sound.

Last edited: Sep 27, 2010
8. Sep 27, 2010

Petek

I think I have a proof. Here's a hint: Think about a famous proof that shows one infinite set to be "larger" than another infinite set. Please post again if you need another hint.

Petek

9. Sep 27, 2010

╔(σ_σ)╝

Cantor's diagonal argument ?

Hm.. if it is cantor's diagonal argument I wonder how I could apply it .

I mean it would be silly to write a list :tongue:

10. Sep 27, 2010

Petek

Yes.

You said you didn't want too many hints, so I'll just suggest that you think about how to apply it to your situation.

Petek

11. Sep 27, 2010

╔(σ_σ)╝

Perfect!

You are sure that using cantor's argument works, right ?

12. Sep 27, 2010

╔(σ_σ)╝

Actually, I think I got it. Perhaps a "list" is not silly after all.

Suppose
E(x) = $$f_{x}$$ for all x in [0,1]

If I define

g : multiply all functions $$f_{x}$$ in E together.
g is in E since it is defined on [0,1] but there is no x in [0,1] such that E(x) = g.

Does this argument seem reasonable ?

Last edited: Sep 27, 2010
13. Sep 27, 2010

Petek

You're on the right track looking for a function that's not in the range of E. However, defining g to be the product of all those functions $f_x$ doesn't work. You've got the issues of how to define a product over an uncountable set (possible, but messy), convergence and how to handle the situation if one of the factors evaluates to zero. Take another look at Cantor's diagonal argument and try to apply it here.

Petek

14. Sep 27, 2010

╔(σ_σ)╝

Thanks for pointing that out. I allowed by ambition to override my common sense :).

I will keep looking.

Hopefully, I get something soon; I am getting weary over the problem.
It does not seem like a ultra challenging problem.

Anyway, I should be looking for a function g that should be in E but happens not to be, by some mischievous means.

15. Sep 28, 2010

╔(σ_σ)╝

I am still stuck.

I have ran out of things to do in order to generate g that is not in E.

The tried the following
1) Multiplying : But as already pointed out I have convergence issues and I have to define products over an uncountable set and also the fact that my product can evaluate to zero.

2) Summing : It has exactly the same problem as multiplying
3) Dividing: This plainly does not work . $$f_{x}=1$$ for some x and $$f_{x}=x-1$$ for some x also. Dividing would not give me a function of [0,1].
4) Composition: It has convergence issues and also does not work. f(x) =-x is in E and h(x) = $$\sqrt(x)$$ is also in E. If I compose $$h \circ f$$ the function is not real valued on [0,1].

16. Sep 28, 2010

Petek

I'd say that you're about one "AHA!" moment away from a solution. Try solving the following problem, which might point you in the right direction:

Let S be the intersection of the interval [0,1] and the rational numbers. Let B be the set of all real-valued functions on S. Show that there does not exist a function from S onto B.

17. Sep 28, 2010

╔(σ_σ)╝

This is almost exactly what I am trying to show except now S is countable.

This would mean that B is countable but if I take any function in B I can multiply it countably infinitely many times by itself and then multiply it by some random function in B such that the product does not evaluate to zero. in which case the function I generate cannot be in B.

This is probably the same pitfall I was running into. I have a feeling that what I just wrote down may not be a valid argument.

18. Sep 28, 2010

Petek

Yes, it is almost the same problem. I thought that making the set countable might help.

You probably can solve these problems with cardinality arguments, but I doubt that that's the intent. Again, take the modified problem and try to apply the diagonal argument. I'll give additional hints in a spoiler box:

Write S = {r1, r2, r3, ...}. If the map E: S --> B is onto then every element of B can be written in the form E(ri) for some i = 1, 2, ... . Now construct an element of B that can't be any of the E(ri).

19. Sep 28, 2010

╔(σ_σ)╝

Hey I think I found something else.

Why can't I do the following

Write out all $$f_{\alpha}$$ such that E( $$\alpha$$) =$$f_{\alpha}$$

Take put x=0 in $$f_{\alpha}$$

Define g such g(0) =/= $$f_{\alpha}(0)$$. G is defined on [0,1] and real valued but g is not in E.

If what I have done is correct, please explain your own proof to me and what you were thinking.

20. Sep 28, 2010

Petek

You're getting real close, but there's still a problem with your solution. If y is any real number, then there exists a function f in A such that f(0) = y. By assumption, f has the form $f_{\alpha}$ for some $\alpha$ in [0,1]. Thus, your definition of g(0) excludes all real numbers.

21. Sep 28, 2010

╔(σ_σ)╝

I am not aware of that theorem but I trust you are right.

The hint you gave me is exactly what I am having problems with. Constructing a function that satisfies the property eludes me.

I can create something but I have not created something good enough to ensure it is not in E.

Btw, should this problem be a challenging one or am I just dull?

22. Sep 28, 2010

Office_Shredder

Staff Emeritus
For the f(0) situation, imagine if I just defined $$f_{\alpha}(x)$$ to be the constant function $$\alpha$$. Then I have no choices left for g(0).

Rather than trying to prove you can't map onto all of A, it might help to first find a subset of A which looks more like the power set of [0,1], and then work from there

23. Sep 28, 2010

╔(σ_σ)╝

If f alpha was the constant function alpha then I would be about to pick g(0) >1 since alpha is between 0 and 1. Anyway since that approach doesn't work there is no merit in discussing it.

As for your suggested approach, it is quite abstract to me. The power set of [0,1] are simply intervals contained in the unit interval . I don't understand how they can "look" the same.

Maybe I just give up trying to solve the problem without straight forward hints. The more I work on the problem and the more suggestions I get, the more I realize that I cannot solve the problem alone.

24. Sep 28, 2010

Petek

Here's another hint: I've suggested that you review Cantor's diagonal argument and find a way to modify it for your problem. Let me be more specific. Cantor's proof shows that there can be no enumeration of the real numbers in the interval [0,1] because any such enumeration necessarily misses at least one such real number. Another way to put that is that there's no mapping from the natural numbers onto [0,1]. That looks similar to your problem, right? Suppose that f maps N onto [0,1]. Then we construct a real number x in [0,1] as follows: Let the first decimal place of x be not equal to the first decimal place of f(1). Let the second decimal place of x be not equal to the second decimal place of f(2). Let the third decimal place of x be not equal to f(3), and so on. Then x cannot equal any of the numbers f(1), f(2), f(3), ... . (That's just a sketch; the real proof needs more details.) Now modify this argument to produce a function g that

1. Maps [0,1] to R, and
2. Is not equal to $f_\alpha$ for any $\alpha \in$ [0,1].

25. Sep 28, 2010

Office_Shredder

Staff Emeritus
The power set of [0,1] is more than just intervals, but that's not terribly relevant to the bigger picture. The key is that the power set P(S) of a set S can be identified in a very natural way with the set of functions from S to {0,1} a set consisting of only two elements.