A student of mine was recently given the following question:
"At least one of us is lying," said Andrew.
"Only one of us is lying," said Bertas.
"Squeak, two of us are lying," said the Chipmunk.
"Either three or four of us are lying," said Daisy.
"Elmo thinks that everybody is lying," said Elmo.
How many liars are there altogether?
We can rehash this into language that is more easy to analyse as follows:
Andrew: the number of truthspeakers is an element of $\{0,1,2,3,4\}.$
Bertas: the number of truthspeakers is an element of $\{4\}.$
Chipmunk: the number of truthspeakers is an element of $\{3\}.$
Daisy: the number of truthspeakers is an element of $\{1,2\}.$
Elmo: the number of truthspeakers is an element of $\{0\}.$
With a bit of thought, we see that the answer is "$2$ truthspeakers."
- It can't be $0$, because then Andrew and Elmo would be truthspeakers.
- It can't be $1$, because then both Andrew and Daisy would be truthspeakers.
- It can be $2$, with Andrew and Daisy being the only truthspeakers.
- It can't be $3$ or more, because the intersection of any three distinct sets listed above is empty.
Anyway, I thought this question was pretty cool, enough so that I tried throwing some abstract nonsense at it. Here's what I came up with.
Definition 0. Consider a category concrete over $\mathbf{Set}.$ Lets refer to its objects as algebras, and lets assume there's a free algebra on every set. Write $U$ for the underlying set functor, $F$ for the free functor, and $\Phi$ for the adjunction $F \dashv U$.
Given
- a set $S$ equipped with a function $f : S \rightarrow UFS$
- an algebra $X$,
a realization of $f$ in $X$ is a function $g : S \rightarrow UX$ such that $g=U(\Phi_{S,X}(g)) \circ f$
For instance:
- Work over the concrete category of Boolean algebras; so in particular, $F$ is the free Boolean algebra functor.
- Define $S = \{A,B,C,D,E\}$.
- Define $f : S \rightarrow UFS$ so that it expresses whom the truthspeakers are conjectured to be:
For example: $$f(A) = \neg(\neg A \wedge \neg B \wedge \neg C \wedge \neg D \wedge \neg E), \qquad f(E) = \bot$$
Then the unique realization of $f$ in the boolean algebra $\{0,1\}$ is $$g : A,D \mapsto 1, \qquad g : B,C,E \mapsto 0.$$
Here's a more simple example:
Liar's paradox. The function $f : \{x\} \rightarrow F(\{x\})$ given by $x \mapsto \neg x$ has no realizations in $\{0,1\}$.
What I'd like to know is:
Question. Does this train of thought lead to any interesting mathematics?
I don't know the answer to this, but I can see something interesting you can do already:
How would your results change if you changed the underlying logic, from Boolean to Heyting for example (so that there is no law of excluded middle)? That could be interesting, even if just to compare with the example(s) you've already worked out.