# Tag Info

142

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

128

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

83

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

61

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

45

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

42

There are really two very different kinds of proofs: Informal proofs are what mathematicians write on a daily basis to convince themselves and other mathematicians that particular statements are correct. These proofs are usually written in prose, although there are also geometrical constructions and "proofs without words". Formal proofs are mathematical ...

42

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

36

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

31

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

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

29

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

29

Starting from the end, if you take Pythagoras' Theorem as an axiom, then proving it is very easy. A proof just consists of a single line, stating the axiom itself. The modern way of looking at axioms is not as things that can't be proven, but rather as those things that we explicitly state as things that hold. Now, exactly what a proof is depends on what ...

26

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

24

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

21

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

19

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.

17

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

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

17

"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

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

16

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

16

The principle of induction (on the natural numbers) is equivalent to the axiom of well-foundedness of the natural numbers. Wikipedia gives (half of) a proof here.

15

First, the good news: There is a strong belief among mathematicians, particularly among mathematical logicians, that nearly all (correct) proofs in the literature could be formalized to the point that a computer could completely verify the proof. There are many automated theorem verifiers ("proof assistants") that have been developed for this ...

14

Yes. For instance, There exists a non-measurable subset of $\mathbb{R}$ (with respect to Lebesgue measure). It requires the axiom of choice; so we could claim that it can't really be found. Any non-constructive proof would be another possible answer. See Wikipedia on constructive proofs. Note the interesting, related question on MO: Are there ...

14

Statements of the form Con(ZFC + T) are never provable in ZFC, because they imply Con(ZFC). Similarly, ZFC can not prove any statement of the form "T is not provable in ZFC", because such statements also imply Con(ZFC). Both of these facts are consequences of Gödel's incompleteness theorems. On the other hand if ZFC + T is consistent, then it is also ...

13

Since you're a high-school student, here's an answer that's less sophisticated and much less rigorous: I suppose you could make up any set of axioms you want, and start using them to prove theorems. So, as you say, you could make Pythagoras' theorem an axiom in your world, and then you wouldn't need to "prove" it. But, if you're going to start making up ...

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