MT181

Página 1

Section 6: LOGIC AND PROOF

Idea of proof:

Take the quadratic z^2 + z + 1. Consider the function f: C-> C defined by f(z) = z^2 + z + 1

Will look at what f does on some paths in its domain

for |z| small : f(z) approximates to 1 + z

for |z| large : f(z) approximates to z^2

Solving a quartic:

z^4 + 2z^3 + 3z^2 + 4z + 2 = 0

Possible integer roots are z = +/-1 , +/-2

f(-1) = 0 so now you can factor to give f(z) = (z+1)(cubic)

Now find a root of a cubic and then solve remaining quadratic

Let x: {1,2,3,4,5,6,7,8,9,10}

A = {n in X : P(n)} = {2,4,6,8,10}

B = {n in X : Q(n)} = {3,6,9}

C = { n in X : R(n)} = {2,3,5,7}

Then {n in X : P(n) V Q(n)} = {2,3,4,6,8,9,10} this is {n in X : P(n)}U{n in X:Q(n)} = A U B

{n in X : P(n) n Q(n)} = {6} = A n B

{n in X : P(n)} n {n in X : Q(n)} = A n B

Taking complements in X we have

{n in X : ¬P(n)} = {n in X : n is odd} = {1,3,5,7,9} = {2,4,6,8,10}' = {n in X : P(n)}'

Find {n in X : P(n) n (Q(n) V R(n))}

First find what is in the brackets Q(n) V R(n) = {2,3,5,6,7,9}

Now consider the entire P(n) n (Q(n) V R(n)) this means P(n) that is in the set above, these will be even numbers {2,6}

Truth tables:

Let P, Q be propositions. A concise way to specify a logical operation such as V, n or ¬ is by a truth table.

PVQ: For the truth table one of P or Q need to be true for PVQ to be true.

PnQ: For the truth table you would need both P and Q to be true otherwise PnQ is false.

Truth table for P implies Q,

It is true that a true implies a truth. There is no way that a truth can imply something F. Something false can imply anything so it can also imply a truth. False implies false is a given.

1. Think of P implies Q as a promise 'if P is true then Q is true'. This promise is broken only in one circumstance when P is true and Q is false. It is reasonable to say P implies Q is true except when P is true and Q is false.

2. Contrapositive: says P implies Q and ¬Q implies ¬P are either both true or both false.

If we take P,Q to be true then P implies Q is true. Then by the contrapositive ¬Q implies ¬P us true. So P false and Q false gives P implies Q to be true.

Truth Table for if and only if

P implies Q is true when P and Q have the same logical status

Because the first implication sign is not reversible it does not follow that both -2 and 1 are solutions. So it does not prove the converse. The converse is false.

a) If A is a knave then Q is false. This would mean P, a truth implies something false. Contradiction! For the implication to not be false, A is a knight.

b) If B is knave then P implies Q is false. So P is true Q is false. C is a knight and B is a knight contradiction! Hence B is a knight and C is a knave.

Logical equivalence and tautologies

If P, Q are propositions such that P iff Q then we say that they are both logically equivalent. If P is always true then P is a tautology.

Section 7: SETS AND COUNTING

Size of sets:

Let X be a set. If X has finitely many members, that is X is finite and write |X| for the size of X. Read as mod X.

Note: When you are asked for the elements of an equation such as z^3 = 1 work out its values in exp form. Also the empty set is a subset of every set but it is NOT an element of every set.

For example empty set is not in the empty set.

Proving that two sets are equal, CLAIM:

Let x, y ,z be sets. Then

1. (X U Y) n Z = (X n Z) U (Y n Z)

distributivity of n over U

2. (X n y) U Z = (X U Y) n (Y U Z)

distributivity of U over n

Proof:

(i) Will show (X U Y) n Z is a subset (X n Z) U (Y n Z)

Take z in (X U Y) n Z

Then z in Z and z in X U Y

Then z in X => z in X n Z and z in Y => z in Y n Z

So Z in (Z n Y) U (Y n Z)

(ii) Will show (X n Z) U (Y n Z) subset of (X U Y) n Z

Let z in (X n Z) U (Y n Z)

Then if z in (X n Z) => z in (X U Y) n Z

and z in (Y n Z) => z in (X U Y) n Z

so z in (X U Y) n Z as required

If A and B are sets such that A is a subset of B and B is a subset of A then

A is subset of B x in A => x in B

B is a subset of A x in B => x in A

So we have x in A x in B and A=B; so here (X U Y) n Z = (X n Z) U (Y n Z)

Columns ¬(PVQ) and (¬P n ¬Q) are the same. So the last column will be T all the way down. So they are logically equivalent.

Example:

(P implies Q) n (Q implies R) implies (P implies R)

Justification: chain of implications, P implies Q implies R.

Deduce from P => Q => R that P => R. This is justified by ((P=>Q) n (Q=>R)) => (P=>R)

Suppose ((P=>Q) n (Q=>R)) => (P=>R) is true and P => R is false, so P is true and R is false.

Since P => Q is true then Q is true. So Q=>R is false this is a contradiction. True => true.

CLAIM:

Let P and Q be prepositions. Then P=>Q is logically equivalent to ¬Q => ¬P

Proof:

1. Will show (P=>Q) => (¬Q => ¬P)

Assume the hypothesis P => Q. Suppose ¬Q is also true. Since P => Q, P must be false.

Hence ¬P is true.

2. Will show (¬Q => ¬P) => (P => Q)

Assume the hypothesis ¬Q => ¬P. Suppose P is true. Since ¬Q => ¬P, ¬Q must be false. Hence Q is true.

Alternative proof using truth table:

The columns here would be; P, Q P=>Q, ¬Q, ¬P and ¬Q => ¬P

Treat ¬Q and ¬P to find out ¬Q => ¬P they same as the previous columns. For instance a false implying false is true, true implying false is false, a truth can imply a false so this is true and a truth implying a truth is true.

Note that (P => Q) and (¬Q => ¬P) columns are the same therefore they are logically equivalent.

CLAIM:

:et a in Q be a non-zero. Let z in R. If x is not in Q then ax is not in Q.

Proof:

We must show that (x not in Q) => (ax in Q)

Equivalent, by the contrapositive to show (ax in Q) => (x in Q)

Suppose ax in Q, since a in Q and non-zero and the rationals is closed under division then (ax/a in Q). Thus x in Q.

Special case: a = 2 after applying the contrapositive.

We wanted to show (2x in Q) => (x in Q)

Let 2x = m/n, m in Z and n in N

Then x = m/2n in Q as m in Z and n in N even after dividing by 2.

Proof by contradiction:

To show P is true by contradiction. Then we suppose that P is false: ¬P is true.

Show that ¬P => c where c is a contradiction as it is a false statement.

Since true statements do not imply false statements then ¬P is false and P is true.

Example:

Let f: X -> Y and g: Y -> Z be functions.

If gf : X -> Z is surjective then g is surjective. In symbols,

gf surjective => g surjective

Using the contrapositive, it is equivalent to show that

g not surjective => gf not surjective

Proof:

If g is not surjective then there exists z in Z such that z is not in the range of g.

Since {g(f(x)) : x in X} subset {g(y) : y in Y} = range g, we see that z is not in the range of gf. Hence gf is not surjective.

Example:

Let f: R ->R>0 be defined by f(x) = 2^x. Then f is bijective.

Let t in R be the unique real number such that 2^t = 3

Claim: t not in Q

Proof:

Suppose for a contradiction, t in Q.

t in Q => there exists m in Z, n in N such that t = m/n

Now 2^t = 3 => 2^m/n = 3

=> 2^m = 3^n

this contradicts unique factorisation, out assumption was wrong, so t not in Q

P: False because 4 does not divide 3^2. Negative is (For all m in Z)(4 does not divide m^2) is true.

Q: True, m = 16

R: True, either m is even and if n=2 then m+n is even or

m is odd and if n = 1 then m+n is odd

R': (There exists n in N)(For all m in Z)(m+n is even).

This is false: consider ¬R': (For all n in N)(¬(For all m in Z)(m+n is even))

iff (For all n in N)(There exists m in Z)¬(m+n is even)

iff (For all n in N)(There exists m in Z)(m+n is odd)

so ¬R' is true (if n is even take m=0 if n is odd take m=1)

Hence R' is false.

S': (For all n in N)(There exists an x in R)(There exists a y in R) (x does not equal y n x^n = y^n)

False, n =1, for all x, y in R, x does not equal y n x=y is false

S'':(For all n in N)(There exists an x in R)(There exists a y in R)(n even => x does not equal y n x^n = y^n)

True, given n in N such that n is even.

take x = 1, y = -1, and x^n = y^n = 1

Note the order of quantifiers matters.

Negation is :

(There exists an epsilon>0)(For all N in N)(There exists n >N)(|an-l|> epsilon)

Claim: ((There exists x in X)(P(x)) => (For all x in X)(P(x))

Proof: Logical equivalence is There exists x in X (P(x) => (For all y in X)P(y))

Case1: If (For all y in X)(P(y)) then take any person x in X and p(x) => (For all y in Y)P(y) is true. Having supposed p(x) is true and so for Y is true. A true proposition implies true.

Case 2: In remaining case: There exists x in X(¬P(x)). So P(x) is false and P(x) => anything is true. (For all y in X)(P(y))

(i) |(X U Y)'| = 100 - 65 - 70 +50 = 15

(ii) 65

(iii) 0 100 - 65 - 70 +b = 0 so b = 35

CLAIM:

Let X, Y, Z be subsets of a finite universe set U.

Then |X U Y U Z|= |X| + |Y| + |Z| - |X n Y| - |Y n Z| - |Z n X| + |X n Y n Z|

Formula for |(X U Y U Z)'| = |U| - |X U Y U Z|

= |U| - (|X| + |Y| + |Z| - |X n Y| - |Y n Z| - |Z n X| + |X n Y n Z|)

Find a formula for an:

By Inclusion/Exclusion number of dots in nth diagram.

= |X U Y U Z|

= |X| + |Y| + |Z| - |X n Y| - |Y n Z| - |Z n X| + |X n Y n Z|

= n^2 + n^2 + n^2 - n - n - n +1

= 3n^2 - 3n + 1

f(1) = 1, f(2) = 7, f(3) = 19

Multiplying choices:

If it is possible to specify an element of a finite set X by making a sequence choices where there are c1 choices then c2 choices,.., finally ck choices then

|X| = c1c2...ck

Example: suppose you roll a die(1 up to 6) then flip a coin (heads or tails). The number of outcomes of this process is 12. (Multiplying choices)

Counting subsets:

The subsets of the set {1,2} are empty set, {1}, {2}, {1,2} where {1,2} is a subset of itself. So there are 4 subsets.

Exercise:

Subsets of {1} are the empty set and {1}

Subsets of {1,2,3} : empty set, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}. There are 8 = 2^3 subsets

To choose a subset of {1,2...,n} we have n independent choices: put in 1 or not, put in 2 or not,..., put in n or not. So by multiplying choices there are 2^n subsets of {1,2,...,n}

(a) Three course meal, multiplying the choices you have 3x4x6 = 72

(b) Two course meals with main course,

possibilities are main and starter or main and dessert: (4x3) + (4x6)

Cartesian Products:

Let X and Y be sets.

The product of X and Y is the set X xY of all ordered pairs (x,y) where x in X and y in Y.

Note that in the form (x,y) x is the first element and y is the second element.

Equality for ordered pairs to be defined so that (x,y) = (x',y') x=x' and y=y'

An important product is RxR = {(x,y) : x in R, y in R} = R^2

a) False, different things appear in different places

b) True, sets font have a notion of order, they have the same elements

c) True, the point that is these coordinates is in the box.

d) False, the coordinates do no lie in the box

e) True

f) False 3 is in X but it is not in Y. Values included on the x axis are not the same as the values included on the y axis.

g) True, both sides have the empty set.

More generally you can take the product of 3 or more sets.

For example: X x Y x Z = {(x,y,z) : (x in X, y in Y, z in Z)}

Elements are ordered triples or sequences of 3 elements. We appear to live in R^3.

Note read X x Y as X cross Y etc.

Example:

Suppose you roll a die, flip a coin, and then choose a card from a deck of 52.

How many outcomes are there? 2 x 6 x 52 = 624

The outcomes could be described as triples.

Outcomes: {(x,y,x) : x in {1,2,3,4,5,6}, y in {heads or tails}, z in {aces spaces,..., 2 of clubs}}

One possible outcome is : (5, Heads, ace of diamonds)

Section 8: Euclids Algorithm and Congruences

Greatest common divisors:

Let m,n be natural numbers. We say that d in N is the greatest common divisor of m and n if d is the greaters natural number such that d divides both m and n.

One way to find gcd(m,n) is to find the prime factorizations of m and n. If p^a is the highest power of p dividing m and p^b is the highest power of p dividing n then p^min(a,b) is the highest power of p dividing gcd(m,n). This determines the prime factorization of gcd(m,n).

Example: m = 216 and n = 60

then m = 6^3 = (2x3)^3 = 2^3 x 3^3

n = 6x10 = 2^2 x 3 x 5

so the greatest common divisor of m and n is 2^2x3 = 12. Take the smaller power of each prime appearing in prime facorizations of m and n.

Notation: gcd(m,n) for greatest common divisor of m and n

Exercise: Find gcd(m,n) in each of these cases:

(i) m = 310 and n = 42.

m = 310 = 31 x 10 = 31 x 5 x 2, n = 2 x 3 x 7

by prime factorization we have the gcd(310,42) = 2

(ii) m = 23 and n = 46

m = 23 is a prime factor and n = 2x23, so the gcd(23,46) = 23

Note that is m divides n then gcd(m,n) = m

(iii) m = 31460, n = 41991752

m = 31460 = 2^x5x11^2x13, note that n is even and it is not divisible by 5, remainder when we divide n by 11^2 is 33..

Note that you do not need to factor n completely to find the gcd.

Example:

m = 216 and n = 60

{d in N: d divides 60 and 216} = {d in N : d divides 216 and r}

= {1,2,3,4,6,12}

216 = (2^3)(3^3) and 60 = 2^3(3)(5) and 216 = 3 x 60 +36

{d in N: d divides 60 and 36} = {1,2,3,4,6,12}

Proof for Lemma:

1) Will shows that {d in N: d divides m and n is a subset of {d in N: d divides m and r}

Let d divide m and n. Want to show that this divides m and r. Since we let d divide m we just need to show d divides r.

We have r/d = (n-qm)/d = (n/d) - q(m/d) in Z

(n/d) is an integer and (m/d) is an integer.

Hence d dividers r, and we know d divides m so

{d in N: d divides r and m}

2) Will show that {d in N: d divides m and r} is a subset of {d in N: d divides m and N}

Let d divide r and m. As we know it divides m then show d divides n.

We have n/d = q(m/d) + r/d in Z since m/d in Z (d divides m) and (r/d) in Z (d didives r). Hence d divides n and we know d divides m so {d in N: d divides m and n}

Putting (1) and (2) together we get that these sets are equal

{ in N: d divides n and m} = {d in N: d divides r and m}

In particular these sets have the same greatest element. The gcd(m,n) = gcd(m,r)

Example (Done by the lemma above)

gcd(60, 216) = gcd(60, 36)

since 216 = 3x60+36, it is esaier to see gce(60,36)=12 than to directly see that gcd(60,216) = 12

Can repeat the lemma to get gcd(60,36) = gcd(36,24)

since 60 =1x36+24 and gcd(36,24) = gcd(24,12) since 36 = 1 x 24+12 and gcd(24,12) = 12

Algorithm:

Let n,m in N. Let n = qm+r where q in N0 and r in {0,1,2,....,m-1}

If r=0 then m divides n and gcd(n,m) = m

Otherwise repeatm replacing n with m and m with r

(Justified by lemma as gcd(n,m) = gcd(m, n) = gcd(m,r)

EXAMPLE: m = 119 and n = 51

51 = 0 x 119 + 51

119 = 2 x 51 +17

51 = 3 x 17 + 0

The final remainder here is 0 so by Euclids Algorithm gcd(51,119) = 17

Problem: suppose you are given a huge supply of rods of length 60 and 216. What lengths can you measure?

Suppose r,s in N0. Then x = r x 216 - s x 60

(r=2 and s=7)

= rx12x18 - sx12x5 = 12(rx18 - sx5) is divisible by 12 so we can only measure lengths that are divisible by 12.

Euclid on n = 216 and m = 60

216 = 3 x 60 +36

60 = 1 x 36 +24

36 = 1 x 24 +12

24 = 2 x 12 + 0

Stop when you have a remainder of 0. so gcd(216,60) = 12

Working back

12 = 36 - (24x1) using the line above the one where you reach a remainder of 0, rearrange to show the remainder

= 36 -1(60 - (36x1)) using the line above the one you use previously, rearrange the equation with 24 so that you can substitute it in here

= 2x 36 -1 x 60, since you have two 36 terms out these together and in the next step, substitute for the first remainder you had.

= 2x(216 - 3x60)- 1x60 this is simplified to the following

= 2(216) - 7(60)

Method of working back

using the last remainder that is the gcd, rearrange and this will be your new eq you work with. Wherever you have previous remainders keep rearrange using the equations you have from Euclid to form and equation in the desired form of sm+tn=gcd(m,n)

Example of working back for 8.6

1 = 43 - (21x2) = 43 - (21(389 - 9(43))) = 190x43 -21x389 = 190(3933-10(389)) - 21x389 = 190(3933)-1921(389)

Key point for working back, although method is understand of constantly rearrange an eq where you have a remainder. Use a calculator and write everything out as terms may be lost or accidently ignored.

CONGRUENCE: Let m in N, and let n,n' in Z. if n and n' have the same remainder on division by m then we say that n is congruent to n'modulom and write n=n'modm

Example:

1) Take m = 10, then 16 and 216 both have remainder 6 after division by 10 so 216=16mod10

2) Take m = 10 then -4=6mod10 since -4=-1x10+6

-14 = -4 = 6 = 16 etc, for the first positive integer subtract m from it to see the negative congruence.

There are infinitely many numbers congruent to mod10

3) Let m = 2. Then 0+0=0=0mod2

0+1=1=1mod2

1+1=1=1mod2

1+1=2=0mod2

Example: 1327 x 499 = 3mod10

7 x 9 = 63 = 3 mod 10

7 x -1 = -7 = -10x1+3 = 3mod10

Justified by 1327 = 7mod10, 499 = 9mod10, 7x9 = 3mod10

Lemma:

Let m in N. Let r,r',s,s' in Z. If r = r'modm and s = s'modm then

(i) r + s congruent to r' + s' modm

(ii) rs is congruent to r's'modm

Proof for (i):

Obeserve that if x,x' in Z then x=x'modm

iff x,x' have the same remainder on division by m

iff there exist t in {0,1,2,...m-1} and quotient q,q' in Z such that x=qm+t, x'= q'm+t

iff x-x' is a multiple of m

Now

r congruent to r'modm => there exists q in Z such that r-r' = qm

s congruent to s'modm => there exists u in Z such that s-s' = um

Hence fo these q, u we have r+s = (r'+qm)+(s'+um) = r'+s' +m(q+u)

so r+s congruent to r'+s'modm.

Proof for (ii):

Similarly rs = (r'+qm)(s'+um) = r's' + qms' +r'um + m^2uq

= r's' + (qs' + r'u + qum)m

so rs is congruent to r's'modm as required.

What is 3^2014 mod10?

Writing out a table for r natural numbers and 3^rmod10 we see how often the numbers repeat. So first we evaluate 3^rmod10 for the first few terms.

3^1 = 3

3^2 = 9

3^3 = 27 since its mod 10 we look at the units = 7

3^4 =81, looking at the units we have 1

3^5 = 343, looking at units we have 3

After a while it starts repeating, what we are looking for is 2014.

So 2014/4 = 503 x 4 + 2

3^(2014) = 3^(4x503+2) = 3^2012x3^2 is congruent to 9 mod10

Solving congruences:

a) we need for there to be a remainder of 7, so x + 9 -12 = 7 so x is 10

b) we need for the remainder to be 2, so x = 4

c) these are all natural numbers ending with 4 or 9 therefore

{n in Z: n congruent to 4mod5} = {4+5q:q in Z} = {4+5(q-1):q in Z}

Example: Not understood.

m = 31, solve 23x = 5mod31

Using Euclids Algorithm we ge,

31 = 1x23+8

23 = 2x8+7

8 = 1x7+1

So the gcd(23,31) is 1 and working back gives -4(23)+3(31) = 1

so -4(23) = 1-3(31) = 1mod31

Hence a solution to the equation 23y congruent to 1 mod31 is y = -4

multiply by 5 using lemma (ii)

23y = 1mod31 => 23 x 5y = 5x1= 5 mod31

so x = 5x-4 = -20 is a solution to 23x = 5mod31

All solutions are obtained

{x in Z: x congruent to -20mod31} = {x in Z : x = 11mod31}

SEction 6 logic and proof

Complex numbers continued

Section 7 Sets and counting

LOGIC AND PROOf continued

Section 8 Euclids algorithm and congruences