29
$\begingroup$

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.

:)

$\endgroup$
  • $\begingroup$ Hilbert's Hotel only has countably infinite rooms. It doesn't have countably infinite guests (or if it does have countably infinite guests, then it has countably infinite staff and countably infinite recepitionists). Consequently, you'll only have a finite number of suspects. If it were the case that we had countably infinite suspects and thus countably infinite testimonies, we'd have countably infinite statements which are not substitution instances of each other. Thus, the consistency problem would not come as solvable. We couldn't determine if the testimonies were consistent. $\endgroup$ – Doug Spoonwood Oct 16 '14 at 17:49
  • $\begingroup$ And if we had countably infinite guests... even with murder as a very, very, very, very rare event, wouldn't we also have countably infinite murders going on also? $\endgroup$ – Doug Spoonwood Oct 16 '14 at 17:51
  • 15
    $\begingroup$ @Doug: "On the morning of the first night at Hilbert's hotel, when all the rooms were taken", if there are infinitely many rooms and all of them are taken, then there are infinitely many suspects. And you might notice that of all the natural numbers, there is exactly one of them which is $0$. Despite it being a very rare property, it's still true for exactly one element. $\endgroup$ – Asaf Karagila Oct 16 '14 at 20:10
  • $\begingroup$ The only 2 ways of solving this are deducting information using 2 or more hints, and using trial and error. $\endgroup$ – ghosts_in_the_code Nov 7 '14 at 12:49
  • 1
    $\begingroup$ @Shaun Is the phenomenon you are interested in the observation that any finite murder problem can be phrased as a murder in the Hilbert hotel? $\endgroup$ – Lord_Farin Feb 14 '15 at 11:40
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (I'm not sure I understand the details of this yet, so I'll revoke the acceptance until I do. This is a busy time for me though! Sorry!) $\endgroup$ – Shaun Apr 27 '15 at 20:14
1
$\begingroup$

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 $?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I don't think this really answers the question. It's not so much the logic of the original puzzle I'm interested in. It's more about the maps between the infinite and finite cases. I suspect that they're just different models of the same theory, where the infinite case is in some sense "free"; that the map given above is somehow related to the notion of a presentation; and that at least some trivial Number Theory problems can be stated this way. How difficult can the latter be? Try replacing guilty/innocent with "is (not) divisible by $3$", for instance, then fiddling with the testimonies. $\endgroup$ – Shaun Nov 7 '14 at 21:33
  • $\begingroup$ Then I guess I don't understand why the puzzle is there at all. I'm afraid I'm having trouble extracting anything specific from your question besides "here is a logic puzzle" and "tell me some things about infinite groups" (which is extremely vague), and I don't see the connection between them. Sorry. $\endgroup$ – Nate Eldredge Nov 7 '14 at 21:38
  • $\begingroup$ It's a necessary motivating example. I needed to put it there to talk about an infinite case that deliberately has the same logical structure as a finite case, so that I can ask questions about "the" infinite case being able to imitate other finite cases. And I do ask for a better way of describing this mathematically. If I knew of a better way, then I'd probably be able to answer this question myself. $\endgroup$ – Shaun Nov 7 '14 at 21:46
  • $\begingroup$ And I don't say anything about infinite groups. $\endgroup$ – Shaun Nov 7 '14 at 21:52
  • $\begingroup$ I'm sorry about the tone of my comments. Naturally, I rushed to defend my question before any negative consequences could ensue. It didn't leave me much time to keep my emotions in check. Your criticisms are helpful and much appreciated :) $\endgroup$ – Shaun Nov 7 '14 at 22:16

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.