Well Ordering Principle

In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which $x$ precedes $y$ if and only if  $y$ is either $x$ or the sum of $x$ and some positive integer (other orderings include the ordering $2,4,6$; and $1,3,5$).

The phrase "well-ordering principle" is sometimes taken to be synonymous with the "well-ordering theorem". On other occasions it is understood to be the proposition that the set of integers $\{…,−2,−1,0,1,2,3,…\}$ contains a well-ordered subset, called the natural numbers, in which every nonempty subset contains a least element.

Well-ordering Principle: If $S$ is a non-empty set of non-negative integers, then $S$ has a least element, i.e., there is an integer $c \in S$ such that $c \le x$ for all $ x \in S$.

The principle of mathematical induction follows directly from well-ordering principle.

(Principle of Induction): Let $S$ be set of positive integers such that
1. $1 \in S$
2. $k \in S \implies  k + 1 \in S$
Then $S$ is the the set $N$ of all natural numbers.
Proof: Consider the complement $S'$ of the set $S$ in $N$:
$$S' = N - S:$$
We want to show that $S'$ is the empty set.Suppose $S'$ is non-empty. Then by wellordering principle it has a least element, say $n'$. Clearly, $n' \ne 1$ as $1 \in S$.Therefore $n' - 1$ is a natural number which is not in $S'$. Hence $n' -1 \in S$. By hypothesis, $n'- 1 \in S \implies n' \in S$. Therefore, $n' \in S \cap S'$, which is a contradiction. Therefore $S'$ must be empty, and $S = N$.
 
Mathematical induction is a powerful proof technique used to prove statements about natural numbers. The principle of mathematical induction can be stated as follows:

Principle of Mathematical Induction: Suppose we have a statement $P(n)$ that we want to prove for all natural numbers $n \geq a$, where $a$ is some fixed natural number. If we can establish two things:
1.Base Case: Prove that the statement holds for the smallest value of $n$, usually $n=a.$
2.Inductive Step: Prove that if the statement holds for some arbitrary $k \geq a$, then it also holds for the next natural number $k+1$.

Then, we can conclude that the statement $P(n)$ is true for all natural numbers $n \geq a$.

Proof by Mathematical Induction:

Let $P(n)$ be the statement that we want to prove for all natural numbers $n \geq a$.

Base Case: Verify that $P(a)$ is true.

Inductive Step: Assume that $P(k)$ is true for some arbitrary natural number $k \geq a$. Then, show that under this assumption, $P(k+1)$ is also true.

Conclusion: By the principle of mathematical induction, $P(n)$ is true for all natural numbers $n \geq a$.

Example:

Let's prove the statement $P(n)$: "The sum of the first $n$ positive integers is given by the formula $\frac{n(n+1)}{2}$ using mathematical induction.

Base Case: When $n = 1$, the sum of the first positive integer is 1, and $\frac{1(1+1)}{2}=1$. So, the formula holds for the base case.

Inductive Step: Assume that the formula holds for some $k \geq 1$, i.e., $P(k)$ is true. That is, the sum of the first $k$ positive integers is $\frac{k(k+1)}{2}$​. Now, we need to show that this implies that $P(k+1)$ is true, i.e., the sum of the first $k+1$ positive integers is $\frac{(k+1)(k+2)}{2}$​.

Starting with $P(k)$, the sum of the first $k$ positive integers: 
$$1 + 2 + 3 + \ldots + k = \frac{k(k+1)}{2}$$

Adding $(k+1)$ to both sides, we get: 
 
$$ 1+ 2 + 3 + \ldots + k + (k+1) = \frac{k(k+1)}{2} +(k+1)$$
$$= \frac{k(k+1) + 2(k+1)}{2}$$​
$$\frac{(k+1)(k+2)}{2}$$

This proves that $P(k+1)$ holds.
 
Conclusion: By the principle of mathematical induction, the formula holds for all natural numbers $n \geq 1$.

This completes the proof by mathematical induction.

Comments

Post a Comment

Popular posts from this blog

Number Theory CST 292 KTU IV Semester Honors Course Notes Dr Binu V P 9847390760

About me Syllabus Scheme Teaching Plan Model Question Paper University Question Papers Assignment-1 Module-1  Introduction Well ordering principle Group Ring Fields Group Ring Fields in detail Divisibility Modular Arithmetic GCD- Euclidean Algorithm Bezout's Identity Extended Euclidean Algorithm LCM-Least Common Multiple Linear Diophantine Equations Modular Division Module-II Prime Numbers and Prime-Power Factorisation Fermat and Mersenne Prime Primality Testing and Factorization Miller Rabin Primality Testing Algorithm Fermat  Factorization Congruence Modular Exponentiation Linear Congruences Simultaneous Linear Congruences- Chinese Remainder Theorem Fermat's Little Theorem and Euler's Theorem Wilson's Theorem Module-III Congruence with Prime modulus Congruence with Prime power modulus Pseudoprime and Carmichael Numbers Euler's Totient Function Cryptography The Group of Units - Primitive Roots Module-IV Quadratic Residues-Legendre and Jacobi Symbols Arithmetic Func
Read more

Sum of Squares

Image
In this our aim is to determine which integers can be expressed as the sum of given number of squares ie; which have the form $x_1^2+x_2^2+\cdots+x_k^2$, where each $x_i \in \mathbb{Z}$, for a given $k$. Definition: For each integer $k \ge 1$, let $S_k=\{n|n=x_1^2+x_2^2+\cdots+x_k^2$ for some $x_1,x_2,\ldots,x_k \in \mathbb{Z} \}$ , the set of all sum of $k$ squares. Example: $S_1=\{0,1,4,9,\ldots\}$ is the set of all squares. By inspection $S_2$, the set of sum of two squares contains 0,1,2,4,5 and 8 but not 3,6, or 7. Lemma: The set $S_2$ contains, the sum of two squares is closed under multiplication ie; if $s,t \in S_2$ , then $st \in S_2$. Proof:Let $s=a_1^2+b_1^2$ and $t=a_2^2+b_2^2$ be the elements of $S_2$, where $a_1,b_1,a_2,b_2 \in \mathbb{Z}$. Then the identity $$(a_1^2+b_1^2)(a_2^2+b_2^2)=(a_1a_2-b_1b_2)^2+(a_1b_2+b_1a_2)^2$$ This shows that $st \in S_2$ Example: We have $8=2^2+2^2$ and $10=3^2+1^2$ so $8.10=80=(2.3-2.1)^2+(2.1+2.3)^2=4^2+8^2$ Note: an equivalent ident
Read more

Quadratic Residues-Legendre and Jacobi Symbols

Image
Quadratic Congruence   There is a general question whether an integer $a$ has a square root $\pmod{n}$ and if so, how many are there and how one can find them. We know that the solution of the quadratic equation can be found by  $$x=\frac{-b \pm \sqrt{b^2-4ac}}{2a}$$ If we want to apply this to the case where $a,b,c \in Z_n$, then $2a$ to be unit in $\pmod{n}$, so that we can divide by $2a$. We can write the equation in the form $$(2ax+b)^2=b^2-4ac$$ If we can find all the square roots $s$ of $b^2-4ac$ in $\mathbb{Z}_n$, we can then find all the solutions $x \in \mathbb{Z}_n$ of the quadratic equation of the form $2ax+b=s$, or equivalently $x=(s-b)/2a$. If we look at the square roots at $\mathbb{Z}_{15}$, then  1 and 4 have four square roots each($\pm 1 ,\pm 4$ and $\pm 2,\pm 7$ respectively, while the other units have none. Example: Find all the solutions of $x^2-3x+2 \equiv 0 \pmod{15}$ given $a=1, b=−3$ and $c=2,$ we have: $b^2−4ac=(−3)^2−4(1)(2)=9−8=1$ So, $b^2−4ac=1.$ Now, we ne
Read more