Another consequence of Cantor's diagonal argument

[Warp]

Thinking about Cantor's diagonal argument, I realized that there's another thing that it proves besides the set of all infinite strings being uncountable.

Namely: That it's not possible to list all rational numbers in an order such that the diagonal of their decimal representation has an infinitely repeating sequence.

My logic goes like this: It's possible to list all rational numbers in order without repetitions, for example using the Calkin-Wilf sequence. However, let's assume that you could list all rational numbers in such an order that the diagonal of their decimal expansion formed an infinitely repeating sequence. Let's say, for example, the sequence 0123456789, like:

0.0xxxxxx...
0.x1xxxxx...
0.xx2xxxx...

and so on. However, if we now apply the diagonal argument and take those digits in the diagonal and eg. increment each of them (with 9 wrapping around to 0), we would get a number that has an infinitely repeating decimal sequence, which is rational, but which is different from all the numbers in the list. Which contradicts the premise that the list contained all the rational numbers.

Since we know that every number with an infinitely repeating decimal sequence is a rational number, the only possible conclusion is that it's not possible to list all the rational numbers in an order such that their diagonal forms a repeating sequence (even if that repeating sequence has all the digits).

However, it's not at all intuitive to me why that's not possible.

(It's very obvious that you cannot list them so that the repeating sequence lacks one of the digits, because then the rational numbers whose decimal expansion does not have said digit wouldn't fit anywhere. It's much less obvious if the sequence has all the digits, eg. 0123456789.)

 

[Warp]

(Sorry for the additional post, but I can't find an edit button for my original post. I would add this as an edit, but it doesn't seem to be possible at this point.)

I notice that' there doesn't seem be an actual question in my post. I suppose my question would be: Why is it not possible to list all the rational numbers in such an order? Is there an intuitive way of understanding the reason?

 

[PeterDonis]

Why is it not possible to list all the rational numbers in such an order? Is there an intuitive way of understanding the reason?

If you don't find a proof you came up with yourself intuitive, I'm not sure how anyone else can be much help.

However, I can offer the following thought:

Since we're only talking about rational numbers, we have two possibilities:

(1) There are some bit strings in the list that are all zeroes after some finite index $i$. The only possible infinite repeating sequence on the diagonal that such bit strings can support is an infinite string of zeroes. The diagonalization then gives us an infinite string of some nonzero digit, and obviously such a number can't be in the list, since the list contains bit strings that are zero after some finite index $i$. So obviously such a list cannot contain all rational numbers.

(2) We carefully select a list of rational numbers that contains no numbers whose bit strings are all zeroes after some finite index $i$--in other words, we limit ourselves to those rational numbers that, after some finite index $i$, are repeating sequences of one or more digits, where zero can only be in the repeating sequence if it has more than one digit. So, for example, the rational number 1/2 would not be in this list, but 1/3 would, and so would 1/11, since its bit string is 090909...

We could try to analyze in detail how diagonalization of such a list would work--but we don't have to, because of course it's obvious from the start that such a list cannot contain all rational numbers, since we explicitly excluded the ones which are all zeroes after some finite index $i$. So either way we know that our list cannot contain all rational numbers.

 

[SSequence]

I notice that' there doesn't seem be an actual question in my post. I suppose my question would be: Why is it not possible to list all the rational numbers in such an order? Is there an intuitive way of understanding the reason?

Interpreting your question for a specific repetition sequence, I assume what you are trying to say is that an enumeration of rational numbers whose diagonal contains the pattern 0123456789 (repeated forever) can't contain all rational numbers. Your conclusion seems correct to me. But didn't you describe the reason yourself (take digits on diagonal and increment by 1 to form a new rational number)?

EDIT: It seems to me that other digit alterations would be more efficient/easier to work with (e.g. for this see post#34 in your thread that got locked). But, in this post, let's work with the digit alteration you suggested. END

For example:
$Q_0:$ 0.0xxxxxxxxxxxxxxxxxxxxxxxx
$Q_1:$ 0.x1xxxxxxxxxxxxxxxxxxxxxxx
$Q_2:$ 0.xx2xxxxxxxxxxxxxxxxxxxxxx
$Q_3:$ 0.xxx3xxxxxxxxxxxxxxxxxxxxx
$Q_4:$ 0.xxxx4xxxxxxxxxxxxxxxxxxxx
$Q_5:$ 0.xxxxx5xxxxxxxxxxxxxxxxxxx
$Q_6:$ 0.xxxxxx6xxxxxxxxxxxxxxxxxx
$Q_7:$ 0.xxxxxxx7xxxxxxxxxxxxxxxxx
$Q_8:$ 0.xxxxxxxx8xxxxxxxxxxxxxxxx
$Q_9:$ 0.xxxxxxxxx9xxxxxxxxxxxxxxx
$Q_{10}:$ 0.xxxxxxxxxx0xxxxxxxxxxxxxxx
$Q_{11}:$ 0.xxxxxxxxxxx1xxxxxxxxxxxxxx
$Q_{12}:$ 0.xxxxxxxxxxxx2xxxxxxxxxxxxx
$Q_{13}:$ 0.xxxxxxxxxxxxx3xxxxxxxxxxxx
$Q_{14}:$ 0.xxxxxxxxxxxxxx4xxxxxxxxxxx
...

As you mentioned yourself the rational number $Q=0.\overline{1234567890}$ [the bar denotes repetition of same pattern forever] won't be on the list. For example, let's take the first rational number $Q_0$. There is only one way we could have $Q_0$ getting its first digit (after decimal point) equal to $1$. And that possibility is:
$Q_0=0.0\overline{9999}$
But now, as you can observe, we have $Q \neq Q_0$.
$Q_0=0.1 \neq Q$

Let's move to second number $Q_1$. The only way $Q_1$ could equate its first two digits with $Q$ would be to have:
$Q_1=0.11\overline{9999}$
But now, as you can observe, we have $Q \neq Q_1$.
$Q_1=0.12 \neq Q$

Let's move to third number $Q_2$. The only way $Q_2$ could equate its first three digits with $Q$ would be to have:
$Q_2=0.122\overline{9999}$
But now, as you can observe, we have $Q \neq Q_2$.
$Q_2=0.123 \neq Q$

Let's move to fourth number $Q_3$. The only way $Q_3$ could equate its first four digits with $Q$ would be to have:
$Q_3=0.1233\overline{9999}$
But now, as you can observe, we have $Q \neq Q_3$.
$Q_3=0.1234 \neq Q$

Jumping to $Q_8$ now. Writing it side by side with $Q$ we get:
$Q=0.12345678901234567890\overline{1234567890}$
$Q_8: 0.xxxxxxxx8xxxxxxxxxxxxxxxx...$
So we at least know $Q_8$ would have to be:
$Q_8=0.123456788xxxxxxxxxxxxxxxx...$

To avoid inequality with $Q$, at this point, we are forced to have $Q_8$ of the form:
$Q_8=0.123456788\overline{9999}xxxxxxxxxxxxxxxx...$
But this leads to:
$Q_8=0.123456789 \neq Q$ (note that: $Q_8=0.123456789 < 0.12345678901<Q$ etc.)

====================

Finally, let's move to $Q_9$ now. Writing it side by side with $Q$ we get:
$Q=0.12345678901234567890\overline{1234567890}$
$Q_9=0.xxxxxxxxx9xxxxxxxxxxxxxxx...$
So we at least know $Q_9$ would have to be:
$Q_9=0.1234567899xxxxxxxxxxxxxxx...$

To avoid inequality with $Q$, at this point, we are forced to have $Q_9$ of the form:
$Q_9=0.1234567899\overline{9999}$
But this leads to:
$Q_9=0.12345679 \neq Q$

Moving to $Q_{10}$ now. Writing it side by side with $Q$ we get:
$Q=0.12345678901234567890\overline{1234567890}$
$Q_{10}=0.xxxxxxxxxx0xxxxxxxxxxxxxx...$
So we at least know $Q_{10}$ would have to be:
$Q_{10}=0.12345678900xxxxxxxxxxxxxx...$
To avoid inequality with $Q$, at this point, we are forced to have $Q_{10}$ of the form:
$Q_{10}=0.12345678900\overline{9999}...$
But this leads to:
$Q_{10}=0.1234567901 \neq Q$

Moving to $Q_{11}$ now. Writing it side by side with $Q$ we get:
$Q=0.12345678901234567890\overline{1234567890}$
$Q_{11}=0.xxxxxxxxxxx1xxxxxxxxxxxxx...$
So we at least know $Q_{11}$ would have to be:
$Q_{11}=0.123456789011xxxxxxxxxxxxx...$
To avoid inequality with $Q$, at this point, we are forced to have $Q_{11}$ of the form:
$Q_{11}=0.123456789011\overline{9999}$
But this leads to:
$Q_{11}=0.12345679012 \neq Q$And so on. (note: need to check typos and clerical mistakes in the post)

 

[FactChecker]

It seems to me that you are considering a hard thing (that the list has the property of an infinitely repeating diagonal sequence) and then are surprised that it can not be done. Your proof that it is impossible seems valid to me, and I consider it to be short and simple enough to become intuitive.

 

[SSequence]

@FactChecker
I think that it becomes easier to see directly if:
(i) we consider a digit change that is always guaranteed to diagonalize [otherwise, it seems, we would have to (additionally) consider something similar (or at least something that serves as a substitute) to post#4].

(ii) the realisation that, with the digit change, a pattern like 1234567890 (that repeats forever in cycles of finite length) will lead to a new pattern (that will still again repeat forever in cycles of finite length)

 

[Warp]

I didn't mean to say that the proof is unintuitive. I meant to say that it's unintuitive why you can't list all the rational numbers in an order that makes the diagonal contain a rational number.

In retrospect, it's after all relatively obvious why in my example 0.12345678901234... is not in the list: Because it cannot be added to the list anywhere, due to the constraint put on the diagonal. No matter where you try to put that number, it never fulfills that constraint. There's no place where the correspondent digit is correct for the diagonal, under the given constraints.

Of course by the same argument no other repeating pattern in the diagonal would work either.

This leads to the semi-interesting conclusion that it's impossible to rearrange the list of rational numbers in such a manner that the diagonal of their decimal expansion forms a rational number. In other words, no matter how you rearrange the list of rationals, the diagonal will always contain an irrational number.

 

[Jarvis323]

(1) There are some bit strings in the list that are all zeroes after some finite index $i$. The only possible infinite repeating sequence on the diagonal that such bit strings can support is an infinite string of zeroes. The diagonalization then gives us an infinite string of some nonzero digit, and obviously such a number can't be in the list, since the list contains bit strings that are zero after some finite index $i$.

I don't quite follow.

Are you talking about diagonalization on an enumeration of the rationals with all zeros after N digits or the set of rationals with finite non-zero digits. i.e. $$Q_n = \{ q \in Q \textit{ s. t. } \forall_{i>n}(q_i= 0)\}$$ or $$\{ q \in Q \textit{ s. t. } \exists_n\forall_{i>n}(q_i= 0)\}$$

If it's the first one, it's a finite set, so diagonalization on it can't produce an infinite sequence.

If it's the second one, then what you said doesn't seem obvious. Why diagonalization must give a trailing infinite string of some nonzero digit? The set is infinite, and there is no largest natural number.

 

[PeterDonis]

Are you talking about diagonalization on an enumeration of the rationals with all zeros after N digits or the set of rationals with finite non-zero digits.

Neither. Given any set of rationals, or more precisely of infinite strings of binary digits that represent rationals, either the set includes some rationals whose infinite strings of binary digits are all zero after some finite index, or it doesn't. Those are the two mutually exclusive, logically exhaustive possibilities. I am not making any further assumptions, in the first possibility, about the properties of the infinite strings of binary digits that are all zero after some finite index, beyond that bare statement.

 

[Jarvis323]

Neither. Given any set of rationals, or more precisely of infinite strings of binary digits that represent rationals, either the set includes some rationals whose infinite strings of binary digits are all zero after some finite index, or it doesn't. Those are the two mutually exclusive, logically exhaustive possibilities. I am not making any further assumptions, in the first possibility, about the properties of the infinite strings of binary digits that are all zero after some finite index, beyond that bare statement.

Can you clarify this sentence?

The only possible infinite repeating sequence on the diagonal that such bit strings can support is an infinite string of zeroes.

I interpret "such bit strings" to be a set, but don't follow how any definition of that set supports the conclusion.

 

[PeterDonis]

I interpret "such bit strings" to be a set

No. In that sentence, I'm talking about the first of the two possibilities: we have an enumeration of infinite bit strings, in which some of the bit strings are all zeroes after some finite index (and the finite index may be different for different bit strings). "Such bit strings" refers to the bit strings in the enumeration that are all zeroes after some finite index.

We are considering the question of whether such an enumeration of bit strings, with some infinite repeating sequence along the main diagonal, can enumerate all rationals--i.e., every rational number is represented by at least one bit string in the enumeration. My point is that, if we are considering an enumeration that meets the above requirement (some of the bit strings have all zeroes after some finite index), the only possible infinite repeating sequence that can be along the main diagonal is all zeroes.

 

[Jarvis323]

This leads to the semi-interesting conclusion that it's impossible to rearrange the list of rational numbers in such a manner that the diagonal of their decimal expansion forms a rational number. In other words, no matter how you rearrange the list of rationals, the diagonal will always contain an irrational number.

Does it matter at all how we think about rearranging? I mean, you have an infinite list, which by definition (as an enumeration) is computable. So now you want to rearrange it. To do so, you need another computable number. But consider that some infinite bit sequences are not computable. The point is that an enumeration cannot be ordered arbitrarily right?

Suppose you have an oracle that gives you the nth digit of an uncomputable number. Does anything change?

 

[Office_Shredder]

I think it's a neat result that the diagonal is irrational.

 

[PeterDonis]

I think it's a neat result that the diagonal is irrational.

That's not the result. The diagonal, by hypothesis, is a repeating decimal, which represents a rational number. But it is a rational number that is not in the list.

 

[Office_Shredder]

I'm confused. Isn't the actual theorem if you write down an enumeration of the rational numbers, the diagonal is an irrational number?

 

[Jarvis323]

I'm confused. Isn't the actual theorem if you write down an enumeration of the rational numbers, the diagonal is an irrational number?

Yes.

 

[Warp]

Does it matter at all how we think about rearranging? I mean, you have an infinite list, which by definition (as an enumeration) is computable. So now you want to rearrange it. To do so, you need another computable number. But consider that some infinite bit sequences are not computable. The point is that an enumeration cannot be ordered arbitrarily right?

In this case I'm talking about the list of all rational numbers. All rational numbers are computable (because all rational numbers have a finite recurring decimal pattern), and being countable, the list of all rational numbers is enumerable, and listable in any order you want (and it's even possible to list them without repetitions).

The thing I noticed during this is that no matter how you order the list of all rational numbers, the diagonal will always form an irrational number. (Might be a somewhat trivial result, but I found it interesting.)

 

[PeterDonis]

The thing I noticed during this is that no matter how you order the list of all rational numbers, the diagonal will always form an irrational number.

No, that is not what your argument in the OP of this thread proves. See my post #14.

 

[Warp]

No, that is not what your argument in the OP of this thread proves. See my post #14.

Do you mean that the proof I wrote in my original post is not enough to prove the hypothesis that the diagonal of the list of all rational numbers (no matter how it's ordered) always forms an irrational number?

If the proof is not complete, what would make it complete?

 

[Jarvis323]

Peter, I think you may be confused. The standard cantor argument is on the reals, and proves the reals are not enumerable because if you had such an enumeration you could construct a real number not in the list.

The op is asking about the rationals, and in this case the interesting thing is that the diagonal of an enumeration of the rationals must be irrational, because we know that the rationals are enumerable.

This means that you cannot enumerate the rationals in a way that gives an irrational number on the diagonal. It's not obvious why that should be at face value.

 

[PeterDonis]

Do you mean that the proof I wrote in my original post is not enough to prove the hypothesis that the diagonal of the list of all rational numbers (no matter how it's ordered) always forms an irrational number?

Yes.

If the proof is not complete, what would make it complete?

It can't be made "complete" in the sense you mean. Your scenario specifies that the diagonal sequence being constructed is a repeating decimal. All repeating decimals represent rational numbers.

What your proof actually shows is that no complete enumeration of the rational numbers can have the property you specified, of having the digits on its main diagonal form a repeating decimal. In other words, any enumeration of the rational numbers that does have the digits on its main diagonal form a repeating decimal must leave out at least one rational number.

I am surprised that you don't get this, since you stated it explicitly in your OP in this thread:

if we now apply the diagonal argument and take those digits in the diagonal and eg. increment each of them (with 9 wrapping around to 0), we would get a number that has an infinitely repeating decimal sequence, which is rational, but which is different from all the numbers in the list. Which contradicts the premise that the list contained all the rational numbers.

Since we know that every number with an infinitely repeating decimal sequence is a rational number, the only possible conclusion is that it's not possible to list all the rational numbers in an order such that their diagonal forms a repeating sequence (even if that repeating sequence has all the digits).

See the bolded items in the above quote.

 

[PeterDonis]

The op is asking about the rationals, and in this case the interesting thing is that the diagonal of an enumeration of the rationals must be irrational

No, that is not what the OP argument proves. See my posts #14, and now #21.

Everyone, please read what the OP actually says. I bolded the key statements in post #21.

 

[Jarvis323]

In this case I'm talking about the list of all rational numbers. All rational numbers are computable (because all rational numbers have a finite recurring decimal pattern), and being countable, the list of all rational numbers is enumerable, and listable in any order you want (and it's even possible to list them without repetitions).

The thing I noticed during this is that no matter how you order the list of all rational numbers, the diagonal will always form an irrational number. (Might be a somewhat trivial result, but I found it interesting.)

Yes, I know that. But the thing is, it is not listable in any order you want. It's only listable in an order that is computable. It means you have to be able to have a program with finite source code that can do the listing or rearranging.

 

[PeterDonis]

Yes, I know that.

No, you don't. As I've already pointed out several times now, the OP does not prove that the diagonal will form an irrational number. It explicitly states the opposite: that the diagonal number, by construction, is rational.

It's only listable in an order that is computable.

This is not a requirement for an enumeration.

 

[Jarvis323]

No, you don't. As I've already pointed out several times now, the OP does not prove that the diagonal will form an irrational number. It explicitly states the opposite: that the diagonal number, by construction, is rational

Which is a contradiction that there existed an enumeration of Q which forms a rational on the diagonal, thus no enumeration of Q can have a rational on the diagonal.

 

[PeterDonis]

Which is a contradiction that there existed an enumeration of Q which forms a rational on the diagonal, thus no enumeration of Q can have a rational on the diagonal.

No. You are misstating the argument in the OP.

The argument given in the OP is:

We assume that there is an enumeration of the rationals that has an infinite repeating decimal on the main diagonal.

The diagonalization method of Cantor then ensures that we can explicitly construct another infinite repeating decimal (the one obtained by shifting each digit in the infinite repeating decimal on the main diagonal by one, wrapping 9 around to 0) which cannot be in the enumeration.

Since any infinite repeating decimal is rational, we thus have proven that any enumeration of the rationals that has an infinite repeating decimal on the main diagonal must be incomplete.

The argument does not prove that there cannot be an enumeration of the rationals that has an infinite repeating decimal on the main diagonal. It only proves that if such an enumeration exists, it must be incomplete.

The argument does not prove that no enumeration of the rationals can have a rational on the main diagonal. It is perfectly possible, consistent with the argument, that such an enumeration exists.

 

[Warp]

It can't be made "complete" in the sense you mean. Your scenario specifies that the diagonal sequence being constructed is a repeating decimal. All repeating decimals represent rational numbers.

What your proof actually shows is that no complete enumeration of the rational numbers can have the property you specified, of having the digits on its main diagonal form a repeating decimal. In other words, any enumeration of the rational numbers that does have the digits on its main diagonal form a repeating decimal must leave out at least one rational number.

I am surprised that you don't get this, since you stated it explicitly in your OP in this thread:

I don't understand. That's exactly the conclusion I'm drawing. Namely: "If you take the list of all rational numbers, it's impossible to rearrange this list in a manner that the main diagonal of their decimal representation would form a rational number."

But then you say that's not a correct conclusion from the proof (or that the proof is not enough to prove that conclusion). I don't understand.

(Maybe you missed the part where I say "the list of all rational numbers"?)

 

[PeterDonis]

"If you take the list of all rational numbers, it's impossible to rearrange this list in a manner that the main diagonal of their decimal representation would form a rational number."

Here is your statement in the OP of what your OP argument shows:

Namely: That it's not possible to list all rational numbers in an order such that the diagonal of their decimal representation has an infinitely repeating sequence.

This does not say the same thing as the quote from you at the top of this post. Can you offer an additional argument that gets from the second statement of yours quoted above (the one from the OP of this thread) to the first (the one from your post #27)?

 

[Warp]

Yes: A number is rational if and only if its decimal representation has a recurring decimal (ie. an infinitely repeating pattern of digits).

In other words, if the decimal representation of a number has an infinitely repeating pattern of digits (even if this repeating pattern is just "0"), it is a rational number.

As a consequence, the decimal representation of an irrational never has a repeating pattern of digits.

Therefore, if it's not possible to list all the rational numbers in an order such that the diagonal of their decimal representation has an infinitely repeating sequence, that means that said diagonal always forms an irrational number, no matter how you rearrange the list of rational numbers.

 

[Office_Shredder]

Maybe the problem is this

The argument does not prove that there cannot be an enumeration of the rationals that has an infinite repeating decimal on the main diagonal. It only proves that if such an enumeration exists, it must be incomplete.

I think most people are using the word enumeration to mean a complete enumeration.

 

[PeterDonis]

A number is rational if and only if its decimal representation has a recurring decimal (ie. an infinitely repeating pattern of digits).

As you described it in the OP, a "recurring decimal" is a number like .0123456789..., i.e., it repeats starting with the first digit (talking only of digits after the decimal point, i.e., numbers between 0 and 1).

Not all rational numbers have that property. They all have the property that the decimal representation becomes repeating eventually, but they do not all have the property that the decimal representation starts repeating at the first digit.

 

[Office_Shredder]

If the diagonal is rational, then it starts repeating at some point down the list, and you can just flip the digits in the manner specified at that point. What you do for the first n digits of the number you're constructing doesn't matter.

 

[Warp]

Are you saying that my original argument does not prove that "no enumeration of all the rational numbers will form a rational number in its main diagonal" because rational numbers may have an arbitrarily large non-repeating string of digits before the recurring decimal part, and thus any "non-fitting" rationals could be placed at the beginning of the list, before the ones that participate in forming the recurring decimal of the diagonal?

I suppose there's a point there. Maybe the proof becomes complete when it's proven that there's an infinite amount of "non-fitting" rationals, and the beginning part of the decimal expansion of any rational number (ie. the part before the recurring decimal) is always finite? (It may be arbitrarily long, but always finite.)

 

[PeterDonis]

Are you saying that my original argument does not prove that "no enumeration of all the rational numbers will form a rational number in its main diagonal" because rational numbers may have an arbitrarily large non-repeating string of digits before the recurring decimal part, and thus any "non-fitting" rationals could be placed at the beginning of the list, before the ones that participate in forming the recurring decimal of the diagonal?

That was the sort of possibility I was thinking of, yes. However, I now realize that that objection is not valid.

The diagonalization process applied to any infinite sequence of infinite strings of digits will produce an infinite string of digits that cannot be in the sequence. That is always true. So if we have an infinite sequence of infinite strings of digits that we assume to include representations of all of the rational numbers (and such a sequence must exist because we know the rationals are countable), the diagonalization process applied to that sequence will have to give us an infinite string of digits that does not represent a rational number.

So now we can look at things in reverse, so to speak, and ask: given the infinite string of digits that we obtained from the diagonalization process as described above, which, as noted above, must represent an irrational number--call this string I--is it possible that the infinite string of digits on the main diagonal of the infinite sequence, the one we applied the "shift each digit by one, wrapping 9 to 0" algorithm to to obtain string I--call it string D--represented a rational number?

I think the answer to this question is no. Or, to put it another way, I think we can prove that applying any "digit shift" algorithm--i.e., an algorithm that shifts each digit the same way--to an infinite sequence of digits that represents a rational number, must result in an infinite sequence of digits that also represents a rational number. The proof seems simple, given that we know that any infinite string of digits that represents a rational number must eventually, after some finite number of digits, become an infinitely repeating string. And it seems obvious that applying any digit shift algorithm that shifts each digit the same way to an infinite string of digits that has this property, will produce another infinite string of digits that also has this property.

In other words, the set of infinite digit strings that represent rational numbers is closed under the "digit shift algorithm" operation. And that, I think, is sufficient to prove what you are saying, that any sequence of infinite digit strings that contains representations of all the rational numbers must have an infinite digit string that represents an irrational number on its main diagonal.

 

[Tendex]

Cantor's diagonalization schemes as is well known reveal the limitations of axiomatic set theory impredicativity involving infinite sets. Besides the inevitability of uncountable sets starting from countable infinite constructions(which is more frequently seen rather than as a limitation as an enrichment;"Cantor's transfinite paradise") it is used to prove Godel's incompleteness and the halting problem.