I am getting frustrated with this question ( Real analysis)

[╔(σ_σ)╝]

Homework Statement

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.

Homework Equations

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=420921Please 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.

 

[Newtime]

...

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.

...

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.

 

[╔(σ_σ)╝]

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.

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.

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

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.

 

[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?

 

[╔(σ_σ)╝]

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.

Are you asking about choices of f(x) or x?

 

[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?

 

[╔(σ_σ)╝]

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?

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.

Please elaborate on your point

 

[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

 

[╔(σ_σ)╝]

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

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

 

[Petek]

Cantor's diagonal argument ?

Yes.

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

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

 

[╔(σ_σ)╝]

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

Perfect!

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

 

[╔(σ_σ)╝]

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 ?

 

[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

 

[╔(σ_σ)╝]

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

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.

 

[╔(σ_σ)╝]

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].I still do not want the answer but I want to know if I am going about this the wrong way.

 

[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.

 

[╔(σ_σ)╝]

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.

 

[Petek]

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

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

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.

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:

Spoiler

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

 

[╔(σ_σ)╝]

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:

Spoiler

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

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.

 

[Petek]

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.

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.

 

[╔(σ_σ)╝]

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?

 

[Office_Shredder]

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

 

[╔(σ_σ)╝]

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

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.

 

[Petek]

I'll let Office_Shredder handle your questions about his suggestion.

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].

 

[Office_Shredder]

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.

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.

 

[╔(σ_σ)╝]

I'll let Office_Shredder handle your questions about his suggestion.

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].

Well how about something like this...

Take $$f_{ \alpha} \left( \alpha \right) = g \left( \alpha \right)$$ for all $$\alpha \in[0,1]$$ g is not in E since the the values of g at every point in [0,1] differ from by functions in E.

Thank you for been patient with me. It must be frustrating for you to keep telling the same thing and I keep producing the wrong result and to make it worse I don't want the answer . I appreciate your help thus far.

 

[╔(σ_σ)╝]

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.

Well if I am right the set containing the two elements is a set. Perhaps the first element is a subset of S that does not contain the element of S in question and the second element would be a subset of S containing the element of S in question. Is this what you mean ?

I am still not seeing anything. I believe you are seeing some solution that exist in the clever realm but I am not seeing it :-).

 

[Petek]

Well how about something like this...

Take $$f_{ \alpha} \left( \alpha \right) = g \left( \alpha \right)$$ for all $$\alpha \in[0,1]$$ g is not in E since the the values of g at every point in [0,1] differ from by functions in E.

Thank you for been patient with me. It must be frustrating for you to keep telling the same thing and I keep producing the wrong result and to make it worse I don't want the answer . I appreciate your help thus far.

That's so close to being correct that I think you must have made a typo. Your function g equals $f_\alpha$ at the point $\alpha$, when you want exactly the opposite to be true. I enjoy helping students, so you're welcome.

 

[╔(σ_σ)╝]

That's so close to being correct that I think you must have made a typo. Your function g equals $f_\alpha$ at the point $\alpha$, when you want exactly the opposite to be true. I enjoy helping students, so you're welcome.

Yeah it should be a not equal sign; sorry about that. I was typing hurriedly from my phone
So I guess we are finally done.

I greatly appreciate all your help and your patience.

I will like to ask again, what do you think is the level of difficulty of this problem. I can't help but think that I sent way more time than I should have on the question.
And also is this the same proof you had in mind or was yours a little different ? If it was, I would like to see it.

 

[╔(σ_σ)╝]

office_shredder I would like to see your proof or understand what you were discribing to me.

 

[Scigatt]

office_shredder I would like to see your proof or understand what you were discribing to me.

I think that this was the proof that office_shredder was hinting at. Hopefully there aren't any errors or gaps here:

Let S be a subset of [0,1]. Consider a function $$f_{S}:[0,1] \rightarrow \{0,1\}$$ such that $$x \in [0,1]$$ implies $$f_{S}(x) = 1\ iff\ x \in S$$. If a subset S has two such functions, then either they are equal or there exists an x that is both an element and a non-element of S, which is impossible, so for each subset of [0,1] there exists a unique function f_S. Also, if a function f_T is the function for both T and T'(T, T' being subsets of [0,1]), then if f_T(x) = 1, then x is in both T and T' and if f_T(x) =/= 1, then x is not in either T or T', thus T and T' have exactly the same elements, and T = T'. Thus for each such function there exists a single subset of S. Also, the set of all functions with with codomain {0,1} that are related to subsets of [0,1] is itself a subset of A. Thus there is a one to one correspondence between the set of subsets of [0,1](i.e. the power set of [0,1]) and the subset of functions in A that can be defined as stated in the start of this proof. Thus, you cannot have an onto function from [0,1] to this subset of A, never mind all of A.

 

[╔(σ_σ)╝]

I think that this was the proof that office_shredder was hinting at. Hopefully there aren't any errors or gaps here:

Let S be a subset of [0,1]. Consider a function $$f_{S}:[0,1] \rightarrow \{0,1\}$$ such that $$x \in [0,1]$$ implies $$f_{S}(x) = 1\ iff\ x \in S$$. If a subset S has two such functions, then either they are equal or there exists an x that is both an element and a non-element of S, which is impossible, so for each subset of [0,1] there exists a unique function f_S. Also, if a function f_T is the function for both T and T'(T, T' being subsets of [0,1]), then if f_T(x) = 1, then x is in both T and T' and if f_T(x) =/= 1, then x is not in either T or T', thus T and T' have exactly the same elements, and T = T'. Thus for each such function there exists a single subset of S. Also, the set of all functions with with codomain {0,1} that are related to subsets of [0,1] is itself a subset of A. Thus there is a one to one correspondence between the set of subsets of [0,1](i.e. the power set of [0,1]) and the subset of functions in A that can be defined as stated in the start of this proof. Thus, you cannot have an onto function from [0,1] to this subset of A, never mind all of A.

Wow *faints*.


Although the proof petek help me cool up with is much shorter this is such a cool proof! Regardless of the amount of hints Office_shredder gave, I would not have come up with this argument.

I love PF simply because of this kind of things; people have such cool and different ways of doing things and this is fun to watch.


I guess proofs like this just come with maturity. Thanks a lot for the proof.

 

[Petek]

Yeah it should be a not equal sign; sorry about that. I was typing hurriedly from my phone
So I guess we are finally done.

I greatly appreciate all your help and your patience.

I will like to ask again, what do you think is the level of difficulty of this problem. I can't help but think that I sent way more time than I should have on the question.
And also is this the same proof you had in mind or was yours a little different ? If it was, I would like to see it.

The solution I had in mind was essentially the same one that you came up with. I would have defined g like this:

$$g(\alpha) = f_\alpha(\alpha) + 1$$

That makes the definition more explicit, but that's a minor point. I can't say how difficult the problem is. It depends on lots of factors. If this problem was assigned to a class, you might want to ask your fellow students about it. Or you could ask the instructor what percentage came up with the right solution.

 

[╔(σ_σ)╝]

The solution I had in mind was essentially the same one that you came up with. I would have defined g like this:

$$g(\alpha) = f_\alpha(\alpha) + 1$$

That makes the definition more explicit, but that's a minor point. I can't say how difficult the problem is. It depends on lots of factors. If this problem was assigned to a class, you might want to ask your fellow students about it. Or you could ask the instructor what percentage came up with the right solution.

Alright. Again, thank you very much for your help! I really appreciate it :-).

 

[FallMonkey]

I think that this was the proof that office_shredder was hinting at. Hopefully there aren't any errors or gaps here:

Let S be a subset of [0,1]. Consider a function $$f_{S}:[0,1] \rightarrow \{0,1\}$$ such that $$x \in [0,1]$$ implies $$f_{S}(x) = 1\ iff\ x \in S$$. If a subset S has two such functions, then either they are equal or there exists an x that is both an element and a non-element of S, which is impossible, so for each subset of [0,1] there exists a unique function f_S. Also, if a function f_T is the function for both T and T'(T, T' being subsets of [0,1]), then if f_T(x) = 1, then x is in both T and T' and if f_T(x) =/= 1, then x is not in either T or T', thus T and T' have exactly the same elements, and T = T'. Thus for each such function there exists a single subset of S. Also, the set of all functions with with codomain {0,1} that are related to subsets of [0,1] is itself a subset of A. Thus there is a one to one correspondence between the set of subsets of [0,1](i.e. the power set of [0,1]) and the subset of functions in A that can be defined as stated in the start of this proof. Thus, you cannot have an onto function from [0,1] to this subset of A, never mind all of A.

Now that Fs is function from [0,1] to {0,1}, then how could f(x)=1 if 1 is not in the codomain? And what do you mean by " functions in A that can be defined as stated in the start of this proof", if we only define it from [0,1] to {0,1}?

Am I missing something? Though this is a classic proof and it should hold.