Using Induction to prove something false?

  • Context: Undergrad 
  • Thread starter Thread starter lpau001
  • Start date Start date
  • Tags Tags
    Induction
Click For Summary

Discussion Overview

The discussion revolves around the use of mathematical induction, particularly whether it can be employed to prove statements false. Participants explore the nature of induction and its traditional application in proving statements true, while questioning the validity of using it for disproving claims.

Discussion Character

  • Exploratory
  • Debate/contested
  • Mathematical reasoning

Main Points Raised

  • One participant expresses uncertainty about using induction to prove something false, noting that induction is typically associated with proving truths.
  • Another participant suggests that induction could be used to show the truth of a negation, thus indirectly disproving a statement.
  • A participant questions how to disprove the claim that there are more even natural numbers than odd natural numbers using induction, proposing that bijections might be a more suitable approach.
  • It is noted that every natural number has a unique successor, and there exists a bijection between even and odd natural numbers, implying they have the same cardinality.
  • One participant expresses skepticism about the naturalness of using induction for such proofs, despite acknowledging the bijection argument.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the appropriateness of using induction to prove statements false. Multiple viewpoints are presented, with some advocating for its use in disproving statements and others questioning its applicability.

Contextual Notes

Participants discuss the implications of using induction in the context of countably infinite sets and the nature of mathematical proofs, but do not resolve the underlying assumptions or limitations of their arguments.

lpau001
Messages
25
Reaction score
0
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?
 
Physics news on Phys.org
lpau001 said:
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?

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.
 
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.
 
Last edited:
SW VandeCarr said:
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.

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.
 
jojay99 said:
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.

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
 
Last edited:
SW VandeCarr said:
Every natural number has a 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.

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

Similar threads

Undergrad Question about mathematical induction
  • · Replies 10 ·
Replies
10
Views
2K
Undergrad Use of induction in the proof of the Chinese Remainder Theorem
  • · Replies 7 ·
Replies
7
Views
3K
Undergrad Prove Even # Transpositions in Identity Permutation w/ Induction & Contradiction
  • · Replies 8 ·
Replies
8
Views
5K
Undergrad Is there any way to simplify my proof by induction?
  • · Replies 13 ·
Replies
13
Views
2K
Prove Fibonacci identity using mathematical induction
  • · Replies 4 ·
Replies
4
Views
3K
Undergrad What is mathematical induction
  • · Replies 5 ·
Replies
5
Views
4K
Prove that ##5 | (2^n a) \rightarrow (5 | a)##for any ##n##
  • · Replies 10 ·
Replies
10
Views
3K
[L'Hospital's Rule] Can I Use Mathematical Induction to Prove This?
  • · Replies 6 ·
Replies
6
Views
2K
Self excited induction generators and grid connected solar inverters?
  • · Replies 9 ·
Replies
9
Views
2K
High School Is 2ab Always Less Than or Equal to a² + b² for All Integers a and b?
  • · Replies 10 ·
Replies
10
Views
3K