It is shown that for every nonzero r.e. degree c there is a linear ordering of degree c which is not isomorphic to any recursive linear ordering. It follows that there is a linear ordering of low degree which is not isomorphic to any recursive linear ordering. It is shown further that there is a linear ordering L such that L is not isomorphic to any recursive linear ordering, and L together with its ‘infinitely far apart’ relation is of low (...) degree. Finally, an analogue of the recursion theorem for recursive linear orderings is refuted. (shrink)

The fundamental question in reverse mathematics is to determine which set existence axioms are required to prove particular theorems of mathematics. In addition to being interesting in their own right, answers to this question have consequences in both effective mathematics and the foundations of mathematics. Before discussing these consequences, we need to be more specific about the motivating question.Reverse mathematics is useful for studying theorems of either countable or essentially countable mathematics. Essentially countable mathematics is a vague term that is (...) best explained by an example. Complete separable metric spaces are essentially countable because, although the spaces may be uncountable, they can be understood in terms of a countable basis. Simpson gives the following list of areas which can be analyzed by reverse mathematics: number theory, geometry, calculus, differential equations, real and complex analysis, combinatorics, countable algebra, separable Banach spaces, computability theory, and the topology of complete separable metric spaces. Reverse mathematics is less suited to theorems of abstract functional analysis, abstract set theory, universal algebra, or general topology.Section 2 introduces the major subsystems of second order arithmetic used in reverse mathematics: RCA0, WKL0, ACA0, ATR0 and – CA0. Sections 3 through 7 consider various theorems of ordered group theory from the perspective of reverse mathematics. Among the results considered are theorems on ordered quotient groups, groups and semigroup conditions which imply orderability, the orderability of free groups, Hölder's Theorem, Mal'tsev's classification of the order types of countable ordered groups. (shrink)