3
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ A nice book on ordered sets is "Linear orderings" by Rosenstein. $\endgroup$
    – Yuval Filmus
    Commented Sep 12, 2010 at 11:44
  • $\begingroup$ I second Rosenstein (he indeed defines sum and product for all ordered spaces, and does some theory on them). $\endgroup$
    – Henno Brandsma
    Commented Sep 12, 2010 at 14:01
  • $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented Sep 12, 2010 at 16:30
  • $\begingroup$ 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 ℤ). $\endgroup$
    – Antonio E. Porreca
    Commented Sep 14, 2010 at 10:18

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
0
1
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Antonio E. Porreca
    Commented Sep 14, 2010 at 10:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .