FACTOID # 12: It's not the government they hate: Washington DC has the highest number of hate crimes per capita in the US.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Reductio ad absurdum (Latin: "reduction to the absurd") also known as an apagogical argument, reductio ad impossibile, or proof by contradiction, is a type of logical argument where one assumes a claim for the sake of argument, derives an absurd or ridiculous outcome, and then concludes that the original assumption must have been wrong as it led to an absurd result. It makes use of the law of non-contradiction — a statement cannot be both true and false. In some cases it may also make use of the law of excluded middle — a statement must be either true or false. The phrase is traceable back to the Greek η εις άτοπον απαγωγή (hê eis átopon apagogê), meaning "reduction to the impossible", often used by Aristotle. Latin is an ancient Indo-European language originally spoken in Latium, the region immediately surrounding Rome. ... In logic, an argument is a set of statements, consisting of a number of premises, a number of inferences, and a conclusion, which is said to have the following property: if the premises are true, then the conclusion must be true or highly likely to be true. ... In logic, the law of noncontradiction judges as false any proposition P asserting that both proposition Q and its denial, proposition not-Q, are true at the same time and in the same respect. In the words of Aristotle, One cannot say of something that it is and that it... â€œExcluded middleâ€ redirects here. ... Aristotle (Greek: AristotÃ©lÄ“s) (384 BC â€“ 322 BC) was a Greek philosopher, a student of Plato and teacher of Alexander the Great. ...

In formal logic, reductio ad absurdum is used when a formal contradiction can be derived from a premise, allowing one to conclude that the premise is false. If a contradiction is derived from a set of premises, this shows that at least one of the premises is false, but other means must be used to determine which one.

Reductio ad absurdum is also often used to describe an argument where a conclusion is derived in the belief that everyone (or at least those being argued against) will accept that it is false or absurd. However, this is a weak form of reductio, as the decision to reject the premise requires that the conclusion is accepted as being absurd. Although a formal contradiction is by definition absurd (unacceptable), a weak reductio ad absurdum argument can be rejected simply by accepting the purportedly absurd conclusion.

There is a fairly common misconception that reductio ad absurdum simply denotes "a silly argument" and is itself a formal fallacy. However, this is not correct; a properly constructed reductio constitutes a correct argument. When reductio ad absurdum is in error, it is because of a fallacy worked into the example, somewhere, not the act of reduction itself. In philosophy, the term logical fallacy properly refers to a formal fallacy : a flaw in the structure of a deductive argument which renders the argument invalid. ...

The infinitude of primes

A classic (arguably the classic) reductio argument is the one used by Euclid to show that there are infinitely many prime numbers. For suppose there are only finitely many primes; say the complete list is p1 to pn. Then we can find the number In mathematics, a prime number, or prime for short, is a natural number greater than one and whose only distinct positive divisors are 1 and itself. ...

P = (p1 × p2 × ... × pn) + 1.

But P cannot be a multiple of any of the pns (division leaves remainder 1). Thus either P is prime itself or P has a prime factor which is not on the list; in either case, the list is not complete. This is absurd, since the list cannot be both complete and incomplete. Thus our assumption was false -- there are infinitely many primes.

Another classic reductio proof from Greek mathematics is the proof that the square root of 2 is irrational. The square root of 2 is equal to the length of the hypotenuse of a right triangle with legs of length 1. ...

Cubing-the-cube puzzle

A more recent use of a reductio argument is the proof that a cube cannot be cut into a finite number of smaller cubes with no two the same size. Consider the smallest cube on the bottom face; on each of its four sides, either a neighbouring cube or the border of the main cube is rising above it. This means that any larger cube will not fit on top of it (the "footprint" of such a cube is too large). Since different cubes aren't permitted to have the same sizes, only smaller cubes can be placed directly on top of it. But then the smallest of these would likewise be surrounded by larger cubes, so could only have smaller cubes directly on top of it... and so on, in an infinite regress, requiring an infinite number of cubes, which violates our conditions. (This gives rise to a proof by induction that the cubing-the-cube puzzle is also unsolvable in dimensions higher than three.) An infinite regress is a series of propositions arises if the truth of proposition P1 requires the support of proposition P2, and for any proposition in the series Pn, the truth of Pn requires the support of the truth of Pn+1. ...

Say we wish to disprove proposition p. The procedure is to show that assuming p leads to a logical contradiction. Thus, according to the law of non-contradiction, p must be false. Broadly speaking, a contradiction is an incompatibility between two or more statements, ideas, or actions. ...

Say instead we wish to prove proposition p. We can proceed by assuming "not p" (i.e. that p is false), and show that it leads to a logical contradiction. Thus, according to the law of non-contradiction, "not p" must be false, and so, according to the law of the excluded middle, p is true.

In symbols:

To disprove p: one uses the tautology [p ^ (R ^ ~R)] → ~p where R is any proposition and the "^" symbol is taken to mean and. Assuming p, one proves R and ~R, together they imply ~p. Within the study of logic, a tautology is a statement containing more than one sub-statement, that is true regardless of the truth values of its parts. ...

To prove p: one uses the tautology [~p ^ (R ^ ~R)] →p where R is any proposition. Assuming ~p, one proves R and ~R, together they imply p.

For a simple example of the first kind, consider the proposition "there is no smallest rational number greater than 0". In a reductio ad absurdum argument, we would start by assuming the opposite: that there is a smallest rational number, say, r0.

Now let x = r0/2. Then x is a rational number, and it's greater than 0; and x is smaller than r0. (In the above symbolic argument, "x is the smallest rational number" would be R and "r (which is different from x) is the smallest rational number" would be ~R.) But that contradicts our initial assumption that r0 was the smallest rational number. So we can conclude that the original proposition must be true — "there is no smallest rational number greater than 0".

It is not uncommon to use this first type of argument with propositions such as the one above, concerning the non-existence of some mathematical object. One assumes that such an object exists, and then proves that this would lead to a contradiction; thus, such an object does not exist. For other examples, see proof that the square root of 2 is not rational and Cantor's diagonal argument. In mathematics, an irrational number is any real number that is not a rational number â€” that is, it is a number which cannot be expressed as a fraction m/n, where m and n are integers. ... Cantors diagonal argument, also called the diagonalisation argument, the diagonal slash argument or the diagonal method, was published in 1891 by Georg Cantor as a proof that there are infinite sets which cannot be put into one-to-one correspondence with the infinite set of natural numbers. ...

On the other hand, it is also common to use arguments of the second type concerning the existence of some mathematical object. One assumes that the object doesn't exist, and then proves that this would lead to a contradiction; thus, such an object must exist. Although it is quite freely used in mathematical proofs, not every school of mathematical thought accepts this kind of argument as universally valid. In schools such as intuitionism, the law of the excluded middle is not taken as true. From this way of thinking, there is a very significant difference between proving that something exists by showing that it would be absurd if it did not; and proving that something exists by constructing an actual example of such an object. These schools will still, however, accept arguments of the first kind concerning non-existence. A famous example of the second kind is Brouwer's own proof of his fixed point theorem, which shows that it is impossible for certain fixed points not to exist, without being able to show how to obtain one in the general case. // Philosophy of mathematics is the branch of philosophy that studies the philosophical assumptions, foundations, and implications of mathematics. ... In the philosophy of mathematics, intuitionism, or neointuitionism (opposed to preintuitionism), is an approach to mathematics as the constructive mental activity of humans. ... The law of excluded middle (tertium non datur in Latin) states that for any proposition P, it is true that (P or ~P). ... Luitzen Egbertus Jan Brouwer (February 27, 1881 - December 2, 1966), usually cited as L. E. J. Brouwer, was a Dutch mathematician, a graduate of the University of Amsterdam, who worked in topology, set theory, measure theory and complex analysis. ... In mathematics, the Brouwer fixed point theorem states that every continuous function from the closed unit ball D n to itself has a fixed point. ...

It is important to note that to form a valid proof, it must be demonstrated that the assumption being made for the sake of argument implies a property that is actually false in the mathematical system being used. The danger here is the logical fallacy of argument from lack of imagination, where it is proven that the assumption implies a property which looks false, but is not really proven to be false. Traditional (but incorrect!) examples of this fallacy include false proofs of Euclid's fifth postulate (a.k.a. the parallel postulate) from the other postulates. The argument from ignorance, also known as argumentum ad ignorantiam (appeal to ignorance [1]) or argument by lack of imagination, is a logical fallacy in which it is claimed that a premise is true only because it has not been proven false, or that a premise is false only because... Euclid (Greek: ), also known as Euclid of Alexandria, was a Greek mathematician of the Hellenistic period who flourished in Alexandria, Egypt, almost certainly during the reign of Ptolemy I (323 BC-283 BC). ... a and b are parallel, the transversal t produces congruent angles. ...

The reason these examples are not really examples of this fallacy is that the notion of proof was different in the 19th century; (Euclidean) geometry was seen as being a 'true' reflection of physical reality, and so deducing a contradiction by concluding something physically implausible (like the angles of a triangle not being 180 degrees) was acceptable. Doubts about the nature of the geometry of the universe led mathematicians such as Bolyai, Gauss, Lobachevsky, Riemann, among others, to question and clarify what actually constituted 'geometry'. Out of these men's work, resulted Non-Euclidean geometry. For a further exposition of these misunderstandings see Morris Kline, Mathematical Thought: from Ancient to Modern Times. Alternative meaning: Nineteenth Century (periodical) (18th century &#8212; 19th century &#8212; 20th century &#8212; more centuries) As a means of recording the passage of time, the 19th century was that century which lasted from 1801-1900 in the sense of the Gregorian calendar. ... János Bolyai (December 15, 1802&#8211;January 27, 1860) was a Hungarian mathematician. ... Johann Carl Friedrich Gauss or GauÃŸ ( ; Latin: ) (30 April 1777 â€“ 23 February 1855) was a German mathematician and scientist of profound genius who contributed significantly to many fields, including number theory, analysis, differential geometry, geodesy, electrostatics, astronomy, and optics. ... Nikolay Ivanovich Lobachevsky Nikolai Ivanovich Lobachevsky (&#1053;&#1080;&#1082;&#1086;&#1083;&#1072;&#769;&#1081; &#1048;&#1074;&#1072;&#769;&#1085;&#1086;&#1074;&#1080;&#1095; &#1051;&#1086;&#1073;&#1072;&#1095;&#1077;&#769;&#1074;&#1089;&#1082;&#1080;&#1081;) (December 1, 1792 - February 24, 1856) was a Russian mathematician. ... Bernhard Riemann. ... Behavior of lines with a common perpendicular in each of the three types of geometry The term non-Euclidean geometry describes hyperbolic, elliptic and absolute geometry, which are contrasted with Euclidean geometry. ... Morris Kline (1 May 1908 â€“ 10 June 1992) was a Professor of Mathematics, a writer on the history, philosophy, and teaching of mathematics, and also a popularizer of mathematical subjects. ...

In mathematical logic

In mathematical logic, the reductio ad absurdum is represented as: Mathematical logic is a subfield of mathematics that is concerned with formal systems in relation to the way that they encode intuitive concepts of mathematical objects such as sets and numbers, proofs, and computation. ...

if
$S cup { p } vdash F$
then
$S vdash neg p.$

or

if
$S cup { neg p } vdash F$
then
$S vdash p.$

In the above, p is the proposition we wish to prove or disprove; and S is a set of statements which are given as true — these could be, for example, the axioms of the theory we are working in, or earlier theorems we can build upon. We consider p, or the negation of p, in addition to S; if this leads to a logical contradiction F, then we can conclude that the statements in S lead to the negation of p, or p itself, respectively.

Note that the set-theoretic union, in some contexts closely related to logical disjunction (or), is used here for sets of statements in such a way that it is more related to logical conjunction (and). In set theory and other branches of mathematics, the union of a collection of sets is the set that contains everything that belongs to any of the sets, but nothing else. ... OR logic gate. ... AND Logic Gate In logic and mathematics, logical conjunction (usual symbol and) is a two-place logical operation that results in a value of true if both of its operands are true, otherwise a value of false. ...

Notation

Proof by reductio ad absurdum often end "Contradiction!", or "Which is a contradiction.". Isaac Barrow and Baermann used the notation Q.E.A., for "quod est absurdum" ("which is absurd"), along the lines of Q.E.D., but this notation is rarely used today[1]. A graphical symbol sometimes used for contradictions is a downwards zigzag arrow "lightning" symbol (U+21AF: ↯), for example in Davey and Priestley[2] Isaac Barrow (October 1630 - May 4, 1677) was an English divine, scholar and mathematician who is generally given minor credit for his role in the development of modern calculus; in particular, for his work regarding the tangent; for example, Barrow is given credit for being the first to calculate the... Look up QED in Wiktionary, the free dictionary. ...

Quotes

In the words of G. H. Hardy (A Mathematician's Apology), "Reductio ad absurdum, which Euclid loved so much, is one of a mathematician's finest weapons. It is a far finer gambit than any chess gambit: a chess player may offer the sacrifice of a pawn or even a piece, but a mathematician offers the game." G. H. Hardy Professor Godfrey Harold Hardy FRS (February 7, 1877 â€“ December 1, 1947) was a prominent English mathematician, known for his achievements in number theory and mathematical analysis. ... A Mathematicians Apology is a 1940 essay by British mathematician G. H. Hardy (ISBN 0521427061). ... A gambit is a chess opening in which something, usually a pawn, but sometimes even a piece, is sacrificed in order to achieve an advantage. ... Chess is a recreational and competitive game for two players. ...

References

1. ^ Hartshorne on QED and related
2. ^ B. Davey and H.A. Prisetley, Introduction to lattices and order, Cambridge University Press, 2002.

Results from FactBites:

 Reductio ad Absurdum [Internet Encyclopedia of Philosophy] (2568 words) Reductio ad absurdum is a mode of argumentation that seeks to establish a contention by deriving an absurdity from its denial, thus arguing that a thesis must be accepted because its rejection would be untenable. The first of these is reductio ad absurdum in its strictest construction and the other two cases involve a rather wider and looser sense of the term. A classic instance of reductio reasoning in Greek mathematics relates to the discovery by Pythagoras - disclosed to the chagrin of his associates by Hippasus of Metapontum in the fifth century BC - of the incommensurability of the diagonal of a square with its sides.
More results at FactBites »

Share your thoughts, questions and commentary here