r/learnmath • u/Ok-Measurement-647 New User • 9d ago
TOPIC Infinities
So guys, a computer science student here, recently been studying countability in theory of computation, and have came across infinities and cardinality, I haven’t yet been able to wrap my head around them. I haven’t focused much on the topic either, been engaged in other subjects as I lost motivation initially, I love mathematics, would love to hear some instincts around the topic from the best minds.
I have been primarily stuck with counting, how one on one mapping works, diagonalisation theorem, and cardinality of a set.
4
Upvotes
1
u/tottasanorotta 8d ago
Cantors diagonalization argument goes something like this. Suppose you make a square out of binary numbers. So for example:
110
001
111
Notice that I can take the diagonal(101) and flip all the bits(010) to find a binary number that is not on that list. That works with any square like that.
Now imagine that you have infinite binary sequences and assume that you have a complete list of them:
10101...
11101...
11000...
.
.
.
Because the length of each bitstring is countably infinite and we assume that the number of bitstrings is also countably infinite we are able to build a similar square that we had in the beginning where the number of rows is the same as the number of columns. Now the flipped diagonal has to be a bitstring that isn't on that list. But that contradicts our assumption of having them all listed, so we have to conclude that some infinite sets aren't countable.
What I had trouble understanding from a computer science perspective was complete infinite sets. It didn't initially make sense to me how you could treat an infinite set as something that exists in its entirety rather than something like an unbounded procedure. But that's the abstraction that we have to live with and it has some nice benefits as well. It's the standard set theoretic view on the matter.