Understanding Cardinality and Enumerating Infinite Sets

T o 0and B eyond... FYS 1023

A lerts p: faith in chaos, by Darren Aronofsky Please find a way to watch this movie, either individually or in small groups. It is available at the Otterbein library It should be available on a variety of streaming services for a small fee If you can't find a copy to watch I can let you borrow mine.

Homer: This time tomorrow, you'll be wearing high heels! Ned: Nope, you will. Homer: 'Fraid not. Ned: 'Fraid so! Homer: 'Fraid not. Ned: 'Fraid so! Homer: 'Fraid not infinity! Ned: 'Fraid so infinity plus one! Homer: D'oh!

C ardinality continued... Review Cardinality: what does it mean? How many? Number of elements Magnitude Size 1-1 Correspondence: what does it mean? Handshake between two sets with no leftovers Perfect pairing of elements from both sets 0: what does it mean? The cardinality of the natural numbers

E numeration This is a key concept Remember Logos/Ratio? A logos was a telling of events one after another, or an enumeration Counting is fundamental to 0 Squares: 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, ... Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, ... To form a 1-1 correspondence with , make a list so that every element is a finite distance from the beginning, also making sure that nothing is left out In other words, each element has to have a position in the list that is a natural number Any set that you can do this with is called denumerable, or countable (finite sets are also countable)

E numeration Examples = { , 3, 2, 1,0,1,2,3, }, the integers Worksheet +: the positive rational numbers 1, 2, 3, ..., 1/2, 3/2, 5/2, ..., 2/3, 4/3, 5/3, ... ??? Oops!! Other ideas? How do we enumerate a set where there are an infinite number of them everywhere we look? Idea: What if we find a way to look at finite subsets of them at a time without leaving any out?

S um of N umerator & D enominator 1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 9/1, 7/3, 3/7, 1/9 11. 10/1, 9/2, 8/3, 7/4, 6/5, 5/6, 4/7, 3/8, 2/9, 1/10 12. 11/1, 7/5, 5/7, 1/11 0/1 1/1 2/1, 1/2 3/1, 1/3 4/1, 3/2, 2/3, 1/4 5/1, 1/5 6/1, 5/2, 4/3, 3/4, 2/5, 1/6 7/1, 5/3, 3/5, 1/7 8/1, 7/2, 5/4, 4/5, 2/7, 1/8 Why does this work?

C ountable vs. U ncountable What is finite? Any natural number (? ) What is countable? 0or finite What is uncountable? A set that is not enumerable! Example: = the real numbers We will actually focus just on [0, 1], the unit interval

C ountable vs. U ncountable How to show that is uncountable? 1. Provide any candidate enumeration 2. If I can demonstrate that this enumeration is missing at least one number in the set, what does that mean? 3. If I can do (2) no matter which enumeration is provided in (1), what does that mean?

D iagonalization 1. 0.1352753198556454451... 2. 0.9876543210987654321... 3. 0.1357902468135790246... 4. 0.2222222222222222222... 5. 0.8989898989898989898... 6. 0.4192736489500135101... 7. 0.5444454443646664550... 8. 0.0000000000100000000... 9. 0.7997466423312552888... ... Let s begin to construct a number that is not on this list 1st digit differs from 1st digit of 1st number 2nd digit differs from 2nd digit of 2nd number 3rd digit differs from 3rd digit of 3rd number 4th digit differs from 4th digit of 4th number and so on... Infinity is bigger than you think - Numberphile 0.2 0.22 0.222 0.2225 0.222522225...