- Mathematics
- >
- Fields of mathematics
- >
- Mathematical logic

- Mathematics
- >
- Philosophy of mathematics
- >
- Mathematical logic

Type (model theory)

In model theory and related areas of mathematics, a type is an object that describes how a (real or possible) element or finite collection of elements in a mathematical structure might behave. More pr

Witness (mathematics)

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.

Theories of iterated inductive definitions

In set theory and logic, Buchholz's ID hierarchy is a hierarchy of subsystems of first-order arithmetic. The systems/theories are referred to as "the formal theories of ν-times iterated inductive defi

Hintikka set

In mathematical logic, a Hintikka set is a set of formulas whose elements satisfy the following properties: 1.
* An atom or its conjugate can appear in the set but not both, 2.
* If a formula in the

Quantum logic

In the mathematical study of logic and the physical analysis of quantum foundations, quantum logic is a set of rules for manipulation of propositions inspired by the structure of quantum theory. The f

Semicomputable function

In computability theory, a semicomputable function is a partial function that can be approximated either from above or from below by a computable function. More precisely a partial function is upper s

Indicator function

In mathematics, an indicator function or a characteristic function of a subset of a set is a function that maps elements of the subset to one, and all other elements to zero. That is, if A is a subset

Friedberg–Muchnik theorem

In mathematical logic, the Friedberg–Muchnik theorem is a theorem about Turing reductions that was proven independently by Albert Muchnik and Richard Friedberg in the middle of the 1950s. It is a more

Implementation of mathematics in set theory

This article examines the implementation of mathematical concepts in set theory. The implementation of a number of basic mathematical concepts is carried out in parallel in ZFC (the dominant set theor

Algorithmic transparency

Algorithmic transparency is the principle that the factors that influence the decisions made by algorithms should be visible, or transparent, to the people who use, regulate, and are affected by syste

Gödel numbering

In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. The concept was dev

Łoś–Vaught test

In model theory, a branch of mathematical logic, the Łoś–Vaught test is a criterion for a theory to be complete, unable to be augmented without becoming inconsistent. For theories in classical logic,

Ground expression

In mathematical logic, a ground term of a formal system is a term that does not contain any variables. Similarly, a ground formula is a formula that does not contain any variables. In first-order logi

Beta-model

In model theory, a mathematical discipline, a β-model (from the French "bon ordre", well-ordering) is a model which is correct about statements of the form "X is well-ordered". The term was introduced

Prime model

In mathematics, and in particular model theory, a prime model is a model that is as simple as possible. Specifically, a model is prime if it admits an elementary embedding into any model to which it i

Reverse mathematics

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 backwa

Löwenheim–Skolem theorem

In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem. The precise formulation is given below. I

Dedekind number

In mathematics, the Dedekind numbers are a rapidly growing sequence of integers named after Richard Dedekind, who defined them in 1897. The Dedekind number M(n) counts the number of monotone boolean f

Vacuous truth

In mathematics and logic, a vacuous truth is a conditional or universal statement (a universal statement that can be converted to a conditional statement) that is true because the antecedent cannot be

Residuated Boolean algebra

In mathematics, a residuated Boolean algebra is a residuated lattice whose lattice structure is that of a Boolean algebra. Examples include Boolean algebras with the monoid taken to be conjunction, th

Saturated model

In mathematical logic, and particularly in its subfield model theory, a saturated model M is one that realizes as many complete types as may be "reasonably expected" given its size. For example, an ul

Stratification (mathematics)

Stratification has several usages in mathematics.

Independence (mathematical logic)

In mathematical logic, independence is the unprovability of a sentence from other sentences. A sentence σ is independent of a given first-order theory T if T neither proves nor refutes σ; that is, it

Glossary of mathematical symbols

A mathematical symbol is a figure or a combination of figures that is used to represent a mathematical object, an action on mathematical objects, a relation between mathematical objects, or for struct

Enumeration reducibility

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 betwee

Lévy hierarchy

In set theory and mathematical logic, the Lévy hierarchy, introduced by Azriel Lévy in 1965, is a hierarchy of formulas in the formal language of the Zermelo–Fraenkel set theory, which is typically ca

Recursive definition

In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the set (Aczel 1977:740ff). Some examples of

Term (logic)

In mathematical logic, a term denotes a mathematical object while a formula denotes a mathematical fact. In particular, terms appear as components of a formula. This is analogous to natural language,

Impredicativity

In mathematics, logic and philosophy of mathematics, something that is impredicative is a self-referencing definition. Roughly speaking, a definition is impredicative if it invokes (mentions or quanti

Modal logic

Modal logic is a collection of formal systems developed to represent statements about necessity and possibility. It plays a major role in philosophy of language, epistemology, metaphysics, and natural

Residuated lattice

In abstract algebra, a residuated lattice is an algebraic structure that is simultaneously a lattice x ≤ y and a monoid x•y which admits operations x\z and z/y, loosely analogous to division or implic

Gödel's β function

In mathematical logic, Gödel's β function is a function used to permit quantification over finite sequences of natural numbers in formal theories of arithmetic. The β function is used, in particular,

Logical machine

A logical machine is a tool containing a set of parts that uses energy to perform formal logic operations. Early logical machines were mechanical devices that performed basic operations in Boolean log

Continuous predicate

Continuous predicate is a term coined by Charles Sanders Peirce (1839–1914) to describe a special type of relational predicate that results as the limit of a recursive process of hypostatic abstractio

Mathesis universalis

Mathesis universalis (from Greek: μάθησις, mathesis "science or learning", and Latin: universalis "universal") is a hypothetical universal science modelled on mathematics envisaged by Descartes and Le

Finitary relation

In mathematics, a finitary relation over sets X1, ..., Xn is a subset of the Cartesian product X1 × ⋯ × Xn; that is, it is a set of n-tuples (x1, ..., xn) consisting of elements xi in Xi. Typically, t

Formulario mathematico

Formulario Mathematico (Latino sine flexione: Formulation of mathematics) is a book by Giuseppe Peano which expresses fundamental theorems of mathematics in a symbolic language developed by Peano. The

Laver table

In mathematics, Laver tables (named after Richard Laver, who discovered them towards the end of the 1980s in connection with his works on set theory) are tables of numbers that have certain properties

Model complete theory

In model theory, a first-order theory is called model complete if every embedding of its models is an elementary embedding. Equivalently, every first-order formula is equivalent to a universal formula

Structuralism (philosophy of mathematics)

Structuralism is a theory in the philosophy of mathematics that holds that mathematical theories describe structures of mathematical objects. Mathematical objects are exhaustively defined by their pla

Rosser's trick

In mathematical logic, Rosser's trick is a method for proving Gödel's incompleteness theorems without the assumption that the theory being considered is ω-consistent (Smorynski 1977, p. 840; Mendelson

Glossary of Principia Mathematica

This is a list of the notation used in Alfred North Whitehead and Bertrand Russell's Principia Mathematica (1910–1913). The second (but not the first) edition of Volume I has a list of notation used a

Reverse Mathematics: Proofs from the Inside Out

Reverse Mathematics: Proofs from the Inside Out is a book by John Stillwell on reverse mathematics, the process of examining proofs in mathematics to determine which axioms are required by the proof.

Gödel's incompleteness theorems

Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of provability in formal axiomatic theories. These results, published by Kurt Gödel in 1931, a

Predicate (mathematical logic)

In logic, a predicate is a symbol which represents a property or a relation. For instance, in the first order formula , the symbol is a predicate which applies to the individual constant . Similarly,

Büchi-Elgot-Trakhtenbrot theorem

In formal language theory, the Büchi-Elgot-Trakhtenbrot theorem states that a language is regular if and only if it can be defined in monadic second-order logic (MSO): for every MSO formula, we can fi

Tautology (logic)

In mathematical logic, a tautology (from Greek: ταυτολογία) is a formula or assertion that is true in every possible interpretation. An example is "x=y or x≠y". Similarly, "either the ball is green, o

Structural induction

Structural induction is a proof method that is used in mathematical logic (e.g., in the proof of Łoś' theorem), computer science, graph theory, and some other mathematical fields. It is a generalizati

Completeness (logic)

In mathematical logic and metalogic, a formal system is called complete with respect to a particular property if every formula having the property can be derived using that system, i.e. is one of its

Rewriting

In mathematics, computer science, and logic, rewriting covers a wide range of methods of replacing subterms of a formula with other terms. Such methods may be achieved by rewriting systems (also known

T-schema

The T-schema ("truth schema", not to be confused with "Convention T") is used to check if an inductive definition of truth is valid, which lies at the heart of any realisation of Alfred Tarski's seman

Metalogic

Metalogic is the study of the metatheory of logic. Whereas logic studies how logical systems can be used to construct valid and sound arguments, metalogic studies the properties of logical systems. Lo

Hub labels

In computer science, hub labels or the hub-labelling algorithm is a method that consumes much fewer resources than the lookup table but is still extremely fast for finding the shortest paths between n

Cointerpretability

In mathematical logic, cointerpretability is a binary relation on formal theories: a formal theory T is cointerpretable in another such theory S, when the language of S can be translated into the lang

Mathematical proof

A mathematical proof is an inferential argument for a mathematical statement, showing that the stated assumptions logically guarantee the conclusion. The argument may use other previously established

Extension by definitions

In mathematical logic, more specifically in the proof theory of first-order theories, extensions by definitions formalize the introduction of new symbols by means of a definition. For example, it is c

Proof of impossibility

In mathematics, a proof of impossibility is a proof that demonstrates that a particular problem cannot be solved as described in the claim, or that a particular set of problems cannot be solved in gen

Curry's paradox

Curry's paradox is a paradox in which an arbitrary claim F is proved from the mere existence of a sentence C that says of itself "If C, then F", requiring only a few apparently innocuous logical deduc

Non-wellfounded mereology

In philosophy, specifically metaphysics, mereology is the study of parthood relationships. In mathematics and formal logic, wellfoundedness prohibits for any x. Thus non-wellfounded mereology treats t

Rules of passage (logic)

In mathematical logic, the rules of passage govern how quantifiers distribute over the basic logical connectives of first-order logic. The rules of passage govern the "passage" (translation) from any

Foundations of mathematics

Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosoph

Elementary definition

In mathematical logic, an elementary definition is a definition that can be made using only finitary first-order logic, and in particular without reference to set theory or using extensions such as pl

Hypostatic abstraction

Hypostatic abstraction in mathematical logic, also known as hypostasis or subjectal abstraction, is a formal operation that transforms a predicate into a relation; for example "Honey is sweet" is tran

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 ψ, an

Entscheidungsproblem

In mathematics and computer science, the Entscheidungsproblem (pronounced [ɛntˈʃaɪ̯dʊŋspʁoˌbleːm], German for 'decision problem') is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. T

On Formally Undecidable Propositions of Principia Mathematica and Related Systems

"Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I" ("On Formally Undecidable Propositions of Principia Mathematica and Related Systems I") is a paper in mathematica

Mivar-based approach

The Mivar-based approach is a mathematical tool for designing artificial intelligence (AI) systems. Mivar (Multidimensional Informational Variable Adaptive Reality) was developed by combining producti

Term algebra

In universal algebra and mathematical logic, a term algebra is a freely generated algebraic structure over a given signature. For example, in a signature consisting of a single binary operation, the t

Finitary

In mathematics and logic, an operation is finitary if it has finite arity, i.e. if it has a finite number of input values. Similarly, an infinitary operation is one with an infinite number of input va

Interior algebra

In abstract algebra, an interior algebra is a certain type of algebraic structure that encodes the idea of the topological interior of a set. Interior algebras are to topology and the modal logic S4 w

Elementary theory

In mathematical logic, an elementary theory is a theory that involves axioms using only finitary first-order logic, without reference to set theory or using any axioms which have consistency strength

Schröder–Bernstein property

A Schröder–Bernstein property is any mathematical property that matches the following pattern If, for some mathematical objects X and Y, both X is similar to a part of Y and Y is similar to a part of

Algorithmic technique

In mathematics and computer science, an algorithmic technique is a general approach for implementing a process or computation.

Successor function

In mathematics, the successor function or successor operation sends a natural number to the next one. The successor function is denoted by S, so S(n) = n + 1. For example, S(1) = 2 and S(2) = 3. The s

Notre Dame Journal of Formal Logic

The Notre Dame Journal of Formal Logic is a quarterly peer-reviewed scientific journal covering the foundations of mathematics and related fields of mathematical logic, as well as philosophy of mathem

Regular numerical predicate

In computer science and mathematics, more precisely in automata theory, model theory and formal language, a regular numerical predicate is a kind of relation over integers. Regular numerical predicate

Institute of Mathematical Logic and Fundamental Research

No description available.

Tarski's undefinability theorem

Tarski's undefinability theorem, stated and proved by Alfred Tarski in 1933, is an important limitative result in mathematical logic, the foundations of mathematics, and in formal semantics. Informall

Class logic

Class logic is a logic in its broad sense, whose objects are called classes. In a narrower sense, one speaks of a class logic only if classes are described by a property of their elements. This class

Algebraic theory

Informally in mathematical logic, an algebraic theory is a theory that uses axioms stated entirely in terms of equations between terms with free variables. Inequalities and quantifiers are specificall

List of first-order theories

In first-order logic, a first-order theory is given by a set of axioms in somelanguage. This entry lists some of the more common examples used in model theory and some of their properties.

Ordinal logic

In mathematics, ordinal logic is a logic associated with an ordinal number by recursively adding elements to a sequence of previous logics. The concept was introduced in 1938 by Alan Turing in his PhD

Lindström's theorem

In mathematical logic, Lindström's theorem (named after Swedish logician Per Lindström, who published it in 1969) states that first-order logic is the strongest logic (satisfying certain conditions, e

Complete theory

In mathematical logic, a theory is complete if it is consistent and for every closed formula in the theory's language, either that formula or its negation is provable. That is, for every sentence the

Axiom

An axiom, postulate, or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Ancient Greek word ἀξίω

Semantics of logic

In logic, the semantics of logic or formal semantics is the study of the semantics, or interpretations, of formal and (idealizations of) natural languages usually trying to capture the pre-theoretic n

End extension

In model theory and set theory, which are disciplines within mathematics, a model of some axiom system of set theory in the language of set theory is an end extension of , in symbols , if 1.
* is a s

Rathjen's psi function

In mathematics, Rathjen's psi function is an ordinal collapsing function developed by Michael Rathjen. It collapses weakly Mahlo cardinals to generate large countable ordinals. A weakly Mahlo cardinal

Logical equivalence

In logic and mathematics, statements and are said to be logically equivalent if they have the same truth value in every model. The logical equivalence of and is sometimes expressed as , , , or , depen

Surreal number

In mathematics, the surreal number system is a totally ordered proper class containing the real numbers as well as infinite and infinitesimal numbers, respectively larger or smaller in absolute value

LowerUnivalents

In proof compression, an area of mathematical logic, LowerUnivalents is an algorithm used for the compression of proofs. LowerUnivalents is a generalised algorithm of the LowerUnits, and it is able to

Outline of logic

Logic is the formal science of using reason and is considered a branch of both philosophy and mathematics and to a lesser extent computer science. Logic investigates and classifies the structure of st

Turnstile (symbol)

In mathematical logic and computer science the symbol has taken the name turnstile because of its resemblance to a typical turnstile if viewed from above. It is also referred to as tee and is often re

Extensions of First Order Logic

Extensions of First Order Logic is a book on mathematical logic. It was written by María Manzano, and published in 1996 by the Cambridge University Press as volume 19 of their book series Cambridge Tr

Fragment (logic)

In mathematical logic, a fragment of a logical language or theory is a subset of this logical language obtained by imposing syntactical restrictions on the language. Hence, the well-formed formulae of

Equiconsistency

In mathematical logic, two theories are equiconsistent if the consistency of one theory implies the consistency of the other theory, and vice versa. In this case, they are, roughly speaking, "as consi

Set theory

Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as

Double turnstile

In logic, the symbol ⊨, ⊧ or is called the double turnstile. It is often read as "entails", "models", "is a semantic consequence of" or "is stronger than". It is closely related to the turnstile symbo

Monadic second-order logic

In mathematical logic, monadic second-order logic (MSO) is the fragment of second-order logic where the second-order quantification is limited to quantification over sets. It is particularly important

Truth predicate

In formal theories of truth, a truth predicate is a fundamental concept based on the sentences of a formal language as interpreted logically. That is, it formalizes the concept that is normally expres

List of statements independent of ZFC

The mathematical statements discussed below are provably independent of ZFC (the canonical axiomatic set theory of contemporary mathematics, consisting of the Zermelo–Fraenkel axioms plus the axiom of

Diagram (mathematical logic)

In model theory, a branch of mathematical logic, the diagram of a structure is a simple but powerful concept for proving useful properties of a theory, for example the amalgamation property and the jo

Entitative graph

An entitative graph is an element of the diagrammatic syntax for logic that Charles Sanders Peirce developed under the name of qualitative logic beginning in the 1880s, taking the coverage of the form

Strength (mathematical logic)

The relative strength of two systems of formal logic can be defined via model theory. Specifically, a logic is said to be as strong as a logic if every elementary class in is an elementary class in .

De Bruijn Factor

The de Bruijn Factor is a measure of how much harder it is to write a formal mathematical proof instead of an informal one. It was created by the Dutch computer-proof pioneer Nicolaas Govert de Bruijn

Peirce's law

In logic, Peirce's law is named after the philosopher and logician Charles Sanders Peirce. It was taken as an axiom in his first axiomatisation of propositional logic. It can be thought of as the law

Model-theoretic grammar

Model-theoretic grammars, also known as constraint-based grammars, contrast with generative grammars in the way they define sets of sentences: they state constraints on syntactic structure rather than

Logical graph

A logical graph is a special type of diagrammatic structure in any one of several systems of graphical syntax that Charles Sanders Peirce developed for logic. In his papers on qualitative logic, entit

Categorical theory

In mathematical logic, a theory is categorical if it has exactly one model (up to isomorphism). Such a theory can be viewed as defining its model, uniquely characterizing its structure. In first-order

Special case

In logic, especially as applied in mathematics, concept A is a special case or of concept B precisely if every instance of A is also an instance of B but not vice versa, or equivalently, if B is a gen

Bunched logic

Bunched logic is a variety of substructural logic proposed by Peter O'Hearn and . Bunched logic provides primitives for reasoning about resource composition, which aid in the compositional analysis of

Free choice inference

Free choice is a phenomenon in natural language where a linguistic disjunction appears to receive a logical conjunctive interpretation when it interacts with a modal operator. For example, the followi

Proof-theoretic semantics

Proof-theoretic semantics is an approach to the semantics of logic that attempts to locate the meaning of propositions and logical connectives not in terms of interpretations, as in Tarskian approache

Mereology

In logic, philosophy and related fields, mereology (from Greek μέρος 'part' (root: μερε-, mere-, 'part') and the suffix -logy, 'study, discussion, science') is the study of parts and the wholes they f

Löb's theorem

In mathematical logic, Löb's theorem states that in Peano arithmetic (PA) (or any formal system including PA), for any formula P, if it is provable in PA that "if P is provable in PA then P is true",

Non-standard model of arithmetic

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

Simplification of disjunctive antecedents

In formal semantics and philosophical logic, simplification of disjunctive antecedents (SDA) is the phenomenon whereby a disjunction in the antecedent of a conditional appears to distribute over the c

Contraposition

In logic and mathematics, contraposition refers to the inference of going from a conditional statement into its logically equivalent contrapositive, and an associated proof method known as proof by co

Classical mathematics

In the foundations of mathematics, classical mathematics refers generally to the mainstream approach to mathematics, which is based on classical logic and ZFC set theory. It stands in contrast to othe

Formal grammar

In formal language theory, a grammar (when the context is not given, often called a formal grammar for clarity) describes how to form strings from a language's alphabet that are valid according to the

Superposition calculus

The superposition calculus is a calculus for reasoning in equational first-order logic. It was developed in the early 1990s and combines concepts from first-order resolution with ordering-based equali

List of mathematical logic topics

This is a list of mathematical logic topics, by Wikipedia page. For traditional syllogistic logic, see the list of topics in logic. See also the list of computability and complexity topics for more th

Knuth's Simpath algorithm

Simpath is an algorithm introduced by Donald Knuth that constructs a zero-suppressed decision diagram (ZDD) representing all simple paths between two vertices in a given graph.

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

Abstract model theory

In mathematical logic, abstract model theory is a generalization of model theory that studies the general properties of extensions of first-order logic and their models. Abstract model theory provides

Grundlagen der Mathematik

Grundlagen der Mathematik (English: Foundations of Mathematics) is a two-volume work by David Hilbert and Paul Bernays. Originally published in 1934 and 1939, it presents fundamental mathematical idea

Compactness theorem

In mathematical logic, the compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of it has a model. This theorem is an important tool in model t

Herbrand structure

In first-order logic, a Herbrand structure S is a structure over a vocabulary σ that is defined solely by the syntactical properties of σ. The idea is to take the symbols of terms as their values, e.g

O-minimal theory

In mathematical logic, and more specifically in model theory, an infinite structure (M,<,...) which is totally ordered by < is called an o-minimal structure if and only if every definable subset X ⊂ M

Gödel logic

In mathematical logic, a first-order Gödel logic is a member of a family of finite- or infinite-valued logics in which the sets of truth values V are closed subsets of the interval [0,1] containing bo

Variable (mathematics)

In mathematics, a variable (from Latin variabilis, "changeable") is a symbol and placeholder for any mathematical object. In particular, a variable may represent a number, a vector, a matrix, a functi

Elementary sentence

In mathematical logic, an elementary sentence is one that is stated using only finitary first-order logic, without reference to set theory or using any axioms which have consistency strength equal to

Proof theory

Proof theory is a major branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as in

Lindenbaum's lemma

In mathematical logic, Lindenbaum's lemma, named after Adolf Lindenbaum, states that any consistent theory of predicate logic can be extended to a complete consistent theory. The lemma is a special ca

Fraïssé limit

In mathematical logic, specifically in the discipline of model theory, the Fraïssé limit (also called the Fraïssé construction or Fraïssé amalgamation) is a method used to construct (infinite) mathema

Institutional model theory

In mathematical logic, institutional model theory generalizes a large portion of first-order model theory to an arbitrary logical system.

Truth-value semantics

In formal semantics, truth-value semantics is an alternative to Tarskian semantics. It has been primarily championed by Ruth Barcan Marcus, H. Leblanc, and J. Michael Dunn and Nuel Belnap. It is also

Boolean differential calculus

Boolean differential calculus (BDC) (German: Boolescher Differentialkalkül (BDK)) is a subject field of Boolean algebra discussing changes of Boolean variables and Boolean functions. Boolean different

Relation algebra

In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is

Substructure (mathematics)

In mathematical logic, an (induced) substructure or (induced) subalgebra is a structure whose domain is a subset of that of a bigger structure, and whose functions and relations are restricted to the

Pure inductive logic

Pure inductive logic (PIL) is the area of mathematical logic concerned with the philosophical and mathematical foundations of probabilistic inductive reasoning. It combines classical predicate logic a

Absoluteness

In mathematical logic, a formula is said to be absolute to some class of structures (also called models), if it has the same truth value in each of the members of that class. One can also speak of abs

Cyclic negation

In many-valued logic with linearly ordered truth values, cyclic negation is a unary truth function that takes a truth value n and returns n − 1 as value if n is not the lowest value; otherwise it retu

Turing's proof

Turing's proof is a proof by Alan Turing, first published in January 1937 with the title "On Computable Numbers, with an Application to the Entscheidungsproblem". It was the second proof (after Church

Term logic

In philosophy, term logic, also known as traditional logic, syllogistic logic or Aristotelian logic, is a loose name for an approach to formal logic that began with Aristotle and was developed further

Beth definability

In mathematical logic, Beth definability is a result that connects implicit definability of a property to its explicit definability. Specifically Beth definability states that the two senses of defina

Cantor's paradox

In set theory, Cantor's paradox states that there is no set of all cardinalities. This is derived from the theorem that there is no greatest cardinal number. In informal terms, the paradox is that the

Mathematical logic

Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly address

Algorithm

In mathematics and computer science, an algorithm (/ˈælɡərɪðəm/) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algori

Hilbert–Bernays provability conditions

In mathematical logic, the Hilbert–Bernays provability conditions, named after David Hilbert and Paul Bernays, are a set of requirements for formalized provability predicates in formal theories of ari

Barwise compactness theorem

In mathematical logic, the Barwise compactness theorem, named after Jon Barwise, is a generalization of the usual compactness theorem for first-order logic to a certain class of infinitary languages.

Kruskal's tree theorem

In mathematics, Kruskal's tree theorem states that the set of finite trees over a well-quasi-ordered set of labels is itself well-quasi-ordered under homeomorphic embedding.

Extension by new constant and function names

In mathematical logic, a theory can be extended withnew constants or function names under certain conditions with assurance that the extension will introduceno contradiction. Extension by definitions

Algebraic semantics (mathematical logic)

In mathematical logic, algebraic semantics is a formal semantics based on algebras studied as part of algebraic logic. For example, the modal logic S4 is characterized by the class of topological bool

Algebraic sentence

In mathematical logic, an algebraic sentence is one that can be stated using only equations between terms with free variables. Inequalities and quantifiers are specifically disallowed. Sentential logi

WFF 'N PROOF

WFF 'N PROOF is a game of modern logic, developed to teach principles of symbolic logic. It was developed by Layman E. Allen in 1962 a former professor of Yale Law School and the University of Michiga

Equality (mathematics)

In mathematics, equality is a relationship between two quantities or, more generally two mathematical expressions, asserting that the quantities have the same value, or that the expressions represent

Solèr's theorem

In mathematics, Solèr's theorem is a result concerning certain infinite-dimensional vector spaces. It states that any orthomodular form that has an infinite orthonormal sequence is a Hilbert space ove

Algebraic definition

In mathematical logic, an algebraic definition is one that can be given using only equations between terms with free variables. Inequalities and quantifiers are specifically disallowed. Saying that a

Converse relation

In mathematics, the converse relation, or transpose, of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relat

Robinson's joint consistency theorem

Robinson's joint consistency theorem is an important theorem of mathematical logic. It is related to Craig interpolation and Beth definability. The classical formulation of Robinson's joint consistenc

Hilbert's program

In mathematics, Hilbert's program, formulated by German mathematician David Hilbert in the early part of the 20th century, was a proposed solution to the foundational crisis of mathematics, when early

Game semantics

Game semantics (German: dialogische Logik, translated as dialogical logic) is an approach to formal semantics that grounds the concepts of truth or validity on game-theoretic concepts, such as the exi

König's theorem (set theory)

In set theory, König's theorem states that if the axiom of choice holds, I is a set, and are cardinal numbers for every i in I, and for every i in I, then The sum here is the cardinality of the disjoi

Subitizing

Subitizing is the rapid, accurate, and confident judgments of numbers performed for small numbers of items. The term was coined in 1949 by E.L. Kaufman et al., and is derived from the Latin adjective

Semantic theory of truth

A semantic theory of truth is a theory of truth in the philosophy of language which holds that truth is a property of sentences.

Model theory

In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and

Elementary equivalence

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. If N is a substruct

List of mathematical symbols by subject

The following list of mathematical symbols by subject features a selection of the most common symbols used in modern mathematical notation within formulas, grouped by mathematical topic. As it is impo

Kripke semantics

Kripke semantics (also known as relational semantics or frame semantics, and often confused with possible world semantics) is a formal semantics for non-classical logic systems created in the late 195

Slicing the Truth

Slicing the Truth: On the Computability Theoretic and Reverse Mathematical Analysis of Combinatorial Principles is a book on reverse mathematics in combinatorics, the study of the axioms needed to pro

Enumeration

An enumeration is a complete, ordered listing of all the items in a collection. The term is commonly used in mathematics and computer science to refer to a listing of all of the elements of a set. The

Peano axioms

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 Giusepp

Formal calculation

In mathematical logic, a formal calculation, or formal operation, is a calculation that is systematic but without a rigorous justification. It involves manipulating symbols in an expression using a ge

Literal (mathematical logic)

In mathematical logic, a literal is an atomic formula (also known as an atom or prime formula) or its negation. The definition mostly appears in proof theory (of classical logic), e.g. in conjunctive

S2S (mathematics)

No description available.

Conservative extension

In mathematical logic, a conservative extension is a supertheory of a theory which is often convenient for proving theorems, but proves no new theorems about the language of the original theory. Simil

Abstract logic

In mathematical logic, an abstract logic is a formal system consisting of a class of sentences and a satisfaction relation with specific properties related to occurrence, expansion, isomorphism, renam

Equational logic

First-order equational logic consists of quantifier-free terms of ordinary first-order logic, with equality as the only predicate symbol. The model theory of this logic was developed into universal al

Universe (mathematics)

In mathematics, and particularly in set theory, category theory, type theory, and the foundations of mathematics, a universe is a collection that contains all the entities one wishes to consider in a

Ludics

In proof theory, ludics is an analysis of the principles governing inference rules of mathematical logic. Key features of ludics include notion of compound connectives, using a technique known as focu

Counting

Counting is the process of determining the number of elements of a finite set of objects, i.e., determining the size of a set. The traditional way of counting consists of continually increasing a (men

Proof sketch for Gödel's first incompleteness theorem

This article gives a sketch of a proof of Gödel's first incompleteness theorem. This theorem applies to any formal theory that satisfies certain technical hypotheses, which are discussed as needed dur

Friedman's SSCG function

In mathematics, a simple subcubic graph (SSCG) is a finite simple graph in which each vertex has degree at most three. Suppose we have a sequence of simple subcubic graphs G1, G2, ... such that each g

Diagonal lemma

In mathematical logic, the diagonal lemma (also known as diagonalization lemma, self-reference lemma or fixed point theorem) establishes the existence of self-referential sentences in certain formal t

Proposition

In logic and linguistics, a proposition is the meaning of a declarative sentence. In philosophy, "meaning" is understood to be a non-linguistic entity which is shared by all sentences with the same me

Computability theory

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 funct

Timeline of mathematical logic

A timeline of mathematical logic. See also History of logic.

Cartesian monoid

A Cartesian monoid is a monoid, with additional structure of pairing and projection operators. It was first formulated by Dana Scott and Joachim Lambek independently.

Coherent space

In proof theory, a coherent space (also coherence space) is a concept introduced in the semantic study of linear logic. Let a set C be given. Two subsets S,T ⊆ C are said to be orthogonal, written S ⊥

Herbrand interpretation

In mathematical logic, a Herbrand interpretation is an interpretation in which all constants and function symbols are assigned very simple meanings. Specifically, every constant is interpreted as itse

Laws of Form

Laws of Form (hereinafter LoF) is a book by G. Spencer-Brown, published in 1969, that straddles the boundary between mathematics and philosophy. LoF describes three distinct logical systems:
* The "p

Truth function

In logic, a truth function is a function that accepts truth values as input and produces a unique truth value as output. In other words: The input and output of a truth function are all truth values;

Infinitesimal

In mathematics, an infinitesimal number is a quantity that is closer to zero than any standard real number, but that is not zero. The word infinitesimal comes from a 17th-century Modern Latin coinage

Structure (mathematical logic)

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it. Universal algebra studies structures that g

Ultraproduct

The ultraproduct is a mathematical construction that appears mainly in abstract algebra and mathematical logic, in particular in model theory and set theory. An ultraproduct is a quotient of the direc

Definable set

In mathematical logic, a definable set is an n-ary relation on the domain of a structure whose elements satisfy some formula in the first-order language of that structure. A set can be defined with or

Archive for Mathematical Logic

Archive for Mathematical Logic is a peer-reviewed mathematics journal published by Springer Science+Business Media. It was established in 1950 and publishes articles on mathematical logic.

List of Hilbert systems

This article contains a list of sample Hilbert-style deductive systems for propositional logics.

Original proof of Gödel's completeness theorem

The proof of Gödel's completeness theorem given by Kurt Gödel in his doctoral dissertation of 1929 (and a shorter version of the proof, published as an article in 1930, titled "The completeness of the

Contradiction

In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a gen

Metamathematics

Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories. Emphasis on metamath

© 2023 Useful Links.