2
$\begingroup$

It is the first time for me to ask here.

I recently read about logic and arguments. I read about inductive and deductive reasoning and found myself asking a question.

Are mathematical theorems and facts proved by deductive or inductive reasoning?

I mean sometimes when I think about algebraic facts such as distibutive property of multiplication.

$a(b + c) = ab + ac$

And when I try to prove that property I try proving it with numbers such as:

$2(7) = 14$

$2(3 + 4) = 2(3) + 2(4) = 6 + 8 = 14$

I am ok with that, but this type of reasoning or proof is inductive on which we can't rely to build facts.

And I started to think about all mathematical facts, where I found that there are lots of algebraic or even geometric theorems have no proof but with induction!

My question is can we really rely on induction in maths?

$\endgroup$
  • 4
    $\begingroup$ Mathematical theorems are proved by deductive reasoning. $\endgroup$ – Mauro ALLEGRANZA Dec 2 '17 at 14:46
  • $\begingroup$ I think you are confusing mathematical induction with inductive reasoning. They are quite different things. $\endgroup$ – Derek Elkins Dec 2 '17 at 14:48
  • $\begingroup$ What is the difference? Isn't it induction at all? $\endgroup$ – Yousef Essam Dec 2 '17 at 14:51
  • 6
    $\begingroup$ Nope, mathematical induction is not induction, just as a hot dog is not a dog. I struggle to answer what the difference is, because there is little, if anything, in common. (Please study at least one proof in maths that uses mathematical induction, then you may see for yourself.) $\endgroup$ – user491874 Dec 2 '17 at 15:01
3
$\begingroup$

Just to hammer home the point made by @NoahSchweber

Beginners, in week one of their first logic course, have the contrast between deductive and inductive arguments dinned into them. So emphatically is the distinction made, so firmly are they drilled to distinguish conclusive deductive argument from merely probabilistic inductions, that some students can't help feeling initially pretty uncomfortable when they first hear of 'induction' being used in arithmetic!

So let's be clear. We have a case of empirical, non-conclusive, induction, when we start from facts about a limited sample and infer a claim about the whole population. We sample some swans, for example, and run $k$ checks showing that $\varphi(0)$, $\varphi(1)$, $\varphi(2), \ldots, \varphi(k)$ are all true (where $\varphi(n)$ says that swan #$n$ is white). We hope that these are enough to be representative of the whole population of swans, and so -- taking a chance -- we infer that for all $n$, $\varphi(n)$, now quantifying over over all (numbers for) swans, jumping beyond the sample of size $k$. The gap between the sample and the whole population, between the particular bits of evidence and the universal conclusion, allows space for error. The inference isn't deductively watertight.

By contrast, in the case of arithmetical induction, we start not from a bunch of claims about particular numbers but from an already universally quantified claim about all numbers, i.e. $\forall \mathsf{x}(\varphi(\mathsf{x}) \to \varphi(\mathsf{Sx}))$ (where $\mathsf{Sx}$ is the successor of $\mathsf{x}$). We put that universal claim together with the particular claim $\varphi(0)$ to derive another universal claim, $\forall \mathsf{x}\varphi(\mathsf{x})$. This time, then, we are going from universal to universal, and there is no deductive gap.

You might say 'Pity, then, that we use the same word in talking of empirical induction and arithmetical induction when they are such different kinds of inference.' True enough!

Further help on induction - Daniel Velleman's quite terrific book How to Prove it.

Also some on-line exercises on induction, with detailed worked answers.

$\endgroup$
2
$\begingroup$

Mathematics is deductive. To be more precise, only deductive proofs are accepted in mathematics. Your "inductive proof" of the distributive property wouldn't be accepted as a proof at all, merely as verification for a finite number of cases (1 case in your question). When mathematicians find a statement to be true for a lot of cases (like in $10^{10} $ or infinitely many but not all) and cannot prove that a counter example exists within the remaining cases, they call this statement in its general form a conjecture or open problem. Only after it is proven to be true it can be called a theorem.

Induction in mathematics is probably called like that because it looks a little bit like inductive reasoning: We have a general statement and only show some finite cases to prove the statement? Almost. Induction is a proof technique that requires us to additionally show how we get can use one already proved case to prove another yet unproved case (induction step). Mathematical deductive reasoning can show that by this technique we prove all cases at once, even though in practice we couldn't prove each induction step on its own because this would require infinite time. Instead we prove "all" those induction steps systematically in a generalised one.

For further reading and concrete examples you can look induction in mathematics up in Wikipedia. The distributive property for natural numbers can be proven with induction, but for real numbers it cannot be used, frankly because there are "too many" real numbers.

$\endgroup$
  • $\begingroup$ I can't understand. When can induction be accepted as proofs for theorems? $\endgroup$ – Yousef Essam Dec 2 '17 at 15:53
  • $\begingroup$ Mathematical induction can always be used insofar it helps the proof. Again mathematical induction ISN'T inductive reasoning, but deductive. $\endgroup$ – SK19 Dec 2 '17 at 17:30
  • 1
    $\begingroup$ @YousefEssam The word "induction" in "mathematical induction" or "proof by induction" is very misleading in my opinion; it is a deductive method, not inductive, and is only called "induction" because of a passing resemblance. In general, induction in the broad sense ("it seems to always hold, so it always holds") is never accepted in mathematics. $\endgroup$ – Noah Schweber Dec 2 '17 at 20:58
1
$\begingroup$

Mathematics is built from assumptions called Axioms. Each area of pure math has them, and all logical conclusions are proven from them deductively. For the case of the distributive property, one can easily deductively prove that for all natural $a,b,c$: $$a(b+c)=\overbrace{(b+c)+\cdots +(b+c)}^{a\text{ times}}=\overbrace{b+\cdots +b}^{a\text{ times}}+\overbrace{c+\cdots +c}^{a\text{ times}} = ab+ac$$

There are a few assumptions here: addition is associative, commutative and multiplication is defined by repetitive addition. One system we know holds these properties is Peano arithmetic which shows us how we can deduce the entire arithmetic of the natural numbers with a few simple axioms.

The same goes for Geomtry. The axioms of Euclidean geometry were first laid done by Euclid. He had 5 axioms describing the behavior of the notion of equality, and 5 postulates dictating which objects can exist in geometry (e.g. lines, dots, circles).

As it turns out, most of the work Euclid has done does not deductively follow from his axioms. Some axioms were simply missing. Only in the 20th century did mathematician David Hilbert finalize the axiom list. It contains about 20 axioms, and I hated it when they made me memorize the entire list in university. You can view it here. Pretty much all of Euclidean geometry can be deductively proven from these.

Although using examples is great for understanding, gaining intuition and making a point, math is always deductive. A great modern-day example would be the Riemann hypothesis, which states that all the zeros of some function (of which there are infinitely many) satisfy a certain property. We know that it's true for the first few trillion zeros, but we can't be sure, perhaps the $10^{3205}$th zero does not satisfy it. And this is why it is considered an open problem, there is even a 1,000,000$ prize for proving it.

As for mathematical induction, it is a different notion than what you think of as induction. it roughly states that if the both are satisfied:

  • The statement is true for $0$
  • If the statement is true for $n$, then it is also true for $n+1$

then the statement is true for all natural $n$. Think of it like dominos. You knock of the first one, and each domino knocks the next one after it. You can deductively deduce that all dominos will fall, using mathematical induction.

$\endgroup$
  • $\begingroup$ Do axioms have proofs? Or can they be proved like theorems? And on what basis can we rely on them? $\endgroup$ – Yousef Essam Dec 2 '17 at 15:50
  • 2
    $\begingroup$ Axioms are assumptions and don't have proofs. For example, one of the Peano axioms is "The number 0 exists". This is not something one can prove from nothing. We are given an empty system, and start adding objects using axioms. We start with 0, then we add an axiom "each number in the system has a successor". That way we define 1 to be the successor of 0, which we know exists, because of the axiom we assumed. $\endgroup$ – Bary12 Dec 2 '17 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.