Related Research Articles
In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets, or its elements can be viewed as generalized truth values. It is also a special case of a De Morgan algebra and a Kleene algebra.
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory.
Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics. Its defining method can briefly be described as "going backwards from the theorems to the axioms", in contrast to the ordinary mathematical practice of deriving theorems from axioms. It can be conceptualized as sculpting out necessary conditions from sufficient ones.
In computability theory, a set S of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if:
In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time and correctly decides whether the number belongs to the set or not.
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable.
In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.
In computability theory, a Turing reduction from a decision problem to a decision problem is an oracle machine which decides problem given an oracle for . It can be understood as an algorithm that could be used to solve if it had available to it a subroutine for solving . The concept can be analogously applied to function problems.
In mathematics, the Fréchet filter, also called the cofinite filter, on a set is a certain collection of subsets of . A subset of belongs to the Fréchet filter if and only if the complement of in is finite. Any such set is said to be cofinite in , which is why it is alternatively called the cofinite filter on .
In computability theory, the Turing jump or Turing jump operator, named for Alan Turing, is an operation that assigns to each decision problem X a successively harder decision problem X′ with the property that X′ is not decidable by an oracle machine with an oracle for X.
In computability theory, a subset of the natural numbers is called simple if it is computably enumerable (c.e.) and co-infinite, but every infinite subset of its complement is not c.e.. Simple sets are examples of c.e. sets that are not computable.
In computability theory, productive sets and creative sets are types of sets of natural numbers that have important applications in mathematical logic. They are a standard topic in mathematical logic textbooks such as Soare (1987) and Rogers (1987).
In computability theory the Myhill isomorphism theorem, named after John Myhill, provides a characterization for two numberings to induce the same notion of computability on a set.
In computability theory and computational complexity theory, RE is the class of decision problems for which a 'yes' answer can be verified by a Turing machine in a finite amount of time. Informally, it means that if the answer to a problem instance is 'yes', then there is some procedure that takes finite time to determine this, and this procedure never falsely reports 'yes' when the true answer is 'no'. However, when the true answer is 'no', the procedure is not required to halt; it may go into an "infinite loop" for some 'no' cases. Such a procedure is sometimes called a semi-algorithm, to distinguish it from an algorithm, defined as a complete solution to a decision problem.
The low basis theorem is one of several basis theorems in computability theory, each of which showing that, given an infinite subtree of the binary tree , it is possible to find an infinite path through the tree with particular computability properties. The low basis theorem, in particular, shows that there must be a path which is low; that is, the Turing jump of the path is Turing equivalent to the halting problem .
In recursion theory, α recursion theory is a generalisation of recursion theory to subsets of admissible ordinals . An admissible set is closed under functions, where denotes a rank of Godel's constructible hierarchy. is an admissible ordinal if is a model of Kripke–Platek set theory. In what follows is considered to be fixed.
In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille whose 1937 paper first defined and constructed it, and after Richard Dedekind because its construction generalizes the Dedekind cuts used by Dedekind to construct the real numbers from the rational numbers. It is also called the completion by cuts or normal completion.
In computability theory, a Π01 class is a subset of 2ω of a certain form. These classes are of interest as technical tools within recursion theory and effective descriptive set theory. They are also used in the application of recursion theory to other branches of mathematics.
In computability theory and computational complexity theory, enumeration reducibility is a method of reduction that determines if there is some effective procedure for determining enumerability between sets of natural numbers. An enumeration in the context of e-reducibility is a listing of the elements in a particular set, or collection of items, though not necessarily ordered or complete.
In order theory and model theory, branches of mathematics, Cantor's isomorphism theorem states that every two countable dense unbounded linear orders are order-isomorphic. For instance, Minkowski's question-mark function produces an isomorphism between the numerical ordering of the rational numbers and the numerical ordering of the dyadic rationals.
References
- Friedberg, Richard M. (1958), "Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication", The Journal of Symbolic Logic, Association for Symbolic Logic, 23 (3): 309–316, doi:10.2307/2964290, JSTOR 2964290, MR 0109125, S2CID 25834814
- Myhill, John (1956), "Solution of a problem of Tarski", The Journal of Symbolic Logic, Association for Symbolic Logic, 21 (1): 49–51, doi:10.2307/2268485, JSTOR 2268485, MR 0075894, S2CID 19695459
- H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability, second edition 1987, MIT Press. ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1.
- Soare, Robert I. (1974), "Automorphisms of the lattice of recursively enumerable sets. I. Maximal sets", Annals of Mathematics , Second Series, Annals of Mathematics, 100 (1): 80–120, doi:10.2307/1970842, JSTOR 1970842, MR 0360235
 | This mathematical logic-related article is a stub. You can help Wikipedia by expanding it. |