Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-19T04:25:49.868Z Has data issue: false hasContentIssue false

Two further combinatorial theorems equivalent to the 1-consistency of peano arithmetic

Published online by Cambridge University Press:  12 March 2014

Peter Clote
Affiliation:
U.E.R. de Mathématiques, Université Paris VII, 75005 Paris, France
Kenneth Mcaloon
Affiliation:
Brooklyn College of Cuny, Brooklyn, New York 11210

Extract

We give two new finite combinatorial statements which are independent of Peano arithmetic, using the methods of Kirby and Paris [6] and Paris [12]. Both are in fact equivalent over Peano arithmetic (denoted by P) to its 1-consistency. The first involves trees and the second linear orderings. Both were “motivated” by anti-basis theorems of Clote (cf. [1], [2]). The one involving trees, however, is not unrelated to the Kirby-Paris characterization of strong cuts in terms of the tree property [6], but, in fact, comes directly from König's lemma, of which it is a miniaturization. (See the remark preceding Theorem 3 below.) The resulting combinatorial statement is easily seen to imply the independent statement discovered by Mills [11], but it is not clear how to show their equivalence over Peano arithmetic without going through 1-consistency. The one involving linear orderings miniaturizes the property of infinite sets X that any linear ordering of X is isomorphic to ω or ω* on some infinite subset of X. Both statements are analogous to Example 2 of [12] and involve the notion of dense [12] or relatively large [14] finite set.

We adopt the notations and definitions of [6] and [12]. We shall in particular have need of the notions of semiregular, regular and strong initial segments and of indicators.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1983

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable