1976Journal of Symbolic LogicRequires access

Types of simple α-recursively enumerable sets

Manuel Lerman

Open publisher page 8 citations

Abstract

Let α be an admissible ordinal, and let (α) denote the lattice of α-r.e. sets, ordered by set inclusion. An α-r.e. set A is α*-finite if it is α-finite and has ordertype less than α* (the Σ1 projectum of α). An a-r.e. set S is simple if (the complement of S) is not α*-finite, but all the α-r.e. subsets of are α*-finite. Fixing a first-order language ℒ suitable for lattice theory (see [2, §1] for such a language), and noting that the α*-finite sets are exactly those elements of (α), all of whose α-r.e. subsets have complements in (α) (see [4, p. 356]), we see that the class of simple α-r.e. sets is definable in ℒ over (α). In [4, §6, (Q22)], we asked whether an admissible ordinal α exists for which all simple α-r.e. sets have the same 1-type. We were particularly interested in this question for α = ℵ1L (L is Gödel's universe of constructible sets). We will show that for all α which are regular cardinals of L (ℵ1L is, of course, such an α), there are simple α-r.e. sets with different 1-types. The sentence exhibited which differentiates between simple α-r.e. sets is not the first one which comes to mind. Using α = ω for intuition, one would expect any of the sentences “S is a maximal α-r.e. set”, “S is an r-maximal α-r.e. set”, or “S is a hyperhypersimple α-r.e. set” to differentiate between simple α-r.e. sets. However, if α > ω is a regular cardinal of L, there are no maximal, r-maximal, or hyperhypersimple α-r.e. sets (see [4, Theorem 4.11], [5, Theorem 5.1] and [1,Theorem 5.21] respectively). But another theorem of (ω) points the way.

About this research paper

What this paper is about

Let α be an admissible ordinal, and let (α) denote the lattice of α-r.e. sets, ordered by set inclusion. An α-r.e. set A is α*-finite if it is α-finite and has ordertype less than α* (the Σ1 projectum of α). An a-r.e. set S is simple if (the complement of S) is not α*-finite, but all the α-r.e. subsets of are α*-finite. Fixing a first-order language ℒ suitable for lattice theory (see [2, §1] for such a language), and noting that the α*-finite sets are exactly those elements of (α), all of whose α-r.e. subsets have complements in (α) (see [4, p. 356]), we see that the class of simple α-r.e. sets is definable in ℒ over (α). In [4, §6, (Q22)], we asked whether an admissible ordinal α exists for which all simple α-r.e. sets have the same 1-type. We were particularly interested in this question for α = ℵ1L (L is Gödel's universe of constructible sets). We will show that for all α which are regular cardinals of L (ℵ1L is, of course, such an α), there are simple α-r.e. sets with different 1-types. The sentence exhibited which differentiates between simple α-r.e. sets is not the first one which comes to mind. Using α = ω for intuition, one would expect any of the sentences “S is a maximal α-r.e. set”, “S is an r-maximal α-r.e. set”, or “S is a hyperhypersimple α-r.e. set” to differentiate between simple α-r.e. sets. However, if α > ω is a regular cardinal of L, there are no maximal, r-maximal, or hyperhypersimple α-r.e. sets (see [4, Theorem 4.11], [5, Theorem 5.1] and [1,Theorem 5.21] respectively). But another theorem of (ω) points the way.

Why it matters

OpenAlex reports 8 citations for this work. Citation counts describe recorded attention and do not establish research quality.

Key contribution

A contribution statement is not available in the OpenAlex record.

Method / approach

Method details are not available in the OpenAlex metadata.

Main findings

Findings are not separately available in the OpenAlex metadata.

Limitations

Limitations are not available in the OpenAlex metadata.

Applications

Application details are not available in the OpenAlex metadata.

Available abstract

Let α be an admissible ordinal, and let (α) denote the lattice of α-r.e. sets, ordered by set inclusion. An α-r.e. set A is α*-finite if it is α-finite and has ordertype less than α* (the Σ1 projectum of α). An a-r.e. set S is simple if (the complement of S) is not α*-finite, but all the α-r.e. subsets of are α*-finite. Fixing a first-order language ℒ suitable for lattice theory (see [2, §1] for such a language), and noting that the α*-finite sets are exactly those elements of (α), all of whose α-r.e. subsets have complements in (α) (see [4, p. 356]), we see that the class of simple α-r.e. sets is definable in ℒ over (α). In [4, §6, (Q22)], we asked whether an admissible ordinal α exists for which all simple α-r.e. sets have the same 1-type. We were particularly interested in this question for α = ℵ1L (L is Gödel's universe of constructible sets). We will show that for all α which are regular cardinals of L (ℵ1L is, of course, such an α), there are simple α-r.e. sets with different 1-types. The sentence exhibited which differentiates between simple α-r.e. sets is not the first one which comes to mind. Using α = ω for intuition, one would expect any of the sentences “S is a maximal α-r.e. set”, “S is an r-maximal α-r.e. set”, or “S is a hyperhypersimple α-r.e. set” to differentiate between simple α-r.e. sets. However, if α > ω is a regular cardinal of L, there are no maximal, r-maximal, or hyperhypersimple α-r.e. sets (see [4, Theorem 4.11], [5, Theorem 5.1] and [1,Theorem 5.21] respectively). But another theorem of (ω) points the way.

Key concepts: Recursively enumerable set, Mathematics, Recursively enumerable language, Combinatorics, Simple (philosophy), Complement (music), Order type, Finite set

Related papers

Back to paper searchBrowse research topicsOriginal source
Types of simple α-recursively enumerable sets — Research Paper | ScholarLens