Skip to content →

Tag: math

some skew Smullyan stumpers

Published September 21, 2023 by lieven

Raymond Smullyan‘s logic puzzles are legendary. Among his best known are his Knights (who always tell the truth) and Knaves (who always lie) puzzles. Here’s a classic example.

“On the day of his arrival, the anthropologist Edgar Abercrombie came across three inhabitants, whom we will call $A$, $B$ and $C$. He asked $A$: “Are you a Knight or a Knave?” $A$ answered, but so indistinctly that Abercrombie could not understand what he said.

He then asked $B$: “What did he say?” $B$ replies: “He said that he is a knave.” At this point, $C$ piped up and said: “Don’t believe that; it’s a lie!”

Was $C$ a Knight or a Knave?”

If you are stumped by this, try to figure out what kind of inhabitant can say “I am a Knave”.

Some years ago, my friend and co-author Karin Cvetko-Vah wrote about a much stranger island, the island of two truths.

“The island was ruled by a queen and a king. It is important to stress that the queen was neither inferior nor superior to the king. Rather than as a married couple one should think of the queen and the king as two parallel powers, somewhat like the Queen of the Night and the King Sarastro in Mozart’s famous opera The Magic Flute. The queen and the king had their own castle each, each of them had their own court, their own advisers and servants, and most importantly each of them even had their own truth value.

On the island, a proposition p is either FALSE, Q-TRUE or K-TRUE; in each of the cases we say that p has value 0, Q or K, respectively. The queen finds the truth value Q to be superior, while the king values the most the value K. The queen and the king have their opinions on all issues, while other residents typically have their opinions on some issues but not all.”

The logic of the island of two truths is the easiest example of what Karin and I called a non-commutative frame or skew Heyting algebra (see here), a notion we then used, jointly with Jens Hemelaer, to define the notion of a non-commutative topos.

If you take our general definitions, and take Q as the distinguished top-element, then the truth tables for the island of two truths are these ones (value of first term on the left, that of the second on top):

\[
\begin{array}{c|ccc}
\wedge & 0 & Q & K \\
\hline
0 & 0 & 0 & 0 \\
Q & 0 & Q & Q \\
K & 0 & K & K
\end{array} \quad
\begin{array}{c|ccc}
\vee & 0 & Q & K \\
\hline
0 & 0 & Q & K \\
Q & Q & Q & K \\
K & K & Q & K
\end{array} \quad
\begin{array}{c|ccc}
\rightarrow & 0 & Q & K \\
\hline
0 & Q & Q & K \\
Q & 0 & Q & K \\
K & 0 & Q & K
\end{array} \quad
\begin{array}{c|c}
& \neg \\
\hline
0 & Q \\
Q & 0 \\
K & 0
\end{array}
\]

Note that on this island the order of statements is important! That is, the truth value of $p \wedge q$ may differ from that of $q \wedge p$ (and similarly for $\vee$).

Let’s reconsider Smullyan’s puzzle at the beginning of this post, but now on an island of two truths, where every inhabitant is either of Knave, or a Q-Knight (uttering only Q-valued statements), or a K-Knight (saying only K-valued statements).

Again, can you determine what type $C$ is?

Well, if you forget about the distinction between Q- and K-valued sentences, then we’re back to classical logic (or more generally, if you divide out Green’s equivalence relation from any skew Heyting algebra you obtain an ordinary Heyting algebra), and we have seen that then $B$ must be a Knave and $C$ a Knight, so in our new setting we know that $C$ is either a Q-Knight or a K-Knight, but which of the two?

Now, $C$ claims the negation of what $B$ said, so the truth value is $\neg 0 = Q$, and therefore $C$ must be a Q-Knight.

Recall that in Karin Cvetko-Vah‘s island of two truths all sentences have a unique value which can be either $0$ (false) or one of the non-false values Q or K, and the value of combined statements is given by the truth tables above. The Queen and King both have an opinion on all statements, which may or may not coincide with the actual value of that statement. However, if the Queen assigns value $0$ to a statement, then so does the King, and conversely.

Other inhabitants of the island have only their opinion about a subset of all statements (which may be empty). Two inhabitants agree on a statement if they both have an opinion on it and assign the same value to it.

Now, each inhabitant is either loyal to the Queen or to the King (or both), meaning that they agree with the Queen (resp. King) on all statements they have an opinion of. An inhabitant loyal to the Queen is said to believe a sentence when she assigns value $Q$ to it (and symmetric for those loyal to the King), and knows the statement if she believes it and that value coincides with the actual value of that statement.

Further, if A is loyal to the Queen, then the value of the statement ‘A is loyal to the Queen’ is Q, and if A is not loyal to the Queen, then the value of the sentence ‘A is loyal to the Queen’ is $0$ (and similarly for statements about loyalty to the King).

These notions are enough for the first batch of ten puzzles in Karin’s posts

Just one example:

Show that if anybody on the island knows that A is not loyal to the Queen, then everybody that has an opinion about the sentence ‘A is loyal to the Queen’ knows that.

After these two posts, Karin decided that it was more fun to blog about the use of non-commutative frames in data analysis.

But, she once gave me a text containing many more puzzles (as well as all the answers), so perhaps I’ll share these in a follow-up post.

Comments closed

A projective plain (plane) of order ten

Published September 19, 2023 by lieven

A projective plane of order $n$ is a collection of $n^2+n+1$ lines and $n^2+n+1$ points satisfying:

  • every line contains exactly $n+1$ points
  • every point lies on exactly $n+1$ lines
  • any two distinct lines meet at exactly one point
  • any two distinct points lie on exactly one line

Clearly, if $q=p^k$ is a pure prime power, then the projective plane over $\mathbb{F}_q$, $\mathbb{P}^2(\mathbb{F}_q)$ (that is, all nonzero triples of elements from the finite field $\mathbb{F}_q$ up to simultaneous multiplication with a non-zero element from $\mathbb{F}_q$) is a projective plane of order $q$.

The easiest example being $\mathbb{P}^2(\mathbb{F}_2)$ consisting of seven points and lines

But, there are others. A triangle is a projective plane of order $1$, which is not of the above form, unless you believe in the field with one element $\mathbb{F}_1$…

And, apart from $\mathbb{P}^2(\mathbb{F}_{3^2})$, there are three other, non-isomorphic, projective planes of order $9$.

It is clear then that for all $n < 10$, except perhaps $n=6$, a projective plane of order $n$ exists.

In 1938, Raj Chandra Bose showed that there is no plane of order $6$ as there cannot be $5$ mutually orthogonal Latin squares of order $6$, when even the problem of two orthogonal squares of order $6$ (see Euler’s problem of the $36$ officers) is impossible.

Yeah yeah Bob, I know it has a quantum solution.

Anyway by May 1977, when Lenstra’s Festschrift ‘Een pak met een korte broek’ (a suit with shorts) was published, the existence of a projective plane of order $10$ was still wide open.

That’s when Andrew Odlyzko (probably known best for his numerical work on the Riemann zeta function) and Neil Sloane (probably best known as the creator of the On-Line Encyclopedia of Integer Sequences) joined forces to publish in Lenstra’s festschrift a note claiming (jokingly) the existence of a projective plane of order ten, as they were able to find a finite field of ten elements.



Here’s a transcript:

A PROJECTIVE PLAIN OF ORDER TEN

A. M. Odlyzko and N.J.A. Sloane

This note settles in the affirmative the notorious question of the existence of a projective plain of order ten.

It is well-known that if a finite field $F$ is given containing $n$ elements, then the projective plain of order $n$ can be immediately constructed (see M. Hall Jr., Combinatorial Theory, Blaisdell, Waltham, Mass. 1967 and D.R. Hughes and F.C. Piper, Projective Planes, Springer-Verlag, N.Y., 1970).

For example, the points of the plane are represented by the nonzero triples $(\alpha,\beta,\gamma)$ of elements of $F$, with the convention that $(\alpha,\beta,\gamma)$ and $(r\alpha, r\beta, r\gamma)$ represent the same point, for all nonzero $r \in F$.

Furthermore this plain even has the desirable property that Desargues’ theorem holds there.

What makes this note possible is our recent discovery of a field containing exactly ten elements: we call it the digital field.

We first show that this field exists, and then give a childishly simple construction which the reader can easily verify.

The Existence Proof

Since every real number can be written in the decimal system we conclude that

\[
\mathbb{R} = GF(10^{\omega}) \]

Now $\omega = 1.\omega$, so $1$ divides $\omega$. Therefore by a standard theorem from field theory (e.g. B. L. van der Waerden, Modern Algebra, Ungar, N.Y., 1953, 2nd edition, Volume 1, p. 117) $\mathbb{R}$ contains a subfield $GF(10)$. This completes the proof.

The Construction

The elements of this digital field are shown in Fig. 1.

They are labelled $Left_1, Left_2, \dots, Left_5, Right_1, \dots, Right_5$ in the natural ordering (reading from left to right).



Addition is performed by counting, again in the natural way. An example is shown in Fig. 2, and for further details the reader can consult any kindergarten student.

In all digital systems the rules for multiplication can be written down immediately once addition has been defined; for example $2 \times n = n+n$. The reader will easily verify the rest of the details.

Since this field plainly contains ten elements (see Fig. 1) we conclude that there is a projective plain of order ten.

So far, the transcript.

More seriously now, the non-existence of a projective plane of order ten was only established in 1988, heavily depending on computer-calculations. A nice account is given in

C. M. H. Lam, “The Search for a Finite Projective Plane of Order 10”.

Now that recent iPhones nearly have the computing powers of former Cray’s, one might hope for easier proofs.

Fortunately, such a proof now exists, see A SAT-based Resolution of Lam’s Problem by Curtis Bright, Kevin K. H. Cheung, Brett Stevens, Ilias Kotsireas, Vijay Ganesh

David Roberts, aka the HigherGeometer, did a nice post on this
No order-10 projective planes via SAT.

Comments closed

A suit with shorts

Published September 18, 2023 by lieven

I’m retiring in two weeks so I’m cleaning out my office.

So far, I got rid of almost all paper-work and have split my book-collection in two: the books I want to take with me, and those anyone can grab away.

Here’s the second batch (math/computer books in the middle, popular science to the right, thrillers to the left).



If you’re interested in some of these books (click for a larger image, if you want to zoom in) and are willing to pay the postage, leave a comment and I’ll try to send them if they survive the current ‘take-away’ phase.

Here are two books I definitely want to keep. On the left, an original mimeographed version of Mumford’s ‘Red Book’.

On the right, ‘Een pak met een korte broek’ (‘A suit with shorts’), a collection of papers by family and friends, presented to Hendrik Lenstra on the occasion of the defence of his Ph.D. thesis on Euclidean number-fields, May 18th 1977.

If the title intrigues you, a photo of young Hendrik in suit and shorts is included.

This collection includes hilarious ‘papers’ by famous people including

  • ‘A headache-causing problem’ by Conway (J.H.), Paterson (M.S.), and Moscow (U.S.S.R.)
  • ‘A projective plain of order ten’ by A.M. Odlyzko and N.J.A. Sloane
  • ‘La chasse aux anneaux principaux non-Euclidiens dans l’enseignement’ by Pierre Samuel
  • ‘On time-like theorems’ by Michiel Hazewinkel
  • ‘She loves me, she loves me not’ by Richard K. Guy
  • ‘Theta invariants for affine root systems’ by E.J.N. Looijenga
  • ‘The prime of primes’ by F. Lenstra and A.J. Oort
  • (and many more, most of them in Dutch)

Perhaps I can do a couple of posts on some of these papers. It might break this clean-up routine.

One Comment