By Peter Cholak

This paintings explores the relationship among the lattice of recursively enumerable (r.e.) units and the r.e. Turing levels. Cholak provides a degree-theoretic strategy for developing either automorphisms of the lattice of r.e. units and isomorphisms among a number of substructures of the lattice. as well as offering one other facts of Soare's Extension Theorem, this method is used to turn out a set of latest effects, together with: each non recursive r.e. set is automorphic to a excessive r.e. set; and for each non recursive r.e. set $A$ and for each excessive r.e. measure h there's an r.e. set $B$ in h such that $A$ and $B$ shape isomorphic primary filters within the lattice of r.e. units.

Show description

Read or Download Automorphisms of the Lattice of Recursively Enumerable Sets PDF

Similar logic books

Sets, logic & numbers

This article is designed to offer the coed a history within the foundations of algebra and research. The algebra of symbolic good judgment and the idea that of set are brought early within the textual content in order that the most definitional improvement of the advanced quantity procedure flows simply from a suite of postulates for the ordinary numbers.

Fuzzy Logic Foundations and Industrial Applications

Fuzzy common sense Foundations and business functions is an geared up edited selection of contributed chapters masking simple fuzzy common sense conception, fuzzy linear programming, and purposes. detailed emphasis has been given to assurance of contemporary examine effects, and to business purposes of fuzzy common sense.

Extra info for Automorphisms of the Lattice of Recursively Enumerable Sets

Sample text

If the system possesses So solution in some extension of M then it possesses a solution already in M. To prove this assertion one may use either purely algebraic means (theorem of Hilbert-Netto, elimination theory, specialization of transcendental parameters) or, again, a metamathematical argument which reduces the algebra required still further. The concept of an algebraically closed field is not complete in the ordinary sense. However, the concept of an algebraically closed field of given characteristic is complete also in the ordinary sense, by the result quoted at the end of the preceding section.

59 Enumeration in a Formal System An interesting question is to examine the possibility of enumerating in a system L all the elements of a model of L. This would clearly be a fertile ground for the operation of the diagonal argument. For instance, if the axiom of the system L is just the formula p given in the preceding section, then an enumeration of a model of L would be provided by (say) a function F such that: F(I)=A (A being the empty set), F(2 a)= f[F(a}], F(3 b)=g[F(b)], F(2 a . 5 C)=h[F(a), F(b), F(c)].

Note that this requirement is metamathematical, and is to be verified by a syntactic argument. The representation has the following two properties which are the formal equivalent in arithmetic of the informal requirement of computability. :a) can be proved in Zk (by means of a proof whose rank depends on the rank of t 1 ) . :a) are equal: only a finite number of values of t 1 are needed to calculate the value of 8(t1 ) . (ii) Given terms t1(a) and t of Zk there is a term t' of Zk such that x ~ t ~ t1(x) = 1'Jt'(x) can be proved in Zk' Informally speaking this means that to any MODELS, TRANSLATIONS AND INTERPRETATIONS 47 function t 1 of Zk there is a function 11t' which is ultimately zero, and has the property that E(11t,)=E(t1 ) .

Download PDF sample

Rated 4.98 of 5 – based on 12 votes