Universal recursion theoretic properties of r.e. preordered structures (Q3699683)
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 3924769
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Universal recursion theoretic properties of r.e. preordered structures |
scientific article; zbMATH DE number 3924769 |
Statements
Universal recursion theoretic properties of r.e. preordered structures (English)
0 references
1985
0 references
recursively enumerable preordering
0 references
prelattice
0 references
Boolean prealgebra
0 references
0.8111172318458557
0 references
0.7643194794654846
0 references
0.747859537601471
0 references
0.742336094379425
0 references
0.7336510419845581
0 references
A r.e. preordered structure is a system \(<\omega,\leq,f_ 1,...,f_ n>\) where \(\leq\) is a r.e. preordering and \(f_ 1,...,f_ n\) are recursive functions. A r.e. preordered structure \(\phi\) is said to be universal w.r. to a class \(\Sigma\) of structures of the same type as \(\phi\) iff for all \(\phi\) '\(\in \Sigma\) there is a recursive monomorphism h from \(\phi\) ' into \(\phi\). \(\phi\) is said recursively homogeneous universal w.r. to \(\Sigma\) iff for each \(\phi\) '\(\in \Sigma\) and for each monomorphism h from a finite substructure \(\phi\) '' of \(\phi\) ' into \(\phi\) there is a recursive monomorphism h' from \(\phi\) ' into \(\phi\) which extends h. Main results: 1) Every r.e. prelattice such that the equivalence associated with the preordering is precomplete, is recursively universal w.r. to the classes of decidable preorderings and of r.e. total preorderings. 2) Every r.e. Boolean prealgebra such that the equivalence classes of 0 and 1 are effectively inseparable is recursively universal w.r. to the class of r.e. preorderings and recursively homogeneous universal with respect to the class of r.e. distributive prelattices. (Any such algebra is recursively isomorphic to the Boolean prealgebra of PA sentences modulo provable equivalence). An easy consequence of 2) is the following: For every r.e. preordering \(<\omega,\preccurlyeq >\), there is a PA formula Ax such that for all m, n, \(m\preccurlyeq n\) iff \(\vdash_{PA}A\bar m\to A\bar n\); moreover, Ax can be chosen to be \(\Sigma^ 0_ 1\).
0 references