Two-dimensional partial orderings: Undecidability

Publisher Website
Google Scholar
Abstract
In this paper we examine the class of two-dimensional partial orderings from the perspective of undecidability. We shall see that from this perspective the class of 2dpo's is more similar to the class of all partial orderings than to its one-dimensional subclass, the class of all linear orderings. More specifically, we shall describe an argument which lends itself to proofs of the following four results: (A) the theory of 2dpo's is undecidable: (B) the theory of 2dpo's is recursively inseparable from the set of sentences refutable in some finite 2dpo; (C) there is a sentence which is true in some 2dpo but which has no recursive model; (D) the theory of planar lattices is undecidable. It is known that the theory of linear orderings is decidable (Lauchli and Leonard [4]). On the other hand, the theories of partial orderings and lattices were shown to be undecidable by Tarski [14], and that each of these theories is recursively inseparable from its finitely refutable statements was shown by Taitslin [13]. Thus, the complexity of the theories of partial orderings and lattices is, by (A), (B) and (D), already reflected in the 2dpo's and planar lattices. As pointed out by J. Schmerl, bipartite graphs can be coded into 2dpo's, so that (A) and (B) could also be obtained by applying a Rabin-Scott style argument [9] to Rogers' result [11] that the theory of bipartite graphs is undecidable and to Lavrov's result [5] that the theory of bipartite graphs is recursively inseparable from the set of sentences refutable in some finite bipartite graph. (However, (C) and (D) do not seem to follow from this type of argument.)

This publication has 9 references indexed in Scilit: