Paradox: The Illusion of Falsidical Proof

1. PARADOX Chi-Kwong Li

2. A ‘ VISUAL ’ PARADOX : I LLUSION

3. F ALSIDICAL PARADOX  A proof that seems right, but actually it is wrong!  Due to: Invalid mathematical proof logical demonstrations of absurdities

4. E XAMPLE 1: 1=0 (?!)  Let x=0  x(x-1)=0  x-1=0  x=1  1=0

5. EXAMPLE 2: THE MISSING SQUARE (?!)

7. Mathematical Induction  The principle of mathematical induction: For a statement involving positive integer n. a) check that the statement is true for n = 1. b) check that if the statement is true for n = k, it will ensure that n = k+1 is true. Then the statement is true for all positive integer n.  Suppose there are n balls in a box such that. If you are ensured that you pick a ball from the box with a certain color, then the next ball must be of the same color. The first ball you pick is a red ball. Then ……

8.  If there are n (> 0) people in the this room, then they are of the same gender. A WRONG INDUCTION PROOF 3

9. Proof by Induction  If there is one person only, then the statement is true.  We show that if k people in this room have the same gender, then k+1 people in this room will have the same gender. Proof. For k+1 people, ask one person to leave the room. Then the k remaining people have the same gender. Now, ask the outside person to come back, and ask another person to leave the room. Then again the k remaining people have the same gender. So, …..

10. B UT WE KNOW , NOT ALL PEOPLE IN THIS ROOM HAVE THE SAME G ENDER !  What is wrong?

11. BARBER PARADOX (BERTRAND RUSSELL, 1901)  Once upon a time... There is a town... - no communication with the rest of the world - only 1 barber - 2 kinds of town villagers: - Type A: people who shave themselves - Type B: people who do not shave themselves - The barber has a rule: He shaves Type B people only.

12. QUESTION: WILL HE SHAVE HIMSELF?  Yes. He will!  No. He won't!  Which type of people does he belong to?

13. ANTINOMY  p -> p' and p' -> p  p if and only if not p  Logical Paradox  More examples:  (1) Liar Paradox  "This sentence is false." Can you state one more example for that paradox?  (2) Grelling-Nelson Paradox  "Is the word 'heterological' heterological?"  heterological(adj.) = not describing itself  (3) Russell's Paradox:  next slide....

14. RUSSELL'S PARADOX  Discovered by Bertrand Russell at 1901  Found contradiction on Naive Set Theory If we define all mathematical entities as sets, and assume that there is a universal set U containing every sets. Problem. Define a set R to be the elements in U such that x is not an element x. Question: Is R an element of R?

15. B IRTHDAY P ARADOX  How many people in a room, that the probability of at least two of them have the same birthday, is more than 50%?  Assumption: 1. No one born on Feb 29 2. No Twins 3. Birthdays are distributed evenly. Formula: ???

16. 3 T YPES OF P ARADOX  Veridical Paradox : contradict with our intuition but is perfectly logical  Falsidical paradox: seems true but actually is false due to a fallacy in the demonstration.  Antinomy: be self-contradictive

17. A DDITIONAL PARADOX  Surprise test paradox The instructor says that he will give a surprise test in one of the lectures. Then ….  Zeno’s paradox ( Zeno of Elea , 490–430 BC) In a race, the quickest runner can never overtake the slowest, since the pursuer must first reach the point whence the pursued started, so that the slower must always hold a lead.

18. HOMEWORK 1. People from H village always tell the truth; people from L village always lie. If you have to decide to go left or go right to visit the H village, and seeing a person at the intersection who may be from H village or L village. What question should you ask the person to ensure that you will be told the right direction to the H village. 2. Consider the following proof of 2 = 1 Let a = b a 2 = ab a 2 – b 2 = ab – ab 2 (a-b)(a+b) = b(a-b) a + b = b b + b = b 2b = b 2 = 1 Which type of paradox is this? Which part of the proof is wrong?