29
$\begingroup$

Context: I know nothing about proofs and only a small amount about formal logic used in proofs. I'm trying to learn the basics of how to write a proof.

For example, suppose I wanted to prove that "all integers divisible by 4 are also divisible by 2".

My first reaction to this would be: "It's self-evident, because 4 is just 2*2". But this is obviously not a formal proof.

Another attempt: "Any integer n that is divisible by 4 must have 2*2 as part of its prime factorisation, therefore it is divisible by 2." But this seems to be explaining something simple by means of something more complex.

It seems that you are just supposed to know that "all integers divisible by 4 are also divisible by 2" and take it for granted. Or you are supposed to know, more generally, that all integers divisible by N are also divisible by P if N is divisible by P. Do you have to know this beforehand? Do mathematicians sometimes just say "it is true because it's obvious"?.

$\endgroup$
15
  • 11
    $\begingroup$ "But this seems to be explaining something simple by means of something more complex.": pretty much a summary of what mathematics looks like most of the times $\endgroup$
    – Zima
    Commented Jun 11 at 14:47
  • 7
    $\begingroup$ Frankly, mathematicians do sometimes say "... because it's obvious", but this is only acceptable when you and your audience are at a sufficient level of mathematical maturity to synthesize the relevant proof in your head on the fly. Every such claim should be provable, but we don't have enough time in this life to fully write out every proof. So, this is an unfortunate but sometimes-necessary shortcut. When you are just starting to learn formal mathematics, you should avoid this as much as possible and prove everything you can! $\endgroup$ Commented Jun 11 at 14:48
  • 1
    $\begingroup$ little steps don't get written out in proofs because the proofs are trivial and everyone reading the proof is supposed to be able to (easily) proof that themselves, just because it makes a proof very unreadable when writing every trivial step. But technically, every proof should be able to be written in terms of axioms. They don't say "it is true because it's obvious", because if you ask them, they can easily proof it and they know why it's true, they might say "it is obvious that it's true" but that is something different. $\endgroup$ Commented Jun 11 at 14:49
  • 7
    $\begingroup$ Btw, the argument you use makes use of the prime factorization, but doesn't have to: $4|n$ (read as $4$ divides $n$) means there exists an $m$ such that $4\cdot m=n$ but then also $2\cdot(2m)=n$ so per definition $2|n$. $\endgroup$ Commented Jun 11 at 14:50
  • 6
    $\begingroup$ Here's important question to consider. This statement does indeed have a formal proof. Do you know how to write one? If so then, when giving a mathematical exposition on the topic, you can use your own judgement regarding whether the proof is sufficiently simple that you can omit it (or leave it as an exercise). But if not, then you had better learn how to do it!! $\endgroup$
    – Lee Mosher
    Commented Jun 12 at 16:13

5 Answers 5

50
$\begingroup$

Great question, and well done for thinking carefully about the basics of proof and mathematics. Let's get into it!


It seems that you are just supposed to know that "all integers divisible by 4 are also divisible by 2" and take it for granted.

This is not true! We can and must prove it.

In order to prove a statement, we must know what it means. In this case, we must define "divisible".

Definition. Let $a$ and $b$ be integers. We say that "$a$ is divisible by $b$" if there exists an integer $c$ such that $a = bc$.

Now that we know what the statement means, we can prove it!

Proposition. Let $a$ be an integer. If $a$ is divisible by $4$, then $a$ is divisible by $2$.

Proof. Suppose $a$ is divisible by $4$. This means that there is an integer $c$ such that $a = 4c$. Equivalently, $a = 2(2c)$. Since $c$ is an integer, $2c$ is an integer. Thus, $a$ is divisible by $2$. $\square$

Of course it would be annoying to reprove thousands of different statements like this for every instance of a basic divisibility fact we need to use. So, it's much better to prove general statements like the one you suggested. Can you try to prove the following more general statement?

Proposition. Let $a$, $b$, and $c$ be integers. If $a$ is divisible by $b$ and $b$ is divisible by $c$, then $a$ is divisible by $c$.

Proof. Fill me in!


Everything in mathematics is this way. When we want to know that something is true, we must first make careful definitions to specify exactly what it is that we want to prove. Once we have those definitions in place, we can try to prove whatever we want!

$\endgroup$
5
  • 2
    $\begingroup$ Thanks for the answer! As for the problem, I stared at this blankly for a long time, and had a lot of failed lines of thought. At the moment it's hard for me to think in this way, at least quickly. But here's my attempt, using the "divisible" definition you provided above: Proof. Suppose a, b and c are integers where a is divisible by b and b is divisible by c. This means that for some integer d, b=cd, and for some integer e, a=be, and further, that a=cde. Because c is a factor in this product, a is divisible by c. $\endgroup$
    – matt_rule
    Commented Jun 11 at 15:45
  • $\begingroup$ I tried a proof by negation and realised that it was the same difficulty as proving things the positive way. And then I had this argument: '...This means that for some integer d, b=cd therefore to state "a is divisible by b" is to state "a is divisible by cd" and therefore "a is divisible by c" ', but I felt I'd only get half marks for that. $\endgroup$
    – matt_rule
    Commented Jun 11 at 15:50
  • 4
    $\begingroup$ @matt_rule Reword "is a factor" sentence to something like "$a = (cd)·e$ implies $a = c·(de)$, which means $a$ is divisible by $c$", and you got it. $\endgroup$ Commented Jun 11 at 23:36
  • 7
    $\begingroup$ "We can and must prove it" - that very much depends on the context. Not every discussion of mathematics, even in classrooms, is part of a careful systematic development. In this case, yes, the context "want to prove that" deserves something more than "it's obvious" and more concrete than intuitive. $\endgroup$
    – aschepler
    Commented Jun 12 at 1:43
  • 2
    $\begingroup$ In a fully rigorous proof of this, you would explain that the "equivalently" step is valid because multiplication is associative. $\endgroup$
    – Barmar
    Commented Jun 13 at 22:49
16
$\begingroup$

No

Nothing is "self-evident" in mathematics, although this is a relatively new position (circa. 150 years). For millennia, mathematicians considered axioms (or postulates) to be self-evident, but now we consider them to be unprovable assumptions that are accepted so we can do mathematics, and each branch of mathematics may (probably will) be based on different axioms.

For example, the postulates of Euclidian geometry are:

  1. Given any two distinct points, there is a line that contains them.
  2. Any line segment can be extended to an infinite line.
  3. Given a point and a radius, there is a circle with center in that point and that radius.
  4. All right angles are equal to one another.
  5. If a straight line falling on two straight lines makes the interior angles on the same side less than two right angles, the two straight lines, if produced indefinitely, meet on that side on which are the angles less than the two right angles. (The parallel postulate).

Now, for centuries, the parallel postulate bothered people - it's not pithy like the other four, and it doesn't seem quite as "self-evident" - surely, it can be proved from the other four? But it can't be. If you take it away, you get a different branch of mathematics, non-Euclidian geometry, where, among other things, the interior angles of triangles don't add up to 180o. To a large extent, it was the development of non-Euclidian geometries that led mathematicians to the realisation that axioms aren't "self-evident" in the same way that the rules of Association Football aren't self-evident; they're just the rules you have to accept if you want to play the game.

A mathematical statement can only be of the following kinds:

  • An axiom, postulate or assumption which, as stated, is accepted as true to form the basis of the discipline.
  • A theorem is a statement that has been proved from the axioms. Lemma is a minor theorem you prove on your way to a bigger theorem. A corollory is a theorem that pops out as a by-product; for example, in proving two lemmas, a third may also be proven by combining the first two with no further steps.
  • A conjecture is a proposition that is offered on a tentative basis without proof. A conjecture may be resolved by proof (becoming a theorem), disproof (becoming garbage), by being accepted as an independent conjecture (becoming an axiom in a new branch of mathematics), or it may be undecidable (from Godel's incompleteness theorem - unfortunately, for most conjectures, it's undecidable if they're undecidable). It is possible (and done) to build whole branches of mathematics based on a conjectures in the hope that someday someone will prove it.

Since you're working with natural numbers, you need to know the Peano axioms for the natural numbers:

  1. 0 is a natural number.
  2. For every natural number x, x = x. That is, equality is reflexive.
  3. For all natural numbers x and y, if x = y, then y = x. That is, equality is symmetric.
  4. For all natural numbers x, y and z, if x = y and y = z, then x = z. That is, equality is transitive.
  5. For all a and b, if b is a natural number and a = b, then a is also a natural number. That is, the natural numbers are closed under equality.
  6. For every natural number n, S(n) is a natural number, where S is the single-valued successor function (i.e. S(n)=n+1). That is, the natural numbers are closed under S.
  7. For all natural numbers m and n, if S(m) = S(n), then m = n. That is, S is an injection.
  8. For every natural number n, S(n) = 0 is false. That is, there is no natural number whose successor is 0.
  9. If K is a set such that: (a) 0 is in K, and (b) for every natural number n, n being in K implies that S(n) is in K, then K contains every natural number. That is, any natural number can be obtained applying the successor function sufficiently many times to 0.

None of these is "self-evidently" true; they are just the rules we need to define what the natural numbers are. Further, they are insufficient to define the integers, the rationals, the reals, or the complex numbers - each of those needs additional axioms. They're also of little assistance in defining geometry - Euclidian or otherwise.

From these axioms, we can define addition and prove its commutativity. Given addition, we can define multiplication and prove that it is commutative and distributes over addition. Once we have that, we can prove your proposition.

However, it isn't necessary to prove everything from the ground up every time - you are allowed to rely on theorems proved by others. For example, @diracdeltafunk's proof assumes multiplication, which is a perfectly reasonable assumption, but it also presumes that you understand the definition of multiplication over the natural numbers, again, a perfectly reasonable presumption. However, to be a really rigorous proof, it should state that it relies on the definition of multiplication over the natural numbers.

$\endgroup$
11
  • $\begingroup$ Thanks for the background and for exploring the fundamentals of the question! You've given me a lot of things to research. $\endgroup$
    – matt_rule
    Commented Jun 12 at 9:55
  • $\begingroup$ Is the list of mathematical statement types complete?  (For example, ‘1 = 0’ is clearly neither an axiom/postulate/assumption, nor a theorem/lemma/corollary, nor a conjecture.  And would ‘let x = 1’ count as an axiom, since it's clearly neither of the other types?) $\endgroup$
    – gidds
    Commented Jun 12 at 13:21
  • $\begingroup$ I disagree with your claim that "nothing is self-evident in mathematics". Henri Poincaré and others opined that your (9) was self-evident, and that it must be taken as an axiom because there is no way to prove it that is not circular. One can construct a model of the natural numbers, say in ZF, and then prove that (9) holds for the model. But the axioms of ZF are a great deal more complex than your 1—9, and any proof that (9) holds in the ZF model will depend on (9), many times over. For more details see this post quoting Thoralf Skolem. $\endgroup$
    – MJD
    Commented Jun 12 at 15:42
  • 1
    $\begingroup$ @MJD A counterexample: Let K be the set of natural numbers as we know them plus the numbers A, B, C, D where S(A)=B, S(B)=C, S(C)=D, and S(D)=A. This meets all of axioms 1-8 but violates 9. Without 9, the other axioms allow closed loops of numbers outside the normal counting numbers. $\endgroup$
    – Dale M
    Commented Jun 13 at 2:53
  • $\begingroup$ @gidds no, its not complete - its only dealing with for want of a better word "conclusion" statements. Also '1=0' is a disprovable postulate. $\endgroup$
    – Dale M
    Commented Jun 13 at 2:54
13
$\begingroup$

There's an old joke, sometimes claimed to be about Wolfgang Pauli, of a mathematician who says "It is obvious that ..." and when questioned "Is it really?" spends a large amount of time thinking about it (possibly even scribbling down an extensive proof) before finally saying "Yes, it is obvious."

The things we do in mathematics need to be rigorous, and when mathematicians looked at some of the things that were previously taken for granted they found that actually not only were they not obvious, they were potentially broken at quite a fundamental level.

There is another joke that it took 1000 pages to prove that $1+1=2$. The Principia Mathematica is a book that attempts to build mathematics from the ground up, with complete rigor, starting with the very concept of what it even means for a statement to be provable, and the language required to even say what $1+1=2$ even means. Once that's established, actually proving that it's true - in this particular framework - really only takes a few lines.

Once something has been proven, though, it is essentially "free fodder" for future mathematics. If I need to use $1+1=2$ in my own proof, I don't have to write out the entire Principia, I can just say "$1+1=2$ (Russell and Whitehead, 1913)". In fact, I usually only need to include the reference if it's a statement that isn't already considered fundamental to the subject I'm working in. So $1+1=2$ is at this point considered a baseline fact in pretty much any branch of mathematics that might need to refer to it, just like the statement "If $p$ divides $a$ and $a$ divides $b$ then $p$ divides $b$". But that still relies on having a clear understanding of what that all means and the context where we're using it. There are even times when a proof will need to use a smaller result (called a lemma) and the author may only sketch out a basic proof of it if the audience is expected to be able to fill in the blanks themselves.

If you take undergraduate-level courses in topics like logic, proof writing or number theory then you will wind up proving a lot of these apparently obvious things, and it will give you an appreciation of how important it is to be able to do this because mathematicians like to generalise common structures (things like groups, rings and fields are generalisations of sets like the natural numbers and real numbers) and not every proof carries over unscathed. You can have a structure where "$p$ divides $a$" is a meaningful statement, but is it still true that "$p$ divides $a$ and $a$ divides $b$ means $p$ divides $b$"? Better pull up the proof of that in the natural numbers and check whether it still applies here.

So to answer your question, yes it is obvious.

$\endgroup$
3
  • 4
    $\begingroup$ To get a little deeper in the philosophy, $1+1=2$ was of course well-known and "obvious" long before Russell and Whitehead. So maybe more signficant than that proof justifying $1+1=2$, the proof shows that their logical system does model some expected and familiar math. Likewise whether working in Peano, ZF[C], or something just invented, if a theory gives meaning to $=$, $1$, $2$, and $+$, then it ought to model $1+1=2$ (or note how/when/why things differ). $\endgroup$
    – aschepler
    Commented Jun 12 at 1:57
  • 5
    $\begingroup$ @aschepler: So it's the mathematics equivalent of implementing an entire microkernel from scratch, and then writing a hello world program to check that the microkernel works (for a certain bare minimum value of "works," anyway). $\endgroup$
    – Kevin
    Commented Jun 12 at 2:15
  • 1
    $\begingroup$ @aschepler: Yeah, the nature of formalization has evolved. These days, I might show somebody a proof that 2 + 2 = 4 instead. It's still interesting that 1 + 1 = 2, but it's tautological because we usually define 2 as 1 + 1; see the definitions of 2, 3, and 4 in the linked proof. $\endgroup$
    – Corbin
    Commented Jun 12 at 5:05
5
$\begingroup$

The higher the level, the more synthetic the proof of a proposition or theorem is, which is due to practical and situational reasons. At elementary level one needs to be explicit enough while at high level in general the proof is short, incomprehensible to beginners because it is based on background knowledge.

This does not prevent a long proof from being significantly shortened using another route. An example of this is given by Mordell's and Weil's proofs of the Mordell's discovery of the finite basis theorem for elliptic curves (Weil's proof is shorter and simpler than Mordell's but both proofs are rigorous). Another very notable example is given by the proofs of irresolvability with radicals of equations of degree greater than or equal to $5$, given first by Abel and then by Galois, the first being very intricate and the second elegantly concise.

$\endgroup$
0
$\begingroup$

Tangential to this discussion, Poincare's book: science and hypothesis has a great presentation in chapter 1 on "the nature of mathematical reasoning". It addresses the question considered here: "what is mathematics, what is a mathematical proof, what is the necessary rigor that underlies it, etc" and should be readable by anyone who understands recursion and arithmetic.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .