Let's say we've got the following model:
There is a set of people $A_1,...,A_n$ That is split into two groups: Those who always say the truth, and those who always lie.

Now, every person in this set makes a statement about some other people of the set, e.g. $A_1$ might say "$A_3$ and $A_4$ are liars, and $A_5$ is a truth-teller".

The theorem I've deduced (and of which I am asking whether it's correct):
No matter what statements we're given, for any person the guess whether he's a liar or truth-teller never will be better than pure chance.

Sketch: We'll model the statements as a formula in propositional logic, then deduce all models and show that there's equally many models in which a person $A$ is a truth-teller as there are models where $A$ is a liar.


Let's say a person $A$ says that $B_1,...,B_n$ are truth-tellers and $C_1,..,C_n$ are liars.
Then there's two possibilities:

  1. $A$ is a truth-teller. Then the statements are all true.
  2. $A$ is a liar. Then the statements are all false.

Let's say the predicate $T(\cdot)$ stands for being a truth-teller, so that $T(A)$ is true iff $A$ is a truth-teller. Then we can build up the formula

$$\,\bigg(T(A) \land T(B_1)\land ... \land T(B_n) \land\lnot T(C_1)\land ...\land\lnot T(C_n)\bigg) \lor\bigg(\lnot T(A) \land \lnot T(B_1)\land ... \land \lnot T(B_n) \land T(C_1)\land ...\land T(C_n)\bigg) $$ for person $A$, and for each other person another one that will look like this.

The whole formula then is the conjunction ($\land$) of all formulas like above for every person in the set.

Now let's say $v$ is a model of our formula. Then for every formula like the above one, either the left side of the disjunction or the right side of the disjunction has to be true.
Let's say wlog the left side is true.

Then, if we construct the interpretation $v'$ by inverting every assigment (i.e. $v'(A):= \lnot v(T(A)) $ ), in above formula now the right side is true.

Therefore, we've got for every model where $A$ is a truth-teller a dual one where $A$ is a liar, and thus, any deduction we make can never be better than pure chance.

My question is: Is my proof correct? Is my deduction correct? It feels wrong that all this information amounts to nothing.

  • $\begingroup$ If $A_1$ says "$A_1$ and $A_2$ are liars", then you can deduce that $A_1$ is a liar and $A_2$ is a truth-teller. Are you disallowing self-reference ("a statement about some other people")? $\endgroup$
    – SCappella
    Aug 3, 2018 at 7:59
  • $\begingroup$ @User Your version would go against my model - a liar would never say "I'm a liar". Both truth-teller and liar both will always say "I'm a truth-teller". So, self reference wouldn't change the propositional formula (you'd add to the first disjunction $T(A)$, which is already there) $\endgroup$
    – Sudix
    Aug 3, 2018 at 10:52
  • $\begingroup$ @Sudix: A liar can say "I and that other guy are both liars", if (and only if) the other guy is a truth teller -- because then the entire claim would be a genuine lie. Note that this is different from saying "I am a liar" and "that other guy is a liar" separately. $\endgroup$ Aug 3, 2018 at 13:26
  • $\begingroup$ @HenningMakholm That's what I'm stumbling about here... I kinda meant the whole question that "a liar always lies means" any statement from a liar is solely made up from statements that are lies. $\endgroup$
    – Sudix
    Aug 3, 2018 at 13:30
  • $\begingroup$ @Sudix: So a "liar" in your definition is unable to utter the words "it is not true that ..." -- because no matter what the "...", either that or his entire statement would fail to be a lie? $\endgroup$ Aug 3, 2018 at 13:32

2 Answers 2


In your model where nobody can make (meaningful) compound statements, what you observe is:

  • $A$ will say "$B$ is a liar" if and only if $A$ and $B$ belong to different groups.

  • $A$ will say "$B$ is a truth teller" if and only if $A$ and $B$ belong to the same group.

Then nothing you hear will differ if everyone switch side all at once.

That doesn't mean you learn nothing from all the information. You will be able to reconstruct what the two groups are, just not which of them is the liars and which is the truth tellers.

In other words, hearing everyone's evidence will narrow the $2^n$ possible distributions of liars and truth tellers down to $2$ -- that's hardly "nothing".


I think you are right to say that it can't be that all this information comes to nothing.

So you do seem to be disallowing self reference as you say that every person makes statements about other people.

So how about this? A says that B always tells the truth. This means that they are either both truth tellers or both liars, so they are equivalent. Then, as described in the first comment, B says that A and C are both liars.

If B tells the truth then A is a liar and this means that B is a liar (because A said that B always tells the truth).

So B cannot be telling the truth which means he must be a liar. So A is a liar but because A is a liar, we can deduce that C tells the truth (because we know that B is a liar and (s)he said that A and C both lie.

So hence, we know stuff :)

Actually, I had two more thoughts while I was doing the washing up.

If we ban self-referential cycles as used above then we can still make progress. Somebody saying that $1+1=2$ would be a truth teller and $1+1=3$ would indicate a consistent liar. If we only allow comments about the ability of others to lie and tell the truth then saying '$A$ tells the truth and $A$ doesn't tell the truth' must indicate a liar and '$A$ tells the truth implies $A$ tells the truth' or indeed any other tautology must indicate a truth teller.

  • $\begingroup$ I've checked, and your scenario has no model at all - i.e. it's an antilogy. $\endgroup$
    – Sudix
    Aug 3, 2018 at 11:12
  • $\begingroup$ OK so it may be worth one more look. The model is: A is a liar, B is a liar and C tells the truth. Let's see why this works. A said that B tells the truth. This is a lie which is fine because A is a liar. B says that A and C are both liars. This is a lie because C tells the truth. And this is fine because B is a liar. $\endgroup$ Aug 3, 2018 at 11:18
  • $\begingroup$ But in your scenario, $B$ is a liar, who tells a truth, i.e. that $A$ is a liar. The model prerequisites that a liar 'always' lies - not a single word he utters is a truth $\endgroup$
    – Sudix
    Aug 3, 2018 at 11:29
  • $\begingroup$ B says that A and C are liars. This is not the truth as C is a truth-teller. B is making a single compound statement not two individual statements. $\endgroup$ Aug 3, 2018 at 11:32
  • $\begingroup$ I see your point, it's a subtlety of the English I speak yet don't understand. With your interpretation of my question the line in the proof $$$$ "$A$ is a liar. Then the statements are all false." would be wrong, so under this interpretation you're right $\endgroup$
    – Sudix
    Aug 3, 2018 at 11:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .