Monthly Archives: April 2009

An Interesting Puzzle in Propositional Logic

Suppose that you’re translating an ancient text, and in this text you come across three words whose meaning you are unsure of: \mathit{bal}, \mathit{kat}, and \mathit{lot}.  So, you head down to the ancient language department of your local university.

The first professor you come across, \hbox{Prof. Bal}, knows what \mathit{bal} means, the second professor you come across, \hbox{Prof. Kat}, knows what \mathit{kat} means, and the third professor you come across, \hbox{Prof. Lot}, knows what \mathit{lot} means.  So you have fortunately solved your problem.

But you’re now curious and decide to meet some other professors in the department.  The next professor you come across is named \hbox{Prof. }(\mathrm{Bal}\rightarrow\mathrm{Kat}).  He doesn’t know what \mathit{bal} means or what \mathit{kat} means, but if you told him what \mathit{bal} meant, he would be able to tell you what \mathit{kat} means (for example, maybe he knows that \mathit{kat} is the noun form of \mathit{bal}).

The next professor you meet is named \hbox{Prof. }(\mathrm{Bal}\rightarrow(\mathrm{Kat}\rightarrow\mathrm{Lot})).  If you told him what \mathit{bal} meant and what \mathit{kat} meant, he would be able to tell you what \mathit{lot} means.

The next professor you meet is named \hbox{Prof. }((\mathrm{Bal}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Lot}).  If you told him a method for finding out the meaning of \mathit{kat} given the meaning of \mathit{bal}, he would be able to tell you the meaning of \mathit{lot}.

In general, for any two professors \hbox{Prof. }P and \hbox{Prof. }Q, there is a professor \hbox{Prof. }P\rightarrow Q with the property that if you told him what \hbox{Prof. }P knew, he would be able to tell you what \hbox{Prof. }Q knows (but \hbox{Prof. }P\rightarrow Q doesn’t know any more than that).

Notice that some professors have essentially the same state of knowledge.  For example, \hbox{Prof. Bal} and \hbox{Prof. }((\mathrm{Kat}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Bal}) have essentially the same knowledge, since to get the meaning of \mathit{bal} out of \hbox{Prof. }((\mathrm{Kat}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Bal}) you only have to tell him a method for finding out the meaning of \mathit{kat} given the meaning of \mathit{kat}, which is something that you can do without any particular special knowledge concerning \mathit{bal}, \mathit{kat} and \mathit{lot}.

A more nontrivial example is that \hbox{Prof. }(((\mathrm{Bal}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Bal})\rightarrow\mathrm{Kat}) has the same state of knowledge as \hbox{Prof. }(\mathrm{Bal}\rightarrow\mathrm{Kat}).  This is because each can “simulate” the other.  In one direction, suppose somebody told \hbox{Prof. }(((\mathrm{Bal}\rightarrow\mathrm{Kat})\rightarrow\mathrm{Bal})\rightarrow\mathrm{Kat}) the meaning of \mathit{bal}.  He therefore knows a trivial “method” for getting the meaning of \mathit{bal} given any inputs, and so he knows the meaning of \mathit{kat}.  In the other direction, suppose we told \hbox{Prof. }(\mathrm{Bal}\rightarrow\mathrm{Kat}) a method for turning (methods for turning the meaning of \mathit{bal} into the meaning of \mathit{kat}) into the meaning of \mathit{bal}.  Well, \hbox{Prof. }(\mathrm{Bal}\rightarrow\mathrm{Kat}) knows a method for turning the meaning of \mathit{bal} into the meaning of \mathit{kat}, so he can use that find the meaning of \mathit{bal}.  He can then use his method a second time to turn that into the meaning of \mathit{kat}.

The puzzle is then to prove that there are only finitely many professors with different states of knowledge.

This puzzle is equivalent to showing that intuitionistic implicational propositional logic over three variables has only finitely many logically inequivalent formulas.  Another formulation is: Let \mathbb{C}_n be the free cartesian closed category over n objects.  Given objects A and B\in \mathbb{C}_n, say that A and B are equivalent if there is an arrow from A to B and an arrow from B to A.  Then there are only finitely many equivalence classes in \mathbb{C}_3.  (The corresponding statements are also true with 3 replaced by n.)

Continue reading

Leave a comment

Filed under Uncategorized