Let me begin with a short quotation from Wikipedia:
“In logic and mathematics, proof by contradiction is a form of proof that establishes the truth or the validity of a proposition, by showing that assuming the proposition to be false leads to a contradiction. Proof by contradiction is also known as indirect proof, proof by assuming the opposite, and reductio ad impossibile.”
In this lesson we learn how to perform a proof by contradiction.
In the first video I prove that the set of natural numbers has no upper bound. In other words, we’ll show that there is no biggest natural number.
We also solve some simple problems using indirect proof. Then I offer you some similar problems for your self-study and revision.
Problems for self-study.
1 There is a square island 5 km x 5 km in area. 24 different pirates buried their treasure chests on this island. Prove that there is a square 1 km x 1 km with no treasure chest.
2 17 black and white marbles are arranged in a circle. Prove that there are two marble of the same color next to each other.
3 A soccer league has 24 teams. During the season each team plays one match against every other team of the league. Prove that at any given time there are two teams which have played the same number of games.
1,692 total views, 5 views today