|
Craig's Theorem
In mathematical logic, Craig's theorem states that any recursively enumerable set of well-formed formulas of a first-order language is (primitively) recursively axiomatizable. This result is not related to the well-known Craig interpolation theorem, although both results are named after the same logician, William Craig. Recursive axiomatization Let A_1,A_2,\dots be an enumeration of the axioms of a recursively enumerable set T of first-order formulas. Construct another set T* consisting of :\underbrace_i for each positive integer ''i''. The deductive closures of T* and T are thus equivalent; the proof will show that T* is a recursive set. A decision procedure for T* lends itself according to the following informal reasoning. Each member of T* is either A_1 or of the form :\underbrace_j. Since each formula has finite length, it is checkable whether or not it is A_1 or of the said form. If it is of the said form and consists of ''j'' conjuncts, it is in T* if the (reoccurring) ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Mathematical Logic
Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics. Since its inception, mathematical logic has both contributed to and been motivated by the study of foundations of mathematics. This study began in the late 19th century with the development of axiomatic frameworks for geometry, arithmetic, and Mathematical analysis, analysis. In the early 20th century it was shaped by David Hilbert's Hilbert's program, program to prove the consistency of foundational theories. Results of Kurt Gödel, Gerhard Gentzen, and others provided partial resolution to the program, and clarified the issues involved in pr ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Recursively Enumerable Set
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: *There is an algorithm such that the set of input numbers for which the algorithm halts is exactly ''S''. Or, equivalently, *There is an enumeration algorithm, algorithm that enumerates the members of ''S''. That means that its output is simply a list of all the members of ''S'': ''s''1, ''s''2, ''s''3, ... . If ''S'' is infinite, this algorithm will run forever. The first condition suggests why the term ''semidecidable'' is sometimes used. More precisely, if a number is in the set, one can ''decide'' this by running the algorithm, but if the number is not in the set, the algorithm runs forever, and no information is returned. A set that is "completely decidable" is a computable set. The second condition suggests why ''computably enumerable'' is used. The abbreviations ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Well-formed Formula
In mathematical logic, propositional logic and predicate logic, a well-formed formula, abbreviated WFF or wff, often simply formula, is a finite sequence of symbols from a given alphabet that is part of a formal language. A formal language can be identified with the set of formulas in the language. A formula is a syntactic object that can be given a semantic meaning by means of an interpretation. Two key uses of formulas are in propositional logic and predicate logic. Introduction A key use of formulas is in propositional logic and predicate logic such as first-order logic. In those contexts, a formula is a string of symbols φ for which it makes sense to ask "is φ true?", once any free variables in φ have been instantiated. In formal logic, proofs can be represented by sequences of formulas with certain properties, and the final formula in the sequence is what is proven. Although the term "formula" may be used for written marks (for instance, on a piece of paper or ch ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
First-order Language
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists''"'' is a quantifier, while ''x'' is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic. A theory about a topic is usually a first-order logic together with a specified domain of discourse (over which the quantified variables range), finitely many functions from that domain to itself, finitely many predicates defined on that domain, and a set of ax ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Axiomatization
In mathematics and logic, an axiomatic system is any Set (mathematics), set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A Theory (mathematical logic), theory is a consistent, relatively-self-contained body of knowledge which usually contains an axiomatic system and all its derived theorems. An axiomatic system that is completely described is a special kind of formal system. A formal theory is an axiomatic system (usually formulated within model theory) that describes a set of sentences that is closed under logical implication. A formal proof is a complete rendition of a mathematical proof within a formal system. Properties An axiomatic system is said to be ''Consistency, consistent'' if it lacks contradiction. That is, it is impossible to derive both a statement and its negation from the system's axioms. Consistency is a key requirement for most axiomatic systems, as the presence of contradiction would allow any statement to ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Craig Interpolation
In mathematical logic, Craig's interpolation theorem is a result about the relationship between different logical theories. Roughly stated, the theorem says that if a formula φ implies a formula ψ, and the two have at least one atomic variable symbol in common, then there is a formula ρ, called an interpolant, such that every non-logical symbol in ρ occurs both in φ and ψ, φ implies ρ, and ρ implies ψ. The theorem was first proved for first-order logic by William Craig in 1957. Variants of the theorem hold for other logics, such as propositional logic. A stronger form of Craig's interpolation theorem for first-order logic was proved by Roger Lyndon in 1959; the overall result is sometimes called the Craig–Lyndon theorem. Example In propositional logic, let ::: \varphi = \lnot(P \land Q) \to (\lnot R \land Q) ::: \psi = (S \to P) \lor (S \to \lnot R) . Then \varphi tautologically implies \psi. This can be verified by writing \varphi in conjunctive normal form: : ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
William Craig (philosopher)
William Craig (November 13, 1918 – January 13, 2016) was an American academic and philosopher, who taught at the University of California, Berkeley, in Berkeley, California. His research interests included mathematical logic, and the philosophy of science, and he is best known for the Craig interpolation theorem. Biography William Craig was born in Nuremberg, German Empire, on November 13, 1918. He graduated from Harvard University with a Ph.D in 1951. He married Julia Rebecca Dwight Wilson and had four children: Ruth, Walter, Sarah, and Deborah. In 1959 he moved to UC Berkeley. He died on January 13, 2016, at the age of 97. Achievements Craig is particularly remembered in two theorems that bear his name: * the Craig interpolation theorem, and * Craig's theorem, also known as ''Craig's axiomatization theorem'' or ''Craig's reaxiomatization theorem''. See also * American philosophy * List of American philosophers This is a list of American philosophers; of philosophers who ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Deductive Closure
In mathematical logic, a set of logical formulae is deductively closed if it contains every formula that can be logically deduced from , formally: if always implies . If is a set of formulae, the deductive closure of is its smallest superset that is deductively closed. The deductive closure of a theory is often denoted or . This is a special case of the more general mathematical concept of closure — in particular, the deductive closure of is exactly the closure of with respect to the operation of logical consequence (). Examples In propositional logic, the set of all true propositions is deductively closed. This is to say that only true statements are derivable from other true statements. Epistemic closure In epistemology, many philosophers have and continue to debate whether particular subsets of propositions—especially ones ascribing knowledge or justification of a belief A belief is an attitude that something is the case, or that some propositi ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Primitive Recursive
In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined before entering the loop). Primitive recursive functions form a strict subset of those general recursive functions that are also total functions. The importance of primitive recursive functions lies in the fact that most computable functions that are studied in number theory (and more generally in mathematics) are primitive recursive. For example, addition and division, the factorial and exponential function, and the function which returns the ''n''th prime are all primitive recursive. In fact, for showing that a computable function is primitive recursive, it suffices to show that its time complexity is bounded above by a primitive recursive function of the input size. It is hence not that easy to devise a computable function that is ''n ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Kleene's T Predicate
In computability theory, the T predicate, first studied by mathematician Stephen Cole Kleene, is a particular set of triples of natural numbers that is used to represent computable functions within formal theories of arithmetic. Informally, the ''T'' predicate tells whether a particular computer program will halt when run with a particular input, and the corresponding ''U'' function is used to obtain the results of the computation if the program does halt. As with the smn theorem, the original notation used by Kleene has become standard terminology for the concept.The predicate described here was presented in (Kleene 1943) and (Kleene 1952), and this is what is usually called "Kleene's ''T'' predicate". (Kleene 1967) uses the letter ''T'' to describe a different predicate related to computable functions, but which cannot be used to obtain Kleene's normal form theorem. Definition The definition depends on a suitable Gödel numbering that assigns natural numbers to computable fu ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Carl Gustav Hempel
Carl Gustav "Peter" Hempel (January 8, 1905 – November 9, 1997) was a German writer, philosopher, logician, and epistemologist. He was a major figure in logical empiricism, a 20th-century movement in the philosophy of science. He is especially well known for his articulation of the deductive-nomological model of scientific explanation, which was considered the "standard model" of scientific explanation during the 1950s and 1960s. He is also known for the raven paradox (also known as "Hempel's paradox"). Education Hempel studied mathematics, physics and philosophy at the University of Göttingen and subsequently at the University of Berlin and the Heidelberg University. In Göttingen, he encountered David Hilbert and was impressed by his program attempting to base all mathematics on solid logical foundations derived from a limited number of axioms. After moving to Berlin, Hempel participated in a congress on scientific philosophy in 1929 where he met Rudolf Carnap and ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hilary Putnam
Hilary Whitehall Putnam (; July 31, 1926 – March 13, 2016) was an American philosopher, mathematician, and computer scientist, and a major figure in analytic philosophy in the second half of the 20th century. He made significant contributions to philosophy of mind, philosophy of language, philosophy of mathematics, and philosophy of science. Outside philosophy, Putnam contributed to mathematics and computer science. Together with Martin Davis he developed the Davis–Putnam algorithm for the Boolean satisfiability problem and he helped demonstrate the unsolvability of Hilbert's tenth problem. Putnam was known for his willingness to apply equal scrutiny to his own philosophical positions as to those of others, subjecting each position to rigorous analysis until he exposed its flaws. As a result, he acquired a reputation for frequently changing his positions. In philosophy of mind, Putnam is known for his argument against the type-identity of mental and physical states based on ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
