1
$\begingroup$

I was watching this video How An Infinite Hotel Ran Out Of Room, by Veritasium.

The video says that it is not possible to fit names made of infinite strings of $\{A,B\}$.

We know we can fit infinite people in the hotel, we also know that there solution that works and solution that don't work. For example if you have infinite buses with infinite people if we gave a room one bus at a time we would be full after the first bus, on the other hand if we make a matrix and translate the diagonal to a single line (as shown on the video) we can fit everyone.

Following this if we ignore the name and treat the set as a stack then you would fit all of them because it's then a infinite stack and we can use their hotel room number to identify them, would this not be a possible solution?

$\endgroup$
5
  • 1
    $\begingroup$ This question about set theory fits the scope of Mathematics. $\endgroup$ Jun 18 at 23:51
  • $\begingroup$ @Yuval Filmus interestingly I can't find anything about stacks or queue in mathematics, it's combination of both but since nothing on stacks seems to exist in mathematics I asked here $\endgroup$ Jun 18 at 23:56
  • 3
    $\begingroup$ That’s because your question has nothing to do with stacks and queues. It’s about elementary set theory, most of all about the definition of a countable set and Cantor’s diagonal argument. I’m sure you can find scores of questions about this topic on Mathematics. $\endgroup$ Jun 18 at 23:58
  • $\begingroup$ @YuvalFilmus if you have a stack based hotel where each room are stacked, hence you have to go from room $1$ to room $n$, you can fit another infinite stack onto this hotel including $\mathbb{R}$ is this then a different infinity or different data structure? $\endgroup$ Jun 19 at 15:29
  • $\begingroup$ I suggest reviewing a formal treatment of set-theoretic cardinality. It should answer all your questions. Stacks and queues won’t get mentioned. $\endgroup$ Jun 19 at 15:53
2
$\begingroup$

An (infinite) string is uniquely identified by a function $s:\mathbb{N}\rightarrow \{A,B\}$, such that $s(n)$ is the $n$'th character in the string.

The number of such functions is known to be: $|\{A,B\}|^{|\mathbb{N}|}=2^{\aleph_0}$.

Now, its also known that $2^{\aleph_0}>\aleph_0$, and hence there is no way to assign strings to hotel numbers, and more formally:

there is no one-to-one function between the set of all strings, (denoted $\{A,B\}^\omega$) and between $\mathbb{N}$.

$\endgroup$
16
  • $\begingroup$ if your doing $s(n)$ you are treating it as a list hence claiming countability I'm saying to treat it as a stack, which can store uncountable set and uses FILO method which does not rely on indexing $\endgroup$ Jun 18 at 17:17
  • 1
    $\begingroup$ There is no "stack", "list", or "FILO" notions being used here. A function is a function, its not a list, nor a stack. Also, I don't think you understood what $s(n)$ represents. $s$ is a function representing a single string, not multiple strings. $\mathbb{N}\rightarrow \{A,B\}$ is the set of all such functions, hence it represents the set of all infinite strings. $\endgroup$
    – nir shahar
    Jun 18 at 18:02
  • $\begingroup$ I see now $s(n)$ is a single string. What I was referring to as stack and list was the set of all values created by the function. While it is known that $2^{\aleph_0}>\aleph_0$ that is due to using a matrix, on my question I gave an example of solution that gives incorrect solution when trying to solve problem for "infinite buses with infinite people". If you do it one bus at a time you would have $|P(N)| > \aleph_0$, however if you construct a diagonal you have $|P(N)| = \aleph_0$ hence the answer depends on the method you use $\endgroup$ Jun 18 at 19:33
  • $\begingroup$ A infinite matrix is structure that can store a countable infinite set of a countable infinite set, the reason why it is countable is because you can get a specific value using the index, however the set is a uncountable set of countable infinite values. A stack/queue can store uncountable set of constable infinite, it is uncountable because you can not get a specific value by index without removing and adding each before it. This is why you can make it work using a stack but not using a infinite matrix, hence it is solvable if you use the right method $\endgroup$ Jun 18 at 19:44
  • 1
    $\begingroup$ Showing $a>b$ for $a=|A|, b=|B|$ means showing that $a\ge b$, and also showing that $a\neq b$. To show $a\neq b$ you have to show there doesnt exist an invertible mapping between $A$ and $B$. Showing for a specific function that it isn't invertible isn't good enough. $\endgroup$
    – nir shahar
    Jun 18 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.