The theory PA(aa), which is Peano Arithmetic in the context of stationary logic, is shown to be consistent. Moreover, the first-order theory of the class of finitely determinate models of PA(aa) is characterized.

In a countable, recursively saturated model of Peano Arithmetic, an interstice is a maximal convex set which does not contain any definable elements. The interstices are partitioned into intersticial gaps in a way that generalizes the partition of the unbounded interstice into gaps. Continuing work of Bamber and Kotlarski [1], we investigate extensions of Kotlarski's Moving Gaps Lemma to the moving of intersticial gaps.

Bounded lattices (that is lattices that are both lower bounded and upper bounded) form a large class of lattices that include all distributive lattices, many nondistributive finite lattices such as the pentagon lattice N₅, and all lattices in any variety generated by a finite bounded lattice. Extending a theorem of Paris for distributive lattices, we prove that if L is an ℵ₀-algebraic bounded lattice, then every countable nonstandard model ������ of Peano Arithmetic has a cofinal elementary extension ������ such that (...) the interstructure lattice Lt(������ / ������) is isomorphic to L. (shrink)

Let ℳ be a countable, recursively saturated model of Peano Arithmetic, and let Aut be its automorphism group considered as a topological group with the pointwise stabilizers of finite sets being the basic open subgroups. Kaye proved that the closed normal subgroups are precisely the obvious ones, namely the stabilizers of invariant cuts. A proof of Kaye's theorem is given here which, although based on his proof, is different enough to yield consequences not obtainable from Kaye's proof.

A model $\mathscr{M} = (M,+,\times, 0,1,<)$ of Peano Arithmetic $({\sf PA})$ is boundedly saturated if and only if it has a saturated elementary end extension $\mathscr{N}$. The ordertypes of boundedly saturated models of $({\sf PA})$ are characterized and the number of models having these ordertypes is determined. Pairs $(\mathscr{N},M)$, where $\mathscr{M} \prec_{\sf end} \mathscr{N} \models({\sf PA})$ for saturated $\mathscr{N}$, and their theories are investigated. One result is: If $\mathscr{N}$ is a $\kappa$-saturated model of $({\sf PA})$ and $\mathscr{M}_0, \mathscr{M}_1 \prec_{\sf end} (...) \mathscr{N}$ are such that $\aleph_1 \leq \mathrm{min}(\mathrm{cf}(M_0),\mathrm{dcf}(M_0)) \leq \mathrm{min}(\mathrm{cf}(M_1), \mathrm{dcf}(M_1)) < \kappa$, then $(\mathscr{N},M_0) \equiv (\mathscr{N},M_1)$. (shrink)

For a model M of Peano Arithmetic, let Lt(M) be the lattice of its elementary substructures, and let Lt⁺(M) be the equivalenced lattice (Lt(M), ≅M), where ≅M is the equivalence relation of isomorphism on Lt(M). It is known that Lt⁺(M) is always a reasonable equivalenced lattice. Theorem. Let L be a finite distributive lattice and let (L,E) be reasonable. If M₀ is a nonstandard prime model of PA, then M₀ has a confinal extension M such that Lt⁺(M) ≅ (L,E). A (...) general method for proving such theorems is developed which, hopefully, will be able to be applied to some nondistributive lattices. (shrink)

This paper is primarily concerned with ℵ 0 -categoricity of theories of partially ordered sets. It contains some general conjectures, a collection of known results and some new theorems on ℵ 0 -categoricity. Among the latter are the following. Corollary 3.3. For every countable ℵ 0 -categorical U there is a linear order of A such that $(\mathfrak{U}, is ℵ 0 -categorical. Corollary 6.7. Every ℵ 0 -categorical theory of a partially ordered set of finite width has a decidable theory. (...) Theorem 7.7. Every ℵ 0 -categorical theory of reticles has a decidable theory. There is a section dealing just with decidability of partially ordered sets, the main result of this section being. Theorem 8.2. If $(P, is a finite partially ordered set and K P is the class of partially ordered sets which do not embed $(P, , then Th(K P ) is decidable iff K P contains only reticles. (shrink)

The paper presents an outline of the general theory of countable arithmetically saturated models of PA and some of its applications. We consider questions concerning the automorphism group of a countable recursively saturated model of PA. We prove new results concerning fixed point sets, open subgroups, and the cofinality of the automorphism group. We also prove that the standard system of a countable arithmetically saturated model of PA is determined by the lattice of its elementary substructures.

A structure A = (A; E₀, E₁ , . . . , ${E_{n - 2}}$) is an n-grid if each E i is an equivalence relation on A and whenver X and Y are equivalence classes of, repectively, distinct E i and E j , then X ∩ Y is finite. A coloring χ : A → n is acceptable if whenver X is an equivalence class of E i , then {ϰ Є X: χ(ϰ) = i} is finite. If (...) B is any set, then the n-cube B n = (B n ; E₀ E₁ , . . . , ${E_{n - 2}}$) is considinate axis. Kuratowski [9], generalizing the n = 3 case proved by Sierpiński [17], proved that ℝ n has an acceptable coloring iff ${2^{{N_0}}}$ ≤ ${N_{n - 2}}$. The main result is: of A is a semialgebraic (i.e., first-order definable in the field of reals) n-grid, then the following are equivalent: (1) if A embeds all finite n-cubes, then ${2^{{N_0}}}$ ≤ ${N_{n - 2}}$; if A embeds ℝ n , then ${2^{{N_0}}}$ ≤ ${N_{n - 2}}$; (3) A has an acceptable coloring. (shrink)

For each completion of Peano Arithmetic there is a weakly definable type which is not definable.

We investigate some properties of ordered structures that are related to their having cofinal elementary extensions. Special attention is paid to models of some very weak fragments of Peano Arithmetic.

Every ℵ 0 -categorical partially ordered set of finite width has a finitely axiomatizable theory. Every ℵ 0 -categorical partially ordered set of finite weak width has a decidable theory. This last statement constitutes a major portion of the complete (with three exceptions) characterization of those finite partially ordered sets for which any ℵ 0 -categorical partially ordered set not embedding one of them has a decidable theory.

There is a recursive set of natural numbers which is the difference set of some recursively enumerable set but which is not the difference set of any recursive set.

For each infinite cardinalκ, the set of algebraic hypergraphs having chromatic number no larger thanκis decidable.

A theorem of Enayat's concerning models of ZFC which had been proved using several different additional set-theoretical hypotheses is shown here to be absolute.

Improving a theorem of Gasarch and Hirst, we prove that if 2 ≤ k ≤ m < ω, then the following is equivalent to WKL0 over RCA0 Every locally k-colorable graph is m-colorable.

There is an infinite set T of Turing-equivalent completions of Peano Arithmetic such that whenever M and N are nonisomorphic countable, arithmetically saturated models of PA and Th, Th∈T, then Aut≇Aut.

Suppose that M⊧PA\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal M}\models \mathsf{PA}$$\end{document} and X⊆P\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathfrak X} \subseteq {\mathcal P}$$\end{document}. If M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal M}$$\end{document} has a finitely generated elementary end extension N≻endM\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal N}\succ _\mathsf{end} {\mathcal M}$$\end{document} such that {X∩M:X∈Def}=X\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{X \cap M : X \in {{\mathrm{Def}}}\} = (...) {\mathfrak X}$$\end{document}, then there is such an N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal N}$$\end{document} that is, in addition, a minimal extension of M\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathcal M}$$\end{document} iff every subset of M that is Π10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi _1^0$$\end{document}-definable in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$$$\end{document} is the countable union of Σ10\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Sigma _1^0$$\end{document}-definable sets. (shrink)

No theory of a partially ordered set of finite width has the independence property, generalizing Poizat's corresponding result for linearly ordered sets. In fact, a question of Poizat concerning linearly ordered sets is answered by showing, moreover, that no theory of a partially ordered set of finite width has the multi-order property. It then follows that a distributive lattice is not finite-dimensional $\operatorname{iff}$ its theory has the independence property $\operatorname{iff}$ its theory has the multi-order property.

The relationship of Grundy and chromatic numbers of graphs in the context of Reverse Mathematics is investi-gated.

This paper concerns intermediate structure lattices Lt, where [MATHEMATICAL SCRIPT CAPITAL N] is an almost minimal elementary end extension of the model ℳ of Peano Arithmetic. For the purposes of this abstract only, let us say that ℳ attains L if L ≅ Lt for some almost minimal elementary end extension of [MATHEMATICAL SCRIPT CAPITAL N]. If T is a completion of PA and L is a finite lattice, then: If some model of T attains L, then every countable model (...) of T does. If some rather classless, ℵ1-saturated model of T attains L, then every model of T does. (shrink)

Fix a countable nonstandard model M of Peano arithmetic. Even with some rather severe restrictions placed on the types of minimal cofinal extensions N≻M that are allowed, we still find that there are 2ℵ0 possible theories of (N,M) for such N’s.

The set of all difference sets of natural numbers is a ∑11-complete set of reals.