25
$\begingroup$

I remember seeing a list of False Proofs when I was taking Discrete Maths and I found it to be very interesting and also helpful.

So, if anyone knows some common proof mistakes students make or some cool sneaky way to trick people in a proof send them my way! Bonus points if they're cs/algorithms related.

Thank you so much!

$\endgroup$
9
  • 2
    $\begingroup$ This is better suited for Mathematics. I don't know of false proofs in CS, as the goal of CS is not to learn how to prove correctly. $\endgroup$
    – user16034
    Jun 8, 2023 at 14:15
  • 14
    $\begingroup$ @YvesDaoust There are any number of branches of CS where you need to write proofs. It would also be on topic in Mathematics, but it certainly fits here. $\endgroup$
    – Ray
    Jun 8, 2023 at 18:32
  • 1
    $\begingroup$ @YvesDaoust, while I agree with you in general (and also I voted yesterday to close the question as "needs more focus"), "we will now show you a wrong proof" definitely appears. E.g., I saw cs.stackexchange.com/a/160568/141796 in CLRS or something like that. $\endgroup$
    – Dmitry
    Jun 8, 2023 at 20:25
  • 13
    $\begingroup$ @YvesDaoust Errors in proofwriting were discussed repeatedly in my cs education, particularly as relates to 'proofs' (arguments/calculations) of algorithm correctness or complexity. $\endgroup$ Jun 8, 2023 at 20:42
  • 2
    $\begingroup$ @YvesDaoust Algorithm Design by K&T has an example on Pg. 494 (there were a few more examples too but I don't remember where they were on the top of my head). $\endgroup$ Jun 9, 2023 at 7:10

13 Answers 13

18
$\begingroup$

One of my favourites is the "brothers paradox": https://en.wikipedia.org/wiki/Boy_or_Girl_paradox

I tell it as I learned it*, as follows: in a village, each family has two children, elder and younger. The children are born with probability $\frac12$ for either boy or girl.

I knock on a door, and a boy opens it and says "I'm the elder". What is the probability he has a sister? (clearly $\frac12$).

I knock on another door, and a boy opens it and says "I'm the younger". What is the probability he has a sister? (clearly $\frac12$).

I knock on a third door, and a boy opens it and says nothing. What is the probability he has a sister?

Now the lies start: if I use the law of total probability, I might say something like: $$Pr[sister]=Pr[sister|elder]\cdot Pr[elder]+Pr[sister|younger]\cdot Pr[younger]=\frac{1}{2}Pr[elder]+\frac{1}{2}Pr[younger]=\frac12$$ But on the other hand, I could say that the only case where he does not have a sister is the (boy,boy) setting, and we already know this house is not (girl,girl), so the probability is $\frac23$.

Both are very convincing, if told correctly.

The fallacy is that the sample space is undefined, or put more whimsically "How does the family decide who answers the door?"

*I learned it this way from the legendary Prof. Raz Kupferman.

$\endgroup$
14
  • 1
    $\begingroup$ When converting the informal spec to the formal spec, errors may creep in. $\endgroup$
    – Joshua
    Jun 8, 2023 at 16:28
  • 2
    $\begingroup$ @SirHawrk "each family has two children" - the answer is 1/2. $\endgroup$
    – rus9384
    Jun 9, 2023 at 11:05
  • 3
    $\begingroup$ @Shaull I thought if specific conditions are not specified a true randomness is commonly assumed, i.e. "there is an equal probability that the elder or the younger child would open the door regardless of sexes." In that case the probability indeed would be 1/2. Also, the fact that a (girl, girl) pairing is impossible does not change the probability to 2/3. The chances of (boy, girl) - 25%, (girl, boy) - 25% and (boy, boy) - 50% are not equal here. $\endgroup$
    – rus9384
    Jun 9, 2023 at 12:43
  • 2
    $\begingroup$ To quote a famous saying: "assumption is the mother of all f-ups :)". Indeed, if you assume randomness, then you have a formal setting which you can analyze. But the "paradox" above demonstrates that you must define the model formally, one way or another. $\endgroup$
    – Shaull
    Jun 9, 2023 at 14:05
  • 2
    $\begingroup$ @SolomonUcko right. The main issue (as pointed out in the OP) is that the answer changes if you interpret "B" to be "at least one child is a boy" vs. "a child chosen uniformly at random is a boy." $\endgroup$
    – user168715
    Jun 11, 2023 at 4:36
16
$\begingroup$

Merge-sort can be done in linear time!

Indeed, the time complexity to sort a list or array of length $n$ verifies$^{(1)}$: $$T(n) = T\left(\left\lfloor\frac{n}2\right\rfloor\right) + T\left(\left\lceil\frac{n}2\right\rceil\right)+ \Theta(n)$$

Let us prove by induction that $T(n) = \Theta(n)$:

  • the base case is $n = 1$, and this is the base case of the merge-sort algorithm, which is indeed done in constant time, so $T(1) = \Theta(1)$.
  • assume $T(k) = \Theta(k)$ for all $k< n$, for some $n> 1$. Then using the previous formula and induction hypotheses: $$T(n) = T\left(\left\lfloor\frac{n}2\right\rfloor\right) + T\left(\left\lceil\frac{n}2\right\rceil\right)+ \Theta(n) = \Theta\left(\left\lfloor\frac{n}2\right\rfloor\right) + \Theta\left(\left\lceil\frac{n}2\right\rceil\right)+ \Theta(n) = \Theta(n)$$

By induction, we indeed got that $T(n) = \Theta(n)$ and we got a comparison sort in linear time.$^{(2)}$

$\phantom{a}$

$^{(1)}$ I will not prove that fact, this is a well-known (correct) formula.

$^{(2)}$ Actually, using the same kind of proof, one could prove that the merge operation is done in $\Theta(1)$, and so, merge-sort can be done in $\Theta(1)$ too.

$\endgroup$
3
  • $\begingroup$ That formula seems to be wrong. T(n) = Θ(n) is demonstrated in the wild for sufficiently simple comparison functions (that are sufficient to produce a unique ordering of all distinct integers). $\endgroup$
    – Joshua
    Jun 8, 2023 at 19:25
  • 5
    $\begingroup$ The recursive definition $f(n) = 2 f(n-1)$ must lead to $f=O(n)$ since by induction $f(n-1) = O(n-1)$ and so $f(n) = 2 O(n-1) = O(n)$. Right? :-P Yours is a nice case where the constant hidden by $O(..)$ is not so constant after all. $\endgroup$
    – chi
    Jun 9, 2023 at 15:19
  • 4
    $\begingroup$ This is a lovely one. It really shows one of the subtleties of $O(n)$ notation: it looks like $n$ is a free variable in the equation, but it isn’t, hence why one can’t prove anything about it by induction on $n$. $\endgroup$ Jun 10, 2023 at 12:44
9
$\begingroup$

I have often seen among undergraduates that they believe that the heaps are constructed in $\Theta(n \log n)$ time.

The standard algorithm for that is to insert an element to a heap one after another. Each insertion takes $O(\log n)$ time. Atleast $n/2$ elements have heapify cost $\Theta(\log n)$. This gives overall running time of the algorithm: $\Theta(n \log n)$.

However, interestingly, the heaps can be constructed in $\Theta(n)$ time. The algorithm places all the numbers contiguously in an array. Then the algorithm calls heapify operation starting from the last element and iteretively do the same till the first element. In each heapify call, we are bubbling the elements down. Note that the first element has heapify cost of $\Theta(\log n)$ and atleast $n/2$ elements at the end of the array have heapify cost of $\Theta(1)$. Using simple inequlities, one can show that the total heapify cost adds to only $\Theta(n)$.

I find it a sneaky proof indeed!

$\endgroup$
3
  • 4
    $\begingroup$ Well, it's true that heaps can be constructed in n log(n) time; students just aren't aware of the more optimised algorithm. $\endgroup$
    – Stef
    Jun 9, 2023 at 8:35
  • 3
    $\begingroup$ @Stef Yes true. But even for the optimized algorithm, students mostly answer its complexity as $O(n \log n)$ $\endgroup$ Jun 9, 2023 at 9:29
  • 1
    $\begingroup$ @InuyashaYagami $\left( \exists_a \forall_n f(n) \le a \log n \right) \to \left( \exists_a \forall_n f(n) \le a \; n \log n \right)$, so they're not wrong, exactly. This is why you always need to specify you want the smallest valid class. :-) $\endgroup$
    – Ray
    Jun 9, 2023 at 18:07
9
$\begingroup$

This one is regarding $\mathsf{FPT}$ time algorithm.

Suppose an algorithm has time complexity of: $O((\log n)^k \cdot n^{O(1)})$.

Is it an $\mathsf{FPT}$ time algorithm in parameter $k$?

Well obviously no since the time complexity is not of the form $O(f(k) \cdot n^{O(1)})$. This is what most of people think, and even many researchers in the field as well.

However, that is incorrect!

Interestingly, $(\log n)^k$ $= O(2^{k^2/2} \cdot n)$ (See Hint 3.18, Page 74, from the book: Parameterized Algorithms).

Thus, the running time of the algorithm is $O(2^{k^2/2} \cdot n^{O(1)})$ which is indeed $\mathsf{FPT}$ in parameter $k$.

So, the answer is actually yes!

$\endgroup$
0
8
$\begingroup$

This one is classic.

$0$-$1$ Knapsack problem is polynomial time problem since there is dynamic programming solution with running time $O(n W)$ time.

However, it is incorrect.

Note that the input size is $poly(n + \log W)$. Therefore, the running time of $O(n W)$ is exponential in the input size. Infact, the $0$-$1$ Knapsack problem is $\mathsf{NP}$-hard and the running time of $O(n W)$ is pseudo-polynomial.


Similarly, a naive algorithm for testing if a number is a prime number has running time $O(\sqrt{n})$. It is not polynomial running time algorithm.

$\endgroup$
1
  • 1
    $\begingroup$ A good way to explain the difference between polynomial and pseudopolynomial is to say that the running time is exponential in the precision, rather than in the magnitude, of $W$. For instance, imagine $W$ corresponds to a real-world physical weight. Then the values $W=1$ (in tons), $W=1000$ (in kg), $W=10^6$ (in grams), and $W=10^9$ (in mg) all correspond to the same magnitude of weight, but to a different precision. $\endgroup$
    – Stef
    Jun 9, 2023 at 16:31
6
$\begingroup$

An simple example that I can think of, which is commonly use as introductory topic in amortized analysis, is the analysis of dynamic table. The usual scenario is to analyze the total time needed to insert $n$ elements in a dynamic table with some initial capacity, say 1. Now each time the table is full, it will be resized, say twice the size, by creating a larger table and transferring all current elements to the new table and then proceed with the insertion. Clearly, an insert takes $O(n)$ time in the worst-case. So if there are $n$ elements to be inserted, the total time to insert them all is at most $n \times O(n) = O(n^2) $. This of course is not tight and with some careful analysis, e.g. summing-up the actual time of each insert instead of relying on the worst-case, it can be shown that many of these inserts actually takes $O(1)$ time, hence the time needed to perform the sequence is at most $O(n) $.

$\endgroup$
2
  • 3
    $\begingroup$ I upvoted, although this is a correct proof (and the result $O(n^2)$ is no contradiction, since $O(n) \subseteq O(n^2)$). $\endgroup$
    – Stef
    Jun 9, 2023 at 10:53
  • 2
    $\begingroup$ @stef your observation is correct. I guess it is more of proving tighter upper-bound than correctness. $\endgroup$
    – Russel
    Jun 9, 2023 at 11:00
5
$\begingroup$

Induction often yields great wrong proofs because there are many things which can fail:

  • The induction base $P(0)$ can be false, or it may be missing at all and hence the rest of the induction is based on a false assumption. If the induction base is false, everything else is an ex falso quodlibet.
  • The induction step $P(k) \Rightarrow P(k+1)$ can have an antecedens which is not true for all $k$. Also in this case, we have an ex falso quodlibet.

So, with an ex falso quodlibet, every nonsense can be "proven".

There are many cases where it is not quite obvious that either $P(0)$ or $P(k)$ is actually false. One of my favourites (involving $P(k)$ not being generally true): Every non-negative integer number is twice as large as itself:

$\forall n\in \mathbb{N}, n \geq 0: n = 2n$

https://math.stackexchange.com/questions/2439032/given-a-wrong-proof

$\endgroup$
1
3
$\begingroup$

Along the lines of rexkogitans's remark that proofs by induction are fertile ground for false proofs: one of my favorites is that every natural number can be uniquely described in fifteen English words or less.

Let the set of counterexamples be $S$ and assume, for contradiction, that $S$ is nonempty. Every nonempty set of natural numbers must have a least element; call it $x$.

But then $x$ is "the smallest natural number that cannot be uniquely described in fifteen English words or less", and therefore $x$ is not in $S$, a contradiction. So $S$ must be empty and the theorem holds.

$\endgroup$
5
  • $\begingroup$ This is so interesting! Wait, is the theorem/proof wrong or not? It seems convincing enough $\endgroup$ Jun 11, 2023 at 6:27
  • $\begingroup$ @IbrahimHasaan There could exists different sets S. Therefore, if an x is smallest in one of them, it might not be smallest in other. Therefore the statement: x "the smallest natural number that cannot be uniquely described in fifteen English words or less" is incorrect. $\endgroup$ Jun 11, 2023 at 10:10
  • $\begingroup$ @InuyashaYagami ohhh! very sneaky proof! thank you! $\endgroup$ Jun 12, 2023 at 6:59
  • 1
    $\begingroup$ @InuyashaYagami The statement "there could exist different sets $S$" seems misleading. The clearer point should be that set $S$ is not well defined. Given a natural number $n$ such as 3, 100721, 107966, etc., does $S$ contain $n$ or not? When $S$ is not well defined, it is nonsense to apply math/logic to it so as to deduce any mathematical/logical conclusion about it, such as whether $S$ is empty or not. $\endgroup$
    – John L.
    Jun 18, 2023 at 2:28
  • 1
    $\begingroup$ @user168715 The fundamental problem here has nothing to do with proof by induction. It is about a set that is not well-defined, which it is not a set at all. In particular, we cannot apply "every nonempty set of natural numbers must have a least element" to it. $\endgroup$
    – John L.
    Jun 18, 2023 at 2:36
3
$\begingroup$

Spaghetti sort can sort numbers in linear time.

Assume without loss of generality that the numbers to be sorted are all in the interval $(0,1)$. A whole spaghetti has length $1$.

  1. For each number cut one spaghetti to the corresponding length. This clearly takes $O(n)$.

  2. Grab all the spaghetti and hit the whole bundle on the table upright. Takes $O(1)$.

  3. Lower your hand slowly on the bundle of spaghetti. The first spaghetti you hit corresponds to the biggest number. Remove it from the bundle. Doing this once takes $O(1)$. Repeat this step $n$ times.

Total time to sort the entire stack is $O(n)$.

Edit: I encountered this 'algorithm' first in my student days and we knew there had to be a problem because sorting numbers should always take at least $O(n\log(n))$. I thought the key problem lies in step 2. This step is not actually constant effort, it takes longer with a bigger number of spaghetti. From discussions in the comments I learned that step 1 is not actually linear either. You need to cut to a certain accuracy and this takes more effort if you need higher accuracy.

$\endgroup$
8
  • $\begingroup$ I see. It is similar to counting sort. You just squeezed all numbers in interval 0 to 1. Complexity is actually O(max value). $\endgroup$ Jun 10, 2023 at 6:46
  • $\begingroup$ @InuyashaYagami No, that is not where the trick lies. If you start with arbitrary real numbers you can first apply a function like arctan to each of them and compress them to a finite interval without any loss of information. That step is linear in time. $\endgroup$
    – quarague
    Jun 10, 2023 at 6:54
  • $\begingroup$ I am not talking about that. I am talking about Step 1: "For each number cut one spaghetti to the corresponding length". $\endgroup$ Jun 10, 2023 at 9:13
  • 1
    $\begingroup$ To cut at 0.35, you need precision of two decimal places. Similarly, for every other number. How can that be done is $O(1)$? Maybe you should add to your answer what is wrong with your proof : ) $\endgroup$ Jun 10, 2023 at 16:57
  • 4
    $\begingroup$ I think the precision of the inputs is a red herring here. The proposed "spaghetti sort" is not a comparison-based sorting algorithm and so of course is not required to have $\Omega(n\log n)$ running time. Indeed, if your input is provided in a data structure with $O(1)$ extract-max, you can sort in linear time. Why not? $\endgroup$
    – user168715
    Jun 11, 2023 at 3:58
3
$\begingroup$

Maybe not exactly what you're looking for, but the Monty Hall problem is famously counterintuitive.

There are three doors. One conceals a car, and the other two goats. You select one door. The host opens another door, and it has a goat. By changing your choice to the other closed door, you double your odds of choosing the car, compared to keeping your original choice.

Many readers of Savant's column refused to believe switching is beneficial and rejected her explanation. After the problem appeared in Parade, approximately 10,000 readers, including nearly 1,000 with PhDs, wrote to the magazine, most of them calling Savant wrong...Paul Erdős, one of the most prolific mathematicians in history, remained unconvinced until he was shown a computer simulation demonstrating Savant's predicted result.

https://en.wikipedia.org/wiki/Monty_Hall_problem

$\endgroup$
1
  • 1
    $\begingroup$ A similar-in-spirit probability problem is the birthday paradox, which asks how large can a group of (completely independent) people be before the probability of at least one duplicate birthday exceeds 1/2. The surprising and unintuitive answer is 23. The same logic is directly applicable to analyzing the likelihood of hashing collisions. $\endgroup$
    – pjs
    Jun 9, 2023 at 21:33
2
$\begingroup$

As a general idea, maybe a 'proof' of a greedy algorithm as applied to a problem where the failure case is not immediately obvious?

A classic example (used for introducing Ford-Fulkerson) would be always taking the s-t path with max flow (without creating the residual graph), with some hand waving on how another "optimal" solution replacing paths $P_0, \cdots, P_n$ with paths $Q_0, \cdots, Q_n$ must have the cumulative flow of the first set larger or equal to the second set.

For example (an argument I just came up with): all of the Q flows cannot be added to the current optimal solution, and thus each of them shares a bottleneck with one of the P flows (it cannot bottleneck another flow that is unchanged otherwise the solution we are considering is not feasible). Thus, replacing a P flow with the associated Q flows that it bottlenecks will at most maintain the flow because the bottleneck is still there. This could probably seem believable if the final statement is disguised well and given some supporting "evidence".

A greedy algorithm for set cover also seems very intuitive (because of how similar it seems to other greedy problems) and it takes a bit of thinking to find a counter example.

$\endgroup$
1
$\begingroup$

(Too long and formatting-heavy for a comment.)

For each of the false proofs you linked (https://imgur.com/a/SUT0cRX), here is my brief analysis of each. I've spoilered them in case you want to look at each one individually yourself before checking what I said. Please let me know in the comments if I made any mistakes or you have any questions.

Theorem 0.1:

This is true given the condition that for all x there exists some y such that x ~ y. P.S. #1: This condition is necessary because being reflexive implies this. P.S. #2: https://en.wikipedia.org/wiki/Equivalence_relation#Connections_to_other_relations confirms both parts of this: "A partial equivalence relation is transitive and symmetric. Such a relation is reflexive if and only if it is total, that is, if for all a, there exists some b such that a ∼ b. [ proof 1: If: Given a, let a ∼ b hold using totality, then b ∼ a by symmetry, hence a ∼ a by transitivity. — Only if: Given a, choose b = a, then a ∼ b by reflexivity. ] Therefore, an equivalence relation may be alternatively defined as a symmetric, transitive, and total relation."

Theorem 0.6:

This works for propositions which only have 2 possible values, true or false. It does not work for predicates that are sometimes true and sometimes false.

Theorem 0.2:

"x times" depends on x, but you treated it as a constant. (Also, you divided by x without stating that it must be non-zero.)

Theorem 0.3:

Splitting the square root only works when the terms are positive.

Theorem 0.4:

The inductive step is invalid when n=1, because there is no overlap between the sets.

Theorem 0.5:

The inductive step is invalid when n=0, because 1 is not less than or equal to 0.

$\endgroup$
8
  • 2
    $\begingroup$ Please make your question self-contained, so that we can understand it without having to visit an external link (like your imgur link). Please don't use images of text or mathematics; instead, transcribe them using MathJax/Latex. $\endgroup$
    – D.W.
    Jun 8, 2023 at 17:39
  • $\begingroup$ @D.W. The imgur link is from OP. Do I need to transcribe it all myself? $\endgroup$ Jun 8, 2023 at 21:25
  • 3
    $\begingroup$ I don't understand how this is answering the question. The question asked for some false proofs and gave a few examples. An answer should presumably give more false proofs. General commentary on the false proofs mentioned in the question is not an answer to the question. $\endgroup$
    – D.W.
    Jun 8, 2023 at 21:52
  • 2
    $\begingroup$ If it's not an answer to the question, it should not be posted as an answer. Perhaps it should not be posted at all. It doesn't appear to be what the asker was requesting. The fact that it is too long to post as a comment does not make it correct to post a non-answer as an answer. $\endgroup$
    – D.W.
    Jun 9, 2023 at 8:03
  • 1
    $\begingroup$ @D.W. Counterargument: SE Q&A is not about helping out the poster, but about answering the generic question for both the poster and anybody else who has the same question. The OP is not the exclusive target audience of the answers. That is the 'feature' that makes SE unique. Thus if someone is looking for useful false proofs in education, including the false proofs the OP happened to know about seems to make perfect sense. $\endgroup$ Jun 9, 2023 at 12:35
0
$\begingroup$

Here's a wrong proof, though it only takes a moment's thought to dispel:

"Theorem": $\mathrm{P} \not= \mathrm{NP}$

"proof": There is some oracle $O$ such that $\mathrm{P}^O \not= \mathrm{NP}^O$. But if $\mathrm{P} = \mathrm{NP}$ then $\mathrm{P}^O = \mathrm{NP}^O$ for any oracle $O$! QED.

$\endgroup$
2
  • $\begingroup$ what does the superscript O to a problem class denote here? $\endgroup$
    – Danyal
    Aug 3, 2023 at 18:22
  • $\begingroup$ @Danyal the notation $A^O$ denotes the class of programs that run with resource $A$ and oracle access to some "complete" problem for the class $O$. What "complete" means is usually clear from context, for $\mathrm{P}$, $\mathrm{NP}$ "complete" means "under-polynomial Karp reductions". $\endgroup$
    – cody
    Aug 3, 2023 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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