# Thread: Power set of N uncountably infinite. Why?

1. Hi,

I understand that N is countably infinite. And that the real numbers are uncountably infinite, since you can't really pick a place to start (e.g. [0,1], you can start at 0.0001 or 0.0000000001. It basically goes for ever).

However, I don't understand that the power set of N is uncountable. Why can't I just start with {1} then {2} , {1,2} to go through all subsets?

Is it possible to show an example/explain without the Cantor Diagonal argument? Or is that not possible?

2.

3. Originally Posted by AndyDufresne
Why can't I just start with {1} then {2} , {1,2} to go through all subsets?
It is because you are counting only the finite subsets of the natural numbers. It is the inclusion of the infinite subsets of the natural numbers that makes the power set uncountable.

4. Thank you for this comment. It is more clear now.

From what I understand (according to wikipedia), the inclusion is the relationship of one set being a subset of another.
But I think I get it, because the amount of those "infinite subsets'' are what makes it uncountable.

5. Every real number between 0 and 1 can be mapped to an element of (via its binary expansion, ignoring technicalities) which is the power set of the naturals - showing that this power set has to be at least as large as the continuum.

6. Originally Posted by AndyDufresne
And that the real numbers are uncountably infinite, since you can't really pick a place to start (e.g. [0,1], you can start at 0.0001 or 0.0000000001. It basically goes for ever).
You can't pick a place to start with the rationals either, since .1, .01, .001, .0001, ... are all rational numbers. Yet the rationals are countable. Perhaps going back to basics and reviewing the definition of uncountability would be a great help here.

7. There is no doubt in my mind that the diagonal argument is he most elegant proof that is uncountable. Here is another, somewhat less satisfactory argument.

First consider an arbitrary set . Writing for the cardinality of this set, it will suffice to show that .In turn it will suffice to show there is no bijection that is

So it what follows it is important to keep at the front of our minds that elements in are subsets in (I know we all know this, but my notation, which is almost unavoidable, may confuse this fact.

So we have . The injection is obvious, which establishes

I assume that is a bijection, and try for a contradiction.

Define (Recall that ) by
By hypothesis I assume there exists such that

Now recall that - then either or

In the former case I have that, by the definition of that , but by this is impossible

In the latter case, implies (definition of ) but since , this cannot be

Thus our contradiction, there is no bijection and thus .

Setting which is obviously countable but infinite, then I will say that and and is not countable

To show that reqires more work - to say that is, so far as I am aware contentious

8. The thing to ask with a countable set is this: Can any given member be enumerated with a finite amount of steps? With N, it clearly can. You can't come up with a natural number that a counting algorithm won't get to in finite steps, even though there are an infinite amount of such numbers. But with the power set, you can define a set, like the infinite set of all even numbers in N, which will take your algorithm infinite steps to reach if it starts with enumerating finite sets. So clearly, its uncountable.

9. Originally Posted by TridentBlue
The thing to ask with a countable set is this: Can any given member be enumerated with a finite amount of steps? With N, it clearly can. You can't come up with a natural number that a counting algorithm won't get to in finite steps, even though there are an infinite amount of such numbers. But with the power set, you can define a set, like the infinite set of all even numbers in N, which will take your algorithm infinite steps to reach if it starts with enumerating finite sets. So clearly, its uncountable.
What do you mean by "enumerated?" The real numbers contain uncountably many elements, but each element can be enumerated in one step. I enumerate 3 as 3. I enumerate 47 as 47. I enumerate pi as pi. So I'm really not clear what you mean here. I can enumerate every element of the reals in one step. Yet the set of reals is uncountable.

Originally Posted by Guitarist

To show that reqires more work - to say that is, so far as I am aware contentious
Easy proof. You correspond a subset of with the binary decimal that has 1 in place n iff n is in that subset. It's not contentious at all. What's contentious is whether there's some cardinality strictly in between that of and .

10. What do I mean by enumerated? Okay, imagine an algorithm which enumerates all the digits between 1 and 2. The first 11 members of the set enumerated might be the decimals with only one decimal number:
1.0, 1.1, 1.2 ... 1.9, 2.0
then the next pass the numbers with two digits in the decimal:
1.01, 1.02, 1.03 ... 1.98, 1.99
Then the the next pass would have all the numbers with 3 digits, and so on. This would define a countably infinite set of numbers. However, the square root of two would not be in this countably infinite set, because it would take the algorithm an infinite amount of steps to reach it, because it has infinite decimal places.

Now, we could also define a countably infinite set that contains the square root of two, its the set of all square roots of natural numbers. Easily done. (note that countability refers to sets, not numbers themselves.) But what we cannot do is define a set that enumerates all the numbers between 1 and 2. There would always be some number, the digits of which are totally random and go on forever, that would not be enumerated in finite time.

Why is this? Some people like the diagonalization argument, but I like the work of Chaitin. He makes the case there must be a vast amount of numbers with infinite random digits, and that these in effect contain infinite information. Because of this, these numbers cannot be compressed down into any finite mathematical expression, like a computer program which enumerates their digits. (as we can do with e or pi or 2^(1/2)) Its impossible to represent these numbers because it is impossible to compress infinite information into a finite package. So they cannot be enumerated, and the real numbers are uncountable.

A number can be enumerated only if it takes finite infomation to specifiy it. An uncountable set is a set which allows the possibility of sets which take infinite information to specify.

11. Originally Posted by TridentBlue
An uncountable set is a set which allows the possibility of sets which take infinite information to specify.
Counterexample: Any countable set of non-computable (or algorithmically incompressible) numbers. Such a set has the property that each of its elements require an infinite amount of information to specify, yet the set is still countable. In fact just take a finite set of incompressible numbers for an even stronger counterexample. I get where you're coming from, but the OP in this thread is already confused about the definition of an uncountable set, and your example doesn't help, because it's inaccurate. You might be able to fix it up but you haven't so far.

12. My example is correct. You can't specify a single number which takes infinite information to specify, because it takes infinite information to do so. You would be writing the digits, or the computer program that enumerates its digits, forever. If you are able to specify such a number with finite information somehow, then yes, its part of a countable set. But there must be an ininite amount of numbers within that system of representation which take infinite information to specify within that system of representation.

What I'm saying can also be related strait back to the diagonalization argument as well. Its the exact same thing.

13. Here's an even simpler way of putting it: A set is countable if a 1-to-1 relationship can be defined between all its members, and the natural numbers. A natural number cannot have infinite digits. So if some number in the set, based on the rules of a given map, results in a natural number representation which has infinite digits, then that set is not countable by that map.

an uncountable set is one which no map exists that map all its members to the natural numbers, without resulting in natural numbers with infinite digits.

I think the information view is intuitive for understanding this: For a given encoding, somewhere between 0 and 1 is a real number which has every movie ever shot encoded in its first decimal digits, then every concievable variation on every movie, then every variation on the variation - resulting in documentaries on alien worlds and so on - and on and on to infinity. It contains infinite information. It can't be mapped to a natural number because of this: You just can't put infinite information in a finite box, no matter how big the box is. And with every map, there's going to be some number like that if you're dealing with an uncountable set.

14. Originally Posted by TridentBlue
You can't specify a single number which takes infinite information to specify, because it takes infinite information to do so. You would be writing the digits, or the computer program that enumerates its digits, forever. If you are able to specify such a number with finite information somehow, then yes, its part of a countable set. But there must be an ininite amount of numbers within that system of representation which take infinite information to specify within that system of representation.

What I'm saying can also be related strait back to the diagonalization argument as well. Its the exact same thing.
Here's a clearer example, since it doesn't require the use of noncomputable numbers.

Let (a, b) stand for the open interval of real numbers strictly between a and b. That is,

Now let X = {(n, n+1) : n = 1, 2, 3, ...}

In other words X is the collection of all open intervals of real numbers with natural number endpoints.

You can see that each element of X is uncountable. But what is the cardinality of X? Clearly, it's countable.

So just because a set contains elements that can not be enumerated, the set itself could still be finite, countable, or uncountable.

Originally Posted by TridentBlue
A set is countable if a 1-to-1 relationship can be defined between all its members, and the natural numbers. A natural number cannot have infinite digits. So if some number in the set, based on the rules of a given map, results in a natural number representation which has infinite digits, then that set is not countable by that map.
You are confused between a set and its elements. Why can't I have a finite or countable set of elements; where each element is in fact an uncountable set or an incompressible real?

Originally Posted by TridentBlue
I think the information view is intuitive for understanding this: For a given encoding, somewhere between 0 and 1 is a real number which has every movie ever shot encoded in its first decimal digits, then every concievable variation on every movie, then every variation on the variation - resulting in documentaries on alien worlds and so on - and on and on to infinity. It contains infinite information. It can't be mapped to a natural number because of this: You just can't put infinite information in a finite box, no matter how big the box is. And with every map, there's going to be some number like that if you're dealing with an uncountable set.
That's exactly right. Call that incompressible number x. Now the set {x} has how many members? Exactly 1. It's a finite set.

So your claim that P(N) is uncountable because some subsets of N are incompressible, simply fails. (It's a false proof of a true fact). Sure, P(N) contains some incompressible sets. (But the even numbers are most definitely NOT one of those!! That's another of your errors). But I already showed you a countable set containing uncountable intervals. And I showed you a finite set, {x}, containing exactly one element, which happens to be an incompressible real.

So for all you know, P(N) is countable. For all you know, P(N) is finite! You haven't proved otherwise. You need a stronger proof. You are totally confused about the difference between the cardinality of a set, and the cardinality of some of its elements.

Let me leave you with a question. What is the cardinality of the set ?

15. [QUOTE=someguy1;568663]
Originally Posted by TridentBlue
You are confused between a set and its elements. Why can't I have a finite or countable set of elements; where each element is in fact an uncountable set or an incompressible real?
I hear you, and you totally can. How about the singleton set with the set of real numbers mapped to 1? I may have used sloppy language in making my point, but my point is good: The basics of what I'm saying is that if you define some mapping from members of some infinite set to the natural numbers, and that mapping results in some clearly defined member of your set mapping to a natural number with infinite digits, (infinite information) than that set is not countable by that mapping.

For instance, suppose I claim that by mapping the decimals between 0 and 1 to the the naturals, as I did above, (so 0.1 =1, 0.55 = 55, 0.12334 = 12,334, etc) that I have found a way to count the rational numbers. You come along and point out as counter example 1/3, which is a rational but maps to the natural number 333333.... a natural number with infinite digits, all 3's. That means that my mapping does not count the rational numbers. Note that this does not mean the rational numbers are uncountable, as we both know they are. Just that my mapping fails to count them all.

A set of numbers is uncountable when no mapping to the natural numbers exists which doesn't have SOME members of the set requiring infinite-digit-naturals to represent them, aka infinite information. Trivially, every finite set is countable. If we allow that non-algorithmically compressible numbers can be well defined (I'm not sure about this) than this doesn't change the fundamentals: Even if it takes infinite information to represent the number, it must not take infinite information to represent the natural number it maps to : it cannot map to a natural number with infinite digits. You need to always be able to come up with a map that will, in all cases, represent this number with a finite amount of information. With uncountable sets, this is simply impossible.... Its not impossible to come up with a map that represents some numbers which are infinitely long with vast information, but its impossible to come up with a map that represents ALL such numbers.

16. [QUOTE=TridentBlue;568674]
Originally Posted by someguy1
Originally Posted by TridentBlue
You are confused between a set and its elements. Why can't I have a finite or countable set of elements; where each element is in fact an uncountable set or an incompressible real?
I hear you, and you totally can. How about the singleton set with the set of real numbers mapped to 1? I may have used sloppy language in making my point, but my point is good: The basics of what I'm saying is that if you define some mapping from members of some infinite set to the natural numbers, and that mapping results in some clearly defined member of your set mapping to a natural number with infinite digits, (infinite information) than that set is not countable by that mapping.

For instance, suppose I claim that by mapping the decimals between 0 and 1 to the the naturals, as I did above, (so 0.1 =1, 0.55 = 55, 0.12334 = 12,334, etc) that I have found a way to count the rational numbers. You come along and point out as counter example 1/3, which is a rational but maps to the natural number 333333.... a natural number with infinite digits, all 3's. That means that my mapping does not count the rational numbers. Note that this does not mean the rational numbers are uncountable, as we both know they are. Just that my mapping fails to count them all.

A set of numbers is uncountable when no mapping to the natural numbers exists which doesn't have SOME members of the set requiring infinite-digit-naturals to represent them, aka infinite information. Trivially, every finite set is countable. If we allow that non-algorithmically compressible numbers can be well defined (I'm not sure about this) than this doesn't change the fundamentals: Even if it takes infinite information to represent the number, it must not take infinite information to represent the natural number it maps to : it cannot map to a natural number with infinite digits. You need to always be able to come up with a map that will, in all cases, represent this number with a finite amount of information. With uncountable sets, this is simply impossible.... Its not impossible to come up with a map that represents some numbers which are infinitely long with vast information, but its impossible to come up with a map that represents ALL such numbers.

Just tell me what you think is the cardinality of {R, N}, so I know how to proceed in this conversation. One word answer please. Then we can deal with what you wrote here.

17. Originally Posted by someguy1

Just tell me what you think is the cardinality of {R, N}, so I know how to proceed in this conversation. One word answer please. Then we can deal with what you wrote here.
Aleph-

Oh out of words, darn.

Edit: That was intended as light hearted. You are asking me about the cardinality of all possible combinations of real numbers with naturals? I believe its the same as the cardinality of the reals. So Aleph one.

18. I think he was asking about the cardinality of the set containing two members, both sets, which is obviously 2, but is also pretty much irrelevant. (someguy1, that set has a very simple mapping: N->0, R->1. Notice that it has nothing to do with members of the members of that set.)

Edit: If he was asking about the combination of the naturals and the reals, you're right that that would be the same cardinality as the reals. (Divide the number line into unit segments. Each segment can stretch out to cover the reals, while number of the segment covers the naturals.)

19. Originally Posted by TridentBlue
Originally Posted by someguy1

Just tell me what you think is the cardinality of {R, N}, so I know how to proceed in this conversation. One word answer please. Then we can deal with what you wrote here.
Aleph-

Oh out of words, darn.

Edit: That was intended as light hearted. You are asking me about the cardinality of all possible combinations of real numbers with naturals? I believe its the same as the cardinality of the reals. So Aleph one.

Here then is the source of your error. The cardinality of is 2.

To see this, I will show a bijection between the set X and the set {0, 1}, as follows:

<--> 0

<--> 1

Now, I believe you are concerned that I've corresponded the entire set of real numbers to the number 0. If I understand you correctly, you believe that there needs to be some kind of relationship in which 0 encodes the reals or something like that.

But this is not true. A bijection is simply a correspondence, it need not have any coding or information-preserving properties. The 0 doesn't represent the real numbers in any way; it simply matches up to them. It's like bijecting your coffee cups to your saucers. Nobody is saying that if you had a saucer you could figure out how to make a coffee cup. All it means is that there's a cup for every saucer and a saucer for every cup. That is the nature of bijection.

So the cardinality of the set X is 2. Even though one of its elements is itself an uncountable set.

20. Originally Posted by MagiMaster
I think he was asking about the cardinality of the set containing two members, both sets, which is obviously 2, but is also pretty much irrelevant. (someguy1, that set has a very simple mapping: N->0, R->1. Notice that it has nothing to do with members of the members of that set.)
It has everything to do with it. TridentBlue thinks that P(N) is uncountable because some of its elements can't be "enumerated." And as an example of such an element, he gives the set of even numbers, which of course can be very easily enumerated.

See his post #7, which clearly shows his confusion between the cardinality of a set and the cardinalities of that set's elements. In that post, he claims that P(N) is uncountable because one of its elements is the infinite set of even numbers. Surely the misunderstandings there are obvious.

I am slowly and methodically trying to unpack and correct TridentBlue's misunderstandings. The biggest one is as you say his confusion between the cardinality of a set and the cardinalities of its elements.

Once he agrees that the cardinality of {R, N} is 2, then we'll think about {R, R^2, R^3, ...}, a countable set each of whose elements is uncountable.

None of this has anything to do with information theory, interesting as that subject is. I believe TridentBlue thinks that the bijection needs to encode or preserve information, which is why he says that you can't correspond an infinite element to a finite one. This is the heart of his confusion. A bijection is just a correspondence. It need not preserve information.

That's why I used the example of {R, N}. It shows that a 2-element set can nevertheless contain an uncountable set as an element. And that bijections need not preserve information.

21. No, I actually assumed you meant something else, indicating the set of all Tuples where one number is a real, and one is a Natural. The cardinality of that set is aleph one. If you mean the set of two sets, {R, N}, than its obvious that its 2, that's why I assumed you weren't asking me that.

What I'm saying is that if you can't define a bijection from a given set to the natural numbers, then the set is uncountable.

22. Yeah, you understand how I interpreted it. My argument that this set of tuples has the cardinality Aleph One comes from the fact that any Euclidian space, R^n has the same cardinality as the reals, so it can't be bigger than Aleph one, and from the continuum hypothesis, which says it can't be less. Same result as you, different method. All on this page too:
Cardinality of the continuum - Wikipedia, the free encyclopedia

23. Originally Posted by TridentBlue
No, I actually assumed you meant something else, indicating the set of all Tuples where one number is a real, and one is a Natural. The cardinality of that set is aleph one. If you mean the set of two sets, {R, N}, than its obvious that its 2, that's why I assumed you weren't asking me that.

What I'm saying is that if you can't define a bijection from a given set to the natural numbers, then the set is uncountable.

Fine, you agree that the card of {R, N} is 2. And that I can biject it to {0,1} without any problem.

So now explain your post #7 in which you use the fact that P(N) contains as an element the set of even numbers, which is infinite (though perfectly well enumerable). How would that show that P(N) is uncountable? Maybe P(N) consists of countably many infinite sets. How do you know it doesn't? What does the fact that the even numbers are an infinite set have to do with anything?

Suppose P(N) = {the evens, the odds, the multiples of three, the primes, the squares, etc}

How do you know that set is uncountable? Do you see that your proof in #7 is insufficient? You haven't even proved that P(N) is infinite! Maybe it's finite. You haven't proved it isn't. All you've proved is that it has some infinite elements. But each element only counts as 1 when you're counting up the cardinality of P(N).

Originally Posted by TridentBlue
What I'm saying is that if you can't define a bijection from a given set to the natural numbers, then the set is uncountable.
Yes, that is quite correct. That is the actual definition.

But that is totally inconsistent with your post #7, which is the post I'm objecting to and trying to correct. And the reason I'm bothering in the first place is that some OTHER poster started this thread to ask about uncountable sets; and your information in post #7 was anti-helpful.

Oh ... ps ... you used the word "define." Are you playing constructivist games with me? In standard set theory I do not need to define a bijection. I only need to show that a bijection exists. Is that your concern? That the bijection may not be definable? Yes, the constructivists like to make that argument. But if you're going to do that, just say, "I'm going to make a constructivist argument," so that people can understand what you're doing. Is that the intended interpretation of your posts?

24. Hey, first about post #7. My intent was to provide a counter-example to the original poster's idea, which was to enumerate all the sets in that manner. I wanted to show that his method would never enumerate the infinite set of all even numbers, as an example of why it wouldn't work.

Originally Posted by someguy1
Are you playing constructivist games with me?
Holy moly, get out the leather handcuffs and blindfolds, we may have a pure mathematician in the house.

Seriously, what is up with you guys? I've had previous conversations on the net with pure mathematicians, that angrily accuse me of constructivism with the same "You're going to get what you deserve" S&M tone. Why the anger of playing "constructivist games"?

The answer, dear master/mistress, is that my crime, my sin, is actually much worse than mere constructivism. I question mathematical realism, and believe the correct foundations of math may lay in information theory. I believe that we could define a countable set where the first member is the set of all real numbers minus 1, the second is the set of all real numbers minus 2, and so on. But we could do this because when we reference the set of all real numbers, we are not actually referencing the set in its entirety, but actually referencing a blurry probability distribution of what may be. Its easy to point to blurry probability spaces, but the more we shape a space, the more we widdle it down to get to a certain number, the information involved goes up and up. In formal terms, the information it takes to express a number is the log of the reciprocal of its probability in a given encoding. So we can wave our hands and say "all the real numbers between 0 and 1" with very little information expressed, but when it actually comes down to specifying a given non-compressible real number in that interval, it takes an eternity to do so as we spell out digit after digit in it.

the fundamental crime, the fundamental heresy, of my beliefs is that I don't believe the set of real numbers has any kind of self standing independent existance at all. I believe there are numbers on the real line - the vast majority in fact - which will never be expressed in any way, and therefore don't exist. Does that make me a sort of constructionist? My beliefs are different, but they are related in some ways.

Let the whipping of me begin:

25. While I don't really want to get in to the argument in general, I just want to throw in that information theory is really non-intuitive and that one definition of information (Kolmogorov complexity - Wikipedia, the free encyclopedia) is basically defined as how short of a description can you give a thing. The shorter the description, the less information. As "the set of real numbers" is a description of the set of real numbers, that's about as much information as that set contains. While the number K defined by the following actually contains much more information:
- Let a(0) = 3
- Let a(n) = (71 * a(n-1) + 13) % 100
- K is the infinite sum of a(n) / 100^n

(I think the above description is slightly shorter than writing the resulting rational number out as there are about 200 digits between the numerator and the denominator.)

26. Thanks for sharing MagiMaster, your responses are a big part of why I visit this forum, you're really freaking brilliant. That post gives me some new directions of research into my intution. I also hope someguy1 posts back and gives me some more hell: (s)he seems to be a rigorous thinker, while I am more the imaginative type. My experience is the really good work happens where imagination and rigor meet.

27. Originally Posted by MagiMaster
As "the set of real numbers" is a description of the set of real numbers, that's about as much information as that set contains.
Unfortunately, this type of description is prone to the Berry paradox (e.g. "the smallest positive integer not definable in under eleven words").

28. @TridentBlue, Thanks

@KJW, normally Kolmogorov complexity is defined more rigorously in terms of algorithms, in which case, "the set of all real numbers" would probably be defined as a filter that always returned true (depending on the universe of discussion). But then that shades in to Godel's incompleteness theorem in that any system is going to end up with similar paradoxes.

Edit: I just noticed the wiki article already mentioned most of that.

29. Originally Posted by TridentBlue
Thanks for sharing MagiMaster, your responses are a big part of why I visit this forum, you're really freaking brilliant. That post gives me some new directions of research into my intution. I also hope someguy1 posts back and gives me some more hell: (s)he seems to be a rigorous thinker, while I am more the imaginative type. My experience is the really good work happens where imagination and rigor meet.
I'm feeling trolled. You have been knowingly arguing from nonstandard premises, Not necessarily wrong or bad premises -- but definitely nonstandard. It is therefore your responsibility to mention that. Otherwise, well-meaning people might come here and try to correct your misunderstandings; and finding that futile; we would eventually realize that you are playing a different game than we are; and we would then feel badly used.

It's like going to a football forum and a novice comes to the forum and asks how long the field is. And you say, "110 yards." And someone starts disputing you, pointing out that

a) A football field has 100 yards; and

b) Your response is especially annoying because it was designed to confuse the innocent OP, who now has no idea what to believe.

So this goes on for a few hours, then finally someone says, "Aha! You must be talking about Canadian football." And then you "innocently" say, "But of course. Whatever else did you think I meant? And why are you all so mean to me?"

You see the game you've been playing. This is how I experience it. Perhaps that's why you got the other guy angry too. There is a standard modern understanding of the real numbers; and there are legitimate alternative views, especially in our age of computation. If you are arguing from an alternative viewpoint, just state that up front and save everyone a lot of confusion.

That said, here are my answers to some good questions that you asked.

Originally Posted by TridentBlue
the fundamental crime, the fundamental heresy, of my beliefs is that I don't believe the set of real numbers has any kind of self standing independent existance at all.
I think that one of your meta-errors is that you think there's a right and a wrong to this question; and that you are right and that conventional math is wrong, and that you're being attacked for your beliefs. That's cranky. It will get you negative attention on any online forum.

What's true is that if you argue from the standard ZF axioms, you can construct the uncountable set of real numbers. It's true that you can't name them all; but then again, I can't name all my neighbors, but I'm sure that they exist.

And if you modify the axioms so that sets and functions have to be definable (a highly technical term, by the way); then you get a different set of real numbers.

There's no right or wrong. There is no fight to the death. Nobody is attacking you for your views.

I suspect you're being attacked for being trollish about which set-building principles you allow.

By your quoted words, I take it that you feel you're being attacked. But as I mentioned earlier, constructivism is making a comeback these days. It's not your ideas people are attacking; rather, it seems I'm not the first person to get annoyed at your trolling. If you just say, "In Canadian football, the field is 110 yards long," everyone will agree with you, then mention that in American football it's 100 yards. If you just keep insisting the field is 110 yards long, everyone will argue with you and you'll feel attacked.

Originally Posted by TridentBlue
I believe there are numbers on the real line - the vast majority in fact - which will never be expressed in any way, and therefore don't exist. Does that make me a sort of constructionist? My beliefs are different, but they are related in some ways.
It's a compelling argument. I have a collection of things that I cannot possibly name or characterize, but I tell you that they exist and are vital to my enterprise. Surely I have a lot to answer for here.

But if I reject the noncompressible reals, I have some problems.

* My real line is full of holes. In fact it has more holes than points. In fact if I tossed a conceptual dart at the constructive real line, I would hit a hole with probability 1; and a point with probability zero. (Explanation: The computable reals have measure zero. There are only countably many of them.]

* The Intermediate Value Theorem is false. I can have a continuous function that starts below the line, crosses the line and ends up above the line; but never intersects a point of the line. That deeply violates our intuitions about continuity.

* The constructive real line utterly fails to model the ancient intuition of the continuum. It is not Euclid's line. It's is not anybody's line. Between any two points there are mostly holes. The constructive line therefore fails its philosophical mission to model the continuum. It's not even a line in the common meaning of the word.

* What does beautifully model the idea of the continuum? The conventional, standard, uncountable real line. That's a continuum. True, it has a lot of stuff in it that I can't name. Just like the fruitcake I got last Christmas. The unnameable stuff holds the line together, just like some unnameable stuff holds the fruitcake together.

Those are my arguments against rejecting the incompressible numbers. I truly do think of them as my neighbors down the block whose names I don't know, but without whose existence the neighborhood would not be the same.

Perhaps we can think of the noncompressible reals like the grains of sand in the cement that holds together the bricks that make up your house. The individual particles don't need to have names and we don't need to know anything about them as individuals. All we need to know is that without them, our entire house would fall down.

Or perhaps [now I'll do some speculating] they are like the dark matter and dark energy of the universe. We don't even know what they are, but we know they must be there.

Or perhaps [more speculation again] the incompressible reals are trying to tell us something about the limits to computation. There are aspects of the universe that are not computable. This is my preferred philosophical interpretation. You say you can't compute them so they don't exist. I say you can't compute them, so your computational methods are inadequate to fully understand the world.

30. Thanks for your response, someguy1. Its what I was hoping for. Yes, I'm being provocative with you, because in hearing the flaws in my intuitions, I can develop them. But no, its not intended as mean spirited toward you. I just really want to hear the flaws in what they may be. Thanks for sharing. I'm going to print these out and think about them before I response, particularly the problems of holes in the real line.

31. Okay, I printed that out, I had time to go over it, to think about it, and now I have some things to say. Perhaps a good way to start is by saying that I think your closing statement is your most brilliant:

Or perhaps [more speculation again] the incompressible reals are trying to tell us something about the limits to computation. There are aspects of the universe that are not computable. This is my preferred philosophical interpretation. You say you can't compute them so they don't exist. I say you can't compute them, so your computational methods are inadequate to fully understand the world.

But I will come back that. I now find myself apologizing somewhat to you. Yes, I suppose you could say I troll sometimes, but for a good cause: It works. I've been an Internet junky long enough to know that threads where every one nods and agrees die, the threads where there is a conflict go on, and get lengthy responses like the one you gave me, which is exactly what I wanted from you. I cannot deny this is Machiavellian, but if that's what it takes to make smart people speak their minds so be it. I'll troll.

So let my questioning of your ideas begin: The first thing I wanted to zoom in on is your statement that if you threw a dart at the real line, it would hit a hole in the constructivist line with probability one. This is theoretically correct, the constructivist line must be countable. But is it physically correct? Modelling the exact position of a dart is complicated, but at the smallest levels, the laws of quantum mechanics kick in. Living in a quantum universe means that things don't necessarily have absolute positions, but rather exist as a sort of probability blur until we measure them, at which point they collapse into one of a set of discrete states. What that seems to tell me is - if you will forgive the language - God herself doesn't know the position of a particle with absolute precision, doesn't bother to express all these "holes" in actuality as a particle moves from point 0 to point 1.

That gets to the deepest question I have: Is the entire concept of the continuum divorced from physical reality? I'm not a guru physicist or anything, but I've read enough to come to the conclusion that it might be, that many of the numbers in the continuum never manifest in our universe in any observable way.

In more direct math terms, what I'm saying can be illustrated pretty well through a thought experiment, an uncompressible number we'll call TridentBlue's constant. What is it you ask? I can tell you its between 0 and 1, but beyond that, I can only tell you if its lesser to or greater than a number in that interval you give me. On you giving me a number between 0 or 1, I will flip a coin to tell you if its greater or lesser than than your guess, based on the coin flip. You can then ask again based on the new interval defined, and I will flip a coin again, and tell you and so on. TridentBlue's constant is the number that would emerge after you and I started playing that game right -NOW - till eternity. Oops, you didn't give me a number, and I didn't flip a coin. Your brain state has changed, my blood sugar is lower and flipping muscles slighty weaker, so TridentBlue's constant is lost to the ages, we will never know it.

So is TridentBlue's constant really a number? Surely, if we had started playing that game at that moment, SOME number would have started to be enumerated, even though its physically impossible to play till the end of time, (unless we migrate to the realm of the gods where we are both immortal) we theoretically could have, and some number would have emerged, right? The axioms of the continuum show that between any two numbers on the real line an infinite more must exist.

My contention is that its basically absurd to think TridentBlue's constant is a number, even though realism basically allows it to be. It exists for us mortals, and always will, basically as a probability distribution between 0 and 1, period, though in the realm of the Gods, which realism allows, it could be a real number, just one that we will never know.

This is unacceptable to me. In the words of an eastern mystic, my greatest knowledge is the knowledge of my own ignorance. So it must be with us: To move forward, we must be able to explicitly acknowledge the things which we cannot know as something forever alien to our reality, and move forward nonetheless. We must cultivate knowledge both of what we know, and of what we cannot.

All this said, constructivism, at least as it has been presented in the past, has major flaws. That pure mathematician's warnings to me proved correct: I couldn't prove even basic things with purely constructionist axioms. However if we stand back from the specific details of past constructionists, and take in the bigger idea, I think its on the right track. I think mathematical truth is a human creation, I think it is constantly in the process of being created - not discovered - created. An information entity being created.

But why have the realists prevailed where the constructionists have failed? I think realists allow for the POSSIBILITY of new things where past constructivist attempts would like to know it all right now, and that traps them: I have no idea what future technologies will exist, its totally possible that a set of numbers which are now viewed as totally random and uncompressible, for instance will, with some new type of computability, be as familiar to the people living in distant future times as the natural numbers are to us now. The real number line doesn't exclude this possibility, and therein lies its power. However, in the language of your metaphor, it must also be acknowledge that it includes neighbors that you will NEVER meet, nor will any human, or alien, in the lifespan of the universe. And therefore from the viewpoint of all sentient beings in the lifespan of the universe, these neighbors really don't exist.

That's why I quote your closing paragraph in the beginning of this post, because I think its a perfect expression of the power of realism, it allows the future possibilities that are blocked by the current close minded forms of constuctionism. This, I believe is why it has been dominant to this point.

However at some point, when we consider the vast amount of possibilities that will never be realized, this ocean of possibilities we live in out of which a very few are manifested, we have to see that we are in fact playing a constructive role in realizing any piece of information as true, whether mathematical or otherwise. We are in fact changing the universe with what we choose to know, as we are also in and part of the universe. This to me calls for a new kind of constructivism - not one which denies the possibilities of the future (as past forms have) but one which allows for them, while acknowledging that not ALL of them can happen, the fact that the realm of the gods, of the realists, does not in fact exist. One which takes formally into account not just what we know, but the limits on what we can know, and our current level of uncertainty.

Thanks again for responding. Sorry for a lack of anything formal in this, but your post got me fired up and thinking in the philosophical realm.

32. Oh, and one more quick thought about realism. Have you heard of Russell's paradox? It is the statement:

The set of all sets which do not contain themselves contains itself.

If you assume this statement is true, its logically inconsistent. If you assume it is false, its logically inconsisent. Thus its a paradox. Paradox isn't the problem with realism though, it is the shy, deadly secretive twin of paradox, I call anti-paradox. Where for a paradoxical statement assuming either truth value results in logically inconsistent statement, for an anti-paradox, assuming either truth value results in a logically consistent statement. For instance, the statement:

The set of all sets which contains themselves contains itself

Is an anti-paradox. Its logically consistent if you assume its true, its logically consistent if you assume its false. All it asks of us is that we decide, that we insert one axiomatic assumption like a coin in a vending machine, and out pops a logically consistent mathematical reality. The reality is that a mathematician could encounter anti-paradoxes all day long, and still assume he or she was discovering the mathematical reality, when the fact is their own axiomatic choices are playing a critical role in creating, or constructing, that said reality.

That to me gets at the deepest problem in realism. The idea that we are discovering some higher truth ignores the fundamental, profound and obvious role our own choice of axioms play in the truth we are exploring. Yes once the axioms have been declared higher truth exists, but there are situations all through math - like with euclidian and non-euclidian geometry - where a choice of axioms can create different, but logically consistent realities.

PEace!

33. Originally Posted by TridentBlue
I have some things to say. Perhaps a good way to start is by saying that I think your closing statement is your most brilliant:

Or perhaps [more speculation again] the incompressible reals are trying to tell us something about the limits to computation. There are aspects of the universe that are not computable. This is my preferred philosophical interpretation. You say you can't compute them so they don't exist. I say you can't compute them, so your computational methods are inadequate to fully understand the world.

Thank you for calling that out. It's a reaction to the recent ideas floating around that "the universe is mathematics" or that we'll all soon upload ourselves to our PCs or that everything is a computation. We live in the age of computation, so it's understandable that these ideas would gain currency. But I believe that the world is more complicated that that. There are things we can't compute. Of course Tegmark and Kurzweil etc. are very smart guys. But still ... they're wrong

Originally Posted by TridentBlue
I cannot deny this is Machiavellian, but if that's what it takes to make smart people speak their minds so be it. I'll troll.

Originally Posted by TridentBlue
if you threw a dart at the real line, it would hit a hole in the constructivist line with probability one. This is theoretically correct, the constructivist line must be countable. But is it physically correct?

Ah, well, we're talking math and not physics. The OP (long gone from this thread, having not been helped at all) asked about uncountable sets. As far as we know, not only does the universe have no uncountable sets; it has no infinite sets! There are 10^87 atoms in the universe. And (I looked this up a while back, and it's good for idle conversation among one's geeky friends) there are, give or take a couple of orders of magnitude, about a googol quarks in the universe. That's 10^100. Not a very large number in the mathematical scheme of things.

We must distinguish between mathematical ideas and physical ones. Are you saying that perhaps you accept uncountable sets in math but just not in the physical world? You'd get no argument from me. But there aren't any infinite sets either. There is no constructive real line in the physical world because there aren't enough elementary objects out of which it could be made.

So if we're purely in the realm of math, then why not accept uncountable sets based on the fact that they're logically implied by the axioms of standard (ZF) set theory? It's no argument against uncountable sets to say that they don't exist in the real world. Of course they don't. Neither do infinite sets. Let's not get ourselves confused here any more than we already are.

Originally Posted by TridentBlue
Modelling the exact position of a dart is complicated, but at the smallest levels, the laws of quantum mechanics kick in

Again: Let's not confuse math with physics. It's still the case that the chance of hitting an element of a countable set of points on the (standard) real line is zero. That's a mathematical fact. In the real world there are no 1-dimensional lines at all, since there are only finitely many quarks in the universe.

Originally Posted by TridentBlue
That gets to the deepest question I have: Is the entire concept of the continuum divorced from physical reality?

It's divorced from our best theories of physical reality. As far as reality itself ... who can say. We're barely out of caves, we know nothing.

Originally Posted by TridentBlue
I'm not a guru physicist or anything, but I've read enough to come to the conclusion that it might be, that many of the numbers in the continuum never manifest in our universe in any observable way.

Nor infinite sets, even countable ones. So even throwing out all the incompressible reals won't help you to model reality. Even if all you have is algorithms, some algorithms are too long to ever be written down, even though they're finite. In the real world, there's a number, call it N, that has the property that no number beyond N has any correspondence to the real world. In the philosophy of math, that would be called ultrafinitism: the doctrine that not only don't infinite sets exist; but in fact that extremely large finite sets don't exist.

Ultrafinitism - Wikipedia, the free encyclopedia

Originally Posted by TridentBlue
In more direct math terms, what I'm saying can be illustrated pretty well through a thought experiment, an uncompressible number we'll call TridentBlue's constant. ...

I'm not sure I followed your point in detail. But if you are saying that you can't name or individually characterize the incompressible numbers, I already said that I regard that in the same way that I don't know the names of all my neighbors. To amplify this point, I don't know the names or individual characteristics of all the people in China (I'm in the US). But I'm certain they exist and that they're important.

If we're talking math, the uncountable set of reals is a logical consequence of the axioms, which themselves may well be a complete fiction. (They probably are). If we're talking physics, all you've got is a googol quarks.

So you can't name or identify the uncompressible bitstrings. So what? Their existence logically follows from the axioms. Change the axioms and they'd go away, but your real line then has holes in it; and it's still not a good model for reality because you haven't got enough quarks.

Originally Posted by TridentBlue
My contention is that its basically absurd to think TridentBlue's constant is a number ...

Every real number occupies a specific place on the number line. You're unhappy because you haven't got enough algorithms. But as I said, that's a problem with the idea that you can describe everything with algorithms. Clearly you can't. You can not name each of the real numbers with an algorithm. That shows that there's more to math than algorithms. It doesn't prove that "the real numbers don't exist," or whatever. Of course the real numbers don't exist. They're a mathematical abstraction that logically follows from some axioms. Why is this bothering you so much?

Originally Posted by TridentBlue
This is unacceptable to me. In the words of an eastern mystic, my greatest knowledge is the knowledge of my own ignorance. So it must be with us: To move forward, we must be able to explicitly acknowledge the things which we cannot know as something forever alien to our reality, and move forward nonetheless. We must cultivate knowledge both of what we know, and of what we cannot.

I am not personally acquainted with every single person in China. But I'd never say they are "forever alien to my reality." On the contrary, they're very important to me and to the world. You seem to be a bit of a solipcist. You think that whatever you don't personally know, doesn't exist.

Originally Posted by TridentBlue
All this said, constructivism, at least as it has been presented in the past, has major flaws. That pure mathematician's warnings to me proved correct: I couldn't prove even basic things with purely constructionist axioms. However if we stand back from the specific details of past constructionists, and take in the bigger idea, I think its on the right track. I think mathematical truth is a human creation, I think it is constantly in the process of being created - not discovered - created. An information entity being created.

You're losing me here. This seems way off-topic to our discussion. Written mathematics is a historically contingent human artifact. What of it?

Originally Posted by TridentBlue
But why have the realists prevailed where the constructionists have failed? <snip>

I'm not up on realism. I'll never meet all those people in China. But they're essential to the ecology of the planet and the economy of the world. The incompressible reals fill out the continuum, which is an ancient intuition of the human mind, regardless of its status as a physical entity. Justice, truth, compassion, and love are also ancient abstract ideals of the human mind, which exist in the world and are of vital importance, despite not being describable by algorithms. Abstraction is one of the most important human characteristics. Our entire civilization is based on mental abstraction. You stop at a red light. Why? It's a societal agreement, backed by the force of law, which itself is yet another abstraction.

Originally Posted by TridentBlue
That's why I quote your closing paragraph in the beginning of this post, because I think its a perfect expression of the power of realism, it allows the future possibilities that are blocked by the current close minded forms of constuctionism. This, I believe is why it has been dominant to this point.

Constructivism's making a comeback lately, due to (among other things) interest in automated proof systems and alternate foundations of math.

(continued next post ...)

34. Originally Posted by TridentBlue
Oh, and one more quick thought about realism. Have you heard of Russell's paradox?

Yes of course. But you're about to read much more into it than you should.

Originally Posted by TridentBlue
It is the statement:

The set of all sets which do not contain themselves contains itself.

If you assume this statement is true, its logically inconsistent. If you assume it is false, its logically inconsisent. Thus its a paradox. Paradox isn't the problem with realism though, it is the shy, deadly secretive twin of paradox, I call anti-paradox. Where for a paradoxical statement assuming either truth value results in logically inconsistent statement, for an anti-paradox, assuming either truth value results in a logically consistent statement. For instance, the statement:

The set of all sets which contains themselves contains itself

Is an anti-paradox. Its logically consistent if you assume its true, its logically consistent if you assume its false. All it asks of us is that we decide, that we insert one axiomatic assumption like a coin in a vending machine, and out pops a logically consistent mathematical reality. The reality is that a mathematician could encounter anti-paradoxes all day long, and still assume he or she was discovering the mathematical reality, when the fact is their own axiomatic choices are playing a critical role in creating, or constructing, that said reality.

All Russell's paradox did was show early set theorists that you cannot allow unrestricted set formation based on predicates. If P is a predicate, you can NOT form the set of all x such that P(x). That leads to paradoxes.

The solution is that the elements x must already be known to be members of some other set. So I can always form the set of all x, elements of S, such that P(x). It's just a technical thing, it's not really all that profound. It just shows that you can't associate sets with arbitrary predicates. Perhaps that is profound, but it was profound in 1900. It's well understood today.

So for example, let X be the set of all natural numbers x that are not members of themselves. Is X an element of X? No, because X is not a natural number. Done and done. No paradox, no problem.

Originally Posted by TridentBlue
However at some point, when we consider the vast amount of possibilities that will never be realized, this ocean of possibilities we live in out of which a very few are manifested, we have to see that we are in fact playing a constructive role in realizing any piece of information as true, whether mathematical or otherwise. We are in fact changing the universe with what we choose to know, as we are also in and part of the universe. This to me calls for a new kind of constructivism - not one which denies the possibilities of the future (as past forms have) but one which allows for them, while acknowledging that not ALL of them can happen, the fact that the realm of the gods, of the realists, does not in fact exist. One which takes formally into account not just what we know, but the limits on what we can know, and our current level of uncertainty.

Lost me here.

Originally Posted by TridentBlue
Thanks again for responding. Sorry for a lack of anything formal in this, but your post got me fired up and thinking in the philosophical realm.

I really didn't say anything other than to try to explicate the standard mathematical view of uncountable sets. I make no pretensions to know whether God knows where the particles are, or what the future of mathematical philosophy will be.

I believe you are looking for a theory that encompasses math, physics, and metaphysics. I think that's a tall order. We don't have any such theory nor is it certain (to me) that one even exists. Maybe the core of reality is an essential mystery that our rational minds can never know. That's something I believe. I oppose the computationalists. I've been thinking about this for a while. I'd write an article but I'm too lazy to actually read Tegmark and Kurzweil. I'm probably afraid that if I did, I'd be converted.

Originally Posted by TridentBlue
That to me gets at the deepest problem in realism.

I've heard of mathematical realism, but I don't know anything about it. So I'm not in a position to understand your remarks about it. But I don't really care about it one way or the other. Uncountable sets are interesting, whether they're "real" or not. I like the idea of fictionalism, which says that math is an entertaining story that may be useful and interesting, but is not necessarily true.

Fictionalism is the view in philosophy according to which statements that appear to be descriptions of the world should not be construed as such, but should instead be understood as cases of "make believe", of pretending to treat something as literally true (a "useful fiction").

http://en.wikipedia.org/wiki/Fictionalism

After all, the physicists use uncountable sets and infinitary mathematical arguments all the time, in order to derive truths about the real world, which contains no infinite sets. So math is just a useful story, in the same way that the story of Little Red Riding Hood reminds us not to trust strangers we meet in the woods.

Originally Posted by TridentBlue
The idea that we are discovering some higher truth ignores the fundamental, profound and obvious role our own choice of axioms play in the truth we are exploring. Yes once the axioms have been declared higher truth exists, but there are situations all through math - like with euclidian and non-euclidian geometry - where a choice of axioms can create different, but logically consistent realities.
I completely agree. I never ever claimed that math is true. I only pointed out that the standard real line follows from the axioms; and that it satisfies our deepest intuitions about continuity and the continuum. I have no idea what's "true" or even if that question is meaningful.

Originally Posted by TridentBlue
PEace!

Likewise!

35. There is a general proof that the cardinality of set's power set is greater than the cardinality of the original set. That is,
card(P(S)) > card(S)

Let is suppose that they are equal. That means that for every a in S, there is an A in P(S), and vice versa. Consider set N which is all the a's whose corresponding A's do not contain them. It must be in P(S), and it corresponds to an element of S, n.

Is n in N?
If so, then n must correspond to a set that does not contain it, and thus, n is not in N.
If not, then n must be an a whose corresponding A does not contain it, and thus, n is in N.

That is a contradiction, and we conclude that card(P(S)) != card(S)

But since every a matches onto {a} and vice versa, then card(P(S)) >= card(S)

Thus, card(P(S)) > card(S)

For finite sets, card(P(S)) = 2card(S) and one can also prove that inequality with that.

For countable-infinite sets, card(P(S)) > aleph-0, making P(S) uncountably infinite.

 Bookmarks
##### Bookmarks
 Posting Permissions
 You may not post new threads You may not post replies You may not post attachments You may not edit your posts   BB code is On Smilies are On [IMG] code is On [VIDEO] code is On HTML code is Off Trackbacks are Off Pingbacks are Off Refbacks are On Terms of Use Agreement