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.


~~~~