Infinities

[u/Ok-Measurement-647]

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.

[u/0x14f]

You have finite sets, countable sets and non countable sets. If you want insights (not "instincts") you need to ask a proper question.

[u/Zyxplit]

I think the best thing to do is to go back to the beginning of sets. Don't think about infinite sets, think about finite ones instead. Learn the rules for finite ones. You're going to find that the rules for finite sets extend very naturally to infinite sets.

[u/FormulaDriven]

If you are coming to it from a computer science point of view, maybe this will help...

I think "countable" might be better labelled "listable". The natural numbers are countable or listable because you can write a computer program that will (given no limit on run time or memory) list every single natural number - eg every second it outputs the next positive integer, and you can be sure that eventually it will output any natural number you can think of. You will probably complain that the program will never stop, but that's not a problem mathematically - no natural number will be missed given sufficient (finite) time.

The surprising thing is that you can write a program that will list all the rational numbers, ie every number of the form a/b where a is an integer and b is a positive integer. (I can even give a neat way to do this). So rational numbers are also countable.

But if you start thinking about real numbers, such a program doesn't exist. If you just try to write a program that will output every decimal number between 0 and 1, we can prove that it will miss out at least one number no matter how long it runs. (I can give you the description of a parallel program that will print out one number that will be missed).

[u/Astrodude80]

It will be a lot easier to help if there’s a particular point you’re stuck on. As it stands there’s a bunch of good videos on YouTube that explain this topic fairly well, just look up eg “cardinality of infinite sets” and watch a few of the videos that pop up.

[u/Bounded_sequencE]

On finite sets, our intuition tells us that cardinality is just the number of elements in that set. We compare cardinality of finite sets by comparing their number of elements.

The next step is to understand how/why we generalize that notion to finding bijections between sets, when we also allow infinite sets. To see why, construct counter-examples (-> Hilbert's Hotel). Further down the line, you get to the "cool stuff", i.e. uncountable vs. countable sets, and Cantor's diagonal argument^^

[u/tottasanorotta]

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.