Well ordering principle, Induction

STATS·2023년 7월 16일

0

해석개론

목록 보기

1/4

Well ordering Principle

집합 $S$ 가 $S \subset \N$ , $S \ne \empty$ 일 때, $S$ 는 최솟값을 원소로 포함한다.

S \subset \N, \ S \ne \empty \Rightarrow \exist x \in S, \forall y \in S, \ s.t \ x \le y

Structure of Mathematical Induction

수학적 귀납법은 $n$ 의 값에 따라 참/거짓이 달라지는 명제 $p(n)$ 이 모든 자연수에 대해 참임을 증명할 때 사용하는 증명법이다. 수학적 귀납법의 구조는 다음과 같다.

(Base case) $p(1)$ 이 참임을 증명
(Inductive step) $\forall \ n \in N, \ p(n) \Rightarrow p(n+1)$ 을 증명

[p(1) \ and \ \forall n \in \N, \ p(n) \Rightarrow p(n+1)] \Rightarrow \forall n \in \N, \ p(n)

Proof of Mathematical Induction By WOP

S = \{n | \text{p(n) is not true}\} \\ {} \\ \text{Assume Base case, Inductive step, We want to show } S = \empty. \\ \text{We work by Contradiction.} \\ {} \\ \text{Suppose } S \ne \empty. \ \text{by WOP, }\exist x \in S, \forall y \in S, \ s.t \ x \le y. \\ {} \\ \text{By Base case, p(1) is true. Therefore } 1 \notin S \Rightarrow x > 1. \\ \text{Since x is the least element of S, } (x-1) \notin S \Rightarrow p(x-1) \text{ is true}. \\ {} \\ \text{By Inductive step, } p(x-1) \text{ is true} \Rightarrow p(x) \text{ is true.} \Rightarrow x \notin S \\ \text{This leads to a contradiction, that x is both in S and not in S.} \\ \text{Therefore}, S = \empty.

Example of proof using Mathematical Induction

\text{Proof if } c \ge -1 \text{ then } \forall n \in \N, (1+c)^n \ge 1+nc \\ {} \\ \text{I) Base case} : \text{For n = 1, } (1+c)^1 = (1+1c) \Rightarrow \text{p(1) is true} \\ {} \\ \text{II) Inductive Step : Suppose } (1+c)^n \ge 1+nc. \\ {} \\ \text{Then for n+1, } (1+c)^{n+1} = (1+c)^n (1+c). \\ \text{Since } (1+c) \ge 0, \ (1+c)^n \ge 1+nc \Rightarrow (1+c)^n(1+c) \ge (1+nc) (1+c) \\ = 1+nc+c+nc^2 \ge 1+nc+c \\ \Rightarrow (1+c)^{n+1} \ge 1+(n+1)c \\ {} \\ \therefore \text{if p(n) is true, then p(n+1) is true.}\\ \text{By principle of Induction, } \forall n \in \N, \ p(n) \ is \ true.

다음 포스트

Function, Cardinality : Definition

0개의 댓글