354 relations: Ackermann function, ACL2, AD+, Affine logic, Age (model theory), Alan Turing, Aleph number, Alfred Tarski, Algebra of sets, Algebraic logic, Algorithm, Alonzo Church, Alternative set theory, Amalgamation property, Analytic proof, Analytic set, Analytical hierarchy, Arithmetical hierarchy, Arithmetical set, Arithmetization of analysis, Atomic model (mathematical logic), Automated Mathematician, Automated theorem proving, Ax–Grothendieck theorem, Ax–Kochen theorem, Axiom of choice, Axiom of countable choice, Axiom of dependent choice, Axiom of determinacy, Axiom of projective determinacy, Axiom of real determinacy, Axiom schema, Axiomatic system, Łoś–Vaught test, Back-and-forth method, Barwise compactness theorem, Begriffsschrift, Beth number, Boolean algebra, Boolean algebra (structure), Boolean-valued model, Borel equivalence relation, Burali-Forti paradox, C-minimal theory, Calculus of constructions, Cantor's diagonal argument, Cantor's theorem, Cardinal number, Cardinality, Cartesian product, ..., Categorical logic, Church–Rosser theorem, Church–Turing thesis, Cirquent calculus, Class (set theory), Cointerpretability, Combinatory logic, Compactness theorem, Complement (set theory), Complete Boolean algebra, Complete theory, Complexity class, Computability logic, Computability theory, Computable function, Computable measure theory, Computable model theory, Computation, Computational complexity theory, Conservative extension, Consistency, Constructible universe, Constructive analysis, Constructive proof, Continuum (set theory), Continuum hypothesis, Cook–Levin theorem, Coq, Countable set, Criticism of non-standard analysis, Curry–Howard correspondence, Cut-elimination theorem, Decidability (logic), Decision problem, Deduction theorem, Definable real number, Definable set, Descriptive complexity theory, Descriptive set theory, Determinacy, Diagonal lemma, Dialectica space, Differentially closed field, Diophantine set, Direct proof, E theorem prover, Effective results in number theory, Ehrenfeucht–Fraïssé game, Element (mathematics), Elementary Calculus: An Infinitesimal Approach, Elementary class, Elementary equivalence, Emil Leon Post, Empty set, Entscheidungsproblem, Epsilon-induction, Erdős cardinal, Eurisko, Existence theorem, Existentially closed model, Exponential field, Exponential hierarchy, Extendible cardinal, Finite model theory, Finitism, First-order logic, Forcing (mathematics), Forking extension, Formal language, Formal system, Foundations of mathematics, Function (mathematics), Functional predicate, Fuzzy set, Gandalf (theorem prover), Gödel's completeness theorem, Gödel's incompleteness theorems, General frame, Gentzen's consistency proof, Georg Cantor's first set theory article, Gerhard Gentzen, Giuseppe Peano, Halting problem, Hartogs number, Haskell Curry, Herbrand interpretation, Herbrand structure, Higher-order logic, Hilbert's program, History of topos theory, HOL (proof assistant), Hrushovski construction, Huge cardinal, Hypercomputation, Hyperinteger, Hyperreal number, Imaginary element, Impredicativity, Inaccessible cardinal, Indescribable cardinal, Indiscernibles, Ineffable cardinal, Infinitary logic, Infinite descending chain, Infinity-Borel set, Institution (computer science), Institutional model theory, Interactive proof system, Interior algebra, Internal set theory, Interpretability, Interpretability logic, Interpretation (logic), Interpretation (model theory), Intersection (set theory), Intuitionistic logic, Intuitionistic type theory, Isabelle (proof assistant), Θ (set theory), Μ operator, Jacques Herbrand, Kleene's recursion theorem, Kripke semantics, Kripke–Platek set theory with urelements, Kurt Gödel, L(R), L. E. J. Brouwer, Lambda calculus, Lambda cube, Large cardinal, Löb's theorem, Löwenheim–Skolem theorem, Lightface analytic game, Limit ordinal, Lindenbaum–Tarski algebra, Lindström quantifier, Linear logic, List of complexity classes, List of computability and complexity topics, List of first-order theories, Logic for Computable Functions, Logical framework, Ludics, Mahlo cardinal, Many-sorted logic, Markov algorithm, Mathematical induction, Mathematical proof, Measurable cardinal, Metamathematics, Mizar system, Model checking, Model complete theory, Morley rank, Morley's categoricity theorem, Morse–Kelley set theory, Naive set theory, Natural proof, New Foundations, Non-standard analysis, Non-standard calculus, Non-standard model, Non-standard model of arithmetic, Nonfirstorderizability, NP-completeness, O-minimal theory, Oracle machine, Ordinal number, Original proof of Gödel's completeness theorem, Outline of logic, Overspill, P versus NP problem, Paradox (theorem prover), Peano axioms, Perfect set property, Polish space, Polynomial hierarchy, Positive set theory, Post correspondence problem, Post's theorem, Potential isomorphism, Power set, Pregeometry (model theory), Presburger arithmetic, Prewellordering, Prime model, Primitive recursive function, Principia Mathematica, Projective hierarchy, Proof by exhaustion, Proof net, Proof-theoretic semantics, Property of Baire, Provability logic, Prover9, Pseudoelementary class, QED manifesto, Quantifier elimination, Ramsey cardinal, Rank-into-rank, Rózsa Péter, Recursion, Recursive definition, Recursive language, Recursively enumerable language, Recursively enumerable set, Reduct, Reductio ad absurdum, Relevance logic, Remarkable cardinal, Resolution (logic), Reverse mathematics, Rice's theorem, Russell's paradox, Saharon Shelah, Sahlqvist formula, Saturated model, Schröder–Bernstein theorem, Second-order arithmetic, Second-order logic, Self-verifying theories, Sequent, Sequent calculus, Set (mathematics), Set theory, Set theory (music), Shelah cardinal, Signature (logic), Simple theorems in the algebra of sets, Simply typed lambda calculus, Singleton (mathematics), Skolem normal form, Skolem's paradox, Soundness, Space hierarchy theorem, Spectrum of a theory, Stability spectrum, Stable group, Stable theory, Standard part function, Stephen Cole Kleene, Strength (mathematical logic), Strict logic, Strong cardinal, Strongly minimal theory, Structural induction, Structural proof theory, Structural rule, Structure (mathematical logic), Subset, Substructural logic, Substructure, Subtle cardinal, Successor ordinal, Supercompact cardinal, Superstrong cardinal, Suslin's problem, System F, Systems of Logic Based on Ordinals, T-schema, Tame group, Tarski's exponential function problem, Tarski's undefinability theorem, Tautology (logic), Term algebra, Theory (mathematical logic), Time complexity, Time hierarchy theorem, Tolerant sequence, Trakhtenbrot's theorem, Transfer principle, Transfinite induction, Tree (descriptive set theory), Tree (set theory), Turing degree, Turing machine, Type (model theory), Type theory, Typed lambda calculus, Ultrafinitism, Ultraproduct, Undecidable problem, Unfoldable cardinal, Uniformization (set theory), Union (set theory), Universally measurable set, Universe (mathematics), Urelement, Vampire (theorem prover), Vaught conjecture, Von Neumann universe, Weak interpretability, Weakly compact cardinal, Weakly o-minimal structure, Well-founded relation, Well-order, Wilkie's theorem, Woodin cardinal, Word problem for groups, Zariski geometry, Zermelo set theory, Zermelo–Fraenkel set theory, Zero sharp, Zorn's lemma. Expand index (304 more) »

## Ackermann function

In computability theory, the Ackermann function, named after Wilhelm Ackermann, is one of the simplest and earliest-discovered examples of a total computable function that is not primitive recursive.

New!!: List of mathematical logic topics and Ackermann function · See more »

## ACL2

ACL2 (A Computational Logic for Applicative Common Lisp) is a software system consisting of a programming language, an extensible theory in a first-order logic, and a mechanical theorem prover.

New!!: List of mathematical logic topics and ACL2 · See more »

## AD+

In set theory, AD+ is an extension, proposed by W. Hugh Woodin, to the axiom of determinacy.

New!!: List of mathematical logic topics and AD+ · See more »

## Affine logic

Affine logic is a substructural logic whose proof theory rejects the structural rule of contraction.

New!!: List of mathematical logic topics and Affine logic · See more »

## Age (model theory)

In model theory, the age of a structure (or model) A is the class of all finitely generated structures that are embeddable in A (i.e. isomorphic to substructures of A).

New!!: List of mathematical logic topics and Age (model theory) · See more »

## Alan Turing

Alan Mathison Turing (23 June 1912 – 7 June 1954) was an English computer scientist, mathematician, logician, cryptanalyst, philosopher, and theoretical biologist.

New!!: List of mathematical logic topics and Alan Turing · See more »

## Aleph number

In mathematics, and in particular set theory, the aleph numbers are a sequence of numbers used to represent the cardinality (or size) of infinite sets that can be well-ordered.

New!!: List of mathematical logic topics and Aleph number · See more »

## Alfred Tarski

Alfred Tarski (January 14, 1901 – October 26, 1983), born Alfred Teitelbaum,School of Mathematics and Statistics, University of St Andrews,, School of Mathematics and Statistics, University of St Andrews.

New!!: List of mathematical logic topics and Alfred Tarski · See more »

## Algebra of sets

The algebra of sets defines the properties and laws of sets, the set-theoretic operations of union, intersection, and complementation and the relations of set equality and set inclusion.

New!!: List of mathematical logic topics and Algebra of sets · See more »

## Algebraic logic

In mathematical logic, algebraic logic is the reasoning obtained by manipulating equations with free variables.

New!!: List of mathematical logic topics and Algebraic logic · See more »

## Algorithm

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems.

New!!: List of mathematical logic topics and Algorithm · See more »

## Alonzo Church

Alonzo Church (June 14, 1903 – August 11, 1995) was an American mathematician and logician who made major contributions to mathematical logic and the foundations of theoretical computer science.

New!!: List of mathematical logic topics and Alonzo Church · See more »

## Alternative set theory

Generically, an alternative set theory is an alternative mathematical approach to the concept of set.

New!!: List of mathematical logic topics and Alternative set theory · See more »

## Amalgamation property

In the mathematical field of model theory, the amalgamation property is a property of collections of structures that guarantees, under certain conditions, that two structures in the collection can be regarded as substructures of a larger one.

New!!: List of mathematical logic topics and Amalgamation property · See more »

## Analytic proof

In mathematics, an analytic proof is a proof of a theorem in analysis that only makes use of methods from analysis, and which does not predominantly make use of algebraic or geometrical methods.

New!!: List of mathematical logic topics and Analytic proof · See more »

## Analytic set

In descriptive set theory, a subset of a Polish space X is an analytic set if it is a continuous image of a Polish space.

New!!: List of mathematical logic topics and Analytic set · See more »

## Analytical hierarchy

In mathematical logic and descriptive set theory, the analytical hierarchy is an extension of the arithmetical hierarchy.

New!!: List of mathematical logic topics and Analytical hierarchy · See more »

## Arithmetical hierarchy

In mathematical logic, the arithmetical hierarchy, arithmetic hierarchy or Kleene–Mostowski hierarchy classifies certain sets based on the complexity of formulas that define them.

New!!: List of mathematical logic topics and Arithmetical hierarchy · See more »

## Arithmetical set

In mathematical logic, an arithmetical set (or arithmetic set) is a set of natural numbers that can be defined by a formula of first-order Peano arithmetic.

New!!: List of mathematical logic topics and Arithmetical set · See more »

## Arithmetization of analysis

The arithmetization of analysis was a research program in the foundations of mathematics carried out in the second half of the 19th century.

New!!: List of mathematical logic topics and Arithmetization of analysis · See more »

## Atomic model (mathematical logic)

In model theory, an atomic model is a model such that the complete type of every tuple is axiomatized by a single formula.

New!!: List of mathematical logic topics and Atomic model (mathematical logic) · See more »

## Automated Mathematician

The Automated Mathematician (AM) is one of the earliest successful discovery systems.

New!!: List of mathematical logic topics and Automated Mathematician · See more »

## Automated theorem proving

Automated theorem proving (also known as ATP or automated deduction) is a subfield of automated reasoning and mathematical logic dealing with proving mathematical theorems by computer programs.

New!!: List of mathematical logic topics and Automated theorem proving · See more »

## Ax–Grothendieck theorem

In mathematics, the Ax–Grothendieck theorem is a result about injectivity and surjectivity of polynomials that was proved independently by James Ax and Alexander Grothendieck.

New!!: List of mathematical logic topics and Ax–Grothendieck theorem · See more »

## Ax–Kochen theorem

The Ax–Kochen theorem, named for James Ax and Simon B. Kochen, states that for each positive integer d there is a finite set Yd of prime numbers, such that if p is any prime not in Yd then every homogeneous polynomial of degree d over the p-adic numbers in at least d2+1 variables has a nontrivial zero.

New!!: List of mathematical logic topics and Ax–Kochen theorem · See more »

## Axiom of choice

In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that the Cartesian product of a collection of non-empty sets is non-empty.

New!!: List of mathematical logic topics and Axiom of choice · See more »

## Axiom of countable choice

The axiom of countable choice or axiom of denumerable choice, denoted ACω, is an axiom of set theory that states that every countable collection of non-empty sets must have a choice function.

New!!: List of mathematical logic topics and Axiom of countable choice · See more »

## Axiom of dependent choice

In mathematics, the axiom of dependent choice, denoted by \mathsf, is a weak form of the axiom of choice (\mathsf) that is still sufficient to develop most of real analysis.

New!!: List of mathematical logic topics and Axiom of dependent choice · See more »

## Axiom of determinacy

In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962.

New!!: List of mathematical logic topics and Axiom of determinacy · See more »

## Axiom of projective determinacy

In mathematical logic, projective determinacy is the special case of the axiom of determinacy applying only to projective sets.

New!!: List of mathematical logic topics and Axiom of projective determinacy · See more »

## Axiom of real determinacy

In mathematics, the axiom of real determinacy (abbreviated as ADR) is an axiom in set theory.

New!!: List of mathematical logic topics and Axiom of real determinacy · See more »

## Axiom schema

In mathematical logic, an axiom schema (plural: axiom schemata or axiom schemas) generalizes the notion of axiom.

New!!: List of mathematical logic topics and Axiom schema · See more »

## Axiomatic system

In mathematics, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems.

New!!: List of mathematical logic topics and Axiomatic system · See more »

## Ł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.

New!!: List of mathematical logic topics and Łoś–Vaught test · See more »

## Back-and-forth method

In mathematical logic, especially set theory and model theory, the back-and-forth method is a method for showing isomorphism between countably infinite structures satisfying specified conditions.

New!!: List of mathematical logic topics and Back-and-forth method · See more »

## 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.

New!!: List of mathematical logic topics and Barwise compactness theorem · See more »

## Begriffsschrift

Begriffsschrift (German for, roughly, "concept-script") is a book on logic by Gottlob Frege, published in 1879, and the formal system set out in that book.

New!!: List of mathematical logic topics and Begriffsschrift · See more »

## Beth number

In mathematics, the infinite cardinal numbers are represented by the Hebrew letter \aleph (aleph) indexed with a subscript that runs over the ordinal numbers (see aleph number).

New!!: List of mathematical logic topics and Beth number · See more »

## Boolean algebra

In mathematics and mathematical logic, Boolean algebra is the branch of algebra in which the values of the variables are the truth values true and false, usually denoted 1 and 0 respectively.

New!!: List of mathematical logic topics and Boolean algebra · See more »

## Boolean algebra (structure)

In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice.

New!!: List of mathematical logic topics and Boolean algebra (structure) · See more »

## Boolean-valued model

In mathematical logic, a Boolean-valued model is a generalization of the ordinary Tarskian notion of structure from model theory.

New!!: List of mathematical logic topics and Boolean-valued model · See more »

## Borel equivalence relation

In mathematics, a Borel equivalence relation on a Polish space X is an equivalence relation on X that is a Borel subset of X × X (in the product topology).

New!!: List of mathematical logic topics and Borel equivalence relation · See more »

## Burali-Forti paradox

In set theory, a field of mathematics, the Burali-Forti paradox demonstrates that constructing "the set of all ordinal numbers" leads to a contradiction and therefore shows an antinomy in a system that allows its construction.

New!!: List of mathematical logic topics and Burali-Forti paradox · See more »

## C-minimal theory

In model theory, a branch of mathematical logic, a C-minimal theory is a theory that is "minimal" with respect to a ternary relation C with certain properties.

New!!: List of mathematical logic topics and C-minimal theory · See more »

## Calculus of constructions

In mathematical logic and computer science, the calculus of constructions (CoC) is a type theory created by Thierry Coquand.

New!!: List of mathematical logic topics and Calculus of constructions · See more »

## Cantor's diagonal argument

In set theory, Cantor's diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a mathematical proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers.

New!!: List of mathematical logic topics and Cantor's diagonal argument · See more »

## Cantor's theorem

In elementary set theory, Cantor's theorem is a fundamental result that states that, for any set A, the set of all subsets of A (the power set of A, denoted by \mathcal(A)) has a strictly greater cardinality than A itself.

New!!: List of mathematical logic topics and Cantor's theorem · See more »

## Cardinal number

In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets.

New!!: List of mathematical logic topics and Cardinal number · See more »

## Cardinality

In mathematics, the cardinality of a set is a measure of the "number of elements of the set".

New!!: List of mathematical logic topics and Cardinality · See more »

## Cartesian product

In set theory (and, usually, in other parts of mathematics), a Cartesian product is a mathematical operation that returns a set (or product set or simply product) from multiple sets.

New!!: List of mathematical logic topics and Cartesian product · See more »

## Categorical logic

Categorical logic is the branch of mathematics in which tools and concepts from category theory are applied to the study of mathematical logic.

New!!: List of mathematical logic topics and Categorical logic · See more »

## Church–Rosser theorem

In mathematics and theoretical computer science, the Church–Rosser theorem states that, when applying reduction rules to terms in the lambda calculus, the ordering in which the reductions are chosen does not make a difference to the eventual result.

New!!: List of mathematical logic topics and Church–Rosser theorem · See more »

## Church–Turing thesis

In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a hypothesis about the nature of computable functions.

New!!: List of mathematical logic topics and Church–Turing thesis · See more »

## Cirquent calculus

Cirquent calculus is a proof calculus which manipulates graph-style constructs termed cirquents, as opposed to the traditional tree-style objects such as formulas or sequents.

New!!: List of mathematical logic topics and Cirquent calculus · See more »

## Class (set theory)

In set theory and its applications throughout mathematics, a class is a collection of sets (or sometimes other mathematical objects) that can be unambiguously defined by a property that all its members share.

New!!: List of mathematical logic topics and Class (set theory) · See more »

## 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 language of T in such a way that S proves every formula whose translation is a theorem of T. The "translation" here is required to preserve the logical structure of formulas.

New!!: List of mathematical logic topics and Cointerpretability · See more »

## Combinatory logic

Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic.

New!!: List of mathematical logic topics and Combinatory logic · See more »

## 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.

New!!: List of mathematical logic topics and Compactness theorem · See more »

## Complement (set theory)

In set theory, the complement of a set refers to elements not in.

New!!: List of mathematical logic topics and Complement (set theory) · See more »

## Complete Boolean algebra

In mathematics, a complete Boolean algebra is a Boolean algebra in which every subset has a supremum (least upper bound).

New!!: List of mathematical logic topics and Complete Boolean algebra · See more »

## Complete theory

In mathematical logic, a theory is complete if, for every formula in the theory's language, that formula or its negation is demonstrable.

New!!: List of mathematical logic topics and Complete theory · See more »

## Complexity class

In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.

New!!: List of mathematical logic topics and Complexity class · See more »

## Computability logic

Computability logic (CoL) is a research program and mathematical framework for redeveloping logic as a systematic formal theory of computability, as opposed to classical logic which is a formal theory of truth.

New!!: List of mathematical logic topics and Computability logic · See more »

## Computability theory

Computability theory, also known as recursion theory, is a branch of mathematical logic, of computer science, and of the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees.

New!!: List of mathematical logic topics and Computability theory · See more »

## Computable function

Computable functions are the basic objects of study in computability theory.

New!!: List of mathematical logic topics and Computable function · See more »

## Computable measure theory

In mathematics, computable measure theory is the part of computable analysis that deals with effective versions of measure theory.

New!!: List of mathematical logic topics and Computable measure theory · See more »

## Computable model theory

Computable model theory is a branch of model theory which deals with questions of computability as they apply to model-theoretical structures.

New!!: List of mathematical logic topics and Computable model theory · See more »

## Computation

Computation is any type of calculation that includes both arithmetical and non-arithmetical steps and follows a well-defined model, for example an algorithm.

New!!: List of mathematical logic topics and Computation · See more »

## Computational complexity theory

Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.

New!!: List of mathematical logic topics and Computational complexity theory · See more »

## 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.

New!!: List of mathematical logic topics and Conservative extension · See more »

## Consistency

In classical deductive logic, a consistent theory is one that does not contain a contradiction.

New!!: List of mathematical logic topics and Consistency · See more »

## Constructible universe

In mathematics, in set theory, the constructible universe (or Gödel's constructible universe), denoted L, is a particular class of sets that can be described entirely in terms of simpler sets.

New!!: List of mathematical logic topics and Constructible universe · See more »

## Constructive analysis

In mathematics, constructive analysis is mathematical analysis done according to some principles of constructive mathematics.

New!!: List of mathematical logic topics and Constructive analysis · See more »

## Constructive proof

In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object by creating or providing a method for creating the object.

New!!: List of mathematical logic topics and Constructive proof · See more »

## Continuum (set theory)

In the mathematical field of set theory, the continuum means the real numbers, or the corresponding (infinite) cardinal number, \mathfrak.

New!!: List of mathematical logic topics and Continuum (set theory) · See more »

## Continuum hypothesis

In mathematics, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets.

New!!: List of mathematical logic topics and Continuum hypothesis · See more »

## Cook–Levin theorem

In computational complexity theory, the Cook–Levin theorem, also known as Cook's theorem, states that the Boolean satisfiability problem is NP-complete.

New!!: List of mathematical logic topics and Cook–Levin theorem · See more »

## Coq

In computer science, Coq is an interactive theorem prover.

New!!: List of mathematical logic topics and Coq · See more »

## Countable set

In mathematics, a countable set is a set with the same cardinality (number of elements) as some subset of the set of natural numbers.

New!!: List of mathematical logic topics and Countable set · See more »

## Criticism of non-standard analysis

Non-standard analysis and its offshoot, non-standard calculus, have been criticized by several authors, notably Errett Bishop, Paul Halmos, and Alain Connes.

New!!: List of mathematical logic topics and Criticism of non-standard analysis · See more »

## Curry–Howard correspondence

In programming language theory and proof theory, the Curry–Howard correspondence (also known as the Curry–Howard isomorphism or equivalence, or the proofs-as-programs and propositions- or formulae-as-types interpretation) is the direct relationship between computer programs and mathematical proofs.

New!!: List of mathematical logic topics and Curry–Howard correspondence · See more »

## Cut-elimination theorem

The cut-elimination theorem (or Gentzen's Hauptsatz) is the central result establishing the significance of the sequent calculus.

New!!: List of mathematical logic topics and Cut-elimination theorem · See more »

## Decidability (logic)

In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas, or, more precisely, an algorithm that can and will return a boolean true or false value that is correct (instead of looping indefinitely, crashing, returning "don't know" or returning a wrong answer).

New!!: List of mathematical logic topics and Decidability (logic) · See more »

## Decision problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

New!!: List of mathematical logic topics and Decision problem · See more »

## Deduction theorem

In mathematical logic, the deduction theorem is a metatheorem of propositional and first-order logic.

New!!: List of mathematical logic topics and Deduction theorem · See more »

## Definable real number

Informally, a definable real number is a real number that can be uniquely specified by its description.

New!!: List of mathematical logic topics and Definable real number · See more »

## Definable set

In mathematical logic, a definable set is an n-ary relation on the domain of a structure whose elements are precisely those elements satisfying some formula in the first-order language of that structure.

New!!: List of mathematical logic topics and Definable set · See more »

## Descriptive complexity theory

Descriptive complexity is a branch of computational complexity theory and of finite model theory that characterizes complexity classes by the type of logic needed to express the languages in them.

New!!: List of mathematical logic topics and Descriptive complexity theory · See more »

## Descriptive set theory

In mathematical logic, descriptive set theory (DST) is the study of certain classes of "well-behaved" subsets of the real line and other Polish spaces.

New!!: List of mathematical logic topics and Descriptive set theory · See more »

## Determinacy

Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies.

New!!: List of mathematical logic topics and Determinacy · See more »

## Diagonal lemma

In mathematical logic, the diagonal lemma or fixed point theorem establishes the existence of self-referential sentences in certain formal theories of the natural numbers—specifically those theories that are strong enough to represent all computable functions.

New!!: List of mathematical logic topics and Diagonal lemma · See more »

## Dialectica space

Dialectica spaces are a categorical way of constructing models of linear logic.

New!!: List of mathematical logic topics and Dialectica space · See more »

## Differentially closed field

In mathematics, a differential field K is differentially closed if every finite system of differential equations with a solution in some differential field extending K already has a solution in K. This concept was introduced by.

New!!: List of mathematical logic topics and Differentially closed field · See more »

## Diophantine set

In mathematics, a Diophantine equation is an equation of the form P(x1,..., xj, y1,..., yk).

New!!: List of mathematical logic topics and Diophantine set · See more »

## Direct proof

In mathematics and logic, a direct proof is a way of showing the truth or falsehood of a given statement by a straightforward combination of established facts, usually axioms, existing lemmas and theorems, without making any further assumptions.

New!!: List of mathematical logic topics and Direct proof · See more »

## E theorem prover

E is a high performance theorem prover for full first-order logic with equality.

New!!: List of mathematical logic topics and E theorem prover · See more »

## Effective results in number theory

For historical reasons and in order to have application to the solution of Diophantine equations, results in number theory have been scrutinised more than in other branches of mathematics to see if their content is effectively computable.

New!!: List of mathematical logic topics and Effective results in number theory · See more »

## Ehrenfeucht–Fraïssé game

In the mathematical discipline of model theory, the Ehrenfeucht–Fraïssé game (also called back-and-forth games) is a technique for determining whether two structures are elementarily equivalent.

New!!: List of mathematical logic topics and Ehrenfeucht–Fraïssé game · See more »

## Element (mathematics)

In mathematics, an element, or member, of a set is any one of the distinct objects that make up that set.

New!!: List of mathematical logic topics and Element (mathematics) · See more »

## Elementary Calculus: An Infinitesimal Approach

Elementary Calculus: An Infinitesimal approach is a textbook by H. Jerome Keisler.

New!!: List of mathematical logic topics and Elementary Calculus: An Infinitesimal Approach · See more »

## Elementary class

In model theory, a branch of mathematical logic, an elementary class (or axiomatizable class) is a class consisting of all structures satisfying a fixed first-order theory.

New!!: List of mathematical logic topics and Elementary class · See more »

## 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.

New!!: List of mathematical logic topics and Elementary equivalence · See more »

## Emil Leon Post

Emil Leon Post (February 11, 1897 – April 21, 1954) was an American mathematician and logician.

New!!: List of mathematical logic topics and Emil Leon Post · See more »

## Empty set

In mathematics, and more specifically set theory, the empty set or null set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero.

New!!: List of mathematical logic topics and Empty set · See more »

## Entscheidungsproblem

In mathematics and computer science, the Entscheidungsproblem (German for "decision problem") is a challenge posed by David Hilbert in 1928.

New!!: List of mathematical logic topics and Entscheidungsproblem · See more »

## Epsilon-induction

In mathematics, \in-induction (epsilon-induction) is a variant of transfinite induction that can be used in set theory to prove that all sets satisfy a given property P. If the truth of the property for x follows from its truth for all elements of x, for every set x, then the property is true of all sets.

New!!: List of mathematical logic topics and Epsilon-induction · See more »

## Erdős cardinal

In mathematics, an Erdős cardinal, also called a partition cardinal is a certain kind of large cardinal number introduced by.

New!!: List of mathematical logic topics and Erdős cardinal · See more »

## Eurisko

Eurisko (Gr., I discover) is a program written by Douglas Lenat in RLL-1, a representation language itself written in the Lisp programming language.

New!!: List of mathematical logic topics and Eurisko · See more »

## Existence theorem

In mathematics, an existence theorem is a theorem with a statement beginning 'there exist(s)..', or more generally 'for all,,...

New!!: List of mathematical logic topics and Existence theorem · See more »

## Existentially closed model

In model theory, a branch of mathematical logic, the notion of an existentially closed model (or existentially complete model) of a theory generalizes the notions of algebraically closed fields (for the theory of fields), real closed fields (for the theory of ordered fields), existentially closed groups (for the class of groups), and dense linear orders without endpoints (for the class of linear orders).

New!!: List of mathematical logic topics and Existentially closed model · See more »

## Exponential field

In mathematics, an exponential field is a field that has an extra operation on its elements which extends the usual idea of exponentiation.

New!!: List of mathematical logic topics and Exponential field · See more »

## Exponential hierarchy

In computational complexity theory, the exponential hierarchy is a hierarchy of complexity classes, which is an exponential time analogue of the polynomial hierarchy.

New!!: List of mathematical logic topics and Exponential hierarchy · See more »

## Extendible cardinal

In mathematics, extendible cardinals are large cardinals introduced by, who was partly motivated by reflection principles.

New!!: List of mathematical logic topics and Extendible cardinal · See more »

## Finite model theory

Finite model theory (FMT) is a subarea of model theory (MT).

New!!: List of mathematical logic topics and Finite model theory · See more »

## Finitism

Finitism is a philosophy of mathematics that accepts the existence only of finite mathematical objects.

New!!: List of mathematical logic topics and Finitism · See more »

## First-order logic

First-order logic—also known as first-order predicate calculus and predicate logic—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science.

New!!: List of mathematical logic topics and First-order logic · See more »

## Forcing (mathematics)

In the mathematical discipline of set theory, forcing is a technique for proving consistency and independence results.

New!!: List of mathematical logic topics and Forcing (mathematics) · See more »

## Forking extension

In model theory, a forking extension is an extension that is not whereas a non-forking extension is an extension that is as free as possible.

New!!: List of mathematical logic topics and Forking extension · See more »

## Formal language

In mathematics, computer science, and linguistics, a formal language is a set of strings of symbols together with a set of rules that are specific to it.

New!!: List of mathematical logic topics and Formal language · See more »

## Formal system

A formal system is the name of a logic system usually defined in the mathematical way.

New!!: List of mathematical logic topics and Formal system · See more »

## 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 philosophical theories concerning the nature of mathematics.

New!!: List of mathematical logic topics and Foundations of mathematics · See more »

## Function (mathematics)

In mathematics, a function was originally the idealization of how a varying quantity depends on another quantity.

New!!: List of mathematical logic topics and Function (mathematics) · See more »

## Functional predicate

In formal logic and related branches of mathematics, a functional predicate, or function symbol, is a logical symbol that may be applied to an object term to produce another object term.

New!!: List of mathematical logic topics and Functional predicate · See more »

## Fuzzy set

In mathematics, fuzzy sets (aka uncertain sets) are somewhat like sets whose elements have degrees of membership.

New!!: List of mathematical logic topics and Fuzzy set · See more »

## Gandalf (theorem prover)

Gandalf is a first-order automated theorem prover applied to several domain-specific tasks such as Semantic web.

New!!: List of mathematical logic topics and Gandalf (theorem prover) · See more »

## Gödel's completeness theorem

Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic.

New!!: List of mathematical logic topics and Gödel's completeness theorem · See more »

## Gödel's incompleteness theorems

Gödel's incompleteness theorems are two theorems of mathematical logic that demonstrate the inherent limitations of every formal axiomatic system containing basic arithmetic.

New!!: List of mathematical logic topics and Gödel's incompleteness theorems · See more »

## General frame

In logic, general frames (or simply frames) are Kripke frames with an additional structure, which are used to model modal and intermediate logics.

New!!: List of mathematical logic topics and General frame · See more »

## Gentzen's consistency proof

Gentzen's consistency proof is a result of proof theory in mathematical logic, published by Gerhard Gentzen in 1936.

New!!: List of mathematical logic topics and Gentzen's consistency proof · See more »

## Georg Cantor's first set theory article

Georg Cantor's first set theory article was published in 1874 and contains the first theorems of transfinite set theory, which studies infinite sets and their properties.

New!!: List of mathematical logic topics and Georg Cantor's first set theory article · See more »

## Gerhard Gentzen

Gerhard Karl Erich Gentzen (November 24, 1909 – August 4, 1945) was a German mathematician and logician.

New!!: List of mathematical logic topics and Gerhard Gentzen · See more »

## Giuseppe Peano

Giuseppe Peano (27 August 1858 – 20 April 1932) was an Italian mathematician and glottologist.

New!!: List of mathematical logic topics and Giuseppe Peano · See more »

## Halting problem

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running (i.e., halt) or continue to run forever.

New!!: List of mathematical logic topics and Halting problem · See more »

## Hartogs number

In mathematics, specifically in axiomatic set theory, a Hartogs number is a particular kind of cardinal number.

New!!: List of mathematical logic topics and Hartogs number · See more »

## Haskell Curry

Haskell Brooks Curry (September 12, 1900 – September 1, 1982) was an American mathematician and logician.

New!!: List of mathematical logic topics and Haskell Curry · See more »

## Herbrand interpretation

In mathematical logic, a Herbrand interpretation is an interpretation in which all constants and function symbols are assigned very simple meanings.

New!!: List of mathematical logic topics and Herbrand interpretation · See more »

## 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 σ.

New!!: List of mathematical logic topics and Herbrand structure · See more »

## Higher-order logic

In mathematics and logic, a higher-order logic is a form of predicate logic that is distinguished from first-order logic by additional quantifiers and, sometimes, stronger semantics.

New!!: List of mathematical logic topics and Higher-order logic · See more »

## 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 attempts to clarify the foundations of mathematics were found to suffer from paradoxes and inconsistencies.

New!!: List of mathematical logic topics and Hilbert's program · See more »

## History of topos theory

This page gives some very general background to the mathematical idea of topos.

New!!: List of mathematical logic topics and History of topos theory · See more »

## HOL (proof assistant)

HOL (Higher Order Logic) denotes a family of interactive theorem proving systems using similar (higher-order) logics and implementation strategies.

New!!: List of mathematical logic topics and HOL (proof assistant) · See more »

## Hrushovski construction

In model theory, a branch of mathematical logic, the Hrushovski construction generalizes the Fraïssé limit by working with a notion of strong substructure \leq rather than \subseteq.

New!!: List of mathematical logic topics and Hrushovski construction · See more »

## Huge cardinal

In mathematics, a cardinal number κ is called huge if there exists an elementary embedding j: V → M from V into a transitive inner model M with critical point κ and Here, αM is the class of all sequences of length α whose elements are in M. Huge cardinals were introduced by.

New!!: List of mathematical logic topics and Huge cardinal · See more »

## Hypercomputation

Hypercomputation or super-Turing computation refers to models of computation that can provide outputs that are not Turing computable.

New!!: List of mathematical logic topics and Hypercomputation · See more »

## Hyperinteger

In non-standard analysis, a hyperinteger n is a hyperreal number that is equal to its own integer part.

New!!: List of mathematical logic topics and Hyperinteger · See more »

## Hyperreal number

The system of hyperreal numbers is a way of treating infinite and infinitesimal quantities.

New!!: List of mathematical logic topics and Hyperreal number · See more »

## Imaginary element

In mathematical model theory, an imaginary element of a structure is roughly a definable equivalence class.

New!!: List of mathematical logic topics and Imaginary element · See more »

## Impredicativity

Something that is impredicative, in mathematics and logic, is a self-referencing definition.

New!!: List of mathematical logic topics and Impredicativity · See more »

## Inaccessible cardinal

In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic.

New!!: List of mathematical logic topics and Inaccessible cardinal · See more »

## Indescribable cardinal

In mathematics, a Q-indescribable cardinal is a certain kind of large cardinal number that is hard to describe in some language Q. There are many different types of indescribable cardinals corresponding to different choices of languages Q. They were introduced by.

New!!: List of mathematical logic topics and Indescribable cardinal · See more »

## Indiscernibles

In mathematical logic, indiscernibles are objects which cannot be distinguished by any property or relation defined by a formula.

New!!: List of mathematical logic topics and Indiscernibles · See more »

## Ineffable cardinal

In the mathematics of transfinite numbers, an ineffable cardinal is a certain kind of large cardinal number, introduced by.

New!!: List of mathematical logic topics and Ineffable cardinal · See more »

## Infinitary logic

An infinitary logic is a logic that allows infinitely long statements and/or infinitely long proofs.

New!!: List of mathematical logic topics and Infinitary logic · See more »

## Infinite descending chain

Given a set S with a partial order ≤, an infinite descending chain is an infinite, strictly decreasing sequence of elements x1 > x2 >...

New!!: List of mathematical logic topics and Infinite descending chain · See more »

## Infinity-Borel set

In set theory, a subset of a Polish space X is ∞-Borel if it can be obtained by starting with the open subsets of X, and transfinitely iterating the operations of complementation and wellordered union.

New!!: List of mathematical logic topics and Infinity-Borel set · See more »

## Institution (computer science)

The notion of institution has been created by Joseph Goguen and Rod Burstall in the late 1970s.

New!!: List of mathematical logic topics and Institution (computer science) · See more »

## Institutional model theory

This page is about the concept in mathematical logic.

New!!: List of mathematical logic topics and Institutional model theory · See more »

## Interactive proof system

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties.

New!!: List of mathematical logic topics and Interactive proof system · See more »

## 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.

New!!: List of mathematical logic topics and Interior algebra · See more »

## Internal set theory

Internal set theory (IST) is a mathematical theory of sets developed by Edward Nelson that provides an axiomatic basis for a portion of the non-standard analysis introduced by Abraham Robinson.

New!!: List of mathematical logic topics and Internal set theory · See more »

## Interpretability

In mathematical logic, interpretability is a relation between formal theories that expresses the possibility of interpreting or translating one into the other.

New!!: List of mathematical logic topics and Interpretability · See more »

## Interpretability logic

Interpretability logics comprise a family of modal logics that extend provability logic to describe interpretability or various related metamathematical properties and relations such as weak interpretability, Π1-conservativity, cointerpretability, tolerance, cotolerance, and arithmetic complexities.

New!!: List of mathematical logic topics and Interpretability logic · See more »

## Interpretation (logic)

An interpretation is an assignment of meaning to the symbols of a formal language.

New!!: List of mathematical logic topics and Interpretation (logic) · See more »

## Interpretation (model theory)

In model theory, interpretation of a structure M in another structure N (typically of a different signature) is a technical notion that approximates the idea of representing M inside N. For example every reduct or definitional expansion of a structure N has an interpretation in N. Many model-theoretic properties are preserved under interpretability.

New!!: List of mathematical logic topics and Interpretation (model theory) · See more »

## Intersection (set theory)

In mathematics, the intersection A ∩ B of two sets A and B is the set that contains all elements of A that also belong to B (or equivalently, all elements of B that also belong to A), but no other elements.

New!!: List of mathematical logic topics and Intersection (set theory) · See more »

## Intuitionistic logic

Intuitionistic logic, sometimes more generally called constructive logic, refers to systems of symbolic logic that differ from the systems used for classical logic by more closely mirroring the notion of constructive proof.

New!!: List of mathematical logic topics and Intuitionistic logic · See more »

## Intuitionistic type theory

Intuitionistic type theory (also known as constructive type theory, or Martin-Löf type theory) is a type theory and an alternative foundation of mathematics.

New!!: List of mathematical logic topics and Intuitionistic type theory · See more »

## Isabelle (proof assistant)

The Isabelle theorem prover is an interactive theorem prover, a Higher Order Logic (HOL) theorem prover.

New!!: List of mathematical logic topics and Isabelle (proof assistant) · See more »

## Θ (set theory)

In set theory, Θ (pronounced like the letter theta) is the least nonzero ordinal α such that there is no surjection from the reals onto α. If the axiom of choice (AC) holds (or even if the reals can be wellordered), then Θ is simply (2^)^+, the cardinal successor of the cardinality of the continuum.

New!!: List of mathematical logic topics and Θ (set theory) · See more »

## Μ operator

In computability theory, the μ operator, minimization operator, or unbounded search operator searches for the least natural number with a given property.

New!!: List of mathematical logic topics and Μ operator · See more »

## Jacques Herbrand

Jacques Herbrand (12 February 1908 – 27 July 1931) was a French mathematician.

New!!: List of mathematical logic topics and Jacques Herbrand · See more »

## Kleene's recursion theorem

In computability theory, Kleene's recursion theorems are a pair of fundamental results about the application of computable functions to their own descriptions.

New!!: List of mathematical logic topics and Kleene's recursion theorem · See more »

## 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 1950s and early 1960s by Saul Kripke and André Joyal.

New!!: List of mathematical logic topics and Kripke semantics · See more »

## Kripke–Platek set theory with urelements

The Kripke–Platek set theory with urelements (KPU) is an axiom system for set theory with urelements, based on the traditional (urelement-free) Kripke–Platek set theory.

New!!: List of mathematical logic topics and Kripke–Platek set theory with urelements · See more »

## Kurt Gödel

Kurt Friedrich Gödel (April 28, 1906 – January 14, 1978) was an Austrian, and later American, logician, mathematician, and philosopher.

New!!: List of mathematical logic topics and Kurt Gödel · See more »

## L(R)

In set theory, L(R) (pronounced L of R) is the smallest transitive inner model of ZF containing all the ordinals and all the reals.

New!!: List of mathematical logic topics and L(R) · See more »

## L. E. J. Brouwer

Luitzen Egbertus Jan Brouwer (27 February 1881 – 2 December 1966), usually cited as L. E. J. Brouwer but known to his friends as Bertus, was a Dutch mathematician and philosopher, who worked in topology, set theory, measure theory and complex analysis.

New!!: List of mathematical logic topics and L. E. J. Brouwer · See more »

## Lambda calculus

Lambda calculus (also written as λ-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution.

New!!: List of mathematical logic topics and Lambda calculus · See more »

## Lambda cube

In mathematical logic and type theory, the λ-cube is a framework for exploring the axes of refinement in Thierry Coquand's calculus of constructions, starting from the simply typed lambda calculus (written as λ→ in the cube diagram) as the vertex of a cube placed at the origin, and the calculus of constructions (higher-order dependently typed polymorphic lambda calculus; written as λPω in the diagram) as its diametrically opposite vertex.

New!!: List of mathematical logic topics and Lambda cube · See more »

## Large cardinal

In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers.

New!!: List of mathematical logic topics and Large cardinal · See more »

## Löb's theorem

In mathematical logic, Löb's theorem states that in any formal system F with Peano arithmetic (PA), for any formula P, if it is provable in F that "if P is provable in F then P is true", then P is provable in F. More formally, if Bew(#P) means that the formula P with Gödel number #P is provable (from the German "beweisbar"), then or An immediate corollary of Löb's theorem is that, if P is not provable in PA, then "if P is provable in PA, then P is true" is not provable in PA.

New!!: List of mathematical logic topics and Löb's theorem · See more »

## Löwenheim–Skolem theorem

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.

New!!: List of mathematical logic topics and Löwenheim–Skolem theorem · See more »

## Lightface analytic game

In descriptive set theory, a lightface analytic game is a game whose payoff set A is a \Sigma^1_1 subset of Baire space; that is, there is a tree T on \omega\times\omega which is a computable subset of (\omega\times\omega)^.

New!!: List of mathematical logic topics and Lightface analytic game · See more »

## Limit ordinal

In set theory, a limit ordinal is an ordinal number that is neither zero nor a successor ordinal.

New!!: List of mathematical logic topics and Limit ordinal · See more »

## Lindenbaum–Tarski algebra

In mathematical logic, the Lindenbaum–Tarski algebra (or Lindenbaum algebra) of a logical theory T consists of the equivalence classes of sentences of the theory (i.e., the quotient, under the equivalence relation ~ defined such that p ~ q exactly when p and q are provably equivalent in T).

New!!: List of mathematical logic topics and Lindenbaum–Tarski algebra · See more »

## Lindström quantifier

In mathematical logic, a Lindström quantifier is a generalized polyadic quantifier.

New!!: List of mathematical logic topics and Lindström quantifier · See more »

## Linear logic

Linear logic is a substructural logic proposed by Jean-Yves Girard as a refinement of classical and intuitionistic logic, joining the dualities of the former with many of the constructive properties of the latter.

New!!: List of mathematical logic topics and Linear logic · See more »

## List of complexity classes

This is a list of complexity classes in computational complexity theory.

New!!: List of mathematical logic topics and List of complexity classes · See more »

## List of computability and complexity topics

This is a list of computability and complexity topics, by Wikipedia page.

New!!: List of mathematical logic topics and List of computability and complexity topics · See more »

## List of first-order theories

In mathematical logic, a first-order theory is given by a set of axioms in some language.

New!!: List of mathematical logic topics and List of first-order theories · See more »

## Logic for Computable Functions

Logic for Computable Functions (LCF) is an interactive automated theorem prover developed at the universities of Edinburgh and Stanford by Robin Milner and others in 1972.

New!!: List of mathematical logic topics and Logic for Computable Functions · See more »

## Logical framework

In logic, a logical framework provides a means to define (or present) a logic as a signature in a higher-order type theory in such a way that provability of a formula in the original logic reduces to a type inhabitation problem in the framework type theory.

New!!: List of mathematical logic topics and Logical framework · See more »

## Ludics

In proof theory, ludics is an analysis of the principles governing inference rules of mathematical logic.

New!!: List of mathematical logic topics and Ludics · See more »

## Mahlo cardinal

In mathematics, a Mahlo cardinal is a certain kind of large cardinal number.

New!!: List of mathematical logic topics and Mahlo cardinal · See more »

## Many-sorted logic

Many-sorted logic can reflect formally our intention not to handle the universe as a homogeneous collection of objects, but to partition it in a way that is similar to types in typeful programming.

New!!: List of mathematical logic topics and Many-sorted logic · See more »

## Markov algorithm

In theoretical computer science, a Markov algorithm is a string rewriting system that uses grammar-like rules to operate on strings of symbols.

New!!: List of mathematical logic topics and Markov algorithm · See more »

## Mathematical induction

Mathematical induction is a mathematical proof technique.

New!!: List of mathematical logic topics and Mathematical induction · See more »

## Mathematical proof

In mathematics, a proof is an inferential argument for a mathematical statement.

New!!: List of mathematical logic topics and Mathematical proof · See more »

## Measurable cardinal

In mathematics, a measurable cardinal is a certain kind of large cardinal number.

New!!: List of mathematical logic topics and Measurable cardinal · See more »

## Metamathematics

Metamathematics is the study of mathematics itself using mathematical methods.

New!!: List of mathematical logic topics and Metamathematics · See more »

## Mizar system

The Mizar system consists of a formal language for writing mathematical definitions and proofs, a proof assistant, which is able to mechanically check proofs written in this language, and a library of formalized mathematics, which can be used in the proof of new theorems.

New!!: List of mathematical logic topics and Mizar system · See more »

## Model checking

In computer science, model checking or property checking refers to the following problem: Given a model of a system, exhaustively and automatically check whether this model meets a given specification.

New!!: List of mathematical logic topics and Model checking · See more »

## Model complete theory

In model theory, a first-order theory is called model complete if every embedding of models is an elementary embedding.

New!!: List of mathematical logic topics and Model complete theory · See more »

## Morley rank

In mathematical logic, Morley rank, introduced by, is a means of measuring the size of a subset of a model of a theory, generalizing the notion of dimension in algebraic geometry.

New!!: List of mathematical logic topics and Morley rank · See more »

## Morley's categoricity theorem

In model theory, a branch of mathematical logic, a theory is κ-categorical (or categorical in κ) if it has exactly one model of cardinality κ up to isomorphism.

New!!: List of mathematical logic topics and Morley's categoricity theorem · See more »

## Morse–Kelley set theory

In the foundations of mathematics, Morse–Kelley set theory (MK), Kelley–Morse set theory (KM), Morse–Tarski set theory (MT), Quine–Morse set theory (QM) or the system of Quine and Morse is a first order axiomatic set theory that is closely related to von Neumann–Bernays–Gödel set theory (NBG).

New!!: List of mathematical logic topics and Morse–Kelley set theory · See more »

## Naive set theory

Naïve set theory is any of several theories of sets used in the discussion of the foundations of mathematics.

New!!: List of mathematical logic topics and Naive set theory · See more »

## Natural proof

In computational complexity theory, a natural proof is a certain kind of proof establishing that one complexity class differs from another one.

New!!: List of mathematical logic topics and Natural proof · See more »

## New Foundations

In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of Principia Mathematica.

New!!: List of mathematical logic topics and New Foundations · See more »

## Non-standard analysis

The history of calculus is fraught with philosophical debates about the meaning and logical validity of fluxions or infinitesimal numbers.

New!!: List of mathematical logic topics and Non-standard analysis · See more »

## Non-standard calculus

In mathematics, non-standard calculus is the modern application of infinitesimals, in the sense of non-standard analysis, to differential and integral calculus.

New!!: List of mathematical logic topics and Non-standard calculus · See more »

## Non-standard model

In model theory, a discipline within mathematical logic, a non-standard model is a model of a theory that is not isomorphic to the intended model (or standard model).

New!!: List of mathematical logic topics and Non-standard model · See more »

## 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.

New!!: List of mathematical logic topics and Non-standard model of arithmetic · See more »

## Nonfirstorderizability

In formal logic, nonfirstorderizability is the inability of an expression to be adequately captured in particular theories in first-order logic.

New!!: List of mathematical logic topics and Nonfirstorderizability · See more »

## NP-completeness

In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.

New!!: List of mathematical logic topics and NP-completeness · See more »

## O-minimal theory

In mathematical logic, and more specifically in model theory, an infinite structure (M,<,...) which is totally ordered by Knight, Pillay and Steinhorn (1986), Pillay and Steinhorn (1988).

New!!: List of mathematical logic topics and O-minimal theory · See more »

## Oracle machine

In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems.

New!!: List of mathematical logic topics and Oracle machine · See more »

## Ordinal number

In set theory, an ordinal number, or ordinal, is one generalization of the concept of a natural number that is used to describe a way to arrange a collection of objects in order, one after another.

New!!: List of mathematical logic topics and Ordinal number · See more »

## 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 rewritten version of the dissertation, published as an article in 1930) is not easy to read today; it uses concepts and formalism that are no longer used and terminology that is often obscure.

New!!: List of mathematical logic topics and Original proof of Gödel's completeness theorem · See more »

## Outline of logic

Logic is the formal science of using reason and is considered a branch of both philosophy and mathematics.

New!!: List of mathematical logic topics and Outline of logic · See more »

## Overspill

In non-standard analysis, a branch of mathematics, overspill (referred to as overflow by Goldblatt (1998, p. 129)) is a widely used proof technique.

New!!: List of mathematical logic topics and Overspill · See more »

## P versus NP problem

The P versus NP problem is a major unsolved problem in computer science.

New!!: List of mathematical logic topics and P versus NP problem · See more »

## Paradox (theorem prover)

Paradox is an automated theorem proving system developed by Koen Lindström Claessen and Niklas Sörensson at the Chalmers University of Technology.

New!!: List of mathematical logic topics and Paradox (theorem prover) · See more »

## 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 Giuseppe Peano.

New!!: List of mathematical logic topics and Peano axioms · See more »

## Perfect set property

In descriptive set theory, a subset of a Polish space has the perfect set property if it is either countable or has a nonempty perfect subset (Kechris 1995, p. 150).

New!!: List of mathematical logic topics and Perfect set property · See more »

## Polish space

In the mathematical discipline of general topology, a Polish space is a separable completely metrizable topological space; that is, a space homeomorphic to a complete metric space that has a countable dense subset.

New!!: List of mathematical logic topics and Polish space · See more »

## Polynomial hierarchy

In computational complexity theory, the polynomial hierarchy (sometimes called the polynomial-time hierarchy) is a hierarchy of complexity classes that generalize the classes P, NP and co-NP to oracle machines.

New!!: List of mathematical logic topics and Polynomial hierarchy · See more »

## Positive set theory

In mathematical logic, positive set theory is the name for a class of alternative set theories in which the axiom of comprehension.

New!!: List of mathematical logic topics and Positive set theory · See more »

## Post correspondence problem

The Post correspondence problem is an undecidable decision problem that was introduced by Emil Post in 1946.

New!!: List of mathematical logic topics and Post correspondence problem · See more »

## Post's theorem

In computability theory Post's theorem, named after Emil Post, describes the connection between the arithmetical hierarchy and the Turing degrees.

New!!: List of mathematical logic topics and Post's theorem · See more »

## Potential isomorphism

In mathematical logic and in particular in model theory, a potential isomorphism is a collection of finite partial isomorphisms between two models which satisfies certain closure conditions.

New!!: List of mathematical logic topics and Potential isomorphism · See more »

## Power set

In mathematics, the power set (or powerset) of any set is the set of all subsets of, including the empty set and itself, variously denoted as, 𝒫(), ℘() (using the "Weierstrass p"),,, or, identifying the powerset of with the set of all functions from to a given set of two elements,.

New!!: List of mathematical logic topics and Power set · See more »

## Pregeometry (model theory)

Pregeometry, and in full combinatorial pregeometry, are essentially synonyms for "matroid".

New!!: List of mathematical logic topics and Pregeometry (model theory) · See more »

## Presburger arithmetic

Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929.

New!!: List of mathematical logic topics and Presburger arithmetic · See more »

## Prewellordering

In set theory, a prewellordering is a binary relation \le that is transitive, total, and wellfounded (more precisely, the relation x\le y\land y\nleq x is wellfounded).

New!!: List of mathematical logic topics and Prewellordering · See more »

## Prime model

In mathematics, and in particular model theory, a prime model is a model which is as simple as possible.

New!!: List of mathematical logic topics and Prime model · See more »

## Primitive recursive function

In computability theory, primitive recursive functions are a class of functions that are defined using primitive recursion and composition as central operations and are a strict subset of the total µ-recursive functions (µ-recursive functions are also called partial recursive).

New!!: List of mathematical logic topics and Primitive recursive function · See more »

## Principia Mathematica

The Principia Mathematica (often abbreviated PM) is a three-volume work on the foundations of mathematics written by Alfred North Whitehead and Bertrand Russell and published in 1910, 1912, and 1913.

New!!: List of mathematical logic topics and Principia Mathematica · See more »

## Projective hierarchy

In the mathematical field of descriptive set theory, a subset A of a Polish space X is projective if it is \boldsymbol^1_n for some positive integer n. Here A is.

New!!: List of mathematical logic topics and Projective hierarchy · See more »

## Proof by exhaustion

Proof by exhaustion, also known as proof by cases, proof by case analysis, complete induction, or the brute force method, is a method of mathematical proof in which the statement to be proved is split into a finite number of cases or sets of equivalent cases and each type of case is checked to see if the proposition in question holds.

New!!: List of mathematical logic topics and Proof by exhaustion · See more »

## Proof net

In proof theory, proof nets are a geometrical method of representing proofs that eliminates two forms of bureaucracy that differentiates proofs: (A) irrelevant syntactical features of regular proof calculi such as the natural deduction calculus and the sequent calculus, and (B) the order of rules applied in a derivation.

New!!: List of mathematical logic topics and Proof net · See more »

## 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 approaches to semantics, but in the role that the proposition or logical connective plays within the system of inference.

New!!: List of mathematical logic topics and Proof-theoretic semantics · See more »

## Property of Baire

A subset A of a topological space X has the property of Baire (Baire property, named after René-Louis Baire), or is called an almost open set, if it differs from an open set by a meager set; that is, if there is an open set U\subseteq X such that A \bigtriangleup U is meager (where \bigtriangleup denotes the symmetric difference).

New!!: List of mathematical logic topics and Property of Baire · See more »

## Provability logic

Provability logic is a modal logic, in which the box (or "necessity") operator is interpreted as 'it is provable that'.

New!!: List of mathematical logic topics and Provability logic · See more »

## Prover9

Prover9 is an automated theorem prover for First-order and equational logic developed by William McCune.

New!!: List of mathematical logic topics and Prover9 · See more »

## Pseudoelementary class

In logic, a pseudoelementary class is a class of structures derived from an elementary class (one definable in first-order logic) by omitting some of its sorts and relations.

New!!: List of mathematical logic topics and Pseudoelementary class · See more »

## QED manifesto

The QED manifesto was a proposal for a computer-based database of all mathematical knowledge, strictly formalized and with all proofs having been checked automatically.

New!!: List of mathematical logic topics and QED manifesto · See more »

## Quantifier elimination

Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science.

New!!: List of mathematical logic topics and Quantifier elimination · See more »

## Ramsey cardinal

In mathematics, a Ramsey cardinal is a certain kind of large cardinal number introduced by and named after Frank P. Ramsey.

New!!: List of mathematical logic topics and Ramsey cardinal · See more »

## Rank-into-rank

In set theory, a branch of mathematics, a rank-into-rank is a large cardinal property defined by one of the following four axioms given in order of increasing consistency strength.

New!!: List of mathematical logic topics and Rank-into-rank · See more »

## Rózsa Péter

Rózsa Péter, born Politzer, (17 February 1905 – 16 February 1977) was a Hungarian mathematician and logician.

New!!: List of mathematical logic topics and Rózsa Péter · See more »

## Recursion

Recursion occurs when a thing is defined in terms of itself or of its type.

New!!: List of mathematical logic topics and Recursion · See more »

## Recursive definition

A recursive definition (or inductive definition) in mathematical logic and computer science is used to define the elements in a set in terms of other elements in the set (Aczel 1978:740ff).

New!!: List of mathematical logic topics and Recursive definition · See more »

## Recursive language

In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.

New!!: List of mathematical logic topics and Recursive language · See more »

## Recursively enumerable language

In mathematics, logic and computer science, a formal language is called recursively enumerable (also recognizable, partially decidable, semidecidable, Turing-acceptable or Turing-recognizable) if it is a recursively enumerable subset in the set of all possible words over the alphabet of the language, i.e., if there exists a Turing machine which will enumerate all valid strings of the language.

New!!: List of mathematical logic topics and Recursively enumerable language · See more »

## Recursively enumerable set

In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable, provable or Turing-recognizable if.

New!!: List of mathematical logic topics and Recursively enumerable set · See more »

## Reduct

In universal algebra and in model theory, a reduct of an algebraic structure is obtained by omitting some of the operations and relations of that structure.

New!!: List of mathematical logic topics and Reduct · See more »

## Reductio ad absurdum

In logic, reductio ad absurdum ("reduction to absurdity"; also argumentum ad absurdum, "argument to absurdity") is a form of argument which attempts either to disprove a statement by showing it inevitably leads to a ridiculous, absurd, or impractical conclusion, or to prove one by showing that if it were not true, the result would be absurd or impossible.

New!!: List of mathematical logic topics and Reductio ad absurdum · See more »

## Relevance logic

Relevance logic, also called relevant logic, is a kind of non-classical logic requiring the antecedent and consequent of implications to be relevantly related.

New!!: List of mathematical logic topics and Relevance logic · See more »

## Remarkable cardinal

In mathematics, a remarkable cardinal is a certain kind of large cardinal number.

New!!: List of mathematical logic topics and Remarkable cardinal · See more »

## Resolution (logic)

In mathematical logic and automated theorem proving, resolution is a rule of inference leading to a refutation theorem-proving technique for sentences in propositional logic and first-order logic.

New!!: List of mathematical logic topics and Resolution (logic) · See more »

## Reverse mathematics

Reverse mathematics is a program in mathematical logic that seeks to determine which axioms are required to prove theorems of mathematics.

New!!: List of mathematical logic topics and Reverse mathematics · See more »

## Rice's theorem

In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable.

New!!: List of mathematical logic topics and Rice's theorem · See more »

## Russell's paradox

In the foundations of mathematics, Russell's paradox (also known as Russell's antinomy), discovered by Bertrand Russell in 1901, showed that some attempted formalizations of the naïve set theory created by Georg Cantor led to a contradiction.

New!!: List of mathematical logic topics and Russell's paradox · See more »

## Saharon Shelah

Saharon Shelah (שהרן שלח) is an Israeli mathematician.

New!!: List of mathematical logic topics and Saharon Shelah · See more »

## Sahlqvist formula

In modal logic, Sahlqvist formulas are a certain kind of modal formula with remarkable properties.

New!!: List of mathematical logic topics and Sahlqvist formula · See more »

## Saturated model

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

New!!: List of mathematical logic topics and Saturated model · See more »

## Schröder–Bernstein theorem

In set theory, the Schröder–Bernstein theorem states that, if there exist injective functions and between the sets and, then there exists a bijective function.

New!!: List of mathematical logic topics and Schröder–Bernstein theorem · See more »

## Second-order arithmetic

In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets.

New!!: List of mathematical logic topics and Second-order arithmetic · See more »

## Second-order logic

In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic.

New!!: List of mathematical logic topics and Second-order logic · See more »

## Self-verifying theories

Self-verifying theories are consistent first-order systems of arithmetic much weaker than Peano arithmetic that are capable of proving their own consistency.

New!!: List of mathematical logic topics and Self-verifying theories · See more »

## Sequent

In mathematical logic, a sequent is a very general kind of conditional assertion.

New!!: List of mathematical logic topics and Sequent · See more »

## Sequent calculus

Sequent calculus is, in essence, a style of formal logical argumentation where every line of a proof is a conditional tautology (called a sequent by Gerhard Gentzen) instead of an unconditional tautology.

New!!: List of mathematical logic topics and Sequent calculus · See more »

## Set (mathematics)

In mathematics, a set is a collection of distinct objects, considered as an object in its own right.

New!!: List of mathematical logic topics and Set (mathematics) · See more »

## Set theory

Set theory is a branch of mathematical logic that studies sets, which informally are collections of objects.

New!!: List of mathematical logic topics and Set theory · See more »

## Set theory (music)

Musical set theory provides concepts for categorizing musical objects and describing their relationships.

New!!: List of mathematical logic topics and Set theory (music) · See more »

## Shelah cardinal

In axiomatic set theory, Shelah cardinals are a kind of large cardinals.

New!!: List of mathematical logic topics and Shelah cardinal · See more »

## Signature (logic)

In logic, especially mathematical logic, a signature lists and describes the non-logical symbols of a formal language.

New!!: List of mathematical logic topics and Signature (logic) · See more »

## Simple theorems in the algebra of sets

The simple theorems in the algebra of sets are some of the elementary properties of the algebra of union (infix &cup), intersection (infix &cap), and set complement (postfix ') of sets.

New!!: List of mathematical logic topics and Simple theorems in the algebra of sets · See more »

## Simply typed lambda calculus

The simply typed lambda calculus (\lambda^\to), a form of type theory, is a typed interpretation of the lambda calculus with only one type constructor: \to that builds function types.

New!!: List of mathematical logic topics and Simply typed lambda calculus · See more »

## Singleton (mathematics)

In mathematics, a singleton, also known as a unit set, is a set with exactly one element.

New!!: List of mathematical logic topics and Singleton (mathematics) · See more »

## Skolem normal form

In mathematical logic, a formula of first-order logic is in Skolem normal form if it is in prenex normal form with only universal first-order quantifiers.

New!!: List of mathematical logic topics and Skolem normal form · See more »

## Skolem's paradox

In mathematical logic and philosophy, Skolem's paradox is a seeming contradiction that arises from the downward Löwenheim–Skolem theorem.

New!!: List of mathematical logic topics and Skolem's paradox · See more »

## Soundness

In mathematical 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.

New!!: List of mathematical logic topics and Soundness · See more »

## Space hierarchy theorem

In computational complexity theory, the space hierarchy theorems are separation results that show that both deterministic and nondeterministic machines can solve more problems in (asymptotically) more space, subject to certain conditions.

New!!: List of mathematical logic topics and Space hierarchy theorem · See more »

## Spectrum of a theory

In model theory, a branch of mathematical logic, the spectrum of a theory is given by the number of isomorphism classes of models in various cardinalities.

New!!: List of mathematical logic topics and Spectrum of a theory · See more »

## Stability spectrum

In model theory, a branch of mathematical logic, a complete first-order theory T is called stable in λ (an infinite cardinal number), if the Stone space of every model of T of size ≤ λ has itself size ≤ λ. T is called a stable theory if there is no upper bound for the cardinals κ such that T is stable in κ. The stability spectrum of T is the class of all cardinals κ such that T is stable in κ. For countable theories there are only four possible stability spectra.

New!!: List of mathematical logic topics and Stability spectrum · See more »

## Stable group

In model theory, a stable group is a group that is stable in the sense of stability theory.

New!!: List of mathematical logic topics and Stable group · See more »

## Stable theory

In model theory, a complete theory is called stable if it does not have too many types.

New!!: List of mathematical logic topics and Stable theory · See more »

## Standard part function

In non-standard analysis, the standard part function is a function from the limited (finite) hyperreal numbers to the real numbers.

New!!: List of mathematical logic topics and Standard part function · See more »

## Stephen Cole Kleene

Stephen Cole Kleene (January 5, 1909 – January 25, 1994) was an American mathematician.

New!!: List of mathematical logic topics and Stephen Cole Kleene · See more »

## Strength (mathematical logic)

The relative strength of two systems of formal logic can be defined via model theory.

New!!: List of mathematical logic topics and Strength (mathematical logic) · See more »

## Strict logic

Strict logic is essentially synonymous with relevant logic, though it can be characterized proof-theoretically as.

New!!: List of mathematical logic topics and Strict logic · See more »

## Strong cardinal

In set theory, a strong cardinal is a type of large cardinal.

New!!: List of mathematical logic topics and Strong cardinal · See more »

## Strongly minimal theory

In model theory—a branch of mathematical logic—a minimal structure is an infinite one-sorted structure such that every subset of its domain that is definable with parameters is either finite or cofinite.

New!!: List of mathematical logic topics and Strongly minimal theory · See more »

## 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.

New!!: List of mathematical logic topics and Structural induction · See more »

## Structural proof theory

In mathematical logic, structural proof theory is the subdiscipline of proof theory that studies proof calculi that support a notion of analytic proof.

New!!: List of mathematical logic topics and Structural proof theory · See more »

## Structural rule

In proof theory, a structural rule is an inference rule that does not refer to any logical connective, but instead operates on the judgment or sequents directly.

New!!: List of mathematical logic topics and Structural rule · See more »

## 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.

New!!: List of mathematical logic topics and Structure (mathematical logic) · See more »

## Subset

In mathematics, a set A is a subset of a set B, or equivalently B is a superset of A, if A is "contained" inside B, that is, all elements of A are also elements of B. A and B may coincide.

New!!: List of mathematical logic topics and Subset · See more »

## Substructural logic

In logic, a substructural logic is a logic lacking one of the usual structural rules (e.g. of classical and intuitionistic logic), such as weakening, contraction, exchange or associativity.

New!!: List of mathematical logic topics and Substructural logic · See more »

## Substructure

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 the traces of the functions and relations of the bigger structure.

New!!: List of mathematical logic topics and Substructure · See more »

## Subtle cardinal

In mathematics, subtle cardinals and ethereal cardinals are closely related kinds of large cardinal number.

New!!: List of mathematical logic topics and Subtle cardinal · See more »

## Successor ordinal

In set theory, the successor of an ordinal number α is the smallest ordinal number greater than α.

New!!: List of mathematical logic topics and Successor ordinal · See more »

## Supercompact cardinal

In set theory, a supercompact cardinal is a type of large cardinal.

New!!: List of mathematical logic topics and Supercompact cardinal · See more »

## Superstrong cardinal

In mathematics, a cardinal number κ is called superstrong if and only if there exists an elementary embedding j: V → M from V into a transitive inner model M with critical point κ and V_ ⊆ M. Similarly, a cardinal κ is n-superstrong if and only if there exists an elementary embedding j: V → M from V into a transitive inner model M with critical point κ and V_ ⊆ M. Akihiro Kanamori has shown that the consistency strength of an n+1-superstrong cardinal exceeds that of an n-huge cardinal for each n > 0.

New!!: List of mathematical logic topics and Superstrong cardinal · See more »

## Suslin's problem

In mathematics, Suslin's problem is a question about totally ordered sets posed by and published posthumously.

New!!: List of mathematical logic topics and Suslin's problem · See more »

## System F

System F, also known as the (Girard–Reynolds) polymorphic lambda calculus or the second-order lambda calculus, is a typed lambda calculus that differs from the simply typed lambda calculus by the introduction of a mechanism of universal quantification over types.

New!!: List of mathematical logic topics and System F · See more »

## Systems of Logic Based on Ordinals

Systems of Logic Based on Ordinals was the PhD dissertation of the mathematician Alan Turing.

New!!: List of mathematical logic topics and Systems of Logic Based on Ordinals · See more »

## T-schema

The T-schema or truth schema (not to be confused with 'Convention T') is used to give an inductive definition of truth which lies at the heart of any realisation of Alfred Tarski's semantic theory of truth.

New!!: List of mathematical logic topics and T-schema · See more »

## Tame group

In mathematical group theory, a tame group is a certain kind of group defined in model theory.

New!!: List of mathematical logic topics and Tame group · See more »

## Tarski's exponential function problem

In model theory, Tarski's exponential function problem asks whether the theory of the real numbers together with the exponential function is decidable.

New!!: List of mathematical logic topics and Tarski's exponential function problem · See more »

## Tarski's undefinability theorem

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

New!!: List of mathematical logic topics and Tarski's undefinability theorem · See more »

## Tautology (logic)

In logic, a tautology (from the Greek word ταυτολογία) is a formula or assertion that is true in every possible interpretation.

New!!: List of mathematical logic topics and Tautology (logic) · See more »

## Term algebra

In universal algebra and mathematical logic, a term algebra is a freely generated algebraic structure over a given signature.

New!!: List of mathematical logic topics and Term algebra · See more »

## Theory (mathematical logic)

In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language.

New!!: List of mathematical logic topics and Theory (mathematical logic) · See more »

## Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

New!!: List of mathematical logic topics and Time complexity · See more »

## Time hierarchy theorem

In computational complexity theory, the time hierarchy theorems are important statements about time-bounded computation on Turing machines.

New!!: List of mathematical logic topics and Time hierarchy theorem · See more »

## Tolerant sequence

In mathematical logic, a tolerant sequence is a sequence of formal theories such that there are consistent extensions of these theories with each S_ interpretable in S_i.

New!!: List of mathematical logic topics and Tolerant sequence · See more »

## Trakhtenbrot's theorem

In logic, finite model theory, and computability theory, Trakhtenbrot's theorem (due to Boris Trakhtenbrot) states that the problem of validity in first-order logic on the class of all finite models is undecidable.

New!!: List of mathematical logic topics and Trakhtenbrot's theorem · See more »

## Transfer principle

In model theory, a transfer principle states that all statements of some language that are true for some structure are true for another structure.

New!!: List of mathematical logic topics and Transfer principle · See more »

## Transfinite induction

Transfinite induction is an extension of mathematical induction to well-ordered sets, for example to sets of ordinal numbers or cardinal numbers.

New!!: List of mathematical logic topics and Transfinite induction · See more »

## Tree (descriptive set theory)

In descriptive set theory, a tree on a set X is a collection of finite sequences of elements of X such that every prefix of a sequence in the collection also belongs to the collection.

New!!: List of mathematical logic topics and Tree (descriptive set theory) · See more »

## Tree (set theory)

In set theory, a tree is a partially ordered set (T, \omega + 1.

New!!: List of mathematical logic topics and Tree (set theory) · See more »

## Turing degree

In computer science and mathematical logic the Turing degree (named after Alan Turing) or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set.

New!!: List of mathematical logic topics and Turing degree · See more »

## Turing machine

A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.

New!!: List of mathematical logic topics and Turing machine · See more »

## Type (model theory)

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

New!!: List of mathematical logic topics and Type (model theory) · See more »

## Type theory

In mathematics, logic, and computer science, a type theory is any of a class of formal systems, some of which can serve as alternatives to set theory as a foundation for all mathematics.

New!!: List of mathematical logic topics and Type theory · See more »

## Typed lambda calculus

A typed lambda calculus is a typed formalism that uses the lambda-symbol (\lambda) to denote anonymous function abstraction.

New!!: List of mathematical logic topics and Typed lambda calculus · See more »

## Ultrafinitism

In the philosophy of mathematics, ultrafinitism, also known as ultraintuitionism, strict-finitism, actualism, and strong-finitism, is a form of finitism.

New!!: List of mathematical logic topics and Ultrafinitism · See more »

## Ultraproduct

The ultraproduct is a mathematical construction that appears mainly in abstract algebra and in model theory, a branch of mathematical logic.

New!!: List of mathematical logic topics and Ultraproduct · See more »

## Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is known to be impossible to construct a single algorithm that always leads to a correct yes-or-no answer.

New!!: List of mathematical logic topics and Undecidable problem · See more »

## Unfoldable cardinal

In mathematics, an unfoldable cardinal is a certain kind of large cardinal number.

New!!: List of mathematical logic topics and Unfoldable cardinal · See more »

## Uniformization (set theory)

In set theory, the axiom of uniformization, a weak form of the axiom of choice, states that if R is a subset of X\times Y, where X and Y are Polish spaces, then there is a subset f of R that is a partial function from X to Y, and whose domain (in the sense of the set of all x such that f(x) exists) equals Such a function is called a uniformizing function for R, or a uniformization of R. To see the relationship with the axiom of choice, observe that R can be thought of as associating, to each element of X, a subset of Y. A uniformization of R then picks exactly one element from each such subset, whenever the subset is nonempty.

New!!: List of mathematical logic topics and Uniformization (set theory) · See more »

## Union (set theory)

In set theory, the union (denoted by ∪) of a collection of sets is the set of all elements in the collection.

New!!: List of mathematical logic topics and Union (set theory) · See more »

## Universally measurable set

In mathematics, a subset A of a Polish space X is universally measurable if it is measurable with respect to every complete probability measure on X that measures all Borel subsets of X. In particular, a universally measurable set of reals is necessarily Lebesgue measurable (see #Finiteness condition below).

New!!: List of mathematical logic topics and Universally measurable set · See more »

## 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 given situation.

New!!: List of mathematical logic topics and Universe (mathematics) · See more »

## Urelement

In set theory, a branch of mathematics, an urelement or ur-element (from the German prefix ur-, 'primordial') is an object (concrete or abstract) that is not a set, but that may be an element of a set.

New!!: List of mathematical logic topics and Urelement · See more »

## Vampire (theorem prover)

Vampire is an automatic theorem prover for first-order classical logic developed in the School of Computer Science at the University of Manchester by Andrei Voronkov together with Kryštof Hoder and previously with Alexandre Riazanov.

New!!: List of mathematical logic topics and Vampire (theorem prover) · See more »

## Vaught conjecture

The Vaught conjecture is a conjecture in the mathematical field of model theory originally proposed by Robert Lawson Vaught in 1961.

New!!: List of mathematical logic topics and Vaught conjecture · See more »

## Von Neumann universe

In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted V, is the class of hereditary well-founded sets.

New!!: List of mathematical logic topics and Von Neumann universe · See more »

## Weak interpretability

In mathematical logic, weak interpretability is a notion of translation of logical theories, introduced together with interpretability by Alfred Tarski in 1953.

New!!: List of mathematical logic topics and Weak interpretability · See more »

## Weakly compact cardinal

In mathematics, a weakly compact cardinal is a certain kind of cardinal number introduced by; weakly compact cardinals are large cardinals, meaning that their existence cannot be proven from the standard axioms of set theory.

New!!: List of mathematical logic topics and Weakly compact cardinal · See more »

## Weakly o-minimal structure

In model theory, a weakly o-minimal structure is a model theoretic structure whose definable sets in the domain are just finite unions of convex sets.

New!!: List of mathematical logic topics and Weakly o-minimal structure · See more »

## Well-founded relation

In mathematics, a binary relation, R, is called well-founded (or wellfounded) on a class X if every non-empty subset S ⊆ X has a minimal element with respect to R, that is an element m not related by sRm (for instance, "s is not smaller than m") for any s ∈ S. In other words, a relation is well founded if Some authors include an extra condition that R is set-like, i.e., that the elements less than any given element form a set.

New!!: List of mathematical logic topics and Well-founded relation · See more »

## Well-order

In mathematics, a well-order (or well-ordering or well-order relation) on a set S is a total order on S with the property that every non-empty subset of S has a least element in this ordering.

New!!: List of mathematical logic topics and Well-order · See more »

## Wilkie's theorem

In mathematics, Wilkie's theorem is a result by Alex Wilkie about the theory of ordered fields with an exponential function, or equivalently about the geometric nature of exponential varieties.

New!!: List of mathematical logic topics and Wilkie's theorem · See more »

## Woodin cardinal

In set theory, a Woodin cardinal (named for W. Hugh Woodin) is a cardinal number λ such that for all functions there exists a cardinal κ j(f)(κ) ⊆ M. An equivalent definition is this: λ is Woodin if and only if λ is strongly inaccessible and for all A \subseteq V_\lambda there exists a \lambda_A -A-strong.

New!!: List of mathematical logic topics and Woodin cardinal · See more »

## Word problem for groups

In mathematics, especially in the area of abstract algebra known as combinatorial group theory, the word problem for a finitely generated group G is the algorithmic problem of deciding whether two words in the generators represent the same element.

New!!: List of mathematical logic topics and Word problem for groups · See more »

## Zariski geometry

In mathematics, a Zariski geometry consists of an abstract structure introduced by Ehud Hrushovski and Boris Zilber, in order to give a characterisation of the Zariski topology on an algebraic curve, and all its powers.

New!!: List of mathematical logic topics and Zariski geometry · See more »

## Zermelo set theory

Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory.

New!!: List of mathematical logic topics and Zermelo set theory · See more »

## Zermelo–Fraenkel set theory

In mathematics, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox.

New!!: List of mathematical logic topics and Zermelo–Fraenkel set theory · See more »

## Zero sharp

In the mathematical discipline of set theory, 0# (zero sharp, also 0#) is the set of true formulae about indiscernibles and order-indiscernibles in the Gödel constructible universe.

New!!: List of mathematical logic topics and Zero sharp · See more »

## Zorn's lemma

Zorn's lemma, also known as the Kuratowski–Zorn lemma, after mathematicians Max Zorn and Kazimierz Kuratowski, is a proposition of set theory that states that a partially ordered set containing upper bounds for every chain (that is, every totally ordered subset) necessarily contains at least one maximal element.

New!!: List of mathematical logic topics and Zorn's lemma · See more »

## Redirects here:

Outline of mathematical logic.

## References

[1] https://en.wikipedia.org/wiki/List_of_mathematical_logic_topics