Aproximate World Population

The number of people on the planet Earth is now...

Monday, September 17, 2018



These references further demonstrate that the Logic I used in the Book of Pure Logic, is proven through Mathematics, and more advanced logic in intuitionism and constructive proof. Expanding the correct methods of deduction and inference.


Intuitionistic logic

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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. In particular, systems of intuitionistic logic do not include the law of the excluded middle and double negation elimination, which are fundamental inference rules in classical logic.

Formalized intuitionistic logic was originally developed by Arend Heyting to provide a formal basis for Brouwer's programme of intuitionism. From a proof-theoretic perspective, Heyting’s calculus is a restriction of classical logic in which the law of excluded middle and double negation elimination have been removed. Excluded middle and double negation elimination can still be proved for some propositions on a case by case basis, however, but do not hold universally as they do with classical logic.

Several systems of semantics for intuitionistic logic have been studied. One of these semantics mirrors classical Boolean-valued semantics but uses Heyting algebras in place of Boolean algebras. Another semantics uses Kripke models. These, however, are technical means for studying Heyting’s deductive system rather than formalizations of Brouwer’s original informal semantic intuitions. Semantical systems claim to capture such intuitions, due to offering meaningful concepts of “constructive truth” (rather than merely validity or provability), are Gödel’s dialectica interpretation, Kleene’s realizability, Medvedev’s logic of finite problems,[1] or Japaridze’s computability logic. Yet such semantics persistently induce logics properly stronger than Heyting’s logic. Some authors have argued that this might be an indication of inadequacy of Heyting’s calculus itself, deeming the latter incomplete as a constructive logic.[2]

The syntax of formulas of intuitionistic logic is similar to propositional logic or first-order logic. However, intuitionistic connectives are not definable in terms of each other in the same way as in classical logic, hence their choice matters. In intuitionistic propositional logic (IPL) it is customary to use →, ∧, ∨, ⊥ as the basic connectives, treating ¬A as an abbreviation for (A → ⊥). In intuitionistic first-order logic both quantifiers ∃, ∀ are needed.

Weaker than Classical Logic[edit]
Intuitionistic logic is weaker than classical logic. Each theorem of intuitionistic logic is a theorem in classical logic. Many tautologies in classical logic are not theorems in intuitionistic logic. Examples include the law of excluded middle p ∨ ¬p, Peirce's law ((p → q) → p) → p, and double negation elimination ¬¬p → p. But double negation introduction p → ¬¬ p is a theorem.

Rejecting excluded middle may seem strange to those more familiar with classical logic. To prove it in intuitionistic logic, it is necessary to prove the truth or falsity of all possible propositional formulae, which is impossible for a variety of reasons.

Non-interdefinability of operators[edit]
In classical propositional logic, it is possible to take one of conjunction, disjunction, or implication as primitive, and define the other two in terms of it together with negation, such as in Łukasiewicz's three axioms of propositional logic. It is even possible to define all four in terms of a sole sufficient operator such as the Peirce arrow (NOR) or Sheffer stroke (NAND). Similarly, in classical first-order logic, one of the quantifiers can be defined in terms of the other and negation.

These are fundamentally consequences of the law of bivalence, which makes all such connectives merely Boolean functions. The law of bivalence does not hold in intuitionistic logic, only the law of non-contradiction. As a result, none of the basic connectives can be dispensed with, and the above axioms are all necessary. Most of the classical identities are only theorems of intuitionistic logic in one direction, although some are theorems in both directions.

Relation to other logics[edit]
Intuitionistic logic is related by duality to a paraconsistent logic known as Brazilian, anti-intuitionistic or dual-intuitionistic logic.[12]

The subsystem of intuitionistic logic with the FALSE axiom removed is known as minimal logic.

Relation to many-valued logic[edit]
Kurt Gödel's work involving many-valued logic showed in 1932 that intuitionistic logic is not a finite-valued logic.[13] (See the section titled Heyting algebra semantics above for an infinite-valued logic interpretation of intuitionistic logic.)

Relation to intermediate logics[edit]
Any finite Heyting algebra which is not equivalent to a Boolean algebra defines (semantically) an intermediate logic. On the other hand, validity of formulae in pure intuitionistic logic is not tied to any individual Heyting algebra but relates to any and all Heyting algebras at the same time.

Relation to modal logic[edit]
Any formula of the intuitionistic propositional logic may be translated into the normal modal logic S4 as follows...



Constructive proof

From Wikipedia, the free encyclopedia
Jump to navigationJump to search

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. This is in contrast to a non-constructive proof (also known as an existence proof or pure existence theorem) which proves the existence of a particular kind of object without providing an example. For avoiding confusion with the stronger concept that follows, such a constrictive proof is sometimes called an effective proof.

A constructive proof may also refer to the stronger concept of a proof that is valid in Constructive mathematics. Constructivism is a mathematical philosophy that rejects all proof methods that involve the existence of objects that are not explicitly built. This excludes, in particular, the use of the law of the excluded middle, the axiom of infinity, and the axiom of choice, and induces a different meaning for some terminology (for example, the term "or" has a stronger meaning in constructive mathematics than in classical).

Some non-constructive proofs show that if a certain proposition is false, a contradiction ensues; consequently the proposition must be true (proof by contradiction). However, the principle of explosion (ex falso quodlibet) has been accepted in some varieties of constructive mathematics, including intuitionism.

Constructive proofs can be seen as defining certified mathematical algorithms: this idea is explored in the Brouwer–Heyting–Kolmogorov interpretation of constructive logic, the Curry–Howard correspondence between proofs and programs, and such logical systems as Per Martin-Löf's Intuitionistic Type Theory, and Thierry Coquand and Gérard Huet's Calculus of Constructions.

1 An historical example
2 Examples
2.1 Non-constructive proofs
2.2 Constructive proofs
3 Brouwerian counterexamples
4 See also
5 References
6 Further reading
7 External links
An historical example
Until the end of 19th century, all mathematical proofs were essentially constructive. The first non-constructive constructions appeared with Georg Cantor theory of infinite set, and the formal definition of real numbers.

The first use of non-constructive proof for solving previously considered seems to be Hilbert's Nullstellensatz and Hilbert's basis theorem. From a philosophical point of view, the former is specially interesting, as implying the existence of a well specified object.

Nullstellensatz may be stated as follows: If {\displaystyle f_{1},\ldots ,f_{k}} f_{1},\ldots ,f_{k} are polynomials in n indeterminates with complex coefficients, which have no common complex zeros, then there are polynomial {\displaystyle g_{1},\ldots ,g_{k}} {\displaystyle g_{1},\ldots ,g_{k}} such that

{\displaystyle f_{1}g_{1}+\ldots +f_{k}g_{k}.} {\displaystyle f_{1}g_{1}+\ldots +f_{k}g_{k}.}
Such a non-constructive existence theorem was such a surprise for mathematicians of that time that one of them, Paul Gordan wrote: "this is not mathematics, it is theology".

Twenty five years later, Grete Hermann provided an algorithm for computing {\displaystyle g_{1},\ldots ,g_{k},} {\displaystyle g_{1},\ldots ,g_{k},} which is not a constructive proof in the strong sense, as she used Hilbert's result. She proved that, if {\displaystyle g_{1},\ldots ,g_{k}} {\displaystyle g_{1},\ldots ,g_{k}} exist, they can be found with degrees less than

{\displaystyle 2^{2^{n}}.} {\displaystyle 2^{2^{n}}.}
This provides an algorithm, as the problem is reduced to solving a system of linear equations, by considering as unknowns the finite number of coefficients of the {\displaystyle g_{i}.} g_{i}.

Non-constructive proofs
First consider the theorem that there are an infinitude of prime numbers. Euclid's proof is constructive. But a common way of simplifying Euclid's proof postulates that, contrary to the assertion in the theorem, there are only a finite number of them, in which case there is a largest one, denoted n. Then consider the number n! + 1 (1 + the product of the first n numbers). Either this number is prime, or all of its prime factors are greater than n. Without establishing a specific prime number, this proves that one exists that is greater than n, contrary to the original postulate.

Now consider the theorem "There exist irrational numbers {\displaystyle a} a and {\displaystyle b} b such that {\displaystyle a^{b}} a^{b} is rational." This theorem can be proven using a constructive proof, or using a non-constructive proof.

The following 1953 proof by Dov Jarden has been widely used as an example of a non-constructive proof since at least 1970:[1][2]

339. A Simple Proof That a Power of an Irrational Number to an Irrational Exponent May Be Rational.
{\displaystyle {\sqrt {2}}^{\sqrt {2}}} {\sqrt {2}}^{\sqrt {2}} is either rational or irrational. If it is rational, our statement is proved. If it is irrational, {\displaystyle ({\sqrt {2}}^{\sqrt {2}})^{\sqrt {2}}=2} (\sqrt{2}^{\sqrt{2}})^{\sqrt{2}} = 2 proves our statement.
     Dov Jarden     Jerusalem

In a bit more detail:

Recall that {\displaystyle {\sqrt {2}}} {\sqrt {2}} is irrational, and 2 is rational. Consider the number {\displaystyle q={\sqrt {2}}^{\sqrt {2}}} q = \sqrt{2}^{\sqrt2}. Either it is rational or it is irrational.
If {\displaystyle q} q is rational, then the theorem is true, with {\displaystyle a} a and {\displaystyle b} b both being {\displaystyle {\sqrt {2}}} {\sqrt {2}}.
If {\displaystyle q} q is irrational, then the theorem is true, with {\displaystyle a} a being {\displaystyle {\sqrt {2}}^{\sqrt {2}}} \sqrt{2}^{\sqrt2} and {\displaystyle b} b being {\displaystyle {\sqrt {2}}} {\sqrt {2}}, since
{\displaystyle \left({\sqrt {2}}^{\sqrt {2}}\right)^{\sqrt {2}}={\sqrt {2}}^{({\sqrt {2}}\cdot {\sqrt {2}})}={\sqrt {2}}^{2}=2.} \left (\sqrt{2}^{\sqrt2}\right )^{\sqrt2} = \sqrt{2}^{(\sqrt{2} \cdot \sqrt{2})} = \sqrt{2}^2 = 2.
This proof is non-constructive because it relies on the statement "Either q is rational or it is irrational"—an instance of the law of excluded middle, which is not valid within a constructive proof. The non-constructive proof does not construct an example a and b; it merely gives a number of possibilities (in this case, two mutually exclusive possibilities) and shows that one of them—but does not show which one—must yield the desired example.

It turns out that {\displaystyle {\sqrt {2}}^{\sqrt {2}}} \sqrt{2}^{\sqrt2} is irrational because of the Gelfond–Schneider theorem, but this fact is irrelevant to the correctness of the non-constructive proof.

Constructive proofs
A constructive proof of the above theorem on irrational powers of irrationals would give an actual example, such as:

{\displaystyle a={\sqrt {2}}\,,\quad b=\log _{2}9\,,\quad a^{b}=3\,.} a = \sqrt{2}\, , \quad b = \log_2 9\, , \quad a^b = 3\, .
The square root of 2 is irrational, and 3 is rational. {\displaystyle \log _{2}9} \log_2 9 is also irrational: if it were equal to {\displaystyle m \over n} m \over n, then, by the properties of logarithms, 9n would be equal to 2m, but the former is odd, and the latter is even.

A more substantial example is the graph minor theorem. A consequence of this theorem is that a graph can be drawn on the torus if, and only if, none of its minors belong to a certain finite set of "forbidden minors". However, the proof of the existence of this finite set is not constructive, and the forbidden minors are not actually specified. They are still unknown.

Brouwerian counterexamples
In constructive mathematics, a statement may be disproved by giving a counterexample, as in classical mathematics. However, it is also possible to give a Brouwerian counterexample to show that the statement is non-constructive. This sort of counterexample shows that the statement implies some principle that is known to be non-constructive. If it can be proved constructively that a statement implies some principle that is not constructively provable, then the statement itself cannot be constructively provable. For example, a particular statement may be shown to imply the law of the excluded middle. An example of a Brouwerian counterexample of this type is Diaconescu's theorem, which shows that the full axiom of choice is non-constructive in systems of constructive set theory, since the axiom of choice implies the law of excluded middle in such systems. The field of constructive reverse mathematics develops this idea further by classifying various principles in terms of "how nonconstructive" they are, by showing they are equivalent to various fragments of the law of the excluded middle.

Brouwer also provided "weak" counterexamples.[3] Such counterexamples do not disprove a statement, however; they only show that, at present, no constructive proof of the statement is known. One weak counterexample begins by taking some unsolved problem of mathematics, such as Goldbach's conjecture, which asks whether every even natural number larger than 4 is the sum of two primes. Define a sequence a(n) of rational numbers as follows:[4]

{\displaystyle a(n)={\begin{cases}(1/2)^{n}&{\mbox{if every even natural number in the interval }}[4,n]{\mbox{ is the sum of two primes}},\\(1/2)^{k}&{\mbox{if }}k{\mbox{ is the least even natural number in the interval }}[4,n]{\mbox{ which is not the sum of two primes}}\end{cases}}} {\displaystyle a(n)={\begin{cases}(1/2)^{n}&{\mbox{if every even natural number in the interval }}[4,n]{\mbox{ is the sum of two primes}},\\(1/2)^{k}&{\mbox{if }}k{\mbox{ is the least even natural number in the interval }}[4,n]{\mbox{ which is not the sum of two primes}}\end{cases}}}
For each n, the value of a(n) can be determined by exhaustive search, and so a is a well defined sequence, constructively. Moreover, because a is a Cauchy sequence with a fixed rate of convergence, a converges to some real number α, according to the usual treatment of real numbers in constructive mathematics.

Several facts about the real number α can be proved constructively. However, based on the different meaning of the words in constructive mathematics, if there is a constructive proof that "α = 0 or α ≠ 0" then this would mean that there is a constructive proof of Goldbach's conjecture (in the former case) or a constructive proof that Goldbach's conjecture is false (in the latter case). Because no such proof is known, the quoted statement must also not have a known constructive proof. However, it is entirely possible that Goldbach's conjecture may have a constructive proof (as we do not know at present whether it does), in which case the quoted statement would have a constructive proof as well, albeit one that is unknown at present. The main practical use of weak counterexamples is to identify the "hardness" of a problem. For example, the counterexample just shown shows that the quoted statement is "at least as hard to prove" as Goldbach's conjecture. Weak counterexamples of this sort are often related to the limited principle of omniscience.

See also
Errett Bishop - author of the book "Foundations of Constructive Analysis".
Existence theorem#'Pure' existence results
Non-constructive algorithm existence proofs
Probabilistic method

 J. Roger Hindley, "The Root-2 Proof as an Example of Non-constructivity", unpublished paper, September 2014, full text Archived 2014-10-23 at the Wayback Machine.
 Dov Jarden, "A simple proof that a power of an irrational number to an irrational exponent may be rational", Curiosa No. 339 in Scripta Mathematica 19:229 (1953)
 A. S. Troelstra, Principles of Intuitionism, Lecture Notes in Mathematics 95, 1969, p. 102
 Mark van Atten, 2015, "Weak Counterexamples", Stanford Encyclopedia of Mathematics
Further reading
J. Franklin and A. Daoud (2011) Proof in Mathematics: An Introduction. Kew Books, ISBN 0-646-54509-4, ch. 4
Hardy, G.H. & Wright, E.M. (1979) An Introduction to the Theory of Numbers (Fifth Edition). Oxford University Press. ISBN 0-19-853171-0
Anne Sjerp Troelstra and Dirk van Dalen (1988) "Constructivism in Mathematics: Volume 1" Elsevier Science. ISBN 978-0-444-70506-8
External links
Weak counterexamples by Mark van Atten, Stanford Encyclopedia of Philosophy
Categories: Mathematical proofsConstructivism (mathematics)