Using Induction to prove something false?

lpau001

Howdy, I am clumsy at best with induction (pretty new to it sadly), and I was wondering if it's proper to prove something false with induction? Every time I've used induction it's always been to prove something true. It may be a dumb question, but I'm beginning to think induction is only for 'true' proofs, like counterexamples are for 'false' proofs.

Any thoughts?

SW VandeCarr

I don't see why you can't use induction to prove a statement is false. Take the statement: There are more even natural numbers than odd natural numbers.

jojay99

Ipau001, I think I understand where you're coming from. Hopefully, my explanation is correct and makes sense.

We use induction to show that all elements in a countable set (e.g. the set of natural numbers) have a certain property. So to prove a statement is false, we could use induction to show that the negation is true. E.g. to disprove the statement that there exist a positive natural number (i.e not including zero) that is not divisible by one, we could use induction to show that all positive natural numbers are divisible by one.

jojay99

I'm curious. How would you disprove that using induction? They're both countably infinite. The only way I can think of is using bijections between both sets.

SW VandeCarr

Every natural number has a unique successor. Every even natural number has an odd successor such that there is a bijection between the set of even numbers and the set of odd numbers. Therefore the sets are equal (have the same cardinality).

Look up Peano's Axioms for the natural numbers.

http://en.wikipedia.org/wiki/Natural_number

jojay99

I thought so. However, using induction to prove that doesn't seem natural (pun intended) to me.