Communication Theory and Formal Logic

In view of unifying Game Theory, Information/Communication Theory and Formal Logic

Victor Morgante
7 min readDec 29, 2024

Classical Communication Theory can be viewed this way:

Classical Information Theory. Image by author.

The Sender sends a Message through a Medium or Channel to a Receiver, and Noise can be introduced by/within the medium/channel or in the interpretation by the receiver.

Astute observers may realise that the message may intentionally or accidentally obfuscated or corrupted by the sender, with noise within the message itself.

Classical Information Theory with universal potential for noise. Image by author.

When that the case, and as it is, we are left in the position where the message itself (and possibly with noise added by/within the medium/channel) is meaningless, but for the interpretation of the receiver.

Because the sender has the potential to introduce noise into the very message delivered, the sender equally has an interpretative function in acting as a proxy for the receiver in asking before delivery, “How will this message be interpreted by the receiver?”

This poses a considerable problem for formal logic, as practically any theory of formal logic may have multiple and non-standard interpretations.

Ehrenfeucht Fraisse Games and leaping to reality

While it may come as surprise to those who study formal logic and mathematics, Ehrenfeucht Fraisse Games come with a bold assumption, which allows for multiple interpretations to coexist at the same time and neither player of the game any the wiser under the standard interpretation of the game itself.

Any the wiser to what?

Any the wiser as to whether they play under the same interpretation or different interpretations.

To investigate that, let us look at the basic definition of an Ehrenfeucht Fraisse Game:

“The main idea behind the game is that we have two structures, and two players — Spoiler and Duplicator. Duplicator wants to show that the two structures are elementarily equivalent (satisfy the same first-order sentences), whereas Spoiler wants to show that they are different” [1]

Let us say that Spoiler wins, and we have the same elementary equivalent structures, as below:

Elementary Equivalent Structures. Image by author.

You might look at those structures and ask: “Don’t they represent the same thing?”

The answer would be “Yes”, and to make that obvious we can project the image onto a linear plane where both structures map to the following:

Structure under First-Order Sentence. Image by author.

But the definition of an Ehrenfeucht Fraisse Game does not say that the same first-order sentences must be under the same theory.

This is a sizable omission within the definition of an Ehrenfeucht Fraisse Game.

Why?

Well, it comes down to what the elements of the structures represent. They do not represent sentences (or theorems) of a theory but concrete elements that are defined by the sentences/theorems themselves.

This is a crucial point, because multiple first-order theories can use the same symbols of logic, the same theorem construction rules, and are what are otherwise known as structures in their own right under model theory.

What this means is that either Ehrenfeucht Fraisse Games (EF Games) may be exploitable or ambiguity as to the theories used by the Spoiler and Duplicator subjectively and simultaneously (throughout the game) may be the same, or different by default. There is no way of telling whether the Spoiler or Duplicator are playing by the same rules (same theory) or not only that it is agreed that the structures are elementary equivalent under the same first-order sentences (which we say may be under different theories).

By repeated playing of EF Games between two players, both players may, I propose, agree that each player shares the same interpretation (by sequential and iterative game play resulting in agreement of winning or losing, and shared agreement of the rules/theories), or simply be none the wiser as to whether one or other player uses a different theory (or interpretation) that results in harmonious game play.

Indeed, if Spoiler and Duplicator did not play by using different theories, there would be no game at all. Simply two players would agree on the theory being used and two structures elementary equivalent that trivially identified as for there to be no game.

There would be no fun to it. It would be the same as one person saying: “That box is green” and the other saying “Yes, that box is green”.

Games are characterised by their being an element of surprise, especially if they are non-cooperative, and if an EF Game is not cooperative, then Duplicator must be playing under a different theory, or there would be no element of surprise.

We know this to be true, as in our analogy, nobody knows if “green” to one person is the exact same thing in their mind as “green” in another’s mind until it is tested. What would be a surprise, and is testable, is when a person takes a colour-blind test and realises that they are not seeing the world as others see it.

But Ehrenfeucht Fraisse Games are not like that. The only test is that the two structures satisfy the same first-order sentences. And without agreement up-front as to the theory under which the game is being played, and without communication between players as to the theory they are using, neither player would know if the other player was using the same theory because the game would continue on and winners and losers found, each oblivious to the theory under which the other player used. This, because the game would continue on and for all intents and purposes each player would be making an assumption that the other player was using the same theory because none of the moves would seem out of the normal.

Tying Back to Formal Logic and Information/Communication Theory

To tie all that back to Formal Logic (in general) and Information/Communication Theory is easy and straight forward.

There can only be winner in an Ehrenfeucht Fraisse Game is both Spoiler and Duplicator operate over a single structure that is known to be elementary equivalent to two other structures up-front, as below. Otherwise, the game is lost even before the game starts.

Elementary Structures under different interpretations/Theories. Image by author.

It does not matter who goes first, or which player plays Spoiler or Duplicator, because if there is no elementary equivalent structure agreeable to both players up-front, then there is no game worth winning.

To paint an analogy, if two differently worded Google searches came back with the same top-ranking result, then the chances are that the Google search terms were the same or similar. With an Ehrenfeucht Fraisse Game we are talking about concrete elements, and structures as concrete as we can get under formal logic, and so we either start the game with their being elementary equivalent or not.

With first-order theories variably being able to be interpreted as higher-order theories, the result is extensible to other areas of formal logic. Indeed, if it were not in the rules of an EF Game, neither Spoiler or Duplicator would be any the wiser as to which theory, whatsoever, the other player was playing under, as we do not have access to disassemble the human brain as to its inner workings with any knowledge of the models it is using. I.e. We can’t normally read other people’s minds, unless we know them well, which comes from repeated transactions and game play, and as discussed for EF Games here.

So, when it comes to Communication Theory, and elementary equivalent structure may be seen as a message, received by the Receiver if the Receiver has and uses the same interpretation as the Sender, or has/uses a theory that maps to the same elementary equivalent structure for there to be a winner, regardless of which person is the Sender (Spoiler) and which the Receiver (Duplicator).

Agreeing on an Elementary Equivalent Structure. Image by author.

Noise, under this analogy may well be that the Sender perceives that they are using the same theory as the Receiver (but this not being the case), but two winners none the less if both agree on the same elementary equivalent structure. I.e. The message is clear to each player, regardless of differences between the two players.

That it is impossible for any transactions to be shared between players without a message through a medium/channel is central to what we discuss.

In formal logic, there may well be structures to discuss, but when we extend the study of Formal Logic to Model Theory, we don’t just discuss concrete elements, we discuss the symbols of a theory, the structure of theorems of a theory and their rules of inference, and so Formal Logic becomes tightly coupled to Communication Theory, and if we consider the likes of Ehrenfeucht Fraise Games, Formal Logic under Game Theory itself.

Thank you for reading. As time permits, I will write more on the unification of Information/Communication Theory, Formal Logic and Game Theory.

===================End==================

References

  1. “Ehrenfeucht Fraisse Game”, Ehrenfeucht–Fraïssé game — Wikipedia, Wikipedia, Accessed at 29/12/2024

--

--

Victor Morgante
Victor Morgante

Written by Victor Morgante

@FactEngine_AI. Manager, Architect, Data Scientist, Researcher at www.factengine.ai and www.perceptible.ai

No responses yet