Closed world paradoxon - He who knows knothing can believe nothing

Question

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.

Proof:

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.

Answer 1

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".

Answer 2

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.