This page is based on this
Wikipedia article Text is available under the
CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.
First-order logic—also known as predicate 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" and 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.
Mathematical logic is a subfield of mathematics exploring the applications of formal logic to mathematics. It bears close connections to metamathematics, the foundations of mathematics, and theoretical computer science. The unifying themes in mathematical logic include the study of the expressive power of formal systems and the deductive power of formal proof systems.
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete.
In formal logic, a logical system has the soundness property if and only if every formula that can be proved in the system is logically valid with respect to the semantics of the system.
Finitism is a philosophy of mathematics that accepts the existence only of finite mathematical objects. It is best understood in comparison to the mainstream philosophy of mathematics where infinite mathematical objects are accepted as legitimate.
In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.
In mathematical logic, the Löwenheim–Skolem theorem, named for Leopold Löwenheim and Thoralf Skolem, states that if a countable first-order theory has an infinite model, then for every infinite cardinal number κ it has a model of size κ. The result implies that first-order theories are unable to control the cardinality of their infinite models, and that no first-order theory with an infinite model can have a unique model up to isomorphism.
Thoralf Albert Skolem was a Norwegian mathematician who worked in mathematical logic and set theory.
In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively determined. A theory in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory. Many important problems are undecidable, that is, it has been proven that no effective method for determining membership can exist for them.
In model theory, a branch of mathematical logic, two structures M and N of the same signature σ are called elementarily equivalent if they satisfy the same first-order σ-sentences.
In mathematical logic and philosophy, Skolem's paradox is a seeming contradiction that arises from the downward Löwenheim–Skolem theorem. Thoralf Skolem (1922) was the first to discuss the seemingly contradictory aspects of the theorem, and to discover the relativity of set-theoretic notions now known as non-absoluteness. Although it is not an actual antinomy like Russell's paradox, the result is typically called a paradox, and was described as a "paradoxical state of affairs" by Skolem.
In mathematical logic, an arithmetical set is a set of natural numbers that can be defined by a formula of first-order Peano arithmetic. The arithmetical sets are classified by the arithmetical hierarchy.
In mathematical logic, a non-standard model of arithmetic is a model of (first-order) Peano arithmetic that contains non-standard numbers. The term standard model of arithmetic refers to the standard natural numbers 0, 1, 2, …. The elements of any model of Peano arithmetic are linearly ordered and possess an initial segment isomorphic to the standard natural numbers. A non-standard model is one that has additional elements outside this initial segment. The construction of such models is due to Thoralf Skolem (1934).
In mathematical logic, a formula is said to be absolute if it has the same truth value in each of some class of structures. Theorems about absoluteness typically establish relationships between the absoluteness of formulas and their syntactic form.
In non-standard analysis, a hyperinteger n is a hyperreal number that is equal to its own integer part. A hyperinteger may be either finite or infinite. A finite hyperinteger is an ordinary integer. An example of an infinite hyperinteger is given by the class of the sequence (1, 2, 3, ...) in the ultrapower construction of the hyperreals.
In mathematical logic, a witness is a specific value t to be substituted for variable x of an existential statement of the form ∃x φ(x) such that φ(t) is true.
In additive number theory, the Skolem–Mahler–Lech theorem states that if a sequence of numbers is generated by a linear recurrence relation, then with finitely many exceptions the positions at which the sequence is zero form a regularly repeating pattern. More precisely, this set of positions can be decomposed into the union of a finite set and finitely many full arithmetic progressions. Here, an infinite arithmetic progression is full if there exist integers a and b such that the progression consists of all positive integers equal to b modulo a.
