Explaining proof by contradiction using concrete examples

　・In Japanese

■What is proof by contradiction?

Proof by contradiction is a method to prove that if X is not true, a contradiction arises, and therefore X is true.

An example of proof by contradiction is when solving the following "liar problem".

When solving this problem by contradiction, for example, assume that what A is saying is "not true (he is lying)" and show whether a contradiction arises, to verify whether A is telling the truth.



The answer to this problem is that C is lying, as shown below.

■Advantages of using proof by contradiction

Proof by contradiction allows you to indirectly prove a proposition even if you cannot prove it directly. For example, in the above example, to directly prove who is lying, you could measure the height of everyone, but if that is physically impossible, this method is effective. In other words, the advantage of this method is that you can derive the correct answer under limited conditions or with little information.

■An example that seems to be proof by contradiction, but is not

The following is explained by contradiction, but since all that is actually done to prove it is to directly check the height of everyone, it is hard to call it proof by contradiction.

(Proof)
Assume that there is at least one person who is over 190cm tall. When the heights of each person are measured, no one over 190cm tall is found. In other words, this contradicts the assumption, so it can be proven that everyone is under 190cm tall.

List of related articles TOP MENU Mathematics ・Exponential function ・Arctan, tanh ・Matrix multiplication ・Transposed matrix ・Fourier transform ・Fast Fourier Transform ・Matrix derivative ・Manhattan/Euclidean distance ・Centroid ・Vertical bar ・Gaussian integral ・Cosine similarity ・summation Σ, product Π ・Decibel[dB] ・Numerical Differention ・Induction,deduction,abduction ・Spline curve ・Lagrange's Method of Undetermined Multipliers ・Purpose of the matrix ・Proof by contradiction ・Vector field