Get it on Google Play
New! Download Unionpedia on your Android™ device!
Faster access than browser!

Constructive proof

Index 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. [1]

49 relations: Algorithm, Anne Sjerp Troelstra, Axiom of choice, Brouwer–Heyting–Kolmogorov interpretation, Calculus of constructions, Cauchy sequence, Constructive set theory, Constructivism (mathematics), Counterexample, Curry–Howard correspondence, Diaconescu's theorem, Dirk van Dalen, E. M. Wright, Errett Bishop, Euclid, Euclid's theorem, Existence theorem, Forbidden graph characterization, G. H. Hardy, Gérard Huet, Gelfond–Schneider theorem, Goldbach's conjecture, Graph (discrete mathematics), Graph minor, Intuitionism, Intuitionistic logic, Intuitionistic type theory, Irrational number, J. Roger Hindley, James Franklin (philosopher), Law of excluded middle, Limited principle of omniscience, Logarithm, Mathematical object, Mathematical proof, Mathematics, Non-constructive algorithm existence proofs, Per Martin-Löf, Prime number, Principle of explosion, Probabilistic method, Proof by contradiction, Rational number, Reverse mathematics, Robertson–Seymour theorem, Scripta Mathematica, Square root of 2, Thierry Coquand, Torus.


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

New!!: Constructive proof and Algorithm · See more »

Anne Sjerp Troelstra

Anne Sjerp Troelstra (born 10 August 1939) is Emeritus professor of pure mathematics and foundations of mathematics at the Institute for Logic, Language and Computation (ILLC) of the University of Amsterdam.

New!!: Constructive proof and Anne Sjerp Troelstra · 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!!: Constructive proof and Axiom of choice · See more »

Brouwer–Heyting–Kolmogorov interpretation

In mathematical logic, the Brouwer–Heyting–Kolmogorov interpretation, or BHK interpretation, of intuitionistic logic was proposed by L. E. J. Brouwer and Arend Heyting, and independently by Andrey Kolmogorov.

New!!: Constructive proof and Brouwer–Heyting–Kolmogorov interpretation · 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!!: Constructive proof and Calculus of constructions · See more »

Cauchy sequence

In mathematics, a Cauchy sequence, named after Augustin-Louis Cauchy, is a sequence whose elements become arbitrarily close to each other as the sequence progresses.

New!!: Constructive proof and Cauchy sequence · See more »

Constructive set theory

Constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory.

New!!: Constructive proof and Constructive set theory · See more »

Constructivism (mathematics)

In the philosophy of mathematics, constructivism asserts that it is necessary to find (or "construct") a mathematical object to prove that it exists.

New!!: Constructive proof and Constructivism (mathematics) · See more »


In logic, and especially in its applications to mathematics and philosophy, a counterexample is an exception to a proposed general rule or law.

New!!: Constructive proof and Counterexample · 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!!: Constructive proof and Curry–Howard correspondence · See more »

Diaconescu's theorem

In mathematical logic, Diaconescu's theorem, or the Goodman–Myhill theorem, states that the full axiom of choice is sufficient to derive the law of the excluded middle, or restricted forms of it, in constructive set theory.

New!!: Constructive proof and Diaconescu's theorem · See more »

Dirk van Dalen

Dirk van Dalen (born 20 December 1932, Amsterdam) is a Dutch mathematician and historian of science.

New!!: Constructive proof and Dirk van Dalen · See more »

E. M. Wright

Sir Edward Maitland Wright, FRSE (13 February 1906, Farnley – 2 February 2005, Reading) was an English mathematician, best known for co-authoring An Introduction to the Theory of Numbers with G. H. Hardy.

New!!: Constructive proof and E. M. Wright · See more »

Errett Bishop

Errett Albert Bishop (July 14, 1928 – April 14, 1983) was an American mathematician known for his work on analysis.

New!!: Constructive proof and Errett Bishop · See more »


Euclid (Εὐκλείδης Eukleidēs; fl. 300 BC), sometimes given the name Euclid of Alexandria to distinguish him from Euclides of Megara, was a Greek mathematician, often referred to as the "founder of geometry" or the "father of geometry".

New!!: Constructive proof and Euclid · See more »

Euclid's theorem

Euclid's theorem is a fundamental statement in number theory that asserts that there are infinitely many prime numbers.

New!!: Constructive proof and Euclid's theorem · 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!!: Constructive proof and Existence theorem · See more »

Forbidden graph characterization

In graph theory, a branch of mathematics, many important families of graphs can be described by a finite set of individual graphs that do not belong to the family and further exclude all graphs from the family which contain any of these forbidden graphs as (induced) subgraph or minor.

New!!: Constructive proof and Forbidden graph characterization · See more »

G. H. Hardy

Godfrey Harold Hardy (7 February 1877 – 1 December 1947) was an English mathematician, known for his achievements in number theory and mathematical analysis.

New!!: Constructive proof and G. H. Hardy · See more »

Gérard Huet

Gérard Pierre Huet (born 7 July 1947) is a French computer scientist, linguist and mathematician.

New!!: Constructive proof and Gérard Huet · See more »

Gelfond–Schneider theorem

In mathematics, the Gelfond–Schneider theorem establishes the transcendence of a large class of numbers.

New!!: Constructive proof and Gelfond–Schneider theorem · See more »

Goldbach's conjecture

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics.

New!!: Constructive proof and Goldbach's conjecture · See more »

Graph (discrete mathematics)

In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".

New!!: Constructive proof and Graph (discrete mathematics) · See more »

Graph minor

In graph theory, an undirected graph H is called a minor of the graph G if H can be formed from G by deleting edges and vertices and by contracting edges.

New!!: Constructive proof and Graph minor · See more »


In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach where mathematics is considered to be purely the result of the constructive mental activity of humans rather than the discovery of fundamental principles claimed to exist in an objective reality.

New!!: Constructive proof and Intuitionism · 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!!: Constructive proof 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!!: Constructive proof and Intuitionistic type theory · See more »

Irrational number

In mathematics, the irrational numbers are all the real numbers which are not rational numbers, the latter being the numbers constructed from ratios (or fractions) of integers.

New!!: Constructive proof and Irrational number · See more »

J. Roger Hindley


New!!: Constructive proof and J. Roger Hindley · See more »

James Franklin (philosopher)

James Franklin (born 1953 in Sydney) is an Australian philosopher, mathematician and historian of ideas.

New!!: Constructive proof and James Franklin (philosopher) · See more »

Law of excluded middle

In logic, the law of excluded middle (or the principle of excluded middle) states that for any proposition, either that proposition is true or its negation is true.

New!!: Constructive proof and Law of excluded middle · See more »

Limited principle of omniscience

In constructive mathematics, the limited principle of omniscience (LPO) and the lesser limited principle of omniscience (LLPO) are axioms that are nonconstructive but are weaker than the full law of the excluded middle.

New!!: Constructive proof and Limited principle of omniscience · See more »


In mathematics, the logarithm is the inverse function to exponentiation.

New!!: Constructive proof and Logarithm · See more »

Mathematical object

A mathematical object is an abstract object arising in mathematics.

New!!: Constructive proof and Mathematical object · See more »

Mathematical proof

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

New!!: Constructive proof and Mathematical proof · See more »


Mathematics (from Greek μάθημα máthēma, "knowledge, study, learning") is the study of such topics as quantity, structure, space, and change.

New!!: Constructive proof and Mathematics · See more »

Non-constructive algorithm existence proofs

The vast majority of positive results about computational problems are constructive proofs, i.e., a computational problem is proved to be solvable by showing an algorithm that solves it; a computational problem is shown to be in P (complexity) by showing an algorithm that solves it in time that is polynomial in the size of the input; etc.

New!!: Constructive proof and Non-constructive algorithm existence proofs · See more »

Per Martin-Löf

Per Erik Rutger Martin-Löf (born May 8, 1942) is a Swedish logician, philosopher, and mathematical statistician.

New!!: Constructive proof and Per Martin-Löf · See more »

Prime number

A prime number (or a prime) is a natural number greater than 1 that cannot be formed by multiplying two smaller natural numbers.

New!!: Constructive proof and Prime number · See more »

Principle of explosion

The principle of explosion (Latin: ex falso (sequitur) quodlibet (EFQ), "from falsehood, anything (follows)", or ex contradictione (sequitur) quodlibet (ECQ), "from contradiction, anything (follows)"), or the principle of Pseudo-Scotus, is the law of classical logic, intuitionistic logic and similar logical systems, according to which any statement can be proven from a contradiction.

New!!: Constructive proof and Principle of explosion · See more »

Probabilistic method

The probabilistic method is a nonconstructive method, primarily used in combinatorics and pioneered by Paul Erdős, for proving the existence of a prescribed kind of mathematical object.

New!!: Constructive proof and Probabilistic method · See more »

Proof by contradiction

In logic, proof by contradiction is a form of proof, and more specifically a form of indirect proof, that establishes the truth or validity of a proposition.

New!!: Constructive proof and Proof by contradiction · See more »

Rational number

In mathematics, a rational number is any number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator.

New!!: Constructive proof and Rational number · 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!!: Constructive proof and Reverse mathematics · See more »

Robertson–Seymour theorem

In graph theory, the Robertson–Seymour theorem (also called the graph minor theorem) states that the undirected graphs, partially ordered by the graph minor relationship, form a well-quasi-ordering.

New!!: Constructive proof and Robertson–Seymour theorem · See more »

Scripta Mathematica

Scripta Mathematica was a quarterly journal published by Yeshiva University devoted to the philosophy, history, and expository treatment of mathematics.

New!!: Constructive proof and Scripta Mathematica · See more »

Square root of 2

The square root of 2, or the (1/2)th power of 2, written in mathematics as or, is the positive algebraic number that, when multiplied by itself, gives the number 2.

New!!: Constructive proof and Square root of 2 · See more »

Thierry Coquand

Thierry Coquand (born 18 April 1961 in Jallieu, Isère, France) is a professor in computer science at the University of Gothenburg, Sweden.

New!!: Constructive proof and Thierry Coquand · See more »


In geometry, a torus (plural tori) is a surface of revolution generated by revolving a circle in three-dimensional space about an axis coplanar with the circle.

New!!: Constructive proof and Torus · See more »

Redirects here:

Existence proof, Existential proof, Non-constructive, Non-constructive proof, Nonconstructive, Nonconstructive proof, Proof by construction, Weak counterexample.


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

Hey! We are on Facebook now! »