Let’s try induction

Prove that 7ⁿ-1 is divisible by 2 for every positive integer n.

Day 9: Functions and Induction

MTH 300 Fall 2020

Exams are still being graded. �I will probably return them on Thursday this week. Thank you for your patience.

Questions? Concerns?

http://35.247.101.134/Math_300_Fall_2020

For a review of one-to-one and onto, let’s visit the class wikitext!

Task 17: One-to-One, Onto, Both, Neither

• Go to Google Classroom and click on Classwork > Lesson 9> Task 17: One-to-one, Onto, Both, Neither

​

• Take 3 minutes of private reasoning time. Don’t write in the document yet… use your own paper.

​

• Make note of what breakout room you are in. That will dictate which page of the document you will work on.

​

• Take turns sharing your ideas and understanding for each question.

​

​

• Class discussion will follow

​

• Feel free to continue modifying your document at any point in these discussions. When you feel that you have completed it, you may click on the blue button to turn in your work.

​

​

How to prove that a given function is one-to-one

Why do we get to assume that

​

We are proving IF f(x₁)=f(x₂) THEN x₁=x₂

Assume f(x₁) = f(x₂)

This means 1/x₁ = 1/x₂

So x₂ = x₁

Thus, we have shown that f is one-to-one

f(x) = 1/x

How to prove that a given function is NOT one-to-one

Why is this enough to confirm that a function is NOT one-to-one?

We only need to show that there is a pair of x-values that have the same y-value.

​

Let x₁ =2 and x₂ = -2 Then f(2) = 4 and f(-2) = 4 but

2 does not equal -2

f(x) = x²

How to prove that a given function is onto

Why do we start with a y and not start with an x?

​

The enemy picks a y and we must defend ourselves with an x.

Let y be a real number.

{Secret side work:

y=2x+3

y-3 =2x

(y-3)/2 =x}

​

Let x = (y-3)/2.

f(x) = f((y-3)/2) =

2((y-3)/2)+3 =

y-3+3 =

y

Since y was arbitrary, this works for any y in the codomain.

x in dom(f)

f(x) = 2x+3

How to prove that a given function is NOT onto

Why is this enough to confirm that a function is NOT onto?

Because we only need to find one output that is not used to show it is not onto.

y = -1

Any real number, when squared will be greater than

or equal to 0. Thus, no x value will give f(x) = -1.

f(x) = x²

Definition of Isomorphism

We use the term "isomorphic" to express the idea that two groups are essentially the same (equivalent but not necessarily equal). So the group given by the mystery table is isomorphic to the symmetry group of an equilateral triangle.

Write a definition for isomorphic.

Definition: Let (G, •) and (H, *) be groups. G is isomorphic to H if…

There is a bijection f: G -> H such that for any a, b in G

f(a •b) = f(a)*f(b)

So if a•b = c f(a•b) =f(c)=f(a)*f(b)

​

Why do Isomorphisms NEED to be Bijections?

The groups need to have the same number of elements in order to define the equivalence.

D = 0

A = RR

C = R

B = RRR

Proofs about Isomorphisms

Task 18: Proofs about Isomorphisms

• Go to Google Classroom and click on Classwork > Lesson 9> Task 18: Proofs about Isomorphisms

​

• Take 3 minutes of private reasoning time. Don’t write in the document yet… use your own paper.

​

• Make note of what breakout room you are in. That will dictate which page of the document you will work on.

​

• Take turns sharing your ideas and understanding for each question.

​

​

• Class discussion will follow

​

• Feel free to continue modifying your document at any point in these discussions. When you feel that you have completed it, you may click on the blue button to turn in your work.

​

​

Proofs about Isomorphisms Discussion

Proof Techniques Thus Far...

Direct Proof

​

• If P, then Q.
• Assume P is true. �Show Q is true.
• For all x, P(x) is true.
• No matter what value x is, show that P(x) must be true.

​

Let x and y be odd integers, then xy is odd.

​

Assume x and y are odd integers. By the definition of odd, this means x = 2k + 1 for some integer k and y = 2j + 1 for some integer j. Thus, consider

xy = (2k + 1)(2j + 1)

= 4kj + 2j + 2k + 1

= 2(2kj + j + k) + 1

Since k and j are both integers and since the integers are closed under multiplication and addition, 2jk + j + k is itself an integer. Let z = 2jk + j + k. This means that xy = 2z + 1 where z is an integer. Thus, by definition, xy is odd.

​

​

​

Existential Proof

​

There exists an x such that P(x) is true.

• Constructive argument:
• Here is an x. Show P(x) is true.
• Non-constructive argument:
• Show that P(x) must be true for at least one x but without providing that x.

​

There exist real numbers x and y such that |x+y| = |x|+|y|.

​

Constructive proof:

Let x = 1 and y = 2. Notice that both x and y are real numbers. Then |1+2| = |3| = 3 and |1|+|2| = 1 + 2 = 3.

Thus, there exist real numbers x and y such that |x+y| = |x|+|y|.

​

​

Non-constructive proof:

We will demonstrate that this works provided that x and y are both positive, both negative or both 0.

Case 1: Assume x and y are both positive real numbers.

Then |x+y| = x+y and, similarly, |x| = x and |y| = y so |x|+|y| = x+y. Thus, |x+y| = |x|+|y|.

Case 2: Assume x and y are both negative real numbers.

Then |x+y| = -x + -y and |x| = -x and |y| = -y so |x|+|y| = -x + -y

Thus, |x+y| = |x|+|y|.

Case 3: Assume x and y are both 0. Then |x+y| = 0 and |x| = 0 and |y| = 0 so |x|+|y| = 0+0 = 0. Thus, |x+y| = |x|+|y|.

Thus, there exist real numbers x and y that satisfy |x+y|=|x|+|y|.

​

​

​

Proof by Contradiction

• If P, then Q.
• Assume P is true but Q is false. �Find a contradiction.. �Therefore, if P is true, Q is true.
• For all x, P(x) is true.
• Assume there is an x such that P(x) is not true. �Find a contradiction.�Thus, for every x, P(x) is true.
• There exists an x such that P(x) is true.
• Assume for all x, P(x) is false. �Find a contradiction.�Thus, there is an x such that P(x) is true.

​

Any group (G, *) must have a unique identity element.

​

Suppose for the sake of contradiction that G has two distinct identity elements, i and e. Consider the expression i * e.

Since i is an identity element, i * e = e. Since e is an identity element, i * e = i. But since * is a binary operation, i * e can only have one output. This is a contradiction. Thus, G must only have one identity element.

​

​

Disproof by Counterexample

​

• “If P, then Q” is false
• Show that there is an instance where P is true and Q is false.
• “For all x, P(x) is true” is false.
• Find an x such that P(x) is false.

​

If a and b are integers such that ab is divisible by 10 then either a is divisible by 10 or b is divisible by 10.

​

We will disprove this statement by providing a counterexample.

Let a = 4 and b = 5. Then ab = (4)(5) = 20. Note that 20 is divisible by 10 but neither 4 nor 5 are divisible by 10. Thus, the original statement is false.

There is one more big one we have not discussed or seen in practice yet...

Proof by Induction

For all integers x greater than or equal to a, P(x) is true.

• Base Case: Show P(a) is true
• Inductive Hypothesis: Assume P(k) is true for some arbitrary integer k > a.
• Inductive Step: Using the IH, show P(k+1) must be true.

​

​

​

​

​

​

​

​

​

​

P(a)

P(a+1)

P(a+2)

P(k)

P(k+1)

Task 19: Why does Induction Work?

• Go to Google Classroom and click on Classwork > Lesson 9> Task 19: Why does Induction Work?

​

• Take 3 minutes of private reasoning time. Don’t write in the document yet… use your own paper.

​

• Make note of what breakout room you are in. That will dictate which page of the document you will work on.

​

• Take turns sharing your ideas and understanding for each question.

​

​

• Class discussion will follow

​

• Feel free to continue modifying your document at any point in these discussions. When you feel that you have completed it, you may click on the blue button to turn in your work.

​

​

Why does Induction Work?

Let’s try induction

If is an isomorphism between groups (G, *) and (H, #), then for any element a in G and any positive integer k, .

Homework

• Read Chapter 7 of the Prover’s Handbook on Proof by Induction. http://35.247.101.134/The_Principle_of_Mathematical_Induction
• Attempt problems 1, 2 and 3 in this section. Also, share any questions or concerns that came up during the reading.

​

The assignment can be found on the google classroom under Classwork> Lesson 9 > Homework