We give an example of a simple ω-categorical theory such that for any finite set of parameters the corresponding constant expansion does not satisfy the PAPA. We describe a wide class of homogeneous structures with generic automorphisms and show that some natural reducts of our example belong to this class.

It is shown that the theory of fields with an automorphism has a decidable model companion. Quantifier-elimination is established in a natural language. The theory is intimately connected to Ax's theory of pseudofinite fields, and analogues are obtained for most of Ax's classical results. Some indication is given of the connection to nonstandard Frobenius maps.

We give an examination of the automorphism group Aut of a countable recursively saturated model M of PA. The main result is a characterisation of strong elementary initial segments of M as the initial segments consisting of fixed points of automorphisms of M. As a corollary we prove that, for any consistent completion T of PA, there are recursively saturated countable models M1, M2 of T, such that Aut[ncong]Aut, as topological groups with a natural topology. Other results include a (...) classification of the normal subgroups of Aut of the form [lcub]g: g [uharr] A = idA[rcub], for sets A M, and a highly homogeneous representation of Aut as a subgroup of Aut. (shrink)

Chapter 1: Introduction. S = <{We}c<w; C,U,n,0,w> is the substructure formed by restricting the lattice <^P(w); C , U, n,0,w> to the re subsets We of the ...

In this paper we analyze the propositional extensions of the minimal classical modal logic system E, which form a lattice denoted as CExtE. Our method of analysis uses algebraic calculations with canonical forms, which are a generalization of the normal forms applicable to normal modal logics. As an application, we identify a group of automorphisms of CExtE that is isomorphic to the symmetric group S4.

We develop the method of iterated ultrapower representation to provide a unified and perspicuous approach for building automorphisms of countable recursively saturated models of Peano arithmetic . In particular, we use this method to prove Theorem A below, which confirms a long-standing conjecture of James Schmerl.Theorem AIf is a countable recursively saturated model of in which is a strong cut, then for any there is an automorphism j of such that the fixed point set of j is isomorphic to (...) .We also fine-tune a number of classical results. One of our typical results in this direction is Theorem B below, which generalizes a theorem of Kaye–Kossak–Kotlarski .Theorem BSuppose is a countable recursively saturated model of in which is a strong cut. There is a group embedding from into such that for each that is fixed point free, moves every undefinable element of. (shrink)

We discuss automorphisms of saturated models of PA and boundedly saturated models of PA. We show that Smoryński's Lemma and Kaye's Theorem are not only true for countable recursively saturated models of PA but also true for all boundedly saturated models of PA with slight modifications.

We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elements enter them relative to elements entering other sets, and the Martin Invariance Conjecture on their Turing degrees, i.e., their information content with respect to relative computability (Turing reducibility).

Given a group G, there is a proper class of pairwise nonembeddable orthomodular lattices with the automorphism group isomorphic to G. While the validity of the above statement depends on the used set theory, the analogous statement for groups of symmetries of quantum logics is valid absolutely.

A model of Peano Arithmetic is short recursively saturated if it realizes all its bounded finitely realized recursive types. Short recursively saturated models of $\PA$ are exactly the elementary initial segments of recursively saturated models of $\PA$. In this paper, we survey and prove results on short recursively saturated models of $\PA$ and their automorphisms. In particular, we investigate a certain subgroup of the automorphism group of such models. This subgroup, denoted $G|_{M(a)}$, contains all the automorphisms of a (...) countable short recursively saturated model of which can be extended to an automorphism of the countable recursively saturated elementary end extension of the model. (shrink)

Translator's summary The translated paper is an extract, published in 1945, of an unpublished thesis, of both historical and technical import, dealing with notions of definability and their relation to invariance under automorphisms. The author develops a metamathematical Galois theory, and discusses and anticipates some aspects of higher-order model theory in an informal but conceptually rich manner.

We give a survey of automorphisms of countable recursively saturated models of Peano Arithmetic.

This paper generalizes results of F. Körner from [4] where she established the existence of maximal automorphisms (i.e. automorphisms moving all non-algebraic elements). An ω-maximal automorphism is an automorphism whose powers are maximal automorphisms. We prove that any structure has an elementary extension with an ω-maximal automorphism. We also show the existence of ω-maximal automorphisms in all countable arithmetically saturated structures. Further we describe the pairs of tuples (¯a,¯b) for which there is an ω-maximal automorphism mapping (...) ¯a to ¯b. (shrink)

Let \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\fancyscript{L}}$$\end{document} be a finite first-order language and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\langle{\fancyscript{M}_n} \,|\, {n < \omega}\rangle}$$\end{document} be a sequence of finite \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\fancyscript{L}}$$\end{document}-models containing models of arbitrarily large finite cardinality. If the intersection of less than continuum-many dense open subsets of Cantor Space ω2 is non-empty, then there is a non-principal ultrafilter \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} (...) \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\fancyscript{U}}$$\end{document} over ω such that the corresponding ultraproduct \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\prod_\fancyscript{U}\fancyscript{M}_n}$$\end{document} has an automorphism that is not induced by an element of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\prod_{n<\omega}{\rm Aut}(\fancyscript{M}_n)}$$\end{document}. (shrink)

Let $D_{tt} $ denote the set of truth-table degrees. A bijection π: $D_{tt} \to \,D_{tt} $ is an automorphism if for all truth-table degrees x and y we have $ \leqslant _{tt} \,y\, \Leftrightarrow \,\pi (x)\, \leqslant _{tt} \,\pi (y)$ . We say an automorphism π is fixed on a cone if there is a degree b such that for all $x \geqslant _{tt} b$ we have π(x) = x. We first prove that for every 2-generic real X we have (...) X' $X' \le _{tt} \,X\, \oplus \,0'$ . We next prove that for every real $X \ge _{tt} \,0'$ there is a real Y such that $Y \oplus 0{\text{'}}\, \equiv _{tt} \,Y{\text{'}} \equiv _{tt} \,X$ . Finally, we use this to demonstrate that every automorphism of the truth-table degrees is fixed on a cone. (shrink)

We develop an approach to the longstanding conjecture of Kierstead concerning the character of strongly nontrivial automorphisms of computable linear orderings. Our main result is that for any η-like computable linear ordering, such that has no interval of order type η, and such that the order type of is determined by a -limitwise monotonic maximal block function, there exists computable such that has no nontrivial automorphism.

This paper generalizes results of F. Körner from [4] where she established the existence of maximal automorphisms (i.e. automorphisms moving all non-algebraic elements). An ω-maximal automorphism is an automorphism whose powers are maximal automorphisms. We prove that any structure has an elementary extension with an ω-maximal automorphism. We also show the existence of ω-maximal automorphisms in all countable arithmetically saturated structures. Further we describe the pairs of tuples (¯a,¯b) for which there is an ω-maximal automorphism mapping (...) ¯a to ¯b. (shrink)

This article addresses the question which structures occur as fixed structures of stable structures with a generic automorphism. In particular we give a Galois theoretic characterization. Furthermore, we prove that any pseudofinite field is the fixed field of some model ofACFA, any one-free pseudo-differentially closed field of characteristic zero is the fixed field of some model ofDCFA, and that any one-free PAC field of finite degree of imperfection is the fixed field of some model ofSCFA.

We consider questions related to the rigidity of the structure R, the PTIME-Turing degrees of recursive sets of strings together with PTIME-Turing reducibility, pT, and related structures; do these structures have nontrivial automorphisms? We prove that there is a nontrivial automorphism of an ideal of R. This can be rephrased in terms of partial relativizations. We consider the sets which are PTIME-Turing computable from a set A, and call this class PTIMEA. Our result can be stated as follows: There (...) is an oracle, A, relative to which the PTIME-Turing degrees are not rigid . Furthermore, the automorphism can be made to preserve the complexity classes DTIMEA for all k 1, or to move any DTIMEA for n 2. From the existence of such an automorphism we conclude as a corollary that there is an oracle A relative to which the classes DTIME are not definable over R. We carry out the corresponding partial relativization for the many-one degrees to construct an oracle, A, relative to which the PTIMA-many-one degrees relative to A have a nontrivial automorphism, and one relative to which the lattice of sets in PTIMEA under inclusion have a nontrivial automorphism. The proof is phrased as a forcing argument; we construct the set A to meet a particular collection of dense sets in our notion of forcing. Roughly, the dense sets will guarantee that if A meets these sets and we split A into two pieces, A0 and A1, in a simple way, and then switching the roles of A0 and A1 in all computations from A will produce an automorphism of the ideal of PTIMA-degrees below A. We force A0 and A1 to have different PTIME-Turing degree; this will then make the automorphism nontrivial. An appropriately generic set A is constructed using a priority argument. (shrink)

Let M be a countable recursively saturated model of Th(), and let GAut(M), considered as a topological group. We examine connections between initial segments of M and subgroups of G. In particular, for each of the following classes of subgroups HG, we give characterizations of the class of terms of the topological group structure of H as a subgroup of G. (a) for some (b) for some (c) for some (d) for some (Here, M(a) denotes the smallest M containing a, (...) , , and .). (shrink)

Section 1 is devoted to the study of countable recursively saturated models with an automorphism moving every non-algebraic point. We show that every countable theory has such a model and exhibit necessary and sufficient conditions for the existence of automorphisms moving all non-algebraic points. Furthermore we show that there are many complete theories with the property that every countable recursively saturated model has such an automorphism. In Section 2 we apply our main theorem from Section 1 to models of (...) Quine's set theory New Foundations (NF) to answer an old consistency question. If NF is consistent, then it has a model in which the standard natural numbers are a definable subclass N of the model's set of internal natural numbers Nn. In addition, in this model the class of wellfounded sets is exactly $\bigcup_{n\in \mathbb{N}}\mathscr{P}^n(\varnothing)$. (shrink)

Let M be a countable recursively saturated model of PA and H an open subgroup of G = Aut. We prove that I = sup {b ∈ M : ∀u < bfu = u and J = inf{b ∈ MH} may be invariant, i. e. fixed by all automorphisms of M.

We show that if M is a countable recursively saturated model of True Arithmetic, then G = Aut has nonmaximal open subgroups with unique extension to a maximal subgroup of Aut.

Continuing the earlier research in [14] we give some more information about nonmaximal open subgroups of G = Aut with unique maximal extension, where ℳ is a countable recursively saturated model of True Arithmetic.

We present an overview of the recent developments in the study of the classification problem for automorphisms of C*-algebras from the perspective of Borel complexity theory.

In any model theoretic logic, Beth’s definability property together with Feferman-Vaught’s uniform reduction property for pairs imply recursive compactness, and the existence of models with infinitely many automorphisms for sentences having infinite models. The stronger Craig’s interpolation property plus the uniform reduction property for pairs yield a recursive version of Ehrenfeucht-Mostowski’s theorem. Adding compactness, we obtain the full version of this theorem. Various combinations of definability and uniform reduction relative to other logics yield corresponding results on the existence of (...) non-rigid models. (shrink)

The relationship between ideals I of Turing degrees and groups of I-recursive automorphisms of the ordering on rationals is studied. We discuss the differences between such groups and the group of all automorphisms, prove that the isomorphism type of such a group completely defines the ideal I, and outline a general correspondence between principal ideals of Turing degrees and the first-order properties of such groups.

Péraire, Y., Infinitesimal approach to almost-automorphic functions, Annals of Pure and Applied Logic 63 283–297. Thanks to the use of ideal elements of several levels, we are able to give a compact topological characterization of almost-automorphic functions. This new characterization turns out to be equivalent to a geometrical one: the existence of a relatively dense group of “pointwise periods”. However, the more significant result obtained, in our opinion, is a very important lowering of the complexity in characterizations and proofs.

Let σ(U) denote the number of automorphisms of a model U of power ω1. We derive a necessary and sufficient condition in terms of trees for the existence of an U with $\omega_1 < \sigma(\mathfrak{U}) < 2^{\omega_1}$. We study the sufficiency of some conditions for σ(U) = 2ω1 . These conditions are analogous to conditions studied by D. Kueker in connection with countable models.

We show that a stable groupG satisfying certain commutator conditions is nilpotent. Furthermore, a soluble stable group with generically splitting automorphism of prime order is nilpotent-by-finite. In particular, a soluble stable group with a generic element of prime order is nilpotent-by-finite.

Let $\sigma$ denote the number of automorphisms of a model $\mathfrak{U}$ of power $\omega_1$. We derive a necessary and sufficient condition in terms of trees for the existence of an $\mathfrak{U}$ with $\omega_1 < \sigma < 2^{\omega_1}$. We study the sufficiency of some conditions for $\sigma = 2^{\omega_1}$. These conditions are analogous to conditions studied by D. Kueker in connection with countable models.

We give strengthened versions of the Herwig–Lascar and Hodkinson–Otto extension theorems for partial automorphisms of finite structures. Such strengthenings yield several combinatorial and group-theoretic consequences for homogeneous structures. For instance, we establish a coherent form of the extension property for partial automorphisms for certain Fraïssé classes. We deduce from these results that the isometry group of the rational Urysohn space, the automorphism group of the Fraïssé limit of any Fraïssé class that is the class of all ${\cal F}$-free (...) structures, and the automorphism group of any free homogeneous structure over a finite relational language all contain a dense locally finite subgroup. We also show that any free homogeneous structure admits ample generics. (shrink)