# Seeming contradiction of the tertium non datur principle through a logic problem

The problem is as follows.

There is a group of three people (A,B,C) who are perfect logicians, and A is a thief. We say that a person recognises another one if the former knows whether the latter is a thief or not. Every logician knows that ther is only one thief in the group and that the others are perfect logicians as well. Moreover every logician can ask another one if the latter recognices the other two, and the answer will always be sincere (yet they cannot know if the other logicians have already asked questions because, say, they are in different rooms and they communicate through sms).

Eg. If B knows that A is a thief then he also knows that C is not (from the first rule), and furthermore, now A and C know that B has recognised A and C.

Now, A, being the thief, surely knows that B and C are not thief. So B and C know that A has recognised B and C.

The question is: if one person recognises everyone, can we infer that this person is a thief?

Well, if we can, then B would recognise A and C but then C would infer that B is a thief, a contradiction. Yet, if we cannot, the only person who could recognise everyone else would be the thief so you could actually infer that this person is a thief, another contradiction.

Does this contradiction imply that we can't say if the statement "A recognises B and C" implies "A is a thief"?

This problem reminds me of Russel's paradox but that paradox is somewhat solvable saying that the premises are impossible, but in this case the premises seem very plausible. I would also note that, knowing that the others are perfect logicians like himself, A,B and C would know that the other ones would come to the same conclusions, given the same premises.

I hope I was clear enough.

• There has to be a sequence to the deductions. That is to say, $A$ must somehow reveal that he has recognized $B,C$ and only then can subsequent deductions be made. You could formalize this by saying something like "each hour on the hour everyone gets in a room an simultaneously holds up a sign saying whom they have recognized." under this scheme, only $A$ announces anything on the first hour, but all three do at the second. – lulu Jan 20 '18 at 12:55
• That's a good point but suppose they're all in different rooms and as before they can ask (by an sms for example) that question to one person at a time, in this case they wouldn't know if someone else had already asked any question, what would happen then? – Lucio Tanzini Jan 20 '18 at 16:54
• Then $B,C$ would have no basis for making any deductions at all. – lulu Jan 20 '18 at 16:59
• So WE can say that they can't make any deduction but they could never conclide that they can't make any deduction, as otherwise they would deduce that the only one who recognices the other two is the thief. Does that make sense? – Lucio Tanzini Jan 20 '18 at 18:06
• After some thought I also see some connections with the Halting problem – Lucio Tanzini Jan 20 '18 at 18:08

There does indeed appear to be some form of paradox here, but it is very subtle.

To be completely clear, I'm assuming the game proceeds in rounds. In each round, a neutral umpire randomly chooses one of the players and directs him to tell another random player whether he knows yet who the thief is. The recipient of that information then immediately makes all the inferences he can from this knowledge before the next round. The third player, who was not party to the communication does not know what was said and does not even know a round took place.

First off, a few simple facts: If you know you're innocent, and you hear anyone else say they don't know who the thief is, then by elimination you now know that the third person is the thief. Therefore if you ever tell anybody "I don't know", the only thing they can subsequently tell you is "I know who it is". So that won't make you any wiser.

(1) If you know you are innocent and the first thing that happens to you in the game is that someone tells you "I know who the thief is", can you conclude anything?

Of course it is possible that the person who spoke to you is the thief, so the real question is whether it is possible that he is innocent. A priori it sounds conceivable that the two other guys may have communicated without you noticing, such that the innocent among them now knows.

However, how could that communication go? One of them must have spoken first. If the innocent one spoke first, then (as argued above) he will never get any information out of the thief that's useful to him, so he will not end up knowing.

On the other hand, if the thief spoke first, then the innocent guy would have found himself in exactly the situation described by (1) above. And now we're in trouble:

If the correct answer to (1) is "yes", then it is possible that the other innocent guy learned from the thief who the thief was, and therefore you can subsequently be told by either the thief or the other guy that they know. Therefore the correct answer to (1) is "no".

On the other hand, if the correct answer to (1) is "no", then there is no way the other innocent guy could ever know who the thief is, as long as you haven't communicated with either of them. And therefore if one of them admits to knowing, they must be the thief. So the correct answer to (1) is "yes".

Thus, the answer to (1) can be neither "yes" nor "no". A paradox!

I think the resolution to this is that this reasoning depends critically on the assumption that nobody ever knows whether the first communication they are part of is the first round of the game or not. That's a critical part of the argument that the answer to (1) depends on a previous answer to the same question.

On the other hand if somebody knows it's the very first round of the game when someone tells them "I know who it is", then they can comfortably conclude that they must be the thief.

And contrariwise, therefore, if somebody knows it's the second round of the game when they're told that, then they know they can't conclude anything.

So really what enables the paradox is the assumption that time is continuous (or at least dense): no matter how quickly after the game starts we get a message, it is in principle possible that the two other guys may already have talked.

Thus, we might categorize the paradox as a time-reversed cousin of the surprise exam paradox.

Further, I suspect that trying to formalize the paradox (in some appropriate variant of temporal+epistemic logic) will run into trouble with expressing the assumption that everyone are perfect logicians, and everyone knows that everyone else are perfect logicians, and everyone knows that too, et cetera ad infinitum. Even defining what "perfect logic" should mean seems to require a powerful enough reasoning system that Gödelian incompleteness kicks in and tells us that in that case there is no such thing as a perfect logician, at least not one that can be reasoned about.