## Hilbert's Hotel and Cantor's Diagonal Argument

Discussions concerned with knowledge of measurement, properties, and relations quantities, theoretical or applied.

### Hilbert's Hotel and Cantor's Diagonal Argument

Hilbert's Hotel can accommodate any number of extra guests, even when full, because the additional guests do not increase the cardinality of the infinity of existing guests. However, Cantor argues that an array of infinite rows of digits cannot accommodate a diagonally altered string of digits, because the inclusion of the altered string increases the cardinality.

Now, suppose that Cantor's horizontal rows represent the ID numbers of the existing guests in Hilbert's Hotel, and the altered diagonal represents the ID number of a would-be additional guest. Can the would-be guest be admitted to the hotel? If not, can he/she get in by the simple expedient of changing his/her ID number to one of Cantor's horizontal numbers (or to an unaltered diagonal)?

(I presume that if we can postulate an infinite hotel and infinite rows of Cantorian digits, there is no problem about having infinitely long ID numbers.)
Positor
Active Member

Posts: 1115
Joined: 05 Feb 2010
 Lomax liked this post

### Re: Hilbert's Hotel and Cantor's Diagonal Argument

This question has vexed me too. I'm not posting now because I think I can answer it, but in the hope that by making a current comment, someone who missed the original post might be tempted to get involved and keep this interesting discussion going.

I'm not sure that the objection is really "because the inclusion of the altered string increases the cardinality". As I understand it, the diagonally-modified number cannot serve as a guest number because it already belongs to the 'power set' of those numbers. It belongs on a different logical level. It is generated according to an algorithm which assumes that the original set is complete, and so, to include it in the original set would involve a circularity or logical contradiction.

Alan Masterman
Member

Posts: 53
Joined: 04 Mar 2012

### Re: Hilbert's Hotel and Cantor's Diagonal Argument

This question has vexed me too. I'm not posting now because I think I can answer it, but in the hope that by making a current comment, someone who missed the original post might be tempted to get involved and keep this interesting discussion going.

I'm not sure that the objection is really "because the inclusion of the altered string increases the cardinality". As I understand it, the diagonally-modified number cannot serve as a guest number because it already belongs to the 'power set' of those numbers. It belongs on a different logical level. It is generated according to an algorithm which assumes that the original set is complete, and so, to include it in the original set would involve a circularity or logical contradiction.

Alan Masterman
Member

Posts: 53
Joined: 04 Mar 2012

### Re: Hilbert's Hotel and Cantor's Diagonal Argument

Sorry, can't see how to delete a post accidentally duplicated...
Alan Masterman
Member

Posts: 53
Joined: 04 Mar 2012

### Re: Hilbert's Hotel and Cantor's Diagonal Argument

Positor » February 2nd, 2016, 8:36 pm wrote:Hilbert's Hotel can accommodate any number of extra guests, even when full, because the additional guests do not increase the cardinality of the infinity of existing guests. However, Cantor argues that an array of infinite rows of digits cannot accommodate a diagonally altered string of digits, because the inclusion of the altered string increases the cardinality.

Now, suppose that Cantor's horizontal rows represent the ID numbers of the existing guests in Hilbert's Hotel, and the altered diagonal represents the ID number of a would-be additional guest. Can the would-be guest be admitted to the hotel? If not, can he/she get in by the simple expedient of changing his/her ID number to one of Cantor's horizontal numbers (or to an unaltered diagonal)?

(I presume that if we can postulate an infinite hotel and infinite rows of Cantorian digits, there is no problem about having infinitely long ID numbers.)

Thanks Alan for bumping this up. It's easily answered.

Of course Cantor's diagonal argument doesn't say that the anti-diagonal can't be added to the list. It can, via the standard Hilbert trick. All Cantor says is that the anti-diagonal can't possibly already be on the list, and that's the case here.

So you take the anti-diagonal, which is not on the list, and you move each number in a given row of the array up one row. The number (or guest) in row 1 goes to row 2; the number in row 2 goes to row 3, etc. This leaves row 1 empty, and you put the anti-diagonal there.

Now Cantor points out that there's a new anti-diagonal, which isn't on the list, but that can be put on the list.

The point of Cantor's clever argument is that the original list of reals was arbitrary. We can conclude that given any list whatsoever, there's some real -- namely the anti-diagonal -- that's not on the list. So the original list was not complete. And since it was an arbitrary list of reals, we conclude that no list of reals can contain all the reals.

Note by the way that this is NOT a reductio or proof by contradiction. On the contrary. We start with an arbitrary list and show it's not complete.
someguy1
Member

Posts: 753
Joined: 08 Nov 2013

### Re: Hilbert's Hotel and Cantor's Diagonal Argument

While I'm on the subject, let me clarify a couple of points in the OP.

Positor » February 2nd, 2016, 8:36 pm wrote:Hilbert's Hotel can accommodate any number of extra guests, even when full, because the additional guests do not increase the cardinality of the infinity of existing guests.

The missing qualifier is that Hilbert's hotel can accommodate any countable number of additional guests.

Positor » February 2nd, 2016, 8:36 pm wrote:However, Cantor argues that an array of infinite rows of digits cannot accommodate a diagonally altered string of digits, because the inclusion of the altered string increases the cardinality.

No that's not true. Cantor's diagonal proof shows that any list (defined as a function from the natural numbers to the reals) can not contain all the reals. If we take the missing real and add it to the list (via Hilbert's shifting trick) we'll have a new list, which likewise cannot include all the reals.

In passing I'll mention a curiosity in set theory called an amorphous set. An amorphous set is an infinite set that is not the disjoint union of two infinite subsets. An amorphous set can not be Dedekind-infinite. That means that even though it is not in bijection with any finite natural number; it is also NOT in bijection with any of its proper subsets.

Such a strange set can only exist in the absence of the Axiom of Choice. If X is an amorphous set and you add a single element to it, then the new set must have strictly larger cardinality! If not, it would be in bijection with one of its proper subsets, namely X.

The existence of amorphous sets is ruled out by the Axiom of Choice. In fact one of the strongest arguments for accepting Choice is to eliminate these kinds of misbehaving infinite sets.
someguy1
Member

Posts: 753
Joined: 08 Nov 2013
 Positor liked this post