0
$\begingroup$

Let's say I whole-heartedly believe the statement $P(x)$ that all the natural numbers are equal to $1$! (Stupid, I know)

$P(1)$ is true
$P(k) \Rightarrow k = 1$
$P(k+1) \Rightarrow (k+1) = 1$

From step 2, we know that $k = 1$

So, for step 3 we get

$P(k+1) \Rightarrow 1 + 1 = 1$

$ \Rightarrow 2 = 1$

At this point, you could say that this disproves my original statement by contradiction because 1 cannot equal 2.

However, I find this unsatisfactory because $2 = 1$ demonstrates exactly what I stupidly believed in the first place, that all natural numbers are equal to one.

I find it interesting that the technique of induction can give two different answers, depending on what belief you originally hold about the natural numbers. If you are crazy and believe that all numbers are equal to one, it doesn't seem like induction is enough alone to convince you otherwise.

Is this true?

$\endgroup$
  • 1
    $\begingroup$ What is your definition of "natural number"? Peano Axioms tell you that the successor function $n \mapsto n+1$ is injective, so $1+1=1$ is clearly a contradiction. $\endgroup$ – Francesco Polizzi Jun 26 '17 at 22:07
  • $\begingroup$ In the inductive step: $\;\forall k,\;\mathcal P(k)\implies\mathcal P(k+1)$, you simply forgot the $\forall k$ part (as many). With the same induction method, you can prove all horses fly since Pegasus did. $\endgroup$ – Bernard Jun 26 '17 at 22:22
4
$\begingroup$

You need to show that $k+1 = 1$ on the basis of the inductive hypothesis that $k=1$ for some arbitrary $k$. So, you need to show that $1+1=2$ .... but you do no such thing. You just state what you need to prove, and apparently take that statement as proof.

The moral: Don't just write down a bunch of mathematical expressions when trying to prove something. Always clearly separate between what you assume and what you are trying to prove.

EDIT

Now that I understand what you're trying to do and what your question is ... Allow me to first rephrase your question. You are basically asking:

Suppose I believe that all numbers are equal to $1$. Then it doesn't seem like induction will help me prove that I am wrong about this, because when in the inductive proof I get to the point where I end up showing that $2=1$, I don't get a contradiction with my belief, since my belief says exactly that: $2 = 1$, yes, that's right! More general then, it seems like induction cannot show that you are wrong about something since the result of the induction will be compatible with your belief. Is this true?

Answer: No. As long as you believe certain other things, you can use induction to prove a result that contradicts your belief. What you did in your discussion, was to try to prove the very belief that you hold ... and yes, that is not going to help you show you're wrong. That is, you basically do:

Assumption: $\forall n: n=1$

Now let's use induction to show that $\forall n: n=1$

Base: $1=1$. Check

Step: Assume $k=1$. Now, will $k+1=1$? Yes, because of my asumption! So, check!

So, there, we have proven it: $\forall n: n=1$

... well yes ... you can prove it because you assumed it. In fact, any method can prove your result once you assume it. But that does not mean that induction (or any method) can not show you are wrong. As long as you believe other things about numbers, then we can try to use induction to prove other claims .. claims that can end up contradicting your original belief.

Now, given that you believe that all numbers are $1$, I really can't say what other claims you would be willing to agree to ... though probably not too many of the ones that mathematicians hold about numbers, because you effectively end up saying that there is exactly one number: $1$ . That is, you would probably reject the notion that there can be different numbers, and once you rteject that, there is not much left ... But let's assume for the sake of this argument that you do agree to the following claims (after all, you do seem to be ok with induction as a proof technique, and so you do seem to agree that you can reach all numbers, starting with 1, by keep adding 1):

$A$. $1$ is the 'first' natural number. That is, $1$ is not the 'next' number relative to some other number.

$B$. Every number has a 'next' number

(Again, I think that if you believe that all numbers are $1$, and you have some sympathy to the process of induction, you might agree to these as well. That is, presented with these, you might say:

"Yes, $1$ is indeed the first number. It is what starts the induction, so there is no number before it. In fact, it is the only number, since all numbers are equal to it, so what other number could possibly be before it. Ha ha! So sure, I can live with $A$"

"And yes, every number has a 'next' number. This is what we use in the inductive process. In fact, the 'next' number from $1$ is of course just $1$, since all numbers are equal to $1$. Again, no problem there! So sure, I can live with $B$")

OK, but now you will in fact have a contradiction on your hands! By $B$, $1$ has a next number, and by your belief that all numbers are $1$, this will just be $1$ again. But that means that $1$ is the 'next' number from $1$ ... meaning that there is something (namely $1$) that $1$ is the 'next' number of! And that will contradict A.

Of course that is not using induction, but I can use induction if I wanted to. That is, let's use induction that on the basis of your original belief that all numbers are $1$, and that ($B$) all numbers have a 'next' number, it follows that, contrary to A: $1$ isn't just the 'next' number of some number, but of *all numbers! Here is the inductive proof:

Base: $1$ has a next number, and since all numbers are $1$, that next number has to be $1$. So, $1$ is the next number from $1$. Check!

Step: Inductive Hypothesis: Suppose $1$ is the next number from $k$. Now let's show that $1$ is the next number from $k+1$. Well, $k+1$ is a number and, by $B$, has to have a 'next' number. But that next number is of course just $1$, since all numbers are $1$. So, $1$ is the next number from $k+1$. Check!

OK, so now we have proven that $1$ is the next number from all numbers. But wait! That contradicts my belief in A, which says that $1$ is the first number, and thus has nothing 'before' it, because I just proved that everything is 'before' $1$! OK, so since the contradiction was derived from my original belief, $A$, and $B$, I need to reject one of these. Well, I really want to hold on to $A$ and $B$, so there: my original belief that all numbers are $1$ must be mistaken!

OK, so there you have it. I used induction to contradict your original belief, and to indeed possibly make you believe otherwise. Now of course, you could also end up rejecting belief $A$ or $B$ and stubbornly hold on to your original belief, but like I said, there won't be much else you can hold ...

$\endgroup$
  • $\begingroup$ How could I show that k = k without doing the same thing? Wouldn't I also just be stating P(1)=true, p(k) => k=k, and P(k+1) => (k+1) = (k+1). I mean k=k is also what I am trying to prove, but it was a necessary step in the method. Sorry, I need this explained to me like I'm 5 $\endgroup$ – COOLBEANS Jun 27 '17 at 11:48
  • $\begingroup$ When we say that 2=1 is a contradiction, aren't we also assuming that 2 != 1. Isn't our contradiction also based an assumption of how the natural numbers really are? $\endgroup$ – COOLBEANS Jun 27 '17 at 11:52
  • $\begingroup$ @COOLBEANS That's right: to prove $n=n$ for all $n$ using induction, you'd need to show that $k+1=k+1$ in the inductive step, and where you can use the inductive hypothesis that $k=k$. So, you could actually use that: given that $k=k$, we can add $1$ to each side, and thus we get that $k+1=k+1$. But of course we can do this without the inductive hypothesis as well: everything is identical to itself, so $k+1=k+1$ is true by the very nature of $=$. Indeed, there is of course no need to use induction to prove that n=n$ for any $n$ at all! :) $\endgroup$ – Bram28 Jun 27 '17 at 14:42
  • 1
    $\begingroup$ @COOLBEANS Again, you're right: $2=1$ is ot a contradiction in and of itself, but it contradicts the claim that $2 \not = 1$ ... and that is indeed something that follows from 'what the natural numbers are like'. Now you can in fact make that last part very hard, using axioms for the natural numbers ... but yes, ultimately $2 \not = 1 $ because we *defined* $2$ to be the 'next' number from $1$ ... which is of course not $1$ itself. $\endgroup$ – Bram28 Jun 27 '17 at 14:45
  • $\begingroup$ That was helpful. Do these very hard axioms show definitively that 2 > 1 and so on...or can I simply make my own set of axioms which very simply state that all natural numbers are equal to 1. I think it's fascinating that " 2=1 is not a contradiction in and of itself", as you said. So if we re-evaluate my original question: If I clearly state my assumption that all natural numbers are equal to 1, then my induction was, in fact, valid based on that assumption? Thanks for your explanations btw. $\endgroup$ – COOLBEANS Jun 27 '17 at 20:04
1
$\begingroup$

Well, if you want to seriously work with the set of all natural numbers limited to one number, (which for convenience we will call $\{0\}$), which is the result of all arithmetic operations, you can create a well-defined system. But it will be fairly boring :)

In your inductive "proof" -- you are then just reproving the original assumption, not adding any new knowledge to the system...

$\endgroup$
  • $\begingroup$ Is it then possible to make wild assumptions about natural numbers, and prove them to be true if we hold to those wild assumptions? In which case how do know if one set of assumptions is less wild than another? Are they all sort of internally valid? The way I see it, saying that 2!=1 is also relying on an assumption of how the natural numbers are, and so you are also reproving an assumption. I know I sound foolish, but I am learning from people's responses. $\endgroup$ – COOLBEANS Jun 27 '17 at 11:59
  • $\begingroup$ @COOLBEANS you are not proving anything if you assumed what you proved in the first place... $2!=1$ is correct in the system with only 1 natural number, you can say $2!=0$ there as well... $\endgroup$ – gt6989b Jun 27 '17 at 13:08
1
$\begingroup$

This would be true if you had already proven that $2 = 1$. However, you have only stated that it holds for a certain value $k$, and not for the specific case of $k = 2$. On the contrary, the induction step proves that the original statement is false:

Let $P(n)$ be the statement that $n = 1$.

Base case: 1 = 1, so $P(1)$ is correct.

Induction hypothesis: Assume that $P(k)$ is correct for some integer $k$. This means that $k = 1$.

Induction step: $k + 1 = 1 + 1 = 2 \neq 1$.

We cannot yet assume that 2 = 1, since this is exactly what we are trying to prove for all $n \geq 1$.

$\endgroup$
  • $\begingroup$ But, If I am making a claim about the natural numbers, surely we cannot simply dismiss it by referencing another assumption about the natural numbers, namely that 2 != 1. Surely, we cannot dismiss one assumption simply by making another? $\endgroup$ – COOLBEANS Jun 27 '17 at 12:06
1
$\begingroup$

You are not applying induction if you say before hand that $k+1=1$.

That is what you want to prove. You have $k+1=1+1=2$.

Now, only once you prove that $2=1$ will the induction step follow.

$\endgroup$
  • $\begingroup$ But if I was trying to prove that k = k, I would have to do the same thing. p(k) => k = k, and then p(k+1) => k+1 = k+1. In step 2 k=k is also what I am trying to prove. $\endgroup$ – COOLBEANS Jun 27 '17 at 11:38
  • $\begingroup$ In your question, in the third step you write the implication $k+1=1$ which is what you're trying to prove. You can't write $k+1=1$ before having to prove it. You assume something is true for $k$ and then show it is also true for $k+1$. So you can't start by writing $k+1=1$. I think you haven't really understood how to apply induction. $\endgroup$ – Sahiba Arora Jun 27 '17 at 13:07
1
$\begingroup$

Without axioms defining the natural numbers, $1$ and $2$ are simply symbols like $x$ and $y$, and it is perfectly acceptable that $x=y$. Only once you introduce axioms defining the natural numbers, in particular leading to the fact that every pair is distinct, does the equality of two of them become a contradiction.

This resolves your concern that $2=1$ is simply proving what you began with because yes, that is correct. But if you also believe axioms about the integers then the next step is to say that the fact that $1=2$ is in contradiction with your axioms about the integers puts it in contradiction with those axioms.

Ultimately, in order assume something to be true, you are required to make a choice about which axioms will give way to the others. You might equally conclude, that you are so sure that every integer is equal to $1$, that therefore you have disproven the axioms about the integers which they are in contradiction with.

$\endgroup$

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.