Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In the context of supertasks, people and mathematicians are comfortable with the idea of transfinite ordinal time, that is, that time can be divided into an arbitrarily high number of steps. In most cases the number of steps is limited to be $\omega$, but some models, such as Hamkins infinite time Turing machines, assume that a finite amount of time can be divided into a number of steps of arbitrarily high cardinality. I think we can safely extend the concept from time to space (actually the question is the same, just that I think many people will find it easier to identify space with the real line). Then, the original question: The real line has $2^{\aleph_0}$ (which I guess is at most $\aleph_2$) points. But if we can partition it into a number of intervals of arbitrarily high cardinality, shouldn't the number (or set) of points on it have at least the same cardinality? (or you can have more intervals than points?). I am obviously confused. Please help!!

share|cite|improve this question
I don't get why there are three votes to close. This is a legitimate question... – Asaf Karagila Mar 26 '13 at 19:31
Why the close votes to this question? I believe that at its heart this question is requesting clarification on the nature of Hamkins's Infinite Time Turing Machine model and how it relates to other mathematical concepts. IMHO such issues clearly fall under the scope of math.SE. (I'm just a bit later than @Asaf.) – arjafi Mar 26 '13 at 19:31
three vote to close?? – Wolphram jonny Mar 26 '13 at 19:49
I am tempted to vote to close just to see who initiated this closure. :-) – Asaf Karagila Mar 26 '13 at 19:52
I would say this question is in the top 10% we see in terms of thought going into it. I don't understand a vote to close. – Ross Millikan Mar 27 '13 at 4:23
up vote 9 down vote accepted

Hamkins's construction doesn't really assume "assume that a finite amount of time can be divided into a number of steps of arbitrarily high cardinality". Is merely proposes using an arbitrary ordinal (of whatever cardinality) as the time coordinate for the Turing machine computation, and investigates the consequences of such a decision. It doesn't depend on the full ordinal indexed time axis to correspond to "a finite amount of time", or to a subset of $\mathbb R$.

Indeed, Theorem 1.1 of the article you link to says that even if we don't assume a particular cardinality of the time axis, it is impossible for the machine to halt after more than countable steps. So essentially, the possibility of an uncountably long computation is allowed by the definition only to permit an argument that it is not an interesting case; all we really need to consider is computations that terminate in less than $\omega_1$ time.

Now it is well known that every ordinal below $\omega_1$ can be embedded not only into the real interval $[0,1]$, but can even be embedded into the rationals between $0$ and $1$. On the other hand, $\omega_1$ itself is not order-isomorphic to any subset of $\mathbb R$.

On yet another hand, that may not matter (at least if we restrict our attention to finite input tapes -- which, however, is a pretty big if), because there are only countably many different Turing machines, so since $\omega_1$ is a regular cardinal, there will be some countable ordinal before which every terminating computation has terminated. And that upper bound can be embedded into $\mathbb Q\cap[0,1]$.

As a philosophical comment to your question, the real line is merely a (fairly good) mathematical model of physical time. It may or may not correspond to actual physical time, and there seems to be no particular reason to insist that the hypothetical, non-physical, "philosophical time" that the "supertask" concept evokes ought to be constrained to things that can be modeled by the real line. Why not the long line, for example?

share|cite|improve this answer
In terms of your last point, there has been some (speculative and controversial) talk of time being quantized, meaning there could be a smallest unit of time, which would mean time is not a continuum like the real line. – Todd Wilcox Mar 26 '13 at 19:03
@ToddWilcox: That's one reason why I downgraded "very good" (as my first draft read) to "fairly good"... :-) – Henning Makholm Mar 26 '13 at 19:28
I didnt interpret the possibility of computing beyond $\omega_1$ as trivial, the machine can in principle reach that stage in finite time, only the behaviour is not interesting. And if you keep running, wouldnt the machine reach $\omega_2$, and beyond? my be I am wrong in assuming that he is assuming that $\omega_2$ can be reached in finite time too. – Wolphram jonny Mar 26 '13 at 20:00
@julianfernandez: He's not assuming anything about "can be reached in finite time". He's saying "let's consider this strange inductive definition of a function from ordinals to machine states, and study its mathematical properties". There's no need to interpret that as a process that takes place in physical time (or for that matter in any particular non-physical time) -- such an interpretation can at most be a source of intuition about the project. The actual math doesn't need it and is not constrained by it. – Henning Makholm Mar 26 '13 at 20:04
@julianfernandez: That's intuitive motivation, not part of the mathematical development. The actual mathematics doesn't depend on any real-valued time axis; the sentence you're quoting from the introduction is merely a vivid, non-technical, handwavy attempt to suggest a reason to care about the precise mathematics that follows. – Henning Makholm Mar 26 '13 at 20:17

First of all, the real line can be of size $\aleph_2$, but also of size $\aleph_{5223435}$ and even $\aleph_{\omega_1}$. All these are consistent with ZFC, and unless you assume something additional you can't really prove a lot about the cardinality of the continuum.

Secondly, you are correct. Assuming the axiom of choice a set cannot be partitioned into a strictly larger number of parts. That means that if $\Bbb R$ has cardinality $\aleph_2$, then every partition must have size of at most $\aleph_2$. However, do note that there are $\aleph_3$ many ordinals of cardinality $\aleph_2$.

share|cite|improve this answer
Thanks Ross, this tablet has some keyboard issues... – Asaf Karagila Mar 26 '13 at 16:50
Thanks to both answers, give me some time to digest the answers,and I'll be back, perhaps asking some clarification.I am not sure to understand them yet. – Wolphram jonny Mar 26 '13 at 16:56
@julianfernandez Nowhere in the paper do they assume anything like $\lnot\mathsf{CH}$ and certainly not that the continuum is $\aleph_2$. There is one proof, not in the section you suggest, where they prove a result via an absoluteness argument that involves forcing (But this is not what you had in mind anyway). – Andrés E. Caicedo Mar 26 '13 at 18:51
@julianfernandez No one is bullying you. – Andrés E. Caicedo Mar 26 '13 at 20:23
@AndresCaicedo sorry, I misinterpreted you, I got dizzy because a lot o people were saying that I stated things that I didn't, so they didn't read carefully and just put "incorrect" answers too fast (incorrect in the sense that misinterpret what I wrote too easily) – Wolphram jonny Mar 26 '13 at 20:41

$2^{\aleph_0}$ can be almost anything, it is not limited to $\aleph_2$. As long as you can't divide the line into more than $2^{\aleph_0}$ segments, the fact that $|2^{\aleph_0} \times 2^{\aleph_0}|=|2^{\aleph_0}|$ means you have no trouble with more points than intervals. Whatever $2^{\aleph_0}$ is, $\mathbb R^n$ has that number of points in it, too.

share|cite|improve this answer
You can't if you assume the axiom of choice. :-) Without the axiom of choice it might be the case that you can divide the continuum into way more parts than elements! And people complain about the Banach-Tarski paradox... :-) – Asaf Karagila Mar 26 '13 at 16:47
@AsafKaragila: I think the question was in the spirit of ZFC. But I would love to see a reference for that (it must be disjoint parts?!) Sometimes we educate more than OP. – Ross Millikan Mar 27 '13 at 4:27
Take any model in which $\aleph_1\nleq2^{\aleph_0}$ (Solovay's model, Shelah's model, Truss' model[s], Feferman-Levy model, any model of ZF+AD); there is a definable map from $\Bbb R$ onto $\omega_1$. Then you can map $\Bbb R$ onto $\Bbb R\cup\omega_1$ which has a strictly larger cardinality. – Asaf Karagila Mar 27 '13 at 6:01
Ross, you may enjoy this answer, and the link there: – Andrés E. Caicedo Mar 27 '13 at 13:58

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.