Cardinality of uncomputable numbers
Moderators: gmalivuk, Moderators General, Prelates

 Posts: 548
 Joined: Tue Jan 12, 2010 1:04 am UTC
 Contact:
Cardinality of uncomputable numbers
Recently, I was reflecting a bit on the paradoxical idea of uncomputable numbers, and I happened to think about how many their were. I found an answer, and I would a appreciate it if someone told me I was correct.
First, we know there are at least Aleph1 different uncomputable numbers, for if we take any one uncomputable number, then we can add any real number and get a new uncomputable number.
Now, I'm thinking we can sort of view the uncomputables as other "units"  linearly independent units which cannot be reduced, like 1 and i. For example, the number pi*1+sqrt(2)*Chaitin'sconstant can't be simplified out into just units of "1", because this would be computable then.
Since each uncomputable number can be built up of 1, i, Chaitin's contant, etc., it should have the same cardinality as R^n, where n is the number of independent units. Since n is the number of uncomputables, the cardinality of uncomputables (C_u?) is equal to Aleph1 (the R here) to the power of the cardinality of the uncomputables. In other words, C_u=Aleph1^C_u. Now, the set of solutions to this, as far as I can tell, are the epsilon numbers. So the smallest possible number of uncomputables would be epsilon nought.

Hmm, in writing this out I've found one flaw  you can't claim the a number necessarily has an infinite number of uncountable "components" just because there are an infinite number of uncomputables; all uncomputables might be just combinations of 2 different uncomputables and 1, or something. But the argument about R^n should still be valid, except you've go to take into account that there could be only, say, Aleph0 independent uncomputables, and still Aleph1 uncomputables overall. Given the total number of uncomputables is C_u, I suppose the minimum number of independent uncomputables would be log_2(C_u)... which really makes the equation turn into C_u=Aleph1^(log_2(C_u))  pretty much useless.
Any help answering this, and showing it, would be greatly appreciated. Thank you!
First, we know there are at least Aleph1 different uncomputable numbers, for if we take any one uncomputable number, then we can add any real number and get a new uncomputable number.
Now, I'm thinking we can sort of view the uncomputables as other "units"  linearly independent units which cannot be reduced, like 1 and i. For example, the number pi*1+sqrt(2)*Chaitin'sconstant can't be simplified out into just units of "1", because this would be computable then.
Since each uncomputable number can be built up of 1, i, Chaitin's contant, etc., it should have the same cardinality as R^n, where n is the number of independent units. Since n is the number of uncomputables, the cardinality of uncomputables (C_u?) is equal to Aleph1 (the R here) to the power of the cardinality of the uncomputables. In other words, C_u=Aleph1^C_u. Now, the set of solutions to this, as far as I can tell, are the epsilon numbers. So the smallest possible number of uncomputables would be epsilon nought.

Hmm, in writing this out I've found one flaw  you can't claim the a number necessarily has an infinite number of uncountable "components" just because there are an infinite number of uncomputables; all uncomputables might be just combinations of 2 different uncomputables and 1, or something. But the argument about R^n should still be valid, except you've go to take into account that there could be only, say, Aleph0 independent uncomputables, and still Aleph1 uncomputables overall. Given the total number of uncomputables is C_u, I suppose the minimum number of independent uncomputables would be log_2(C_u)... which really makes the equation turn into C_u=Aleph1^(log_2(C_u))  pretty much useless.
Any help answering this, and showing it, would be greatly appreciated. Thank you!
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me  __ 
Good fucking job Will Yu, you found me  __ 
Re: Cardinality of uncomputable numbers
squareroot wrote:First, we know there are at least Aleph1 different uncomputable numbers, for if we take any one uncomputable number, then we can add any real number and get a new uncomputable number.
The cardinality of the reals is [imath]2^{\aleph_0}[/imath]. Whether this is equal to [imath]\aleph_1[/imath] or not depends on whether you accept the Continuum hypothesis.
What you have shown here is that the set of uncomputable (real) numbers has a cardinality of at least [imath]2^{\aleph_0}[/imath].
Since the set of uncomputable numbers is a subset of the reals, its cardinality is also at most [imath]2^{\aleph_0}[/imath].
Therefore its cardinality is equal to [imath]2^{\aleph_0}[/imath].
ETA:
Actually, I'm now not convinced of the quoted statement. If you add an uncomputable number to a computable number, then you definitely get an uncomputable one. But adding two uncomputable numbers may result in a computable one (e.g. if r is uncomputable, then so is 1r, but their sum is computable).
So, it does follow that the cardinality of the set of uncomputable numbers is at greater or equal to the cardinality of the computable numbers, but that does not yet prove that it attains the upper bound of [imath]2^{\aleph_0}[/imath]. To do that, you can instead show that the set of computable numbers is countable, and therefore the set uncomputable numbers must have cardinality of at least [imath]2^{\aleph_0}  \aleph_0 = 2^{\aleph_0}[/imath].
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Cardinality of uncomputable numbers
There are only countably many computer programs, since each may be coded as a number (that's the way they are stored on your hard drive, as a very large number in binary). Therefore, there are only countably many computable numbers, and continuummany uncomputable numbers.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson

 Posts: 548
 Joined: Tue Jan 12, 2010 1:04 am UTC
 Contact:
Re: Cardinality of uncomputable numbers
Thanks! Those arguments make a lot of sense.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me  __ 
Good fucking job Will Yu, you found me  __ 
Re: Cardinality of uncomputable numbers
squareroot wrote:if we take any one uncomputable number, then we can add any real number and get a new uncomputable number.
Uncomputable numbers are also real numbers. In particular, the negative of an uncomputable number is another uncomputable (and real) number.
squareroot wrote:linearly independent units which cannot be reduced, like 1 and i. For example, the number pi*1+sqrt(2)*Chaitin'sconstant can't be simplified out into just units of "1", because this would be computable then.
I don't understand what you're trying to say. If you're trying to say that the uncomputable numbers are linearly independent (say over Q), then this is false; twice an uncomputable number is also an uncomputable number.
It sounds like you should read some textbooks on set theory and countability. Your basic concepts are a little jumbled up.
Re: Cardinality of uncomputable numbers
Is "Uncomputable Numbers" a specific enough statement? "Uncomputable reals" surely is, but there are numbers which are not reals are there not? And surely not all of them are computable.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

 Posts: 548
 Joined: Tue Jan 12, 2010 1:04 am UTC
 Contact:
Re: Cardinality of uncomputable numbers
I'm sorry, I guess I didn't word it very clearly (and some where just mistakes). I'm aware that all uncomputable numbers are real  when I said "add a real number", I really meant "add an uncomputable number".
I shouldn't have said that uncomputable numbers are linearly independent over Q. What I meant was  I think  that you can find an infinite number of uncountable numbers that are... computably independent? That is, we could define some set of "base uncomputables", which could then be combined to form and uncomputable number we like. And I'm pretty sure this set would be infinite. I guess that, because (as other people explained, tyvm) the set all uncomputables have a cardinality of 2^Aleph0, the cardinality of this set of "base uncomputables" would have to be <= Aleph0.
I'm sorry if I'm completely botching most of this. I learned most of it from one short math lesson to some other junior high students, and from wikipedia. @jaap: Is it common not to accept the Continuum hypothesis? I thought it was pretty well accepted. @WarDaft: Sorry, yes, I meant reals.
I shouldn't have said that uncomputable numbers are linearly independent over Q. What I meant was  I think  that you can find an infinite number of uncountable numbers that are... computably independent? That is, we could define some set of "base uncomputables", which could then be combined to form and uncomputable number we like. And I'm pretty sure this set would be infinite. I guess that, because (as other people explained, tyvm) the set all uncomputables have a cardinality of 2^Aleph0, the cardinality of this set of "base uncomputables" would have to be <= Aleph0.
I'm sorry if I'm completely botching most of this. I learned most of it from one short math lesson to some other junior high students, and from wikipedia. @jaap: Is it common not to accept the Continuum hypothesis? I thought it was pretty well accepted. @WarDaft: Sorry, yes, I meant reals.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me  __ 
Good fucking job Will Yu, you found me  __ 
 NathanielJ
 Posts: 882
 Joined: Sun Jan 13, 2008 9:04 pm UTC
Re: Cardinality of uncomputable numbers
squareroot wrote:I'm aware that all uncomputable numbers are real  when I said "add a real number", I really meant "add an uncomputable number".
The statement still isn't true though for the same reason as has been pointed out. If c is uncomputable, so is c. Add them together and you get something computable.
squareroot wrote:I guess that, because (as other people explained, tyvm) the set all uncomputables have a cardinality of 2^Aleph0, the cardinality of this set of "base uncomputables" would have to be <= Aleph0.
Actually, if I'm understanding you correctly, you can not get a "basis" of the uncomputables that have cardinality less than that of the uncomputables themselves. The reason for this is that if you choose an arbitrary uncomputable number and apply various computable operations to it (e.g. multiplying/dividing/adding/subtracting by a computable number, squarerooting, etc etc), you only get a countable set of possible answers. Thus, any countable "basis" can only lead to a countable set of possible answers as well, which is strictly smaller than the set of uncomputable numbers.
Re: Cardinality of uncomputable numbers
squareroot wrote:That is, we could define some set of "base uncomputables", which could then be combined to form and uncomputable number we like. And I'm pretty sure this set would be infinite.
I don't see any reasonable way to do this so that the "base" numbers are "independent" in any reasonable sense.
squareroot wrote:Is it common not to accept the Continuum hypothesis?
The continuum hypothesis isn't a strong enough statement that people outside of set theory and logic really care about it one way or the other; you can't prove any particularly strong theorems with it, for example. My impression is that people avoid it as an assumption if they can.

 Posts: 548
 Joined: Tue Jan 12, 2010 1:04 am UTC
 Contact:
Re: Cardinality of uncomputable numbers
Yes, I see that now. I meant that, when I wrote that first post, that's what I meant.NathanielJ wrote:squareroot wrote:I'm aware that all uncomputable numbers are real  when I said "add a real number", I really meant "add an uncomputable number".
The statement still isn't true though for the same reason as has been pointed out. If c is uncomputable, so is c. Add them together and you get something computable.
[/quote]NatnahielJ wrote:squareroot wrote:I guess that, because (as other people explained, tyvm) the set all uncomputables have a cardinality of 2^Aleph0, the cardinality of this set of "base uncomputables" would have to be <= Aleph0.
Actually, if I'm understanding you correctly, you can not get a "basis" of the uncomputables that have cardinality less than that of the uncomputables themselves. The reason for this is that if you choose an arbitrary uncomputable number and apply various computable operations to it (e.g. multiplying/dividing/adding/subtracting by a computable number, squarerooting, etc etc), you only get a countable set of possible answers. Thus, any countable "basis" can only lead to a countable set of possible answers as well, which is strictly smaller than the set of uncomputable numbers.
I never said that the cardinality of these base numbers would be less than that of the whole uncomputables. It would still be a subset, though.
After a bit more thought ofnthis, I think the basis of the uncomputables could still have an countable cardinality. Even if one element can only produces a countable number of new computables, an infinite (countable) set of uncomputables could still produce an uncountable set of uncomputables.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me  __ 
Good fucking job Will Yu, you found me  __ 
Re: Cardinality of uncomputable numbers
No it cannot. Let [imath]a_0, a_1, \dots[/imath] be a countable set of uncomputables, and suppose you have an oracle that allows you to get any one of those things in constant time. Then the set of numbers that you can compute with programs of at most length n and uses the only the first n [imath]a_i[/imath]'s is still finite. Therefore, you get a countable union of finite sets, which is countably infinite. At least, this holds if you do not allow operations that uses all the uncountable at once. If you do, you will have to define what a "legal" operation would be.squareroot wrote:I think the basis of the uncomputables could still have an countable cardinality. Even if one element can only produces a countable number of new computables, an infinite (countable) set of uncomputables could still produce an uncountable set of uncomputables.
Re: Cardinality of uncomputable numbers
squareroot wrote:I never said that the cardinality of these base numbers would be less than that of the whole uncomputables. It would still be a subset, though.
After a bit more thought ofnthis, I think the basis of the uncomputables could still have an countable cardinality. Even if one element can only produces a countable number of new computables, an infinite (countable) set of uncomputables could still produce an uncountable set of uncomputables.
Only if you don't use countable choice.
 gmalivuk
 GNU Terry Pratchett
 Posts: 26836
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Cardinality of uncomputable numbers
Nope, because a countable set of countable sets is still countable.squareroot wrote:Even if one element can only produces a countable number of new computables, an infinite (countable) set of uncomputables could still produce an uncountable set of uncomputables.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Cardinality of uncomputable numbers
t0rajir0u wrote:squareroot wrote:Is it common not to accept the Continuum hypothesis?
The continuum hypothesis isn't a strong enough statement that people outside of set theory and logic really care about it one way or the other; you can't prove any particularly strong theorems with it, for example. My impression is that people avoid it as an assumption if they can.
Is that true? There's a cool counterexample to the conclusion of Fubini's theorem (due to Sierpinski) which relies on the continuum hypothesis. The theorem is that under the continuum hypothesis, there is a bounded function on the unit square whose iterated integrals exist and are different. I'm not sure if the statement (which is a statement in analysis, not set theory) is true without assuming the continuum hypothesis.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Cardinality of uncomputable numbers
I tend to think its true, at the very least in the weak sense.
There's a thing called "the realvalued measurable cardinal assumption" where you're guaranteed that any order of iterated integral is ok.
skeptical scientist wrote:t0rajir0u wrote:squareroot wrote:Is it common not to accept the Continuum hypothesis?
The continuum hypothesis isn't a strong enough statement that people outside of set theory and logic really care about it one way or the other; you can't prove any particularly strong theorems with it, for example. My impression is that people avoid it as an assumption if they can.
Is that true? There's a cool counterexample to the conclusion of Fubini's theorem (due to Sierpinski) which relies on the continuum hypothesis. The theorem is that under the continuum hypothesis, there is a bounded function on the unit square whose iterated integrals exist and are different. I'm not sure if the statement (which is a statement in analysis, not set theory) is true without assuming the continuum hypothesis.
There's a thing called "the realvalued measurable cardinal assumption" where you're guaranteed that any order of iterated integral is ok.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 imatrendytotebag
 Posts: 152
 Joined: Thu Nov 29, 2007 1:16 am UTC
Re: Cardinality of uncomputable numbers
Since computable numbers are a subfield of the real numbers, you COULD have a basis for the reals over computables which would consist of 1 and uncomputable numbers. This seems like it pretty much satisfies what squareroot is looking for. However, as has been pointed out, the use of said basis to calculate the cardinality doesn't really go through.
Hey baby, I'm proving love at nth sight by induction and you're my base case.
Re: Cardinality of uncomputable numbers
Hasn't skeptical scientist already answered this question? A computer program must be made up of 1s and 0s and have a finite length*, so it's a natural number, so the set of all such programs is a subset of the natural numbers, so it has cardinality Aleph0, and there is an obvious injection from the set of computer programs to the set of computable numbers, so the set of computable numbers is countable.
So the uncomputable numbers are uncountable. That's right, isn't it?
*Just to clarify: if you allow programs of infinite length, every number can be computed simply by writing "print 3; print .; print 1; print 4; print 1; print 5; print 9;" (if you wanted to compute pi, and yes I know pi is computable, but I don't know the decimal expansions of any uncomputable numbers, because they're uncomputable.) So that doesn't work.
So the uncomputable numbers are uncountable. That's right, isn't it?
*Just to clarify: if you allow programs of infinite length, every number can be computed simply by writing "print 3; print .; print 1; print 4; print 1; print 5; print 9;" (if you wanted to compute pi, and yes I know pi is computable, but I don't know the decimal expansions of any uncomputable numbers, because they're uncomputable.) So that doesn't work.
The preceding comment is an automated response.
Re: Cardinality of uncomputable numbers
snowyowl wrote:and there is an obvious injection from the set of computer programs to the set of computable numbers, so the set of computable numbers is countable.
Woah, woah, woah.
There is an obvious injection from the naturals in to the reals (the identity mapping)  the reals are uncountable.
Did you mean surjection?
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Cardinality of uncomputable numbers
Syrin wrote:snowyowl wrote:and there is an obvious injection from the set of computer programs to the set of computable numbers, so the set of computable numbers is countable.
Woah, woah, woah.
There is an obvious injection from the naturals in to the reals (the identity mapping)  the reals are uncountable.
Did you mean surjection?
Also, it's not actually an injection, since there are lots of different computer programs that compute e.g. \(\pi\).
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 Yakk
 Poster with most posts but no title.
 Posts: 11129
 Joined: Sat Jan 27, 2007 7:27 pm UTC
 Location: E pur si muove
Re: Cardinality of uncomputable numbers
A countable number of computer programs that output 4:
for(i = 0 to n);
return 4;
All suitable for many uses.
for(i = 0 to n);
return 4;
All suitable for many uses.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision  BR
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
Re: Cardinality of uncomputable numbers
t0rajir0u wrote: The continuum hypothesis isn't a strong enough statement that people outside of set theory and logic really care about it one way or the other; you can't prove any particularly strong theorems with it, for example.
Wrong. In ZF, CH => Axiom of Choice.
To clarify, Uncomputable numbers have the cardinality of the continuum, computable numbers ( rationals, algebraic, and all computable transcendentals) are countable.
Cmebeh wrote:LOL you computer scientists; isn't it obvious? P = NP is undecidable à la continuum hypothesis
 gmalivuk
 GNU Terry Pratchett
 Posts: 26836
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Cardinality of uncomputable numbers
What? No it certainly doesn't.Cmebeh wrote:Wrong. In ZF, CH => Axiom of Choice.
Re: Cardinality of uncomputable numbers
gmalivuk wrote:What? No it certainly doesn't.Cmebeh wrote:Wrong. In ZF, CH => Axiom of Choice.
LOL i was wrong; ZF + Generalized continuum hypothesis => Axiom of Choice
Cmebeh wrote:LOL you computer scientists; isn't it obvious? P = NP is undecidable à la continuum hypothesis
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Cardinality of uncomputable numbers
That is still getting a big "citation needed".
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Cardinality of uncomputable numbers
Cmebeh wrote:LOL you computer scientists; isn't it obvious? P = NP is undecidable à la continuum hypothesis
 gmalivuk
 GNU Terry Pratchett
 Posts: 26836
 Joined: Wed Feb 28, 2007 6:02 pm UTC
 Location: Here and There
 Contact:
Re: Cardinality of uncomputable numbers
Yeah, but since we already generally accept the AoC, I'd say even the generalized CH isn't all that strong as an additional axiom.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Cardinality of uncomputable numbers
@Cmebeh: You learn something new every day...
Nonetheless, there are a few things that are implied by, or equivalent to, CH that we might choose to care about, though they are definitely obscure. For instance,
though to care about this we would pretty much have to care about he hyperreals, and that's a pretty rare thing.
Another interesting equivalent condition is given in the second comment here
http://consc.net/notes/continuum.html
My intuition tells me that AX is false, so this confirms my thoughts on CH, but perhaps your intuition tells you otherwise.
Nonetheless, there are a few things that are implied by, or equivalent to, CH that we might choose to care about, though they are definitely obscure. For instance,
http://en.wikipedia.org/wiki/Hyperreal_number wrote:One question we might ask is whether, if we had chosen a different free ultrafilter V, the quotient field A/U would be isomorphic as an ordered field to A/V. This question turns out to be equivalent to the continuum hypothesis; in ZFC with the continuum hypothesis we can prove this field is unique up to order isomorphism, and in ZFC with the continuum hypothesis false we can prove that there are nonorderisomorphic pairs of fields which are both countably indexed ultrapowers of the reals.
though to care about this we would pretty much have to care about he hyperreals, and that's a pretty rare thing.
Another interesting equivalent condition is given in the second comment here
http://consc.net/notes/continuum.html
My intuition tells me that AX is false, so this confirms my thoughts on CH, but perhaps your intuition tells you otherwise.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Cardinality of uncomputable numbers
Interestingly, there are several results that are more interesting if you don't believe the continuum hypothesis: there are many results of the form "X is either countable or has cardinality \(2^{\aleph_0}\)" where X is some set which satisfies a definability or other niceness condition. I'm most familiar with this happening in descriptive set theory, but I can think of examples in other branches of logic, and I would be surprised if there aren't also examples in other fields.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: Cardinality of uncomputable numbers
Alright so we know that the CH is independent of ZFC. If I were to adopt another axiom that is weaker than CH (ie you cant add CH or generalized CH), call it X, then can we prove/disprove CH within ZFC + X? How many axioms do we have to append to make CH provable or disprovable? The answer to this question is currently not known, and I believe that no matter how many axioms you append, you'll never be able to prove/disprove CH
Cmebeh wrote:LOL you computer scientists; isn't it obvious? P = NP is undecidable à la continuum hypothesis
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Cardinality of uncomputable numbers
Cmebeh wrote:Alright so we know that the CH is independent of ZFC. If I were to adopt another axiom that is weaker than CH (ie you cant add CH or generalized CH), call it X, then can we prove/disprove CH within ZFC + X? How many axioms do we have to append to make CH provable or disprovable? The answer to this question is currently not known, and I believe that no matter how many axioms you append, you'll never be able to prove/disprove CH
You can trivially add a single new axiom and be able to prove or disprove CH or GCH. Obviously adding CH or GCH works. Slightly less trivially, Sierpinski showed that the following axiom AX (proposed by Freiling) implies the negation of the continuum hypothesis.
$$\text{AX: For all }f: [0,1] \to \{A \mid A \subseteq [0,1] \text{ and }A=\aleph_0\}\text{, there exist }x,y \in [0,1] \text{ such that } x \notin f(y) \text{ and } y \notin f(x).$$
(Proof: We prove the contrapositive. Assume CH, and define a wellordering ≤_{1} of [0,1] of type \(\omega_1\). Let f(x)={y : y≤_{1}x}. Then for each x in [0,1], f(x) is countable, and yet for any x,y in [0,1], either x is in f(y) or y is in f(x) (by trichotomy). So CH implies ¬AX.)
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
 majikthise
 Posts: 155
 Joined: Sun Jun 10, 2007 2:28 am UTC
 Location: Bristol, UK
Re: Cardinality of uncomputable numbers
Another interesting axiom is Martin's Axiom. It's independent of ZFC and can be considered weaker than CH, as it's implied by CH this means adding it to ZFC along with CH adds nothing more than what we already get from adding CH on it's own. What's more interesting though is that it's also consistent with ¬CH, so we can take ZFC + MA + ¬CH and have a consistent theory that does cool new stuff. One of the things it does is prove the existence of Suslin trees, which are crazyweird trees of omega_1 height and omega_1 width but no uncountable branches or antichains. [/offtopic]
edit: oops, wrote the wrong thing! ZFC + MA + ¬CH proves something called the Suslin Hypothesis, which is the same as there being no Suslin trees slightly less cool in my opinion.
edit: oops, wrote the wrong thing! ZFC + MA + ¬CH proves something called the Suslin Hypothesis, which is the same as there being no Suslin trees slightly less cool in my opinion.
Is this a wok that you've shoved down my throat, or are you just pleased to see me?
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Cardinality of uncomputable numbers
I find AX quite fascinating in that it brings out a tension in set theory. Set theorists often want to try to expand the universe of discourse as much as they can. Not CH does that by bringing in more cardinalities, but, contrariwise, not AX does it by allowing for the construction of certain peculiar functions.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Cardinality of uncomputable numbers
Interesting.
Granted I have no formal training in set theory, but how could AX not be true?
Granted I have no formal training in set theory, but how could AX not be true?
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 jestingrabbit
 Factoids are just Datas that haven't grown up yet
 Posts: 5967
 Joined: Tue Nov 28, 2006 9:50 pm UTC
 Location: Sydney
Re: Cardinality of uncomputable numbers
In precisely the way that Skep proved it couldn't be true.
Its perhaps a weird construction, but from my experience if you have to assume that a probability 0 event will occur an uncountable number of times, you're probably in a bad scene.
Its perhaps a weird construction, but from my experience if you have to assume that a probability 0 event will occur an uncountable number of times, you're probably in a bad scene.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Re: Cardinality of uncomputable numbers
I mean, wouldn't it require that you have an uncountable set of countable sets such that every real number in the interval is only not present in countably many countable sets?
Or should I say continuummany rather than uncountable? I suppose uncountable isn't really specific enough in this situation.
Or should I say continuummany rather than uncountable? I suppose uncountable isn't really specific enough in this situation.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Cardinality of uncomputable numbers
WarDaft wrote:I mean, wouldn't it require that you have an uncountable set of countable sets such that every real number in the interval is only not present in countably many countable sets?
Yes, yes it would. However, this is consistent with ZFC, and implied by CH, as shown.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Re: Cardinality of uncomputable numbers
WarDaft wrote:Interesting.
Granted I have no formal training in set theory, but how could AX not be true?
It lead to pathological results like sets of reals that are not lebesgue measurable, which gives us more pathological results like being able to cut up a grape and put it back together so that it is the size of the sun.
Cmebeh wrote:LOL you computer scientists; isn't it obvious? P = NP is undecidable à la continuum hypothesis
Re: Cardinality of uncomputable numbers
Okay, I see now that's actually exactly what your proof was doing. I have to stop posting when tired.
If we supposed CH to be absolutely true, we couldn't ever actually describe such an ordering, only define it, right?
If we supposed CH to be absolutely true, we couldn't ever actually describe such an ordering, only define it, right?
I thought that was the BanachTarski paradox and that it depended on AC.It lead to pathological results like sets of reals that are not lebesgue measurable, which gives us more pathological results like being able to cut up a grape and put it back together so that it is the size of the sun.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
Re: Cardinality of uncomputable numbers
i thought AC and AX were representing the same thing
Cmebeh wrote:LOL you computer scientists; isn't it obvious? P = NP is undecidable à la continuum hypothesis
 skeptical scientist
 closedminded spiritualist
 Posts: 6142
 Joined: Tue Nov 28, 2006 6:09 am UTC
 Location: San Francisco
Re: Cardinality of uncomputable numbers
Cmebeh wrote:i thought AC and AX were representing the same thing
AC is the axiom of choice; AX is the principle I mentioned above.
Last edited by skeptical scientist on Mon May 31, 2010 2:45 am UTC, edited 2 times in total.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.
"With math, all things are possible." —Rebecca Watson
"With math, all things are possible." —Rebecca Watson
Who is online
Users browsing this forum: No registered users and 11 guests