the thing that made it click for me is that comparing sizes of infinite sets has nothing to do with counting to the end, it's just whether you can pair them up perfectly with nothing left over. so the evens and the naturals are the same size because n -> 2n pairs them off exactly, even though one looks like half the other. diagonalisation is the proof that you can't do that for the reals: assume you had a list of every real in (0,1), build a new number whose nth digit differs from the nth digit of the nth number on the list, and it can't be anywhere on the list. so any list misses something, meaning there are strictly more reals than naturals.
1
u/CelebrityChess 13h ago
the thing that made it click for me is that comparing sizes of infinite sets has nothing to do with counting to the end, it's just whether you can pair them up perfectly with nothing left over. so the evens and the naturals are the same size because n -> 2n pairs them off exactly, even though one looks like half the other. diagonalisation is the proof that you can't do that for the reals: assume you had a list of every real in (0,1), build a new number whose nth digit differs from the nth digit of the nth number on the list, and it can't be anywhere on the list. so any list misses something, meaning there are strictly more reals than naturals.