Inductive vs. Deductive Logic

Question 1

Is mathematical induction deductive or inductive?

Answer 1

Although it’s called ‘induction’ it is not an inductive form of inference, but a deductive one.

Question 2

What are the methods by which to make proofs about infinitely many elements?

Answer 2

1. Pick an arbitrary element and show case holds
2. Pick couterexample, to show that the claim does not hold
3. Partition infinite domain into finite numbers or sections and apply proof by cases

Alternatively …

4. Mathematical Induction

Question 3

What is deductive reasoning?

Answer 3

When the truth of the conclusion always follows (necessarily) from the truth of the
premises.
It is impossible for the premises to be true and the conclusion to be false at the same
time.
(‘From general to particular’ — not really. . . )

Premise (Must be true) —–> Conclusion (True)

Ex: Logic, and Mathematical Induction

Question 4

What is inductive reasoning?

Answer 4

When the consequence is made more likely by the premises.

(‘From particular to general.’ — not really. . . )

Hume’s problem of induction: How do I know that the sun will rise tomorrow?

Ex: scientific inquiry

Question 5

How does mathematical induction relate to inductive reasoning?

Answer 5

What we prove by mathematical induction is not only probable, but also deductively valid.

To distinguish it from the inductive method, we call it ‘mathematical induction’.

“Many mathematical results were found by induction first and proved later [by mathematical induction]. Mathematics presented with rigor is a systematic deductive science, but mathematics in the making is an experimental inductive science.”(George Polya, How To Solve It, p.117).

The principle of mathematical induction itself cannot be proved semantically or syntactically.

If we want to use it within our calculus it has to be assumed as an axiom.

We’ll see this when we talk about axiomatizations of number theory.

Question 6

Use dominos to demonstrate the set-up and execution of mathematical induction?

Answer 6

1. A way of setting up the dominos correctly. –> Recursive definition (Inductive/Hereditary)
2. Showing that all fall. –> Mathematical induction (Apply and any domain that is recursive)

Question 7

What are recursive (inductive) definitions?….

Answer 7

• Called “Definition by Induction” or hereditary definition (GEB)
• To make the connection precise = introduce our object by inductive/recursive definition

1. A Base Clause:

Which defines the essential elements of our set

2. Inductive Clause(s):

Tell us how to generate complex elements from parts

3. Final Clause:

States that all elements are either basic elements or generated by an inductive clause

Ex. Natural numbers IN defined as follows

1. (Base Clause) 0 is a natural number
2. (Inductive clause) If n is a natural number, then s(n) is a natural number too
3. (Final clause) Nother else is a natural number

Question 8

What is Mathematical Induction?

Answer 8

My only be applied to an inductively defined domain.

In general, method of induction not tell us how to arrive at the induction hypothesis, shows us it holds all elements of the domain

• Deductive process
• GEB: “an argument based on heredity.”

Show that a certain property holds for all elements in an infinite domain, sure that our inductive proof begins with basic elements

Analogous with dominos: want all to fall - have to set up the first element

• Always state the claim that you are proving.
• Always say whether you are showing the base case or the induction step.
• Always state the induction hypothesis.
• Always make clear where you apply the induction hypothesis.
• Always state the conclusion.

Question 9

What is weak mathematical induction?

Answer 9

(1) Base Case:

Show that the property holds for the basic element(s)

(2) Inductive Step:

Assume that the property holds for some element n (Inductive hypothesis)

Show that also holds for any element generated from n by inductive clauses

(3) Conclusion:

The property holds for all elements

Question 10

What is strong (complete) mathematical induction?

Answer 10

• Would like to assume the inductive hypothesis not only for previous element but all smaller elements*
  (1) Inductive Step:

Assume that the property holds for all elements less than or equal than n (Inductive Hypothesis)

Show that it also holds for any element generated from n by the inductive clause(s)

(2) Conclusion:

The property holds for all elements

• No need to prove base case separately - included in inductive step

Question 11

What is the Inductive Hypothesis?

Answer 11

Weak MI: Assume that the property holds for some element n

Strong MI: Assume that the property holds for all elements less than or equal than n (Inductive Hypothesis)

Question 12

5.1 Solve using mathematical induction:

Answer 12

Question 13

5.2 Solve using mathematical induction:

Answer 13

Question 14

5.3 Solve using mathematical induction:

Answer 14

Question 15

5.4 Solve using mathematical induction:

Answer 15

Question 16

5.5 Solve using mathematical induction:

Answer 16

Question 17

5.6 Solve using mathematical induction:

Answer 17