Cardinality of uncomputable numbers

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Cardinality of uncomputable numbers

Postby squareroot » Sat May 22, 2010 5:52 am UTC

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 Aleph-1 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's-constant 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 Aleph-1 (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, Aleph-0 independent uncomputables, and still Aleph-1 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! :D
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Cardinality of uncomputable numbers

Postby jaap » Sat May 22, 2010 6:18 am UTC

squareroot wrote:First, we know there are at least Aleph-1 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 1-r, 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].

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Cardinality of uncomputable numbers

Postby skeptical scientist » Sat May 22, 2010 3:23 pm UTC

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 continuum-many 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

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: Cardinality of uncomputable numbers

Postby squareroot » Sat May 22, 2010 3:57 pm UTC

Thanks! Those arguments make a lot of sense. :D
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Cardinality of uncomputable numbers

Postby t0rajir0u » Sun May 23, 2010 12:34 am UTC

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's-constant 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.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Cardinality of uncomputable numbers

Postby WarDaft » Sun May 23, 2010 3:59 am UTC

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.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: Cardinality of uncomputable numbers

Postby squareroot » Sun May 23, 2010 5:26 am UTC

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^Aleph-0, the cardinality of this set of "base uncomputables" would have to be <= Aleph-0.

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. :oops:
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

User avatar
NathanielJ
Posts: 882
Joined: Sun Jan 13, 2008 9:04 pm UTC

Re: Cardinality of uncomputable numbers

Postby NathanielJ » Sun May 23, 2010 12:44 pm UTC

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^Aleph-0, the cardinality of this set of "base uncomputables" would have to be <= Aleph-0.


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, square-rooting, 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.
Homepage: http://www.njohnston.ca
Conway's Game of Life: http://www.conwaylife.com

User avatar
t0rajir0u
Posts: 1178
Joined: Wed Apr 16, 2008 12:52 am UTC
Location: Cambridge, MA
Contact:

Re: Cardinality of uncomputable numbers

Postby t0rajir0u » Sun May 23, 2010 11:42 pm UTC

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.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: Cardinality of uncomputable numbers

Postby squareroot » Sun May 23, 2010 11:49 pm UTC

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.
Yes, I see that now. I meant that, when I wrote that first post, that's what I meant.

NatnahielJ wrote:
squareroot wrote:I guess that, because (as other people explained, tyvm) the set all uncomputables have a cardinality of 2^Aleph-0, the cardinality of this set of "base uncomputables" would have to be <= Aleph-0.


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, square-rooting, 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.
[/quote]

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 - __ -

achan1058
Posts: 1783
Joined: Sun Nov 30, 2008 9:50 pm UTC

Re: Cardinality of uncomputable numbers

Postby achan1058 » Mon May 24, 2010 12:40 am UTC

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

Syrin
Posts: 290
Joined: Thu May 24, 2007 7:10 pm UTC
Location: Ontario, Canadia

Re: Cardinality of uncomputable numbers

Postby Syrin » Mon May 24, 2010 12:55 am UTC

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.

User avatar
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

Postby gmalivuk » Mon May 24, 2010 5:09 am UTC

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.
Nope, because a countable set of countable sets is still countable.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Cardinality of uncomputable numbers

Postby skeptical scientist » Tue May 25, 2010 1:23 am UTC

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

User avatar
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

Postby jestingrabbit » Tue May 25, 2010 4:33 am UTC

I tend to think its true, at the very least in the weak sense.

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 real-valued 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.

User avatar
imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

Re: Cardinality of uncomputable numbers

Postby imatrendytotebag » Tue May 25, 2010 6:13 am UTC

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.

User avatar
snowyowl
Posts: 464
Joined: Tue Jun 23, 2009 7:36 pm UTC

Re: Cardinality of uncomputable numbers

Postby snowyowl » Thu May 27, 2010 2:13 pm UTC

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 Aleph-0, 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.
The preceding comment is an automated response.

Syrin
Posts: 290
Joined: Thu May 24, 2007 7:10 pm UTC
Location: Ontario, Canadia

Re: Cardinality of uncomputable numbers

Postby Syrin » Thu May 27, 2010 7:08 pm UTC

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?

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Cardinality of uncomputable numbers

Postby skeptical scientist » Sat May 29, 2010 5:17 am UTC

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

User avatar
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

Postby Yakk » Sat May 29, 2010 10:12 pm UTC

A countable number of computer programs that output 4:
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.

Cmebeh
Posts: 47
Joined: Wed May 26, 2010 4:57 am UTC

Re: Cardinality of uncomputable numbers

Postby Cmebeh » Sun May 30, 2010 3:39 am UTC

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

User avatar
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

Postby gmalivuk » Sun May 30, 2010 4:07 am UTC

Cmebeh wrote:Wrong. In ZF, CH => Axiom of Choice.
What? No it certainly doesn't.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

Cmebeh
Posts: 47
Joined: Wed May 26, 2010 4:57 am UTC

Re: Cardinality of uncomputable numbers

Postby Cmebeh » Sun May 30, 2010 4:16 am UTC

gmalivuk wrote:
Cmebeh wrote:Wrong. In ZF, CH => Axiom of Choice.
What? No it certainly doesn't.



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

User avatar
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

Postby jestingrabbit » Sun May 30, 2010 4:24 am UTC

That is still getting a big "citation needed".
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

Cmebeh
Posts: 47
Joined: Wed May 26, 2010 4:57 am UTC

Re: Cardinality of uncomputable numbers

Postby Cmebeh » Sun May 30, 2010 4:25 am UTC

Cmebeh wrote:LOL you computer scientists; isn't it obvious? P = NP is undecidable à la continuum hypothesis

User avatar
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

Postby gmalivuk » Sun May 30, 2010 6:52 am UTC

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.
Unless stated otherwise, I do not care whether a statement, by itself, constitutes a persuasive political argument. I care whether it's true.
---
If this post has math that doesn't work for you, use TeX the World for Firefox or Chrome

(he/him/his)

User avatar
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

Postby jestingrabbit » Sun May 30, 2010 9:26 am UTC

@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,

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 non-order-isomorphic 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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Cardinality of uncomputable numbers

Postby skeptical scientist » Sun May 30, 2010 3:58 pm UTC

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

Cmebeh
Posts: 47
Joined: Wed May 26, 2010 4:57 am UTC

Re: Cardinality of uncomputable numbers

Postby Cmebeh » Sun May 30, 2010 6:38 pm UTC

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

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Cardinality of uncomputable numbers

Postby skeptical scientist » Sun May 30, 2010 10:06 pm UTC

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 well-ordering ≤1 of [0,1] of type \(\omega_1\). Let f(x)={y : y≤1x}. 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

User avatar
majikthise
Posts: 155
Joined: Sun Jun 10, 2007 2:28 am UTC
Location: Bristol, UK

Re: Cardinality of uncomputable numbers

Postby majikthise » Sun May 30, 2010 10:31 pm UTC

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.
Is this a wok that you've shoved down my throat, or are you just pleased to see me?

User avatar
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

Postby jestingrabbit » Mon May 31, 2010 12:06 am UTC

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.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Cardinality of uncomputable numbers

Postby WarDaft » Mon May 31, 2010 12:27 am UTC

Interesting.

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.

User avatar
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

Postby jestingrabbit » Mon May 31, 2010 12:32 am UTC

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.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Cardinality of uncomputable numbers

Postby WarDaft » Mon May 31, 2010 12:44 am UTC

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 continuum-many 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.

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Cardinality of uncomputable numbers

Postby skeptical scientist » Mon May 31, 2010 1:10 am UTC

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

Cmebeh
Posts: 47
Joined: Wed May 26, 2010 4:57 am UTC

Re: Cardinality of uncomputable numbers

Postby Cmebeh » Mon May 31, 2010 1:35 am UTC

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

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Cardinality of uncomputable numbers

Postby WarDaft » Mon May 31, 2010 1:52 am UTC

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?

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.
I thought that was the Banach-Tarski paradox and that it depended on AC.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

Cmebeh
Posts: 47
Joined: Wed May 26, 2010 4:57 am UTC

Re: Cardinality of uncomputable numbers

Postby Cmebeh » Mon May 31, 2010 1:56 am UTC

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

User avatar
skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Cardinality of uncomputable numbers

Postby skeptical scientist » Mon May 31, 2010 2:35 am UTC

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


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 11 guests