MathOverflow is a question and answer site for professional mathematicians. 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

Motivation. Having read about infinite time Turing machines and ω-languages, I was thinking about more general notions of languages and “computation time”. Languages over strings of length greater than ω seem reasonably easy to define, and using larger ordinals to measure time is quite standard.

However, I’m interested in more general, non necessarily well-founded ordered sets. Using ordered sets to keep track of time seems to require suitable notions of arithmetic operations. For example, it’s easy to generalise sum and multiplication of ordinals to arbitrary totally ordered sets (though, of course, these operations are not defined by transfinite recursion); I’m not sure about exponentiation and other operations.

Question. Is there any good literature about arithmetic of (some classes of) non well-founded ordered sets?

share|cite|improve this question
A nice book on ordered sets is "Linear orderings" by Rosenstein. – Yuval Filmus Sep 12 '10 at 11:44
I second Rosenstein (he indeed defines sum and product for all ordered spaces, and does some theory on them). – Henno Brandsma Sep 12 '10 at 14:01
Antonio, are you proposing in particular to extend Turing machine operation into non-well-founded time? This is very interesting, but I am not clear on what it would mean. Meanwhile, Peter Koepke has extended infinite time Turing machines to use ordinal-length tapes, and quite successfully analyzed their power. – Joel David Hamkins Sep 12 '10 at 16:30
Joel, me and one of my colleagues were just toying with that idea; we’re not sure about the interpretation either (except maybe for a “universe without a beginning” where time has the same order type as ℤ). – Antonio E. Porreca Sep 14 '10 at 10:18

I recommend Rosenstein's excellent book "Linear orderings".

share|cite|improve this answer
Thanks, I’ll take a look at it. – Antonio E. Porreca Sep 14 '10 at 10:18

Peter Aczel's book Non-Wellfounded Sets would be my suggestion.

share|cite|improve this answer
Does non-well-founded set theory provide a more appropriate setting for non-well-founded orders, e.g., for finding canonical representatives of each order type? I’m not familiar with the subject. – Antonio E. Porreca Sep 14 '10 at 10:37

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.