Skip to content →

Author: lievenlb

Heyting Smullyanesque problems

Published February 10, 2018 by lievenlb

Raymond Smullyan brought Knights and Knaves puzzles to a high art in his books. Here’s the setting:

On Smullyan’s islands there are Knights, who always tell true statements, Knaves, who always lie, and sometimes also Normals, who sometimes tell the truth and sometimes lie.


(image credit MikeKlein)

Problems of this sort can be solved by classical propositional logic, replacing every sentence $P$ told by inhabitant $A$ by the formula $k_A \leftrightarrow P$ where $k_A$ is the sentence “A is a Knight”.

Some time ago I asked for Smullyanesque problems in a non-classical logic, where we replace the usual truth-values $T$ (true) and $F$ (false) of propositional logic by elements of an Heyting algebra.

Jason Rosenhouse wrote a paper Knights, Knaves, Normals, and Neutrals for The College Mathematics Journal, containing more information than in his blog post, as well as some nice challenging puzzles. Here’s Rosenhouse’s setting:

Apart from Knights, Knaves and Normals there’s also the tribe of Neutrals (which he describes as a sort of trans-Knights or trans-Knaves) who can only tell sentences with truth value $N$ in the Heyting algebra $\{ T,N,F \}$ with logical connectives

A typical sentence of truth value $N$ is “A is a Knight” or “A is a Knave” whereas, in reality, $A$ is Neutral. Here are the truth values of sentences about a person (the column headings) with respect to the actual situation (the row headings)

A good way into such problems is to focus on sentence like “A is a Neutral” as they have only classical truth values $T$ or $F$ and to remember that Neutrals can never say a sentence with classical truth value. Here’s an example (only Knights,Knaves or Neutrals present):

Problem 1: Suppose you meet three people, named Dave, Evan and Ford. They make the following statements:

Dave: Evan is a knight.
Evan: Ford is a knave.
Ford: Dave is a neutral.

Can you determine the types of all three people?

Solution: Ford’s sentence has value $T$ or $F$, so Ford cannot be Neutral so must be a Knight or Knave. But then Evan’s sentence also has classical truth value, so he can’t be Neutral either, and by the same reasoning also Dave cannot be neutral. So, we know that all three people must be either Knights or Knaves and then it follows at once that Ford is a Knave (because he lied) and that Evan and Dave must be knights.

These puzzles become more interesting once we use logical connectives.

Problem 2: What can you conclude from this dialog?

Mimi: Olaf is a Knight and Olaf is not a Knight.
Nate: Olaf is a Knave or Olaf is not a Knave.
Olaf: Mimi is a Knight or Nate is a Knave or I am Neutral.

Solution: Mimi’s sentence can only have truth value $F$ or $N$ so she can’t be a Knight. Nate’s sentence has value $T$ or $N$ so he cannot be a Knave.
The two first parts of Olaf’s line cannot be $T$ so must be either $N$ or $F$. So, Olav’s line has total value $T$ only if the last part ‘I am Neutral’ is $T$. So, Olaf can neither be a Knight (because then the last part is $F$) nor Neutral (because then the line would have value $T$ and Neutrals can only speak $N$-sentences). So, Olaf must be a knave. Nate must then be a Knight and Mimi a Knave (because the first part of her line is $F$ and so must be the whole sentence).

The situation becomes even more complicated when we allow Normals (who sometimes lie and sometimes tell the truth but never say sentences with value $N$) to be present. Here’s Rosenhouse’s ‘Grand Finale’:

Problem 3: One day a visitor encountered eight people, among them exactly two Knights, two Knaves, two Normals and two Neutrals. What can you conclude from this dialog:

Sara: Walt is a Neutral or Vera is a Neutral.
Todd: Xara is a Knave and Yoav is a Knave.
Ursa: If Sara is a Knight, then Todd and Yoav are Normals.
Vera: I am not a Neutral.
Walt: If Vera is not a Neutral, then neither is Todd.
Xara: Todd is a Knight if and only if Zack is a Neutral.
Zack: Xara is a Neutral if and only if Walt is not a Normal.

You will solve this problem much quicker than to read through the long explanation in Rosenhouse’s paper.

These puzzles beg to be generalised to more complicated Heyting algebras.

What about a book on “Knights, Knaves and Knols”? A Knol (or $X$-Knol) has knowledge limited to sentences with truth value $X$, an element in the Heyting algebra.

Leave a Comment

taking stock

Published February 4, 2018 by lievenlb

The one thing harder than to start blogging after a long period of silence is to stop when you think you’re still in the flow.

(image credit Putnam Consulting)

The Januari 1st post a math(arty) 2018 was an accident. I only wanted to share this picture, of a garage-door with an uncommon definition of prime numbers, i saw the night before.

I had been working on a better understanding of Conway’s Big Picture so I had material for a few follow-up posts.

It was never my intention to start blogging on a daily basis.

I had other writing plans for 2018.

For years I’m trying to write a math-book for a larger audience, or at least to give it an honest try.

My pet peeve with such books is that most of them are either devoid of proper mathematical content, or focus too much on the personal lives of the mathematicians involved.

An inspiring counter-example is ‘Closing the gap’ by Vicky Neal.

From the excellent review by Colin Beveridge on the Aperiodical Blog:

“Here’s a clever way to structure a maths book (I have taken copious notes): follow the development of a difficult idea or discovery chronologically, but intersperse the action with background that puts the discovery in context. That’s not a new structure – but it’s tricky to pull off: you have to keep the difficult idea from getting too difficult, and keep the background at a level where an interested reader can follow along and either say “yes, that’s plausible” or better “wait, let me get a pen!”. This is where Closing The Gap excels.”

So it is possible to publish a math-book worth writing. Or at least, some people can pull it off.

Problem was I needed to kick myself into writing mode. Feeling forced to post something daily wouldn’t hurt.

Anyway, I was sure this would have to stop soon. I had plans to disappear for 10 days into the French mountains. Our place there suffers from frequent power- and cellphone-cuts, which can last for days.

Thank you Orange.fr for upgrading your network to the remotest of places. At times, it felt like I was working from home.

I kept on blogging.

Even now, there’s material lying around.

I’d love to understand the claim that non-commutative geometry may offer some help in explaining moonshine. There was an interesting question on an older post on nimber-arithmetic I feel I should be following up. I’ve given a couple of talks recently on $\mathbb{F}_1$-material, parts of which may be postable. And so on.

Problem is, I would stick to the same (rather dense) writing style.

Perhaps it would make more sense to aim for a weekly (or even monthly) post over at Medium.

Medium offers no MathJax support forcing me to write differently about maths, and for a broader potential audience.

I may continue to blog here (or not), stick to the current style (or try something differently). I have not the foggiest idea right now.

If you have suggestions or advice, please leave a comment or email me.

Leave a Comment

the monster dictates her picture

Published February 3, 2018 by lievenlb

The monstrous moonshine picture is a sub-graph of Conway’s Big Picture on 218 vertices. These vertices are the classes of lattices needed in the construction of the 171 moonshine groups. That is, moonshine gives us the shape of the picture.

(image credit Friendly Monsters)

But we can ask to reverse this process. Is the shape of the picture dictated by group-theoretic properties of the monster?

That is, can we reconstruct the 218 lattices and their edges starting from say the conjugacy classes of the monster and some simple rules?

Look at the the power maps for the monster. That is, the operation on conjugacy classes sending the class of $g$ to that of $g^k$ for all divisors $k$ of the order of $g$. Or, if you prefer, the $\lambda$-ring structure on the representation ring.

Rejoice die-hard believers in $\mathbb{F}_1$-theory, rejoice!

Here’s the game to play.

Let $g$ be a monster element of order $n$ and take $d=gcd(n,24)$.

(1) : If $d=8$ and a power map of $g$ gives class $8C$ add $(n|4)$ to your list.

(2) : Otherwise, look at the smallest power of $g$ such that the class is one of $12J,8F,6F,4D, 3C,2B$ or $1A$ and add $(n|e)$ where $e$ is the order of that class, or, if $n > 24$ and $e$ is even add $(n | \frac{e}{2})$.

A few examples:

For class 20E, $d=4$ and the power maps give classes 4D and 2B, so we add $(20|2)$.

For class 32B, $d=8$ but the power map gives 8E so we resort to rule (2). Here the power maps give 8E, 4C and 2B. So, the best class is 4C but as $32 > 24$ we add $(32|2)$.

For class 93A, $d=3$ and the power map gives 3C and even though $93 > 24$ we add $(93|3)$.

This gives us a list of instances $(n|e)$ with $n$ the order of a monster element. For $N=n \times e$ look at all divisors $h$ of $24$ such that $h^2$ divides $N$ and add to your list of lattices those of the form $M \frac{g}{h}$ with $g$ strictly smaller than $h$ and $(g,h)=1$ and $M$ a divisor of $\frac{N}{h^2}$.

This gives us a list of lattices $M \frac{g}{h}$, which is an $h$-th root of unity centered as $L=M \times h$ (see this post). If we do this for all lattices in the list we can partition the $L$’s in families according to which roots of unity are centered at $L$.

This gives us the moonshine picture. (modulo mistakes I made)

The operations we have to do after we have our list of instances $(n|e)$ is pretty straightforward from the rules we used to determine the lattices needed to describe a moonshine group.

Perhaps the oddest part in the construction are the rules (1) and (2) and the prescribed conjugacy classes used in them.

One way to look at this is that the classes $8C$ and $12J$ (or $24J$) are special. The other classes are just the power-maps of $12J$.

Another ‘rationale’ behind these classes may come from the notion of harmonics (see the original Monstrous moonshine paper page 312) of the identity element and the two classes of involutions, 2A (the Fischer involutions) and 2B (the Conway involutions).

For 1A these are : 1A,3C

For 2A these are : 2A,4B,8C

For 2B these are : 2B,4D,6F,8F,12J,24J

These are exactly the classes that we used in (1) and (2), if we add the power-classes of 8C.

Perhaps I should take some time to write all this down more formally.

Leave a Comment