Definable structures in the lattice of recursively enumerable sets (Q3701408)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3926894
Language Label Description Also known as
default for all languages
No label defined
    English
    Definable structures in the lattice of recursively enumerable sets
    scientific article; zbMATH DE number 3926894

      Statements

      Definable structures in the lattice of recursively enumerable sets (English)
      0 references
      1984
      0 references
      elementary definability
      0 references
      \({\mathcal E}^ n\) denote the lattice of \(\Sigma^ 0_ n\) sets, and (\({\mathcal E}^ m,{\mathcal E}^ n)\) (m\(\geq n)\) denote the lattice \({\mathcal E}^ m\) together with a unary predicate selecting out exactly the \(\Sigma^ 0_ n\) sets. If A and B are r.e. sets with \(A\subseteq B\) then L(A,B) denote the sublattice \(\{\) \(C: A\subseteq C\wedge C\subseteq B\}\) of \({\mathcal E}\). \(L_ r(A,B)\) denotes the family of elements of L(A,B) with a complement in L(A,B). A set \(X\in L(A,B)\) is called r- separable in L(A,B) if for all \(Y\in L(A,B)\) \(((X\cap Y)\setminus A=\emptyset \to \exists R\in L_ r(A,B)(X\subseteq R\wedge (R\cap Y)\setminus A=\emptyset)).\) Let Y be a small major subset of A. For \(X_ 1,X_ 2\in L(Y,A)\) we write \(X_ 1\subseteq_ rX_ 2\), if for all \(A_ i\), if \(X_ 1\cap A_ i\) is not r-separable in \(L(Y\cap A_ i,A_ i)\) then \(X_ 2\cap A_ i\) is not r-separable in \(L(Y\cap A_ i,A_ i)\). \(X_ 1\approx X_ 2\leftrightarrow X_ 1\subseteq_ rX_ 2\wedge X_ 2\subseteq_ rX_ 1.\) The author proves: \((L(Y,A)/\approx_ r,\subseteq_ r/\approx_ r)\cong {\mathcal E}^ 4.\) Corollaries. 1) Every lattice \({\mathcal E}^ n\) (n\(\geq 3)\) is elementarily definable with parameters in \({\mathcal E}\). 2) Every structure (\({\mathcal E}^{n+1},{\mathcal E}^ n)\) \((n=3\) or \(n\geq 5)\) is elementarily definable with parameters in \({\mathcal E}\).
      0 references
      0 references

      Identifiers