Reverse an infinite stream/lazy list

I made a block that reverses a finite stream:


They are kinda like Scheme lists, I just converted car with head of stream and cdr with tail of stream and cons with in front of stream

Anyway I put the NUMBERS FROM stream block as the parameter and it froze. I concluded that it would stay this way forever because there would always be a stream tail.

Now I'm not sure how to reverse an infinite stream. I was thinking of swapping the head and the tail of the stream but that didn't work. I was also thinking of putting the tail in front of the head but that didn't work either. I couldn't begin to think of any other ways to do this so I am stumped.

:~)

So, an infinite stream doesn't really store an infinite amount of data in your computer. What "infinite stream" really means is that you can retrieve any item at a finite position in a finite amount of time. But there is no "last item." Think about NUMBERS FROM. The last item of the stream it reports would be the largest integer. But there is no largest integer! (Proof by contradiction: Suppose there is a largest integer. Add 1 to it. What's the answer?)

So the reason you can't reverse an infinite stream isn't a bug in your code. It's that the whole idea is incoherent.

Since you can't do that, think about how to generate the stream of all the positive rational numbers (ratios of two positive integers). It's a really hard problem, solved around 1900 by Georg [sic] Cantor.

I just tested it w/ JS in the console
and I got 9007199254740992
When i multiply it by itself it just converts it to a bigger scaled integer (8.112963841460666e+31) like a dynamic array

You've either missed Brian's point (or I've missed a joke) :slight_smile:

Both.I did miss his point and I putted a joke for Number.MAX_SAFE_INTEGER is not Infinity

Ohh... That makes a lot of sense.

Wait, 1900? They had streams in 1900? They probably didn't have the technology to put the idea to actual use in 1900 but they had the idea of it? Or are you talking about the century 1900-1999?

No, but they had numbers. Cantor invented set theory, which has to do with measuring the size of sets, and in particular the size of infinite sets. If I lose you in the following, tell me where.

The basic idea is one-to-one correspondence. That is, if you have a big pile of marbles, too big to count in your head, and a big pile of rivets, you can figure out which is bigger by pairing up marbles with rivets. If you have marbles left over, the set of marbles is bigger; if you have rivets etc; if you don't have anything left over, the two sets are the same size.

Okay, that's straightforward for finite sets. But infinite sets can be put in one-to-one correspondence with proper subsets of themselves. ("Proper" means not the set itself.) In fact, this is the definition of an infinite set.

So, for example, let A be the set of positive integers, and let B be the set of even positive integers. So, clearly B is a proper subset of A. But they can be placed in one-to-one correspondence as follows: Pair up the number n from set A with the number 2n in set B. Every number in A is included in this pairing, and so is every number m in set B, because it can be paired with m/2 in set A. (m/2 is an integer because every number in set B is even.)

Still with me? So, what Cantor did that's relevant to rational numbers was to prove that the set of rational numbers is the same size as the set of positive integers.

What does any of this have to do with streams? Well, the way streams work is that you can find any finite item number from the stream with n-1 CDRs and then CAR of that. And, hey, an item number is a positive integer! So: The infinte sets that can be represented as streams are precisely the ones that can be placed in one-to-one correspondence with the positive integers. The integer n is paired with ITEM n OF the stream. So, the correspondence that Cantor invented between the positive integers and the positive rationals is how you write the code for the stream of rationals.

Note: Don't be misled by the even integers example into thinking that the correspondence between two sets of numbers has to follow the size ordering of the numbers. For example, here's how to put the positive integers in one-to-one correspondence with the set of all the integers: You rearrange the integers this way:

0, 1, -1, 2, -2, 3, -3, 4, -4, ...

and then you can line them up with the positive integers.


Now for the exciting part. By this time, Cantor had pretty much convinced himself that all infinite sets would turn out to be the same size, "infinity." But then he proved that the set of real numbers is bigger than the integers!

Ready? Here goes.

To simplify things, we'll actually prove that the set of real numbers in the range 0<r<1 (strictly less than), which is a proper subset of the reals, is bigger than the integers. So the real numbers would be, if anything, bigger than the (0,1) range.

A real number in that range can be represented as a decimal, like this:
0.abcdef...
with an infinite number of digits (maybe mostly 0) after the decimal point. So, proof by contradiction, assume that this set is the same size as the positive integers. Then we can make a one-to-one correspondence between positive integers and decimal fractions. Basically this is an infinite list of decimal fractions. So now we're going to construct a decimal fraction that isn't in the list.

We construct it digit by digit, starting after the decimal point. For the first digit, we look at the fraction that's paired with 1, and we choose any digit that isn't the first digit of that fraction. (And we also don't choose 0 or 9, to avoid the problem that 0.09999... is the same number as 0.10000...) For the second digit, we look at the fraction that's paired with 2, and choose any digit that isn't its second digit or 0 or 9. For the third digit, look at the fraction paired with 3, and choose anything that isn't its third digit or 0 or 9. And so on forever.

So, I claim this fraction we just constructed isn't in the list. Because if it is in the list, it has to be paired with some positive integer n. But the fraction that's paired with n isn't this fraction, because they differ in the nth digit. (Maybe other digits too, but for sure in that digit.) So this decimal fraction isn't in the list, so we can't make a one-to-one correspondence between the positive integers and the real numbers in (0,1), so the reals are bigger than the integers!

Isn't that fantastic? That we can prove such a thing? Cantor himself remarked, "I proved it, but I don't believe it," because it was so counterintuitive that all infinite sets aren't the same size. I was wrong about this; what he said that about was that C²=C.

So, you can construct a stream of all the rational numbers, but you can't construct a stream of all the real numbers.

The numbers that are the sizes of infinite sets are called "transfinite cardinal numbers." (There are also "transfinite ordinal numbers," which have to do with the natural ordering of sets, but they're way more complicated.) The size of the integers is represented as ℵ₀, pronounced "aleph null," and the size of the reals is C, for "continuum" because the reals are continuous on the number line. A set the same size as the integers (or smaller, i.e., finite) is called "countable." So, you can make streams of countable sets.

So, why isn't the size of the reals called ℵ₁? Because Cantor couldn't determine whether there are any infinite sets larger than the integers but smaller than the reals. That question was unsettled until I was in high school, so early '60s, when one day I picked up my copy of the New York Times (I subscribed through the school), and on the front page of the second section was a half-page article saying that someone had just proved that the question C≟ℵ₁ is undecidable, i.e., the axioms of set theory are consistent with either of C=ℵ₁ and C≠ℵ₁. That was the most exciting day of my time in high school.

How does that mean it can't be paired with an integer? Can't you just get a new integer? If the set of integers is infinite, then you should always be able to get a new integer, right? I remember I watched a video that explained this long ago, it was on YouTube made by a guy named Vsauce. Somehow those videos are entertaining. except i forgot most of what the video said

I don't know what size ordering means

Starting with the easy question: When we made the 1-1 correspondence between the positive integers and the positive even integers, the pairing went like this:

1 2
2 4
3 6
4 8

and so on. As you read down the page (I made it vertical just to avoid issues about variable spacing making the pairing hard to see), the even ints are in size order, 2<4<6<8 etc. But for the positive integers vs. the integers, it's

1 0
2 1
3 -1
4 2
5 -2
6 3
7 -3

etc. And reading downward, it's not the case that 0 < 1 < -1 < 2 < -2 etc. That's all I meant by "size ordering." Because the rationals in 1-1 correspondence with the +ints aren't in size order.

Good question! But no. We have supposedly already paired all the +ints with all the reals in (0,1). That's why we were able to make the (hypothetical) claim that the reals are the same size as the integers. So we shouldn't be able to find another real number not in the list. Even if you cons that number onto the front of the list (not the end of the list because it has no end), you now have a new list of supposedly all the reals, and we can still construct a number that isn't in the list, the same way.

You've seen proof by contradiction before, haven't you? Where you start by assuming the opposite of what you want to prove, and show that that leads to a contradiction? That's what we're doing here. We're assuming that you can put the reals in (0,1) in 1-1 correspondence with the +ints, and showing that that leads to a contradiction.

Keep asking questions...

Pair all as many reals as we can with positive odd ints. Construct a new real and put it in idx 2. Construct another new real and put it in idx 4... Is there a problem or contradiction there that I don't see?
EDIT: Brian came up with a good point. My original wording implies that every possible real is still in the list, but I'm thinking that changing the wording doesn't change the math. That makes sense: if it's done infinitely, we can do it again with all of them (the original odd-indexed ones and the filled-in even-indexed ones).

The deep problem is that C > 2ℵ₀ also. (Remember, we've already established that 2ℵ₀=ℵ₀, since the number of even ints is the same as the number of ints.) In fact, C > ℵ₀², so you can do your move infinitely many times and still not make a dent in C. (And no, C isn't the biggest transfinite cardinal by any means; the number of transfinite cardinals is huge, way bigger than C.) It turns out that C = 2^(ℵ₀).

But the flaw in your reasoning is this: By hypothesis, we've put all the reals in that list! So you shouldn't even be able to construct one "new" real, let alone infinitely many of them. Any putative sequence (a 1-1 mapping between something and the +ints) containing all the reals is provably incomplete.

Trying to read your mind, I think you think that if you insert a missing real into the list infinitely many times, you have to have found all of them. But that's true only if the missing reals are countable! "Infinitely many times" really means "countably many times." You are assuming what you're trying to prove.

You guys might want to skim https://en.wikipedia.org/wiki/Georg_Cantor. Like all Wikipedia math articles, it's unreadable, but if you accept that, you can still get a lot out of it. @snapenilk may find its discussion of the theological implications of set theory interesting.

(See, this is how I want to spend my time on the forum!)

:+1: (should be the thumbs-up emoji)

One more idea (that probably won't work, but I think it's good to think about): start as I have previously described (with the wording of "as many as we can" instead of "all" so that the hypothesis is not contradicted), but instead of filling in every even index, fill in every other index so that there are still spaces remaining. What would happen if the infinite-step-filling algorithm was done an infinite number of times? I think somehow some reals will be skipped over, but I think they have to be because there's not a 1-1 correlation between the continuum and the discrete set.


Just terminating decimals

Is the set of terminating decimals a continuum? I can take any two (e.g. 0.5568 and 0.5567) and find one that is between them (e.g. 0.55675), but there is a 1-1 correspondence with them and the positive ints:

  1. 0.0
  2. 0.1
  3. 0.2
  4. 0.3
  5. 0.4
  6. 0.5
  7. 0.6
  8. 0.7
  9. 0.8
  10. 0.9
  11. 0.01
  12. 0.11
  13. 0.21
  14. 0.31
  15. 0.41
    ...
    The algorithm: index - 1 -> reverse -> append after 0.

Terminating decimals are a subset of the rational numbers, so, not a continuum. There's only one way to fill up a number line without any holes, and that's the real numbers. Other continua are things like higher-dimension spaces such as the complex plane.

No matter how you fill in the spaces in a list, the set of everything in the list still has to be the same size as the +ints! That's because the item numbers in the list are integers. And no matter what technique you use to fill up the spaces, you still won't have all the reals when you're done, by Cantor's proof with the digits, above. (This proof technique has a name: diagonalization.)

By the way, in case this wasn't clear, a set of size C is not necessarily a continuum. Consider the irrational numbers. That's a set of size C, but it has infinitely many holes where the rationals go.