# Last in line at Diogenes's

Infinitely many (ℵo) philosophers came to Diogenes's Roadhouse for a night of unbridled belaboring. $\require{begingroup} \begingroup \def \F {{ \sf\scriptsize F }} \def \MiniCap #1{{ \sf\scriptsize #1 }} \def \T {{ \sf\small T }} \def \L #1{{ \rm\small\bf #1 }} \def \S {{ \rm\small S }} \def \O #1{{ \raise6mu\strut \rlap{#1} \kern 21mu }} \def \B {{ \O { \LARGE \raise-1mu \cdot } \kern -6mu }} \def \P {{ \tiny\kern1.5mu \raise5mu ' \kern-2mu }} \def \Check { \llap{\color{black}{ \Large\raise-3mu\unicode{x1F5F8} }}} \def \Box { \raise-5mu\strut \raise4mu\strut \raise-4mu{ \Large\square }} \def \DotStack {{\Large\substack{\kern24mu\\[-1mu] . \\[3mu] . \\[3mu] . }}} \def \TallyDotsF { \raise-2mu\DotStack \qquad & & \rlap\DotStack \\[-2mu] } \def \TallyDots { \raise-2mu\DotStack \qquad & & \DotStack \\[-2mu] } \def \TallySheet #1#2#3{ \small \def \TallyRow ##1##2##3##4##5{ \kern-15mu \sf \MiniCap ##1#1 \kern-4mu : & \sf \unicode{x201c} \kern 3mu \color{black}{ \MiniCap #2. } \kern -3mu \unicode{x201d} \kern32mu & \sf \kern-1mu \llap { \T \kern 3mu } \Box{##2} \kern6mu \Box{##3} \rlap{ \kern5mu \F } & \kern32mu \sf \color{black}{##4} {\scriptsize\text{##5}} \\[-9mu] } \color{darkgreen}{ \begin{array}{rrcl} #3 \end{array} } }$
$\O{\L{ a. }}$ Approaching the door sequentially, each philosopher must provide a valid assertion (that is, utter a true sentence, the occurrence of which is denoted by $\T$).
$\O{\L{ b. }}$ Before that $\T$, the philosopher may utter any number of false assertions (each time denoted by $\F$). If these aren't followed by a $\T$, no more philosophers will even get to the door.

All assertions will be checked by Zeno the bouncer. Any assertions not pertinent to conditions $\L{ a }$ and $\L{ b }$, as with much else in philosophy, will be disregarded. The lamp at the door is dim, so the philosophers will be indistinguishable from each other as they approach in an effectively indeterminable order.

Hoping to seat everyone in time for the presentation of Professor Morris's Equine & Canine Paradox, Zeno streamlines the procedure.
$\B \kern-1mu$ Every assertion will be exactly the same sentence, $\S$, chosen beforehand by the philosophers.
$\B$ It must be possible for Zeno to successfully assess each utterance of $\S$ as being $\T$ or $\F$ without any contradiction among assessed values. If more than one combination of assessments is possible, there is no way to predict which combination will be chosen.
$\B$ All assessments are made at the outset, and they actually predetermine how many assertions are attributed to each philosopher as well as how infinities are arranged (for lack of a better link) within the line to the door.

(For example, $\S$ might be: $\sf\small This~\S~is~the~first~\T \,$ [that is, this assertion is true and all preceding assertions are false]. At most one such utterance could be $\T$, because two $\T$s would contradict each other's claim to be the first. But having even one $\T$ is not guaranteed because Zeno could assess every $\S$ in this example as being $\F$, whereby only one philosopher would get to the door at all.)

Thus the philosophers decide on an (empirically suboptimal) $\S$, evidenced by Zeno's tally sheet.

$~~~~ \TallySheet { ~philosopher~says } {\S} { \TallyRow{ First } {} {\Check} {}{} \TallyRow{ First } {\Check} {} {}{} \TallyRow{ Second \raise12mu\strut } {} {\Check} {}{} \TallyRow{ Second } {\Check} {} {(alternating~\F s~and~\T s)}{} \TallyDots \TallyRow{ Next~to~last } {} {\Check} {}{} \TallyRow{ Next~to~last } {\Check} {} {}{} \TallyRow{ Last \raise14mu\strut } {} {\Check} {}{} \TallyRow{ Last } {} {\Check} {(infinitely~many~\F s)}{} \TallyDotsF \TallyRow{ Last } {} {\Check} {}{} \TallyRow{ Last } {\Check} {} {(\T~ at~last!)}{} }$

Everyone will be admitted after asserting one $\F$ and one $\T$, except for the long-suffering last philosopher, who will be assessed infinitely many $\F$s before the final $\T$. The philosophers' chosen $\S$, in fact, allows for no other way to assess $\T$s and $\F$s than is shown in this tally sheet.

What $\rm\small\bf~ S ~$ would cause this result?

(No need to mention another $\S$ that would cause a better result. Save it for an upcoming Happy Hour at the roadhouse.)
Somewhat related
Infinite choice question
How to become president of the United States of America
Term for an infinite sequence with both a beginning and an end $\endgroup$

• I'm trying to figure out the order-type of this thing. We have infinitely many philosophers but there are first, second, next-to-last and last: is this $\omega+(-\omega)$? (I hope my notation is comprehensible.) But then the last one asks infinitely many questions also including a first and a last -- so the sequence of questions is something like $\omega+(-\omega)+\omega+(-\omega)$? (First two terms for the non-last philosophers, remaining two for the last one.) – Gareth McCaughan Jun 24 '16 at 10:46
• Does Zeno have to make his assessment incrementally, deciding the truth value of each assertion immediately once it's made, or does he somehow wait for everyone to make theirs and then judge? – Gareth McCaughan Jun 24 '16 at 10:48
• I'm not sure you actually answered either of my questions, but never mind. Here's another: although Zeno can't distinguish one philosopher from another, can he tell when a new one arrives or leaves? I guess he can, since they leave as he admits them; is that right? – Gareth McCaughan Jun 24 '16 at 10:59
• Oh, but wait, that's not quite sufficient, because I want to know whether Zeno knows (e.g.) whether a given assertion he's assessing is or isn't the first one offered by the philosopher now standing in front of him. – Gareth McCaughan Jun 24 '16 at 11:01
• But there is a pattern -- in the ordering. Consider the following two collections of infinitely many S's: (1) "S, S, S, ...". (2) "..., S, S, S". They are not the same even though each consists of countably many copies of S. – Gareth McCaughan Jun 24 '16 at 12:14

The philosophers could all say:

This is not my first attempt at getting in; and it is my last attempt if and only if either I am not the last philosopher or this is the last assertion any of us makes.

... Except that some clarification humn just offered in comments to the question looks like it makes this not work. So try the following instead:

If I am not the last philosopher to appear, then this is my second attempt at getting in; if I am the last philosopher to appear, then I have already made infinitely many attempts.

I'm not entirely convinced that the question really makes sense, though. I mean, saying that "Zeno's assessment determines when it's the next philosopher's turn" seems like it describes the following setup: a philosopher makes an assertion, Zeno assesses it, and if he calls it false then the whole process repeats. But that can't produce any order-type that isn't an initial segment of $\omega$. So maybe we say: If he calls infinitely many of them false, then the philosopher gets to start again. Suitably generalized, this lets us produce any ordinal order-type -- i.e., any well-ordered series of assertions -- but what humn has given us isn't well-ordered. So perhaps the idea is that each philosopher precommits to a certain ordered set of assertions, and then Zeno picks where (if at all) to declare one of them true? But that requires Zeno to know ahead of time what the assertions will be. Is he meant to know that? Maybe he is.

So is the setup the following?

• Philosophers precommit to an assertion $S$, a countable total ordering $O$ determining how they will appear, and total orderings $O_k$ for each philosopher determining how they will make their assertions as long as Zeno keeps judging them false.
• Now Zeno picks at most one element of each $O_k$ to be the first (and therefore only) assertion from philosopher $k$ that he will assess as true. He does so in such a way that all the assertions' truth values match their assertions. (If he can't, the philosophers lose.)

We're looking for $(S,O,(O_k))$ for which there is exactly one way for Zeno to make these assessments, and which has the property that he does assess one assertion as true for each philosopher.

If that's the setup, then I think my second proposal above works, but we need to make it explicit that

the last philosopher's $O_k$ does in fact have a last element: if Zeno had reckoned his last assertion false then he would have given up, and Zeno knows this.

There's a bit of extra subtlety to be navigated. My proposal above doesn't uniquely identify an element of the last philosopher's $O_k$, though any way of choosing the element yields isomorphic results so it's not clear how real the distinction is. So, if we formalize the procedure according to my description above, we had better tweak my solution once more so that $S$ says:

If I am not the last philosopher to appear, then this is my second attempt at getting in; if I am the last philosopher to appear, then this is the last attempt I was prepared to make.

where that last clause is implicitly referring to that philosopher's (known-to-Zeno) $O_k$.

• Thank you for helping to clarify the puzzle. I will edit the statement to include something like: The philosophers are checked sequentially and the tally sheet shows the only possible ordering for valid assessment of every $\rm\small S$. – humn Jun 24 '16 at 18:18
• I like (understand) the evolving solution more and more but don't (yet) see how it precludes something like $~ \small O = (-\omega) + \omega ~$. Your depiction of the tally sheet as $~ \small \omega + (-\omega) + \omega + (-\omega) ~$ exactly matches my intent. (Still learning the notation, by the way, and also have some lingering uncertainty about holes in the puzzle statement.) Seeing a solution develop and a puzzle improve does, once again, add to the instructive element of this site. Good for the soul. – humn Jun 24 '16 at 21:13
• I took it that $O=\omega+(-\omega)+\omega+(-\omega)$ was part of what the philosophers agreed at the outset. – Gareth McCaughan Jun 24 '16 at 22:22
• The present $\small\sf S$ looks perfectly efficient if there is guaranteed to be a first and last philosopher but it also allows for consistent assessment of a beginningless and endless ...-F-T-F-T-F-... The puzzle never stated that having a last philosopher is given, though by now the added mention of "how infinities are arranged" tries to be more clear about that, thanks to your initial answer and earlier comments. The statement did at one point mention "the" first philosopher in the example, which was careless writing. – humn Jun 30 '16 at 17:03
• Then I think I once again don't understand the setup. The philosophers submit, what?, just a total order and a map from it to assertions (or maybe just the total order and a single assertion), and then Zeno assesses all the assertions and we pair off philosophers with "true" assessments? But in general this doesn't actually enable us to tell whether all the philosophers get in, because there may be multiple ways to do that pairing. Nor does it tell us which ones get in if not all do. And you can't just say "keep them in the same order" because [...continues] – Gareth McCaughan Jun 30 '16 at 17:28

It assumes that the order type of both the philosophers and the statements is $\omega+1$, so there isn't actually a next-to-last philosopher or statement.
• You have discovered what would have made a better-distilled (and, speaking absurdly, not quite as realistic) puzzle but the $~ \small \omega+(-\omega)+\omega+(-\omega) ~$ ordering shown in the tally sheet is, alas, part of the statement, now perhaps clarified – humn Jun 24 '16 at 19:54