Intereting Posts

Matrix non-identity
Integration with respect to counting measure.
Showing that $G/(H\cap K)\cong (G/H)\times (G/K)$
Find the $least$ number $N$ such that $N=a^{a+2b} = b^{b+2a}, a \neq b$.
Is my proof correct: rank-nullity in a field $K$
Proving that every set $A \subset \Bbb N$ of size $n$ contains a subset $B \subset A$ with $n | \sum_{b \in B} b$
Z coordinates of 3rd point (vertex) of a right triangle given all data in 3D
Is Aleph 0 a natural number?
Sine Approximation of Bhaskara
Is $(P\implies Q)\implies (\lnot Q\implies \lnot P)$ always true?
Proving the integral converges for all $p>1, q<1$
Determine the galois group of $x^5+sx^3+t$
Closed image of locally compact space
Evaluating $\lim_{n\rightarrow\infty}x_{n+1}-x_n$
Kolmogorov's probability axioms

I have searched for an answer to my question but no one seems to be talking about this particular matter..

I will use the all horses are the same color paradox as an example.

Everyone points out that the statement is false for n=2 and that if we want to prove the propositions we should use 2 as the base case for this proof.

- Why isn't $e^{2\pi xi}=1$ true for all $x$?
- What is wrong with this proof of $0=1$?
- Why is $i^3$ (the complex number “$i$”) equal to $-i$ instead of $i$?
- Induction proof. Explain in detail why it’s incorrect
- Finding the fallacy in this broken proof
- fake proof of $\forall a. \forall b. a = b \to 1 = 0$

But, (as I see it..), you have to use reason to figure that out.

My question is, is there anything wrong with induction itself?

except for the fact that we can use reason to understand why the proof is faulty.

This goes for all these problematic propositions..

Thank you all!

- Show that $({\sqrt{2}\!+\!1})^{1/n} \!+ ({\sqrt{2}\!-\!1})^{1/n}\!\not\in\mathbb Q$
- Prove by induction that: $\sum^{2n}_{i=1} \frac{(-1)^{i-1}}{i}=\sum^n_{i=1}\frac{1}{n+i}$
- Prove by induction: $\sum\limits_{k=1}^{n}sin(kx)=\frac{sin(\frac{n+1}{2}x)sin\frac{nx}{2}}{sin\frac{x}{2}}$
- If $a_1,\ldots,a_n>0$ and $a_1+\cdots+a_n<\frac{1}{2}$, then $(1+a_1)\cdots(1+a_n)<2$.
- Is induction valid when starting at a negative number as a base case?
- Induction proof: $S$ contains powers of 2 and predecessors implies $S={\bf N}$
- Solution verification: Prove by induction that $a_1 = \sqrt{2} , a_{n+1} = \sqrt{2 + a_n} $ is increasing and bounded by $2$
- If $\phi$ is a tautology then dual $\phi$ is a contradiction.
- Combinatorics, equality, $n$-permutations with $k$ cycles
- What is the mistake?

“But, (as I see it..), you have to use reason to figure that out. My question is, is there anything wrong with induction itself? except for the fact that we can use reason to understand why the proof is faulty.”

I’m not entirely sure of what you mean with using ‘reason’, but I’m interpreting it as “is there way to spot the mistake in the argument without having the inspiration to check what happens for $n=2$?”

There is. Take Wikipedia’s argument.

Inductive stepAssume that $n$ horses always are the same color. Let us consider a group consisting of $n+1$ horses.

First, exclude the last horse and look only at the first $n$ horses; all these are the same color since $n$ horses always are the same color. Likewise, exclude the first horse and look only at the last $n$ horses. These too, must also be of the same color. Therefore, the first horse in the group is of the same color as the horses in the middle, who in turn are of the same color as the last horse. Hence the first horse, middle horses, and last horse are all of the same color..

Consider a set of $n+1$ horses: $\{h_1, h_2,\ldots ,h_n, h_{n+1}\}$.

Wikipedia now tells you to consider $\{h_2, \ldots ,h_{n+1}\}$ and $\{h_1, \ldots h_n\}$ and apply the induction hypothesis on each of this sets, which then yields that $h_2, \ldots ,h_{n+1}$ are all of the same color and $h_1, \ldots ,h_{n}$ are all of the same color.

Up until this point there’s nothing wrong. But now, to say that $h_1$ has the same color as $h_2$ and consequently as $h_3,\ldots ,h_{n+1}$ you need that $h_2\in \{h_1, \ldots ,h_n\}$, but this is only true if $n>2$, for $n+1=2$ one has $\{h_1 ,\ldots ,h_n\}=\{h_1\}$, so you can’t make further progress.

The formulation that one horse cannot have different colors is mathematically correct,

but useless for the case $n=2$.

Since we need two horses to compare the colors, we

cannot follow that two horses have the same color out of the trivial fact that one horse cannot have different colors.

So, the induction step does not

work from $n=1$ to $n=2$. Thus, the induction is false.

The *induction principle* is expressed in formal terms as follows :

$[P(1) \land \forall n(P(n) \rightarrow P(n+1))] \rightarrow \forall nP(n)$

*Note* : I’m starting from $1$ instead of $0$ in order to comply with the “horses example”.

Consider now this “fake” application of it; let $P(n) := 2 \times n = 2$.

Clearly : $P(1)$ holds; thus, we have the *base* case.

What about the *induction step* ? $P(2) = 2 \times 2 = 4 \ne 2$; thus, $P(2)$ does not hold.

What we can infer about induction ?

$P(1)$ is *true* while $P(2)=P(1+1)$ is *false*. Thus, by the truth-conditions for the *conditional* : $P(1) \rightarrow P(1+1)$ is *false*.

But this implies that $P(n) \rightarrow P(n+1)$ is **not** true for any $n$.

So, the antecedent of the *induction principle* : $P(1) \land \forall x(P(x) \rightarrow P(x+1))$ is *false* and the principle does not license us to infer anything about “all” $P(x)$’s, because a conditional with *false* antecedent is always true, irrespective of the consequent.

In conclusion, we have not “falsified” the induction principle …

In the specific case, induction is not an issue here : having showed that $P(2)$ does not hold, we have already showed that $\forall nP(n)$ is *false*.

What we have learned from this “fake” example regarding the *horses paradox* ?

That the purported proof of the

induction stepis flawed, because we cannot correctly deduce, from the (true) fact that all the horses belonging to a single-members set of horses have the same color, the (false) fact that all the horses belonging to a two-members set of horses have the same color.

The problem with any of these “fake proofs” is that at some point the “proof”

make an additional, unspoken assumption that is not valid to make at that point.

If you observe that such an assumption is made, you know immediately that

the proof is unsound.

You do not necessarily know at that point that the conclusion is false,

but you don’t believe it to be true merely on account of this “proof” either.

This is not a problem with induction per se. It is a problem with proving virtually *any*

substantial result. That is why there are various popular fake “proofs” that do not use

mathematical induction at all.

For example, you can “prove” false results by dividing both sides of an equation by zero,

or by relying on the way objects appear to be arranged in a geometric diagram without

actually establishing that they really must be arranged that way (things that look

like straight lines but are not, points listed in order $A,B,C$ on a line when in

actuality they would occur in sequence $B,A,C,$ and so forth).

In the typical “proof” that all horses are the same color, there is a step that

makes the unspoken assumption that $n \geq 2$ even though it is only actually

given that $n \geq 1.$ The trick works when the unwary listener does not

notice the invalid assumption.

People doing real math can make an invalid assumption during an attempted proof too,

although usually something much more subtle than these.

In short, methods of mathematical proof are sound, but individual human beings are

fallible and do not always follow the rules, even when we try to.

If everyone simply accepted any one individual’s work without checking it,

we might indeed have a lot of false mathematics regarded as true.

Fortunately that is not the way mathematics is done.

- Find all $x$ such that $x^6 = (x+1)^6$.
- Orthogonality for Binomial Coefficients
- Does finite expectation imply bounded random variable?
- Is convex open set in $\mathbb{R}^n$ is regular?
- Approximating Borel sets by finite unions of intervals
- A set is infinite iff it is equivalent to a proper subset of itself
- Why is cross product only defined in 3 and 7 dimensions?
- Is the null set a subset of every set?
- Solving non homogeneous recurrence relation
- Finding the probability density function of $Y=e^X$, where $X$ is standard normal
- Algebraic equation problem – finding $x$
- Test for convergence with either comparison test or limit comparison test
- Sequences of sets property
- If $\frac{z^2_{1}}{z_{2}z_{3}}+\frac{z^2_{2}}{z_{3}z_{1}}+\frac{z^2_{3}}{z_{1}z_{2}} = -1.$Then $|z_{1}+z_{2}+z_{3}|$
- Using Fourier series to calculate an infinite sum