Say that we're asked to give a proof of 'proof by induction'.

i.e. for some property $P$, proving that $$\forall n,P(1) \wedge [P(k) \implies P(k+1)] \implies \forall n, P(n)$$.

Now, I understand the following proof, but it seems rather superfluous:

Assume that $P(1)$ and that $P(k) \implies P(k+1).$

Assume, towards a contradiction, that there exists at least one positive integer $n$ such that $P(n)$ is false, which means the set $S=\{n:P(n) \ \text{is false}\}$ is nonempty.

By the well-ordering property, there exists a smallest element of $S$- let's call it $m$ ($\in \Bbb{Z^+}$)

Now, $m\neq 1$, since $P(1)$ is true (by assumption), so $m>1$.

Now, $m-1<m$, and $m-1 \in \mathbb{Z^+}, $ so $\underbrace{m-1 \notin S}_{m \ \text{is the smallest element of }S}$, so $P(m-1) \ \text{is true}$.

But we have that $P(k) \implies P(k+1)$ by assumption, so $P(m)$ must be true (since $P(m-1)$ is true), a contradiction. Hence, the set $S=\{n:P(n) \ \text{is false}\}$ is empty. i.e. $\forall n, P(n)$. $\square$

Now, I think that this proof really labours the point. Why is it not sufficient just to say that $P(1)$ is true, and $P(k) \implies P(k+1)$, therefore, $P(2) \implies P(3) \implies P(4) \implies ... \implies P(n) \implies...$


Most of the time in mathematics, the concept of proof is an informal one, more importantly it is a social concept. Meaning that what counts as a proof is what certain people say it counts as a proof (e.g. your audience, your lecturer, journal reviewers, etc).

But there is another instance of what proof means, a well defined instance, namely that of formal proof.
Neither of your proofs is a formal one, so if any of them counts as a proof is something that is person-dependent.

Personally, at this level of elementary-hood, anything that includes $\ldots$ to me doesn't count as a proof, I'd rather call it a layout, plausibility argument or general description of what the actual ('social') proof would look like. (I would however accept $\ldots$ if used at a more complex level). I also reject anything related to drawings as proofs. I accept the first version as proof over the second one because it's much clearer how one would formalize it.

  • $\begingroup$ So, unless it consists purely of algebraic symbols, it's not considered a formal proof? Out of curiosity, how would one go about formalising this proof? $\endgroup$ – beep-boop May 17 '14 at 13:51
  • 1
    $\begingroup$ @alexqwx It can consist purely of algebraic symbols and still not be a formal proof. In order to formalize a proof you need a formal a system, i.e., a 'list' of axioms and deduction rules. Given this you can then formalize the concept of proof within the formal system and with this definition you can give formal proofs. See some examples of formal proofs in propositional calculus here and here. $\endgroup$ – Git Gud May 17 '14 at 13:56

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.