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
0.8070411086082458
0 references
0.8019323348999023
0 references
0.8005267381668091
0 references
0.7986162900924683
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