There is no way to do this: proving mathematical induction and proof by contradiction itself

/ SIon | 子虚栈

Original link: https://blog.si-on.top/2023/prove-itself/

Mathematical induction and proof by contradiction are two basic methods for proving problems. They have many uses, such as the summation formula of a sequence, and the proofs of various problems such as limits and inequalities. There are countless proofs, but how can these two methods themselves be established? Why can the conclusion of the hypothesis be extended to N items? Why is the original proposition immediately established if the negative proposition is not established?

The proofs of these two methods themselves seem to touch on some essential issues. Here today I will talk about some of my understanding based on some information I found.

proof of mathematical induction

This method is actually an axiom, coming from the fifth of Peano’s axioms [1] :

Let S⊆N (natural number), and satisfy two conditions (i) 0∈S; (ii) if ∀n∈S, then n’∈S. Then S is the set containing all natural numbers, that is, S=N. Simple expression: If the set S is all natural numbers and meets two conditions: (1) 0 is in the set S. (2) If any given real number n is in the set S, then the successor number n’ of n is also in S, then S is the set containing all natural numbers.

This axiom itself can be proved and requires the use of set theory. Here is the interpretation of @Vidas :

The five Peano axioms (including the axioms of mathematical induction) are actually equivalent to describing the structure of natural numbers. If you want to prove one of the structural descriptions, induction, it is actually equivalent to asking whether it can be constructed with more fragmented tools and materials. A set such that it satisfies all Peano’s axioms? The answer is yes. Starting from set theory, Peano’s axioms are proved as theorems. The objects described by set theory are all sets, and every real number can be a set. So how to use sets to construct natural numbers?

First of all, an axiom of set theory ∃u∀x(x∉u)\exists u\forall x ( x\not\in u) ∃ u ∀ x ( x ∈ u ) , so that there is a set at the beginning, the empty set. A very classic construction method is Von Neumann ordinals , that is, 0←∅,1←0∪{0},2←1∪{1},3←2∪{2},…0 \gets \emptyset, 1 \gets 0 \cup \{0\}, 2\gets 1 \cup \{1\}, 3\gets 2\cup\{2\},\dots 0 ← ∅ , 1 ← 0 ∪ { 0 } , 2 ← 1 ∪ { 1 } , 3 ← 2 ∪ {2} , _ _ … . Therefore, given a set n, we might as well define the progressive operation n+1=n∪{n}n+1 = n \cup \{n\} n + 1 = n ∪ { n } . So what properties should the expected set of natural numbers have?

  1. First: 0∈S0 \in S 0 ∈ S
  2. Secondly: ∀n(n∈S→n+1∈S)\forall n(n \in S \to n+1\in S) ∀n ( n _ ∈ S → n + 1 ∈ S )

The set that satisfies properties 1 and 2 is called an inductive set. However, set theory does not allow you to create a set out of thin air, so we have the following axioms, ∃w(0∈w ∧∀x(x∈w→x+1∈w))\exists w (0\in w\ \wedge \ forall x(x\in w\to x+1\in w)) ∃ w ( 0 ∈ w ∧ ∀x ( x _ ∈ w → x + 1 ∈ w )) . In other words, an induction set w is explicitly created using the axioms.

But inductive sets do not necessarily have induction methods. For example, the set {0,0.5,1,1.5,2,2.5,3,3.5,…}\{0,0.5,1,1.5,2,2.5,3,3.5 ,\dots\} { 0 , 0.5 , 1 , 1.5 , 2 , 2.5 , 3 , 3.5 , … } is also an inductive set, and induction does not hold on this inductive set. The reason for this problem is that there are two disjoint chains in this induction set, one starting from 0 and the other starting from 0.5.

Nevertheless, the set of natural numbers can be defined as, N={x∈w∣∀v(v is inductive set→x∈v)}\mathbb{N} = \{x \in w \mid \forall v(v \text { is inductive set} \to x\in v)\} N = { x ∈ w ∣ ∀ v ( v is inductive set → x ∈ v )} , is actually the intersection of all induction sets. This intersection is the minimal induction set, and there is only one chain starting from 0. Everything is ready. Next, we can start from set theory to prove mathematical induction. ?

Mathematical Induction Theorem: If the proposition about natural numbers PP P satisfies

  1. P(0)P(0) P ( 0 ) is established
  2. P(n)P(n) P ( n ) holds, then P(n+1)P(n+1) P ( n + 1 ) established,

Then we can get the conclusion ∀n∈N\forall n\in\mathbb{N} ∀ n ∈ N P(n)P(n) P ( n ) is established

Proof : Let S={n∈N∣P(n) be true}S = \{n\in \mathbb{N} \mid P(n) \text{is true}\} S = { n ∈ N ∣ P ( n ) is true } , it can be seen that S⊆NS\subseteq\mathbb{N} S ⊆ N. On the other hand, it is not difficult to prove that SS S is an induction set according to N\mathbb{N} Definition of NN⊆S\mathbb{N} \subseteq S N ⊆ S. Therefore, S=NS=\mathbb{N} S = N , certification completed.

In summary, mathematical induction is established because, N\mathbb{N} N is the minimal induction set, which has only one chain starting from 0. For the N\mathbb{N} constructed above N , it is not difficult to prove that it satisfies the other Peano theorems .

Proof by contradiction

Instead of proving the conclusion of a proposition immediately, we first put forward hypotheses that are opposite (repellent) to the conclusion, and then deduce results that are inconsistent with the theorems or axioms, definitions, propositions, etc. that have been proven. This proves the conclusion. The opposite low hypothesis cannot be established, thus confirming that the original conclusion is established. This method of indirectly proving fate is called proof by contradiction. [2]

The method of proof by contradiction is based on the “Law of Contradiction” and “Law of Excluded Middle” in the laws of logical thinking. [3] [4]

  • “Law of Contradiction”: In the same thinking process, two contradictory propositions ( AA A and ¬A\neg A ¬ A ) cannot be true at the same time;
  • “Law of the Excluded Middle”: One of two contradictory propositions must be correct;

Suppose we want to prove proposition AA A : “If a person is alive, he does not need to eat.” According to the method of proof by contradiction, we first

  1. Counter hypothesis: Suppose the negative proposition of proposition A ¬A\neg A ¬ A : “If a person is alive, he needs to eat.”
  2. Reductio ad absurdum: We can easily prove that ¬A\neg A ¬A is established: “Eating is the only way to provide nutrients, and nutrients are needed for survival (self-evident axiom), so you must eat to live.”

There are generally four situations: (1) Contradictory to known conditions; (2) Contradictory to known axioms, theorems, and definitions; (3) Contradictory to assumptions; (4) Self-contradictory.

  1. Conclusion: original proposition AA A is not established

In the process of proving by contradiction, we obtained a judgment that contradicts the proposition ( ¬A\neg A ¬ A ), then according to the “Law of Contradiction”, this contradictory judgment and judgment cannot be true at the same time (it is impossible for a person to live while eating and not eating), there must be one falsehood, and the known conditions, axioms, theorems, and rules can prove AA A is false, so the proposition ¬A\neg A ¬ A must be true; and according to the “law of excluded middle”, the conclusion and the “negative conclusion”, which are opposite mutually negative judgments, cannot be false at the same time, there must be one true, so we get the original conclusion “If a person is alive, he does not need to eat .” must be false.

For a more “mathematical” point, I need to prove the establishment of the law of contradiction and the law of excluded middle. I will leave it here for the time being and wait until I learn it in two days before continuing to write.

  1. The NB axiom that can prove 1+1=2 ↩ ︎

  2. Zhuang Chunlian. A brief discussion on the method of proof by contradiction[J]. Heihe Education, 1995, 0(2):33-34 ↩ ︎

  3. Gao Huiming. Method of proof by contradiction – Lecture series on mathematical thinking methods (10) [J]. Hubei Education, 2019, 0(11):26-27 ↩ ︎

  4. Li Yujie. A brief discussion on the problem of proof by contradiction [J]. Tianjin Education, 1995(6):43-44 ↩ ︎

This article is reproduced from: https://blog.si-on.top/2023/prove-itself/
This site is only for collection, and the copyright belongs to the original author.