Functions as Maps

Functions can also be seen as maps between two characteristics or variables. A function of A and B can also be called a mapping from A to B.

Thinking of this in set notation we can say that the range of a function is A, such that for every B (A,B) is an element of the function set.

Functions

Function as a word was first used by Leibniz in 1694, and Euler popularized the notation f(x) in 1734. In terms of intuitive logic a function describes a rule of correspondence between two sets (i.e.: distance as a function of time).

Looking at functions in terms of relations a function f from A to B is a relation from A to B such that if (x,y) is an element in f and (x,z) is an element in f, then y = z. And also, the Dom(f) = A.

Immediate predecessor

If a and b are elements in a set A and R is a partial ordering on that set, and a is not equal to b, then a is an immediate predecessor of b if a is reflexive on b and there does not exist c in A such that a is not equal to c and b is not equal to c and a is reflexive on c and c is reflexive on b.

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.

Antisymmetric

A relation R on a set A is antisymmetric if, for all x, y is an element of A if x R y and y R x then x=y.

Example:
Consider the relation less than or equal ( < = ) to on the real numbers. It is antisymmetric if x < = y and y < = x, so y = x

Equivalence class

Let R be an equivalence relation for the set A. For any x that is an element of A the equivalence class of x is defined by y being an element in A and x being reflexive on y.

Example:

The Relation R is composed of the following set:

{(1,1),(2,2),(3,3),(1,2),(2,1)}

the equivalence class is as follows:

{{1,2},{3}}

Defining an equivalence relation

An equivalence relation exists if it meet the following three properties, being reflexive, symmetric, and transitive.

We have a set A and R is a relation on that set.

1. R is reflexive on A if and only if for all x that is an element of A, x relates to x, or x R x.

2. R is symmetric if and only if for all x and y in A the relation of x to y is the same as the relation of y to x.

3. R is transitive if and only if for all x,y, and z that are elements in A, if x relates to y, and y relates to z, then x relates to z.

The relation of S and R is not always equal to the relation of R and S

The relation of S and R is not always equal to the relation of R and S

example:

Let R be a set that is equal to y = x + 1
Let S be a set that is equal to y = x^2

Thus the relation of R to S is equal to z=x^2 and y=z+1 so y = x^2 + 1

And the relation of S to R is equal to z= x + 1 and y = z^2 thus y=(x+1)^2

so the relation of R to s is not equal to the relation of S to R

Composites

A composite is a way of relating 3 or more sets.

Let R be a relation from A to B, and let S be a relation from B to C. The composite of R and S is: There is exists a b in B such that (a,b) is in R and (b,c) is in S.

Consider the example:

A={1,2,3,4}
B={1,2,3,4}
C={1,2,3,4}

Let R be a relation from A to B, so

R = {(1,p),(1,q),(2,q),(3,r),(4,s)}

and let S be the relation from B to C:

S = {(p,x),(q,x),(q,y),(s,z)}

Thus the composite of S and R can be seen as the relation of A to C via B.

The composite of S and R = {(1,x),(1,y),(2,x),(2,y),(4,z)}

The Inverse of a Relation

The inverse of a relation is defined as follows

The inverse of R is equal to {(y,x) : where (x,y) is an element of the set R.}

For example, consider the following set:

{(1,d),(2,y),(5,m)}

the inverse would be

{(d,1),(y,2),(m,5)}

Relation of Sets

A relation between two sets is a subset of a Cartesian Product.

For example the numbers and letters of a telephone dialpad are an example of a relation. In this case, 2 is related to a,b,c and 3 is related to d,e,f

Relations will come into greater play with different sets of numbers...like the real, integers, and naturals.

Prove that A X (B U C) = (A X B) U (A X C)

Prove that A X (B U C) = (A X B) U (A X C)

In English this is saying to prove that the Cartesian product of A and B union C is equal to the Cartesian product of A and B union the Cartesian product of A union C.

iff=if and only iff

Consider that the ordered pair (x,y) is an element of A X (B U C)
which is true iff x is an element of A and y is an element on (B U C)
iff x is an element of A and y is an element of B or y is an element of C
iff x is in A and y is in B or x is in A and y is in C
iff (x,y) is in A X B or (x,y) is in A X C
iff (x,y) is in (A X B) U (A X C)

thus A X (B U C) = (A X B) U (A X C)

Cartesian Products

Cartesian products are named after the French philosopher and mathematician Rene Descartes. They can be defined as follows:

A X B = {(a,b): where a is an element in A and b is an element in B}

Consider the example:

A={1,2} and B={2,3,4}

then the Cartesian product of A and B is written as follows:

A X B = {(1,2),(1,3),(1,4),(2,2),(2,3),(2,4)}

Order does matter in Cartesian products, contrast the following:

B X A = {(2,1),(2,2),(3,1),(3,2),(4,1),(4,2)}

How many natural numbers less than 1 million are either cubes or squares of natural numbers?

How many natural numbers less than 1 million are either cubes or squares of natural numbers?

1,000,000 = (10^2)^3 = (10^3)^2 = 10^6

So thus there are 10^2 cubes less than or equal to 1,000,000

and 10^3 squares less than or equal to 1,000,000

and there are 10 natural numbers n^6 that are both squares and cubes. (1^6,2^6,3^6,etc...)

So first we get the number of cubes 10^2 = 100
and add it to the number of squares 10^3 = 1000
and then subtract the 10 that were over counted, in either group. 1000+100-10=1090 squares and cubes less than or equal to 1 million

Combinations

Combinations can be thought of as a layer on top of permutations. They are employed to solve problems of counting how many selections can be made from a particular group. For example, say I wanted to draw 5 marbles from a bag of 15, how many combinations of marbles could I draw?

To answer this question we have to count how many ways we can draw all 15 marbles and then divide that by the number of ways we can draw 10 marbles. This can be written mathematically as:

n!/(n-r)!

so that is

15! / (15-5)!

=

15! / 10!

=

15*14*13*12*11

= 360,360 ways to draw 5 marbles from the bag of 15.

Permutations

We are going to take a break from proofs today to look at some methods of counting in math. Today we will cover Permutations.

A permutation is simply how many possible arrangements there are of any elements in a set. For example, let say we have a set with A,B,C,D in it. How many ways can we order ABCD?

ABCD, ADCB, ACDB, BADB,...and so on. Well, instead of listing every combination out we can use a permutation to count them. A permutation is defined by n factorial (n!)

n! = n(n-1)!
so for example 5!= 5 * 4 * 3 * 2 * 1

And for the ABCD problem we need to take 4! which is 4*3*2*1 = 24

So there are 24 possible permutations.

An interesting facet with permutations is that the numbers tend to rise quite quickly:
5!=120
6!=720
7!=5040
8!=40,320
9!=362,880
10!= 3,362,800

So if we tried to order ABCDEFGHIJ we would get over 3 million permutations!

Prove if the sets A x B = A x C and A is nonempty then B=C

Prove if the sets A x B = A x C and A is nonempty then B=C

Suppose there exists an element b in the set B and an element a in the set A. Then a and b are elements in A x B. But since A x B = A x C then a and b are also elements in A x C. So b is an element in C, which proves B is a subset of C. You could prove that C is a subset of B in a similar manner and so B = C.

Prove that the square root of 2 is irrational

Prove that the square root of 2 is irrational.

We will use the well ordering principle for this proof and try to reach a contradiction.

Let A be a set in the natural numbers so that there exists b and a in the natural numbers so that sqrt(2)=(a)/(b)

thus 2 =(a^2)/(b^2)

and (a^2)= 2(b^2)

From the formula above we see that a must be an even number because it is equal to 2(b^2). If we substitute 2k for a to represent this we get:

(2k^2) = 2 (b^2)

(b^2) = 4(k^2) / 2 = 2(k^2)

so
b = 2k

And so b also must be even, however if both a and b are smallest elements in the set A, then one must be even and one must be odd so we have a contradiction and the square root of 2 cannot be expressed as the ratio of two numbers, thus it is irrational.

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 if a and b are natural numbers with b < = a then there exists a q and r in the natural numbers such that a=qb +r.(Division Algorithm)

Prove if a and b are natural numbers with b < = a then there exists a q and r in the natural numbers such that a = qb + r and 0 < = r < b. Where q and r are the quotient and remainder. This is a proof of the division algorithm.

First we let T equal a number s in the natural numbers where a < sb. By the well ordering principle T has a smallest element which we can call w. Now we let q = w - 1 and r = a - qb since a > = b , w > 1 , q is in the natural numbers. Thus q < w , a > qb and r > = 0. By definition of r a = qb + r. Now suppose if r > = b. Then a - (w - 1)b > = b. so a >= wb, which contradicts the fact that a < wb. Therefore, r < b. In other words, the remainder should never be larger than the divisor. So r < 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.

Proof of the Fibonacci sequence and Golden Ratio

This is a proof of the Fibonacci sequence and its relation to the Golden Ratio.

If we consider the equation (x^2) - x - 1 we find it can be solved by letting x=a=(1+sqrt(5))/2)=1.618 which is the golden ratio.

We can prove that all numbers in the Fibonacci sequence produces solutions for this equation if we can prove that any number in the sequence f(n) is less than or equal to any solution before it a^(n-1)

We start by testing the first two cases which is a=1 and a=2, (1 and 2 are both Fibonacci numbers) thus we have 1 < = (a^0) = 1, and 1 < = a^1 = (1+sqrt(5))/2)

Now we prove the general case,

f(n) = f(n-1) + f(n-2) where f(n) is any Fibonacci number (in other words a Fibonacci number is generated by the addition of the two previous numbers, consider the first few numbers in the Fibonacci sequence: (1,2,3,5,8...)

f(n-1) + f(n-2) < = a^(n-2) + a^(n-3)

= a^(n-3) * (a+1) by factorization

= a^(n-3) * (a^2) (because a+1 is a solution to the equation (x^2) - x - 1

= a(n-1)

so therefore f(n) < = a^(n-1)

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. ~~~~

Prove for every natural number n, 1+3+5+...(2n-1)=(n^2)

Prove for every natural number n, 1+3+5+...(2n-1)=(n^2)

First let us consider an example where n=6, then we see that

1+3+5+7+9+11 = 36 = (6^2) = (n^2)

Now we have use to the principle of mathematical induction (PMI) to prove that this is true for all cases.

So we define a set S to be the set of natural numbers for which the statment:

for every natural number n, 1+3+5+...(2n-1)=(n^2)

is true.

First, let us find that the statement is true for the first natural number: 1=(1^2)

Thus, 1 is an element in our set S.

Now that we have proved the case for 1, we should prove the same thing for the next case which is (n+1), if we can prove that (n+1) is in the set S, then by induction we have proved it to be true for all n.

To do this we take the original antecedent:

1+3+5+...(2n-1)=(n^2) and add 2(n+1) - 1 to both sides, doing that we get

1+3+5+...(2n-1) + [2(n+1) - 1] = (n^2) + 2(n+1) - 1

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

thus (n+1) is in our set S, and the statement: 1+3+5+...(2n-1)=(n^2), is true for all n.

Another way to think about a proof by induction is as a direct proof in which we are saying, for all n, n in S implies that n+1 is in S, and thus is true for all n.

~~~~

Prove that the intersection of ~(A and B) is equal to the union of ~A and ~B

Prove that the intersection of ~(A and B) is equal to the union of ~A and ~B

This is the second of De Morgan's Laws.

We use the "~" to represent "not".

So first we assume there is an object x that is a member of the intersection of ~(A and B)
which is true, if and only if(iff) x is a member of ~A and ~B
which is true if x isn't in A and isn't in B
which is the same as x being in ~A and ~B
which is the same as x being in the union of ~A and ~B.

Prove that the union of ~(A and B) is equal to the intersection of ~A and ~B

Prove that the union of ~(A and B) is equal to the intersection of ~A and ~B

This is the first of De Morgan's Laws.

We use the "~" to represent "not".

So first we assume there is an object x that is a member of the union of ~(A and B)
which is true, if and only if(iff) x is not a member of A and B
which is true if x isn't in A and isn't in B
which is the same as x being in ~A and ~B
which is the same as x being in the intersection of ~A and ~B.


~~~~

Prove that the union of A and (~A) is equal to the unvierse

Let ~A = not A, or all elements that are not in the set "A" and prove that the union of A and ~A is equal to the Universe.

First, assume that A and ~A is a subset of the universe. Let x be an object in the universe, then x is either an object in A or not an object in A, and therefore is always in the universe.

Prove that the intersection of A and B is a subset of A

Prove that the intersection of A and B is a subset of A


Suppose there is a x which is in the intersection of A and B. Therefore that x is also in A, and so the intersection of A and B is a subset of A. ~~~~

Let A= x: P(x) and B= x: Q(x) Prove that if for all x: P(x) = > Q(x) then A is a subset of B.

Let A= x: P(x) and B= x: Q(x)Prove that if for all x, P(x) implies Q(x) then A is a subset of B.

Let x be any object and suppose that it is a subset of A. Then P(x) must be true for all x, and since for all x, P(x) implies Q(x) then x is a subset of B. So therefore, A is a subset of B.~~~~

Prove if A is a subset of B, and B is a subset of C, then A is a subset of C.

Prove if A is a subset of B, and B is a subset of C, then A is a subset of C.

Assume A is a subset of B, and B is a subset of C.

Then there is an x in B such that, for every x in B x is in C and there exists an x in A such that, for every x in A x is in B. Thus, for every x in A, x is also in C, and therefore A is a subset of C.

Prove for any set A, A is a subset of A

Prove for any set A, A is a subset of A

Assume we have a set A, and x is an object in that set.

Then x being a subset of A, implies x is a subset of A.

Thus, for all x that is are objects in A, x is an object in A, and so, A is a subset of A. ~~~~

Prove for any set A, null is a subset of A.

Prove for any set A, null is a subset of A.

Let A be any set, and x any object.

Consider the conditional sentence: x is a subset of null implies x is a subset of A. Since the antecedent (x is a subset of null) is false, then the sentence itself is true, and therefore null is a subset of A.

Euclid's Algorithm: Let a and b be two positive integers with a <= b. Let d be their greatest common divisor(GCD). Then there are two lists of...

Euclid's algorithm is a way to find the GCD of any Euclidian domain, in this case, the natural numbers.

Euclid's Algorithm: Let a and b be two positive integers with a <= b. Let d be their greatest common divisor(GCD). Then there are two lists of positive integers q(i) and r(i) such that

b > r(1) > r(2) > r(3) ... > r(k-1) > r(k) > r(k+1) = 0 and

a = bq(1) + r(1)
b = r(1)q(2) + r(2)
r(1) = r(2)q(3) + r(3)
r(2) = r(3)q(2) + r(4)
.
.
.
r(k-2) = r(k-1)q(k) + r(k)
r(k-1) = r(k)q(k+1) (that is, r(k+1) = 0 )

and therefore d = r(k)

Proof

Since a < = b then there exists a q(1) and r(1) such that a = bq(1) + r(1) where 0 < = r(1) < b , and therefore, since r(1) < b there exists a q(2) and r(2) such that b=r(1)q(2) + r(2) and so one for r(2)< r(1). If we keep going down the line of positive integers we reach a point were r(k+1)=0 and so it is evident that:

b > r(1) > r(2) > r(3) ... > r(k-1) > r(k) > r(k+1) = 0

Now, to show that d (the GCD) is equal to r(k) we have to show that r(k) < = d and r(k) > = d.

First we show that r(k) < = d.

We first notice that r(k) divides r(k-1) (because r(k-1) = r(k)q(k+1)), we also notice that r(k) divides r(k-2) because r(k-2) = r(k-1)q(k) + r(k), and so r(k) divides both r(k) and r(k-1) by the proof we did two days ago. (When another proof is used in a proof, it is called a lemma). Now, if we keep going up the line, we see that every number has a component of the previous integer, and so r(k) is a common divisor for all the numbers including a and b. Since d is the GCD for a and b, then r(k) has to be < = d by the proof we did yesterday.

Now we show that r(k) > = d.

We note that d divides r(1) since r(1) = a - bq(1), and since d divides r(1) then by the proof we did two days ago, d also divides r(2) since r(2) = b - r(1)q(2), continuing this pattern down the line we see that d divides r(k-1) and r(k) and therefore r(k) > = d.

Now we can say that d= r(k) which is equal to 1, and 1 is the GCD of all positive integers, or the natural numbers.

Let d be the greatest common divisor of two positive integers a and b. If c is a positive integer such that c divides a ,and c divides b, then c <= d

Let d be the greatest common divisor of two positive integers a and b. Prove if c is a positive integer such that c divides a ,and c divides b, then c <= d.

This is a somewhat simple proof since it uses the definition of a greatest common divisor.

A greatest common divisor (GCD) is the largest integer which divides two other integers. Take for example the numbers 24 and 16. 8 is the GCD for 24 and 16 since 8 is the largest number that will divide both of them.

So if the GCD=d then d divides a, and d divides b.

The numbers 4 and 2 also divide 24 and 16, but are not the "Greatest". However, we do see that 4 and 2 also divide 8, which is the second part of the definition of a GCD.

For every positive integer c, if c divides a and c divides b, then c divides d.

It is this last part of the definition we will use for our proof. If c is an integer which divides a and b, then by definition c must also divide the GCD, which is d. And therefore c < d. ~~~~

Prove if c divides a and c divides b, then c divides any combination an+bm, where n and m are integers

Prove if c divides a and c divides b, then c divides any combination an+bm, where n and m are integers.

Since c divides both a and b then there must exist integers j and t such that a=cj and b=ct.

So by substitution into an+bm we get

an+bm = (cj)n+(ct)m = c (jn + tm). So c divides (an + bm) ~~~~

Thus, if c divides a and b, then c also divides any multiple of a and b.

Prove that X = Y where X is a solution to x^2 - 1 = 0 and y = 1,-1

Prove that X = Y where X is a solution to x^2 - 1 = 0 and y = 1,-1

This is a set theory proof. The idea is that if X is a subset of Y, and Y is a subset of X, then X = Y.

So, first we show that Y is a subset of X. And we can do this by simply substituting the values for y in x^2 - 1 = 0. We see that both 1 and -1 work when substituted for X, and so Y is a subset of X.

Now we have to prove that X is a subset of Y. If we factor x^2 - 1 we get (x-1)(x+1) = 0. It is evident that this product is 0 exactly when x=1 or x=-1; so X is a subset of Y.

Now since Y is a subset of X, and X is a subset of Y, then X=Y

Prove if k and m are rational numbers with k < m, there exists a rational number between k and m

Prove if k and m are rational numbers with k < m, there exists a rational number between k and m

k < m = k+k < k+m = 2k < k+m = k < k+m/2 so k < (m+k)/2

and

k < m = k+m < m+m = k+m < m+m = k+m < 2m so (k+m)/2 < m

if we let t=(k+m)/2 then t is a rational number between k and m. ~~~~

Prove if x+y is irrational then x or y are irrational.

For real numbers x and y prove if x+y is irrational then x or y are irrational.

This is a proof by contraposition, so we assume x and y are rational.

then x=m/k and y=n/t where m,k,n,t are integers.

so x+y = m/k + n/t = (mt + nk)/(kt) which is rational since m t n k are integers.

So x+y is rational. Therefore, by contraposition (~q=>~p therefore p=>q), if x+y is irrational then x or y are irrational.

Prove for every odd integer n, 4n^2 + 3n + 2 is odd

Prove for every odd integer n, 4n^2 + 3n + 2 is odd

Let n be an odd integer, so n = 2h + 1 for some integer h.

So 4n^2 + 3n + 2 = 4(2h+1)^2 + 3(2h+1) + 2 =

16h^2 + 16h + 4 + 6h + 3 + 2 =

16h^2 + 22h + 9 =

2(8h^2 + 11h + 4) + 1, which is odd, and therefore

4n^2 + 3n + 2 is odd for every odd integer n.

Prove that there do not exist integers k and j such that 2j + 6k = 9

Prove that there do not exist integers k and j such that 2j + 6k = 9

Assume that j and k are integers. Then 2j + 6k = 2(j+3k) which is even, but 9 is odd, so it is evident that no integers j and k can be used to equal an odd number.

Prove if m is irrational, then 5m is irrational. (Contraposition)

Prove if m is irrational, then 5m is irrational.

Remember that contraposition is where we have to prove P => Q so we use the following logic:

~Q => ~P so therefore P => Q

Thus we start off assuming the opposite of the consequent (~Q) which is that 5m is rational.

If that is true then 5m can be equal to two integers j and k(non-zero) such that 5m = j/k , since a rational number is one that can be expressed as the ratio of two integers, and an irrational number is one which can't, like 3.333333 or Pi.

So 5m = j/k and m = j/(5*k) , and thus m is rational, so now we have ~P for the contraposition part of the proof, and so we can say ~Q => ~P so therefore P => Q and so if m is irrational then 5m is irrational

Prove if ab is odd, then both a and b are odd. (Contradiction)

Assume a and b are positive integers, prove if a*b is odd then a and b are odd.

Proof by contradiction: where we want to prove Q => P we take ~P=> Q Λ ~ Q which is a contradiction, so therefore we conclude P.

This is a proof by contradiction which means that we have to assume the opposite consequent, which is the say that a and b are not both odd. So either a is even or b is even.

If a is even, then a=2k for some integer k, and b*2k will always be even.

If b is even, then b=2m for some integer m, and a*2m will always be even.

So either case leads to a contradiction that a*b is odd, and therefore if a*b is odd, then both a and b are odd.

Prove if x is even, then x+1 is odd.

Let x be an integer and prove if x is even, then x+1 is odd.

We will use contraposition for this proof, so we start by assuming that x + 1 is not odd.

Then we can say there exists an integer k such that x + 1 = 2k

so x = 2k - 1 = 2(k-1) + 1

Thus x = 2(k-1) + 1 which is odd. So we can no say if x + 1 is not odd, then x is not even. Thus, by contraposition, if x is even, x+1 is odd.

If x^2 (x squared) is odd then x is odd. (Contraposition)

Assume x is an integer. If x^2 (x squared) is odd then x is odd.


This is the same proof as we did yesterday, except this time we will prove the statement using another form of logic called contraposition.


To do this, we must first state the contrapositive of what we set out to prove.

so

If x^2 (x squared) is odd then x is odd

now becomes

If x^2 (x squared) is even then x is even

which is the contrapositive, the idea is that if we can prove that x^2 is even for all x that is even, it stands to reason that x^2 can only be odd for all x that is odd.

The way to write this symbolically is ~Q => ~P so therefore P => Q.

So now we prove if x^2 (x squared) is even then x is even

x is even so x=2y for some integer y.

then x^2 = 2y(2y) = (4y^2) = 2(2y^2) which is even.

Therefore if x^2 is even x is even, so by contraposition, if x^2 is odd, x is odd.

Prove that if x^2 is odd then x is odd. (Direct proof)

Assume x is an integer. If x^2 (x squared) is odd then x is odd.

First lets look at some examples

3^2 is 9
5^2 is 25
7^2 is 49
9^2 is 81

So it does appear that for any odd integer, its square is also an integer, how can we prove this for all cases?

First we assume x is odd, then x=2y+1 for some integer y.

So now x^2 = (2y+1)(2y+1) = 4y^2 + 4y + 1= 2(2y^2 + 2) + 1 which is odd.

Prove if x*y = 1 then x = y = 1

Assume that x and y are positive integers, prove that if x * y = 1 then x = y = 1

If x * y = 1 then x = (1/y) and y = (1/x)

Yesterday we proved that if an integer x divides an integer y then x<=y.

So since y divides 1 or (1/y) then y<=1

and since x divides 1 or (1/x) then x<=1

Since both x and y are integers then y=1 and x=1, so x = y = 1

Prove that if x divides y, then x<=y

Assume that x and y are positive integers, prove that if x divides y then x<=y.

If x divides y then there exists another integer j such that y=xj.


Now we can say x =< xj and canceling out the x we get 1<=j or that is to say, j is greater than or equal to 1.

This is true because both x and y are positive so j must be positive for our initial antecedent y=xj to be true. Also since we assumed j is an integer then j>=1. So now we know that x<=xj and by substitution of y=xj we get x<=y.

Prove that |x+y| <= |x| + |y|

Assume x and y are real numbers prove that the absolute(positive) value of x+y is less than or equal to the absolute value of x plus the absolute value of y.

Or:

Prove that |x+y| <= |x| + |y|

This proof has 4 parts:

PART 1
Assume x < 0 and y < 0 then x + y< 0, so that |x+y| = (x+y) or -(x+y) in the first case (x+y)=|x|+|y| and in the second case -(x+y)<|x|+|y| thus |x+y|<=|x|+|y|

Part 2
Assume x < 0 and y >= 0 then since x<0 then |x+y| < y < |x| + |y|

thus |x+y| < |x|+|y|

Part 3
Assume y < 0 and x >= 0 then since y<0 |x+y| < x < |x| + |y|

thus |x+y| < |x|+|y|

Part4
Assume x > 0 and y > 0 then |x+y| = x + y = |x| + |y|

thus |x+y|=|x|+|y|

Prove that if x is even and y is odd, then x+y is odd

Let x and y be integers. Prove that if x is even and y is odd, then x+y is odd.

x is even, therefore x=2k for some integer k.
y is odd, therefore y=2j+1 for some integer j.

by substitution into x+y=odd we get

2k + 2j + 1 = odd

2k + 2j + 1 = 2(k+j) + 1, which is odd.

Prove that there exist integers m and n such that 2m+7n=1

Prove that there exist integers m and n such that 2m + 7n=1

Let m=4 and n=-1. Then 2m + 7n = 1

On Mathematics and Mathematical Proofs

Mathematics is a language like any other language. It uses symbols to represent ideas, and those ideas attempt to represent reality. Like any language however, the symbols, letters, or words used are an abstraction, they are meaningless by themselves.

The beauty of mathematics is that new meanings fall from the symbols which cannot always be explained. One could say the same thing for words, a certain arrangement of words, in a novel or poem might enlighten us to new meanings we had not before perceived, and in mathematics there exist certain inherent patterns and meanings within the system, waiting to be explained or discovered.

The symbols matter. The better the symbols, the more efficient the phrases, and the more profound the thoughts. Let's consider for a moment all the different ways to write division:

1. In English: Six divided by four.
2. On way in math: 6 ÷ 4
3. Another math way: 6/4

Which method of representing the idea of six divided by four best leads you to realize that six divided by four is that same idea as three divided by two?

Or that is to say:

6/4 = 3/2

Thus in mathematics, or all languages, we are presented with the interesting problem that the symbols we contrive to use have a direct impact on the conclusions we make and how clearly we can express them.

For the purposes of mathematical proofs we will use the following generally accepted standard symbols:

Λ as "and"
V as "or"
~ as "the opposite"