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
      0 references
      0 references
      1985
      0 references
      recursively enumerable preordering
      0 references
      prelattice
      0 references
      Boolean prealgebra
      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

      Identifiers