Online research in philosophy

Two ways of describing a group are considered. 1. A group is finite-automaton presentable if its elements can be represented by strings over a finite alphabet, in such a way that the set of representing strings and the group operation can be recognized by finite automata. 2. An infinite f.g. group is quasi-finitely axiomatizable if there is a description consisting of a single first-order sentence, together with the information that the group is finitely generated. In the first part of the (...) paper we survey examples of FA-presentable groups, but also discuss theorems restricting this class. In the second part, we give examples of quasifinitely axiomatizable groups, consider the algebraic content of the notion, and compare it to the notion of a group which is a prime model. We also show that if a structure is bi-interpretable in parameters with the ring of integers, then it is prime and quasi-finitely axiomatizable. (shrink)

We compare various notions of algorithmic randomness. First we consider relativized randomness. A set is n-random if it is Martin-Löf random relative to θ(n−1). We show that a set is 2-random if and only if there is a constant c such that infinitely many initial segments x of the set are c-incompressible: C(x) ≥ |x| − c. The 'only if' direction was obtained independently by Joseph Miller. This characterization can be extended to the case of time-bounded C-complexity. Next we prove (...) some results on lowness. Among other things, we characterize the 2-random sets as those 1-random sets that are low for Chaitin's Ω. Also, 2-random sets form minimal pairs with 2-generic sets. The r.e. low for Ω sets coincide with the r.e. K-trivial ones. Finally we show that the notions of Martin-Löf randomness, recursive randomness, and Schnorr randomness can be separated in every high degree while the same notions coincide in every non-high degree. We make some remarks about hyperimmune-free and PA-complete degrees. (shrink)

We show that in the lattice E Π of Π 0 1 classes there are initial segments [ $\emptyset$ , P] = L(P) which are not Boolean algebras, but which have a decidable theory. In fact, we will construct for any finite distributive lattice L which satisfies the dual of the usual reduction property a Π 0 1 class P such that L is isomorphic to the lattice L(P)*, which is L(P), modulo finite differences. For the 2-element lattice, we obtain (...) a minimal class, first constructed by Cenzer, Downey, Jockusch and Shore in 1993. For the simplest new Π 0 1 class P constructed, P has a single, non-computable limit point and L(P)* has three elements, corresponding to $\emptyset$ , P and a minimal class P $_0 \subset$ P. The element corresponding to P 0 has no complement in the lattice. On the other hand, the theory of L(P) is shown to be decidable. A Π 0 1 class P is said to be decidable if it is the set of paths through a computable tree with no dead ends. We show that if P is decidable and has only finitely many limit points, then L(P)* is always a Boolean algebra. We show that if P is a decidable Π 0 1 class and L(P) is not a Boolean algebra, then the theory of L(P)interprets the theory of arithmetic and is therefore undecidable. (shrink)

We prove that each Σ 0 2 set which is hypersimple relative to $\emptyset$ ' is noncuppable in the structure of the Σ 0 2 enumeration degrees. This gives a connection between properties of Σ 0 2 sets under inclusion and and the Σ 0 2 enumeration degrees. We also prove that some low non-computably enumerable enumeration degree contains no set which is simple relative to $\emptyset$ '.

We show that the partial order of Σ0 3-sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. Odifreddi.