Hot answers tagged

177

To determine what can and cannot be proved by contradiction, we have to formalize a notion of proof. As a piece of notation, we let $\bot$ represent an identically false proposition. Then $\lnot A$, the negation of $A$, is equivalent to $A \to \bot$, and we take the latter to be the definition of the former in terms of $\bot$. There are two key logical ...


140

Relatively recent discoveries yield a number of so-called 'natural independence' results that provide much more natural examples of independence than does Gödel's example based upon the liar paradox (or other syntactic diagonalizations). As an example of such results, I'll sketch a simple example due to Goodstein of a concrete number theoretic theorem whose ...


102

Over at this MathOverflow question, I posted the following answer to a similar question (and there are several other interesting answers there): With good reason, we mathematicians prefer a direct proof of an implication over a proof by contradiction, when such a proof is available. (all else being equal) What is the reason? The reason is the fecundity ...


65

A standard example of this is the halting problem, which states essentially: There is no program which can always determine whether another program will eventually terminate. Thus there must be some program which does not terminate, but no proof that it does not terminate exists. Otherwise for any program, we could run the program and at the same time ...


52

Proof by contradiction, as you stated, is the rule$\def\imp{\Rightarrow}$ "$\neg A \imp \bot \vdash A$" for any statement $A$, which in English is "If you can derive the statement that $\neg A$ implies a contradiction, then you can derive $A$". As pointed out by others, this is not a valid rule in intuitionistic logic. But I shall now show you why you ...


47

I actually like this one: There are uncountably many real numbers. However, given that all specifications of specific real numbers (be it by digits, by an algorithm, or even a description of the number in plain English) is ultimately given by a finite string of finitely many symbols, there are only countably many descriptions of real numbers. A ...


46

The situation you ask about, where $P$ is inconsistent with our axioms and $\neg P$ is also inconsistent with our axioms, would mean that the axioms themselves are inconsistent. Specifically, the inconsistency of $P$ with the axioms would mean that $\neg P$ is provable from those axioms. If, in addition, $\neg P$ is inconsistent with the axioms, then the ...


44

If a statements says "not $X$" then it is perfectly fine to assume $X$, arrive at a contradiction and conclude "not $X$". However, in many occasions a proof by contradiction is presented while it is really not used (let alone necessary). The reasoning then goes as follows: Proof of $X$: Suppose not $X$. Then ... complete proof of $X$ follows here... ...


41

The statements that are relevant here are called universal statements (because they involve a universal quantifier). These are the statements of the form "for all foos, statement(foo) is true." Many things you will be asked to prove in mathematics are universal statements, but we are also interested in non-universal statements. The negation of a universal ...


38

It somewhat depends on whether you are intuitionist or not (or both? or neither? Who knows without the law of excluded middle). According to the Wikipedia article even intuitionists accept some versions of what one could call indirect proof, but reject most. In that sense, a direct proof would be preferable (and is often even a bit more elegant). An ...


35

Gödel was able to construct a statement that says "this statement is not provable." The proof is something like this. First create an enumeration scheme of written documents. Then create a statement in number theory "$P(x,y,z)$", which means "if $x$ is interpreted as a computer program, and we input the value $y$, then the value $z$ is the output." (This ...


32

There is a disappointing way of answering your question affirmatively: If $\phi$ is a statement such that First order Peano Arithmetic $\mathsf{PA}$ proves "$\phi$ is provable", then in fact $\mathsf{PA}$ also proves $\phi$. You can replace here $\mathsf{PA}$ with $\mathsf{ZF}$ (Zermelo Fraenkel set theory) or your usual or favorite first order formalization ...


32

It is possible for both $P$ and $ \neg P $ to be consistent with a set of axioms. If this is the case, then $P$ is called independent. There are a few things known to be independent, such as the Continuum Hypothesis being independent of ZFC. It is also possible for both $P$ and $ \neg P $ to be inconsistent with a set of axioms. In this case the axioms ...


30

Yes, a single counterexample is a rigorous proof that an assertion is false. One can often say more, of course: it might be possible, for instance, to exhibit a whole class of counterexamples, or even to show exactly when the assertion is true and when it’s false. It might be possible to show that if the hypotheses are strengthened slightly, the assertion is ...


30

You asked in a comment: Who cares if a theory can prove itself consistent, if it can be proven using some other method? Let us first observe that inconsistent theories are entirely worthless. You want to know if $X$ is true, and then you prove that it is a consequence of theory $T$, so you now go around believing $X$. If you later find that $T$ is ...


27

Simple questions often have complex answers, or no answers at all. If you were to ask me why the sky was blue, to give a complete answer I would have to describe the heliocentric model, the earth's atmosphere, and the electromagnetic spectrum. If you asked me how my computer connected to the internet, the answer would take a considerable amount of time to ...


27

Axioms are not "defined to be true"; I'm not even sure what that would mean. What they are is evaluated as true. Practically speaking all this means is that in the mathematical context at hand, you're allowed to jot them down at any time as the next line in your proof. Definitions have virtually nothing to do with truth, but are instead shorthand for ...


27

There are various ways to interpret the question. One interesting class of examples consists of "speed up" theorems. These generally involve two formal systems, $T_1$ and $T_2$, and family of statements which are provable in both $T_1$ and $T_2$, but for which the shortest formal proofs in $T_1$ are much longer than the shortest formal proofs in $T_2$. One ...


26

Set theory with all sets finite has been studied, is a familiar theory in disguise, and is enough for most/all concrete real analysis. Specifically, Zermelo-Fraenkel set theory with the Axiom of Infinity replaced by its negation (informally, "there is no infinite set") is equivalent to first-order Peano Arithmetic. Call this system finite ZF, the theory of ...


24

Take the Cantorian diagonal argument that, given a countable sequence of infinite binary strings, there must be a string not in the sequence. To get the argument to fly you don't need to actually construct the anti-diagonal string in the sense of print out all the digits (that would indeed be an infinite task)! You just need to be able to specify the string ...


22

I suppose there is a way to formalize your question into a relatively precise one. Let $P$ be the set of all propositions in the language of Zermelo-Frankel set theory for which there exist proofs. Given a natural number $k$ we want to have an upper bound $l(k)$ on the minimal-length of the proof of any proposition $p$ from $P$ such that the length of ...


21

See this post: Are proofs by contradiction weaker than other proofs?. There are some wonderful answers related to your question - and addresses, directly, your "aside": See, in particular, what JDH writes. One of the advantageous to constructing direct proofs of propositions, when this is feasible, is that one can discover other useful propositions in the ...


20

The usual proof of Gödel's First Incompleteness Theorem is entirely constructive. We don't have to rely on excluded middle, or have to rely on proving an existential quantification for which we can't produce a witness. For recall: the proof consists in (a) giving a recipe which takes a suitable specification of a sufficiently strong theory $T$ and constructs ...


20

Start will all one-character strings. Check for each "Is this a proof of my theorem?" Then check the two character strings. Are any of these proofs of my theorem? Repeat for each length $n$ until you find a proof of your theorem. The question, "Is this string a proof of my theorem?" is decidable, so you are done.


19

Proof theorists have obtained several "relative consistency" proofs between classical and constructive theories. These show that if certain theories of classical mathematics are inconsistent, then corresponding theories of constructive mathematics are also inconsistent. These relative consistency results are proved constructively. They show that the ...


19

A contradiction isn't a “problem”. A contradiction is an impossibility. This isn't a matter of saying “Gee, if I have fewer than 20 dollars in the back I won't be able to go out to dinner and I want to so badly, I'll just assume I have more than 20 dollars.” This is a matter of walking into the bank and saying "I'd like to withdraw 20 dollars" and having ...


18

A "proof" in mathematics always means a proof in some system/theory. You have to specify the system/theory that you want a proof for the induction axiom. (You should also formally specify what you mean by the induction axiom since there are various axioms that are called induction axiom.) The induction axiom in an arithmetical theory (like Peano arithmetic) ...


18

"Can't be proven" is an inappropriately vague notion for the question you want to ask. Proven from what axioms? In a logical system that includes Goldbach's conjecture as an axiom, the proof of Goldbach's conjecture is only one line long. So to have the question make sense, you can't just say "proven"; you have to say "proven from such-and-so axioms". ...


17

Most logicians consider proofs by contradiction to be equally valid, however some people are constructivists/intuitionists and don't consider them valid. (Edit: This is not strictly true, as explained in comments. Only certain proofs by contradiction are problematic from the constructivist point of view, namely those that prove "A" by assuming "not A" and ...


17

Sometimes students misinterpret show to mean give an example. I now avoid using show in exams; I always use prove when a proof is required. In the context of examples or calculations, it might be ok use show. For instance, "Show that $2$ is a root of $x^2-4$" or "Show that $\sin x$ is a solution of $y''= -y$.



Only top voted, non community-wiki answers of a minimum length are eligible