Murder at Hilbert's Hotel!

Question

I'm sorry if this is a duplicate in any way. I doubt it's an original question. Due to my ignorance, it's difficult for me to search for appropriate things.

Motivation.

This question is inspired by Exercise 1.2.16 of these logic notes by S. G. Simpson. Here is a shortened version of that exercise for convenience.

Brown, Jones, and Smith are suspected of a crime. They testify as follows:

Brown: Jones is guilty and Smith is innocent.

Jones: If Brown is guilty then so is Smith.

Smith: I’m innocent, but at least one of the others is guilty.

a) Are the three testimonies consistent?

b) The testimony of one of the suspects follows from that of another. Which from which?

c) Assuming everybody is innocent, who committed perjury?

d) Assuming all testimony is true, who is innocent and who is guilty?

e) Assuming that the innocent told the truth and the guilty told lies, who is innocent and who is guilty?

I like to challenge friends and family with similar problems. It's fun to make up scenarios and the solutions are fairly easy to those familiar with basic mathematical logic. I can vary the testimonies, the number of suspects, the questions about the testimonies, etc.; it's good stuff.

Lately, though, I've wondered what it would mean to have (at least countably) infinitely many suspects. To make the problem tractable the testimonies would need some sort of defining rule and the questions ought to address appropriate groups of suspects.

The Question.

With this in mind, here's my scenario.

On the morning of the first night at Hilbert's hotel, when all the rooms were taken, the receptionist was found dead at his desk; it looked extremely suspicious. Was he murdered? The police interviewed all the tenants and staff, and concluded that the staff couldn't possibly have been involved in the death. However, the tenants had some interesting testimonies which amounted to the following.

$[\dots ]$

Okay, so I've given this some thought and I suspect that the original set up is at least similar to letting $$\begin{align} \text{Brown}&\mapsto [1]_3:=\{n\in\mathbb{N}\mid n\cong 1\pmod{3}\}, \\ \text{Jones}&\mapsto [2]_3, \\ \text{Smith}&\mapsto [3]_3, \end{align}$$ where each number $n$ represents the tenant in Room $n$, then changing the testimonies accordingly. (I'll leave that as an exercise for the reader (ha!): this is too long already.)

Immediately, I'm reminded of the notion of presentations and freeness. The above smells like a presentation (or perhaps some kind of homomorphism). I suppose my main bunch of questions here are:

What is this thing? What's a better, more formal way of describing the mathematics behind this scenario? What similar things have been done before?

The reason why I included the (number-theory) tag is that I'm curious now as to what number theoretic problems, if any, can be phrased this way. (Does that make any sense?)

Thoughts and Clarification.

This is based on the comments.

It's more about the maps between the infinite and finite cases.

A thorough answer would include a mathematical description of what the infinite case is, a mathematical description of how the infinite case relates to finite cases, details on what similar things have been done before, and perhaps a number-theoretic problem phrased using the above.

One has to take into account negations in the infinite case in such a way that the structure of the given finite case is preserved.

I suspect that they're just different models of the same theory, where the infinite case is in some sense "free"; that maps like the one given above are somehow related to the notion of a presentation; and that at least some trivial Number Theory problems can be stated this way.

:)

Answer 1

Well, let's look at the structure of the problem:

There is a set $S$ of suspects (three in the original problem, a countably infinite number of them in Hilbert's hotel).

There's a subset $G\subset S$ of guilty suspects.

And there's a mapping $f:S\to P(S)$ where $P(S)$ is the power set (set of subsets) of $S$, where $M\in f(s)$ means "If $s$ says the truth, it is possible that $G=M$". $f(s)$ is specified by a logical form $L_s$, that is, $f(s) = \{M\in P(S): L_s(M)\}$.

Now we can formulate the separate questions as follows:

a) Is $\bigcap_{s\in S} f(s) \ne \emptyset$?

b) For which pairs $(s,t)\in S\times S$ do we have $f(s)\subseteq f(t)$?

c) Assuming $G=\emptyset$, what is $\{s\in S: G\notin f(s)\}$?

d) What is $\bigcap_{s\in S} f(s)$? (Actually, the question as formulated already presumes that this set has exactly one element; especially it assumes that the answer to (a) is "yes").

e) What is $\bigcap_{s\in G} (P(S)\setminus f(s)) \cap \bigcup_{s\in S\setminus G} f(s)$?

So to generalize the problem to Hilbert's hotel, you have to find a function $f(n)$ specified by a logical formula dependent on $n$ such that $\bigcap_{s\in n} f(n)$ has exactly one element, and (to be a generalization of the original problem) reduces to the original problem when restricted to the set $\{0,1,2\}$

Let's look closer at the original testimonies:

• Brown gives an explicit list of who's guilty or innocent.
• Jones gives an implication connecting the other two.
• Smith makes a testimony about himself, and the claim that someone is guilty.

Associating $0$ with Brown, $1$ with Jones and $2$ with Smith, we could write those as follows in the formalism derived above, with $S=\{1,2,3\}$ $$\begin{align} f(0) &= \{M\in P(S): 1 \in M \land 2\notin M\}\\ f(1) &= \{M\in P(S): 0 \in M \implies 2\in M\}\\ f(2) &= \{M\in P(S): 2 \notin S \land M\ne\emptyset\} \end{align}$$

There are of course many ways to generalize that, but let's try the following: $$f(n) = \begin{cases} \{M\in P(\mathbb N): \forall m > n, m\in M\iff m \equiv 1\ (\mod 2)\} & n \equiv 0\ (\mod 3)\\ \{M\in P(\mathbb N): \forall i < n, \forall k > n, m\in M\implies k\in M\} & n \equiv 1\ (\mod 3)\\ \{M\in P(\mathbb N): n\notin M\land M\ne\emptyset\} & n\equiv 2\ (\mod 3) \end{cases}$$ However this gives an inconsistent set of conditions (i.e. $\bigcup_{n\in\mathbb N} f(n)=\emptyset$), since from $f(0)$, one concludes $5\in G$, but from $f(5)$ one concludes $5\notin G$. This is a deviation from the original problem where the statements are indeed consistent.

I'm not going to spend the time to actually find a proper generalization now (I already spent far more time on this answer than originally planned), but I think the mathematical concepts involved should now be clear.

Answer 2

It sounds to me like you are asking about Infinitary logic. I've pondered this idea myself a fair bit. For instance, we can make sense of the 'limit object' of this sequence $$ a_1 \wedge a_2, (a_1 \wedge a_2) \wedge a_3, (((a_1 \wedge a_2) \wedge a_3) \wedge a_4$$ where $\wedge $ denotes logical and. In this case the limit object has a value of true if and only if every $ a_n $ is true, otherwise it is false. But what if we replace those and's with logical implication, $\Rightarrow $?

Answer 3

I don't think this question really has anything to do with infinity or number theory.

Stripped of all the flavor text, you have three sentences about three logical statements:

1. J and not S

2. If B then S

3. (Not S) and (J or B)

You could replace J,B,S with any sort of logical statement, such as "Jones is guilty" or "It will rain on Thursday" or "The snark is a boojum" or "Every hotel guest with a room number divisible by three is guilty". They can involve finite sets, or infinite sets, or mythical creatures, or weather. It doesn't affect the logic of the puzzle in any way.