Partial order

Consider a relation R on a set A, the relation is a partial order for A if R is reflexive, antisymmetric, and transitive.

Examples,

The relation less than or equal to ( < = ) on the Natural numbers.

Prove for natural numbers a and b, the greatest common divisor of a and b may be written as a linear combination of a and b.

Prove for natural numbers a and b, the greatest common divisor of a and b may be written as a linear combination of a and b. Or if d is the greatest common divisor of a and b GCD(a,b) there exist integers x and y such that

ax+ by = d

Let C be a set defined by z where z=ax+by for some integers x and y, and z is greater than 0. C is in the natural numbers and has a smallest element. m such that m=ax(0)+by(0). No we see that m < = a and m < = b because a(1) + b(0) and a(0) + b(1) are also in C. We will show that m=d. Since d divides a and d divides b, d divides ax(0) + by(0). Thus d divides m. Therefore d < = m.

Now the proof by contradiction...
suppose m does not divide a. Then by the division algorithm we proved yesterday there exist natural numbers q and r such that a=mq+r, where 0 < style="color: rgb(204, 0, 0);">m= ax(0) + by(0)
mq = aqx(0) + bqy(0)
a -r =aqx(0) + bqy(0)
r = a - aqx(0) - bqy(0)
r = a(1-qx(0) + b(-qy(0))

So r is a linear combination of a and b, so r is in our first set C. But r < style="color: rgb(204, 153, 51);">m < = d and as we proved earlier d <= m so d = m , so d (the GCD) can be written as a linear combination of a and b.

Prove every natural number n > 1 has a prime factor

Prove every natural number n > 1 has a prime factor.

Prime numbers are numbers which have no divisors other than 1 (i.e. 1,3,5,7,11...)
Composite numbers have more than one divisor (i.e. 4,6,8,9...)

If n is prime (has no divisor other than 1), then n is a prime factor of n. If n is composite then n has divisors other than 1 and n. We will make p a number that is the smallest divisor of n (other than 1), and show that p is prime.

To do this we will use a proof by contradiction, so start by assuming the opposite. Assume p is composite and not prime, then p must also have a divisor d, where 1 < d < p. So now d divides p, and p divides n, but then d < p which contradicts the definition of p being the smallest divisor. Thus p must be prime if it is the smallest divisor, and so every natural number has a prime factor.

Prove every non empty subset of the natural numbers has a smallest element. (Well-Ordering Principle)WOP

Prove every non empty subset of the natural numbers has a smallest element. (Well-Ordering Principle) WOP

To prove this we must define a subset of the natural numbers T, and show that T is nonempty, and has a smallest element.

We will use a combination of taking the contrapositive and proving it by induction. That sounds more complicated than it is, so hold on to your hat and see the proof before thinking all this is confusing!

The contrapositive is to suppose that T has no smallest element. If this is true then there must be another set S that is equal to the natural numbers(N) so that we can make the statement:

S = N - T , or that is to say that S will be equal to N only if T is empty.

To prove this using iduction we take the first case in the natural numbers which is 1. 1 is the smallest element in the natural numbers and as T has no smallest element, 1 must be in S by our statement S = N - T

Now, say that a number k is an element in S, then that number cannot be in T, because if it were, it would imply that there is a smallest element in T, and also, k cannot be in T since k is in S. Then k+1 cannot be in T, by the same implication of there being a smallest element in T, and so k+1 must be an element in S.

So by induction S = N, or the set S is equal to the natural numbers, and since T has no smallest element, T has to be an empty subset of the natural numbers.

However, by contraposition, if T had an element, then it would have to have a smallest element. Thus, any non-empty subset of the natural numbers (N) has a smallest element, and this is the Well Ordering Principle.

Prove that (4^n)-1 is divisible by 3 for all natural numbers

Prove that (4^n)-1 is divisible by 3 for all natural numbers

We will use induction for this proof, so first we prove the case for the first natural number 1:

(4^1) - 1 = 3 which is divisible by 3.

Now we need to prove the general case for n+1

4^(n+1) - 1

= 4(4^n) - 1

= 4((4^n) - 1) - 1 + 4

= 4((4^n) - 1) + 3

Now both (4^n - 1) and 3 are divisible by 3, thus by induction we can say for all natural numbers 4^n - 1 is divisible by 3.

Prove for all natural numbers a and b, there exists a natural number s such that a < sb (Archimedean Principle)

Prove for all natural numbers a and b, there exists a natural number s such that a < sb.

This is a proof of the Archimedean Principle which states that with a lever large enough a man could move the earth. In other words, with a multiple large enough, a can be surpassed by b.

This is a proof by induction, so we prove the first case which is 1 for the natural numbers.

If b = 1 then we choose s to be a+1. Then a < a+1 = sb, so the first case works.

Now let us assume the general case where b is equal to some natural number n. Then there exists an s such that a < sn < s(n+1), so the statement is true when b=n+1.

Thus, by induction there exists a natural number s such that a < sb for all natural numbers a and b. ~~~~

Prove for every natural number n, x-y divides (x^n) - (y^n)

Prove for every natural number n, x-y divides (x^n) - (y^n)

This is another proof by induction, so first we prove the first case, which for the natural numbers is 1.

x - y divides (x^1) - (y^1) = 1(x-y) so this is true.

Now by induction we must show that x-y divides x^(n+1) - y^(n+1)

x^(n+1) - y^(n+1)

= x(x^n) - y(y^n)

= x(x^n) - y(x^n) + y(x^n) - y(y^n)

= (x-y)(x^n) + y(x^n - y^n)

so now we have a form where x-y divides the first term (since x-y is a factor) and divides the second term((x^n - y^n)) by the hypothesis of induction.

Thus x-y divides (x^n) - (y^n) for all natural numbers n.

Prove that for all natural numbers n, n+3 < 5(n^2)

Prove that for all natural numbers n, n+3 < 5(n^2)

Once again we will use induction to solve this proof.

First we prove the case to be true for the first natural number:1

1+3 < 5*(1^2) that is to say 4 < 5

Now we will try prove the case to be true for n+1 to do this, we will add one to both sides and get:

(n+1) + 3 < 5(n^2) + 1

5(n^2) + 1 < 5 = 5(n+1)^2

thus

(n+1) + 3 < 5(n+1) ^2

The reason why we did all that algebra in the middle was to get the form n+1 on both sides which is important to use the principle of mathematical induction to conclude that n+3<5(n^2) for all n in the natural numbers. ~~~~