Search
Search Results
-
Computably Enumerable and Arithmetic Sets
We introduce the computably enumerable sets and the arithmetic sets and show that the form a hierarchy. These results, and the existence of...
-
On Proofs of Properties of Semirecursive Sets
In this paper, we present proofs of properties of semirecursive sets based directly on the definition of these sets and on the recursiveness of...
-
Isolation from Side and Cone Avoidance in the 2-Computably Enumerable wtt-Degrees
We consider isolation from side in the structure of 2-computably enumerable wtt -degrees. Intuitively, a 2-computably enumerable degree d is isolated...
-
Some Properties of the Upper Semilattice of Computable Families of Computably Enumerable Sets
We look at specific features of the algebraic structure of an upper semilattice of computable families of computably enumerable sets in Ω. It is...
-
Incompleteness of Arithmetic from the Viewpoint of Diophantine Set Theory
The authors analyze Diophantine sets and show that all recursively enumerable sets are Diophantine. Based on the classical results from the theory of...
-
Cup** Computably Enumerable Degrees Simultaneously
In this paper, we will construct for each \(n\ge 1\)...
-
Inductively Defined Sets; Structural Induction
This chapter introduces a generalisation of the definitions by induction (recursion) of the last section. Here we define sets inductively, not...
-
Turing Reducibility
Turing reducibility is introduced as a notion of relative complexity and we study the relationship between the arithmetic hierarchy and the jump...
-
Index Sets for Classes of Positive Preorders
We study the complexity of index sets with respect to a universal computable numbering of the family of all positive preorders. Let ≤ c be computable...
-
Generic Amplification of Recursively Enumerable Sets
Generic amplification is a method that allows algebraically undecidable problems to generate problems undecidable for almost all inputs. It is proved...
-
Cohesive powers of structures
A cohesive power of a structure is an effective analog of the classical ultrapower of a structure. We start with a computable structure, and consider...
-
Reducts of Relation Algebras: The Aspects of Axiomatisability and Finite Representability
In this paper, we show that the class of representable residuated semigroups has the finite representation property. That is, every finite...
-
-
Gödel’s Incompleteness Theorems
Gödel’s Incompleteness Theorems are proved. We show that the sets definable in the natural numbers are exactly the arithmetic sets. The Arithmetized...
-
Computability Theory
Computability theory is the mathematical theory of algorithms, which explores the power and limitations of computation. Classical computability...
-
Prerequisites: Sets, Algebraic Systems and Classical Analysis
This chapter assembles together some basic concepts and results of set theset theory, modern algebra, classical analysis and also of category theory...
-
Computability Theory
Computability theory is the mathematical theory of algorithms, which explores the power and limitations of computation. Classical computability...
-
Quantified block gluing for multidimensional subshifts of finite type: aperiodicity and entropy
It is possible to extend the notion of block gluing for subshifts studied in [PS15] adding a gap function which gives the distance which allows to...
-
Separable Algorithmic Representations of Classical Systems and their Applications
The main results of the theory of separable algorithmic representations of classical algebraic systems are presented. The most important classes of...
-
Reverse Mathematics
Reverse mathematics is a new take on an old idea: asking which axioms are necessary to prove a given theorem. This question was first asked about the...