Real Analysis / Set Theory

onemachine

New member
Joined
Feb 2, 2012
Messages
28
Does there exist a function from the Reals to the Power Set of the Naturals such that IF x < y, THEN f(x) is a subset of f(y) AND f(x) does not equal f(y)?

a) Yes
b) No
c) Nobody knows

...edit: by "Nobody knows" I mean nobody in the world (i.e. the question has not yet been proven or disproven), not nobody in this forum. I don't expect a proof...just an answer with a concise explanation. ;) Thanks!
 
Last edited:
Consider the poset induced by the partial order \(\displaystyle \subsetneq\) over \(\displaystyle \mathcal{P}(\mathbb{N})\). Any chain in this poset can have at most a countable number of links. However, if there did exist such a function, it would imply an uncountable number of links, a contradiction. Therefore, no such function could exist.
 
Has this been proved?

Isn't it obvious? For any "link" you must add another natural number to get proper set inclusion. So at its "slowest" it approaches \(\displaystyle \mathbb{N}\) the same rate as the sequence {1}, {1,2}, {1,2,3},...
 
Isn't it obvious? For any "link" you must add another natural number to get proper set inclusion. So at its "slowest" it approaches \(\displaystyle \mathbb{N}\) the same rate as the sequence {1}, {1,2}, {1,2,3},...

Are you assuming that each additional link has only one possibility? i.e. the next link in the sequence {1}, {1,2}, {1,2,3} would be {1,2,3,4}. But in fact there are countably infinite many possibilities for each link. For example, {1,2,3,5}, {1,2,3,6}, ... ,{1,2,3,n},...

I am beginning to believe that the original question statement has not been proved or disproved under the current axioms of set theory.
 
No, that is not what I claimed. We aren't counting the number of possibilities as far as I am aware. But if you are assuming one such chain does exist then every increment in the chain adds a subset of N properly containing the previous one. What I said is that the slowest it can "go" is by adding one element at a time, creating a natural bijection (at best) from N to the sets in the chain.
 
Thanks for the responses. I was unable to open the link you posted. One thing to keep in mind about the original question is that function need not be a bijection. The function has only one requirement: IF x < y (otherwise arbitrary), THEN f(x) is a subset of f(y) AND f(x) does not equal f(y).

I'm still looking into this. I will be sure to post a proper explanation unless someone else finds it first. Thanks again!
 
Below is a proof of that the specified function does exist. I don't know latex so please bear with me on the symbols (N = naturals, Q = rationals, R = reals).


We know N~Q. So fix a 1-1, onto funtion, g: Q -> N.

Define h: P(Q) -> P(N) by h(S) = {g(x) : x is an element of S}.

Note: h is 1-1 and onto.

Note also: If S is a subset of T, then h(S) is a subset of h(T).

Define f: R -> P(Q) by f(x) = {y in Q : y < x}.

Note: If r < s, then f(r) is a subset of f(s).

Consider h composed of f : R -> P(N).

This composed function has the property specified in the question.
 
Below is a proof of that the specified function does exist. I don't know latex so please bear with me on the symbols (N = naturals, Q = rationals, R = reals).
Learning LaTeX is really quit easy and useful.
[TEX]\mathbb{N}, \mathbb{Q}, \mathbb{R}[/TEX] gives \(\displaystyle \mathbb{N},~ \mathbb{Q},~ \mathbb{R}\)

[TEX]g: \mathbb{Q}\to \mathbb{N}[/TEX] gives \(\displaystyle g: \mathbb{Q}\to \mathbb{N}\).

Here is a suggestion on notation. If \(\displaystyle S\in\mathcal{P}(\mathbb{Q})\) define \(\displaystyle h=\{g(x):x\in S\}\).

For each \(\displaystyle x\in\mathbb{R}\) define \(\displaystyle \lambda_x=\{q\in\mathbb{Q}:q\le x\}\).

Now you can define \(\displaystyle f(x)=\lambda_x\).
If \(\displaystyle x<y\) then \(\displaystyle \exists\gamma\in\mathbb{Q}\) such that \(\displaystyle x<\gamma<y\),
That means \(\displaystyle \gamma\notin\lambda_x\) but
\(\displaystyle \gamma\in\lambda_y\) so \(\displaystyle f(x)\ne f(y)\) and also \(\displaystyle f(x)\subset f(y)\).

BTW: If you click on reply with quote, you can see the other LaTeX code in this reply.
Here is more on LaTeX
 
Last edited:
Learning LaTeX is really quit easy and useful.
[TEX]\mathbb{N}, \mathbb{Q}, \mathbb{R}[/TEX] gives \(\displaystyle \mathbb{N},~ \mathbb{Q},~ \mathbb{R}\)

[TEX]g: \mathbb{Q}\to \mathbb{N}[/TEX] gives \(\displaystyle g: \mathbb{Q}\to \mathbb{N}\).

Here is a suggestion on notation. If \(\displaystyle S\in\mathcal{P}(\mathbb{Q})\) define \(\displaystyle h=\{g(x):x\in S\}\).

For each \(\displaystyle x\in\mathbb{R}\) define \(\displaystyle \lambda_x=\{q\in\mathbb{Q}:q\le x\}\).

Now you can define \(\displaystyle f(x)=\lambda_x\).
If \(\displaystyle x<y\) then \(\displaystyle \exists\gamma\in\mathbb{Q}\) such that \(\displaystyle x<\gamma<y\),
That means \(\displaystyle \gamma\notin\lambda_x\) but
\(\displaystyle \gamma\in\lambda_y\) so \(\displaystyle f(x)\ne f(y)\) and also \(\displaystyle f(x)\subset f(y)\).

BTW: If you click on reply with quote, you can see the other LaTeX code in this reply.
Here is more on LaTeX


Wow, sweet! Thanks!
 
The problem is as follows:

Let \(\displaystyle f\) be the function described. Let \(\displaystyle A_x = \left\{r \in \mathbb{Q} \mid r < x\right\}\). For any irrational number \(\displaystyle x \in \mathbb{R}\), the must exist some rational number \(\displaystyle y>x\) such that \(\displaystyle A_x = A_y\). Now, \(\displaystyle f(x) = f(y)\). (This assumes the function \(\displaystyle f\) defined as onemachine did, not as pka did). There is an equivalent argument if you deal with the function as described by pka (only now you want a rational number less than the irrational number in question).
 
Let \(\displaystyle f\) be the function described. Let \(\displaystyle A_x = \left\{r \in \mathbb{Q} \mid r < x\right\}\). For any irrational number \(\displaystyle x \in \mathbb{R}\), the must exist some rational number \(\displaystyle y>x\) such that \(\displaystyle A_x = A_y\).
This is not correct. Recall that between any two real numbers there is a rational number. Thus if \(\displaystyle x<y\) then \(\displaystyle \exists r\in\mathbb{Q}\) such that \(\displaystyle x<r<y.\)
Now \(\displaystyle r\in A_y\) but \(\displaystyle r\notin A_x.\)
In other words, if \(\displaystyle x<y\) then \(\displaystyle A_x\ne A_y\).
 
This is not correct. Recall that between any two real numbers there is a rational number. Thus if \(\displaystyle x<y\) then \(\displaystyle \exists r\in\mathbb{Q}\) such that \(\displaystyle x<r<y.\)
Now \(\displaystyle r\in A_y\) but \(\displaystyle r\notin A_x.\)
In other words, if \(\displaystyle x<y\) then \(\displaystyle A_x\ne A_y\).

Yep
 
This is not correct. Recall that between any two real numbers there is a rational number. Thus if \(\displaystyle x<y\) then \(\displaystyle \exists r\in\mathbb{Q}\) such that \(\displaystyle x<r<y.\)
Now \(\displaystyle r\in A_y\) but \(\displaystyle r\notin A_x.\)
In other words, if \(\displaystyle x<y\) then \(\displaystyle A_x\ne A_y\).

That is incorrect. \(\displaystyle A_x\) is actually an open interval. \(\displaystyle A_x = (-\infty,x)\cap\mathbb{Q}\). So, the question is, how many such intervals are there? Well, since \(\displaystyle \mathbb{Q}\) is COUNTABLE, there are a countable number of such intervals. Therefore, by the Pigeonhole Principle, if you attempt to assign a countable number of images to an uncountable set, there must exist an INFINITE number of points that are equal to some other points. It is easy to see that the multiple assignments occur when irrationals are assigned the same sets that rationals are assigned.
 
\(\displaystyle A_x\) is actually an open interval. \(\displaystyle A_x = (-\infty,x)\cap\mathbb{Q}\).

Yes, but earlier you said if \(\displaystyle y>x\) then \(\displaystyle A_x = A_y\). In fact, if \(\displaystyle y>x\), then \(\displaystyle A_x\ne A_y\). I believe this was the logic error pka was pointing out.
 
OH, I think it just clicked! Slipeternal, what you are saying is that the function I described does not hold the property that f(x) does not equal f(y) for all x, y such that x < y because the irrationals are dense in R. Correct?
 
OH, I think it just clicked! Slipeternal, what you are saying is that the function I described does not hold the property that f(x) does not equal f(y) for all x, y such that x < y because the irrationals are dense in R. Correct?

Exactly
 
Slip, I now completely understand what you are saying. However, I see one major problem with this argument:

The problem is as follows:

Let \(\displaystyle f\) be the function described. Let \(\displaystyle A_x = \left\{r \in \mathbb{Q} \mid r < x\right\}\). For any irrational number \(\displaystyle x \in \mathbb{R}\), the must exist some rational number \(\displaystyle y>x\) such that \(\displaystyle A_x = A_y\). Now, \(\displaystyle f(x) = f(y)\). (This assumes the function \(\displaystyle f\) defined as onemachine did, not as pka did). There is an equivalent argument if you deal with the function as described by pka (only now you want a rational number less than the irrational number in question).

By the well known theorem which states the density of the rationals in the reals, there must exist a rational number, \(\displaystyle z\) such that \(\displaystyle y>z>x\). Thus, \(\displaystyle f(x)\ne f(y)\).


But I also see that one could once again argue that there exists an irrational number between these that would appear to satisfy \(\displaystyle f(x) = f(y)\). This switching of arguments seems like it would go on forever. What I dont understand is: if the irrationals so far outnumber the rationals, how can it be that there is no spot along the real line with two adjacent irrationals?
 
Top