The fundamental misconception of Finite Model Theory
Finite Model Theory (FMT) is a branch of logic the theories (symbolic languages) of which have interpretations which limit the model of theorems of those theories to the finite. No matter how many times you extend the model by 1 element you never make the break to infinity and always remain within the realm of the finite.
The idea is that where data structures studied under areas like computer science exist in physical terms within the confines of a disk drive on a computer, those data structures are necessarily finite and so a theory was invented to study the limits of those structures and functions that range over them.
Vast amounts of literature have been written on finite model theory, and as if by submitting oneself to theories under FMT the supposed limits of the theory manifest as real.
The reality could not be any more different. For starters, you, as interpreter of sentences of theories under FMT, have to submit to the notion that you are working in the realm of the finite. i.e. You have to submit to the theory such that the theory holds true. What magic.
Allow me to explain. Consider if you will the following diagram (on the left in the picture) and the sentences of a theory under finite model theory on the right.
The first (the diagram) is of a graphical theory called Object-Role Modeling (ORM). On the right are sentences of a language of FMT called, KL, and which is largely homomorphic with ORM.
The sentences of KL are written in a type font in the software that generated them called ZFont, standing for the Z Notation of logic. Sentences in Z Notation are not under finite model theory, but rather typed first-order predicate logic. It just so happens, however, that Z Notation shares symbols used by KL, and just looking at the theorems above you wouldn’t know if the language was KL or Z.
So to the casual observer, you, as interpreter, get to choose whether you are looking at theorems of Z Notation or theorems of finite-model theory. One can range over structures ranging to the infinite, the other limited to the finite.
So, you, as observer, play an integral part in whether you submit to a theory or not. The whole point of data is that at some point it is interpreted by an observer/interpreter as one thing or another. In this case, you could choose to interpret the theorems ranging over a model that is extensible to the infinite.
So why does finite model theory confine an interpreter to a fundamental misconception? Is there a fundamental misconception held by proponents of finite model theory?
A simple thought experiment may help understand. Imagine the sentences in the picture above were intended to range over a necessarily finite model stored on the Medium server hosting this article. The data of the relation mapping Part to Bin to Warehouse, “1, H2, London”, most certainly is stored on Medium’s hard drive somewhere. The theorems most certainly are stored their too. The conceptual structure they range over would be thought of as under the same finite confines. Both would be stored on a hard disk somewhere in the world. Proponents of finite model theory would say, “Aha. You see. The model under those sentences is necessarily finite because they would be on a hard disk of finite capacity”. Even if you did not buy that analogy, it is trivial to imagine where the same set of theorems ranged over an actual database on a hard-drive somewhere in the world.
Are the theorems really ranging over a model limited to the finite? In reality you get to choose if you conceptualise that the hard-drive is of infinite capacity or not. You, as interpreter, can imagine the model under the sentences (which could otherwise be under Z Notation, or some other notation) as ranging to the infinite. Just because one or two data structures reside on the hard drive does not limit the theory to the finite unless the interpreter submits to thinking that. That is, you have to submit your interpretation to one theory or another. The choice is yours.
The fundamental misconception of die-hard proponents of finite model theory is that an interpreter of sentences written on paper or a computer screen are bound to choose the intended theory under which the originator of the sentences intended the interpreter to use. At least those proponents unfamiliar with the game theory of logic and when….
We arrive at the notion of Ehrenfreucht Fraisse Games, and their extension to a duplicator (final interpreter) finding a different interpretation than the one proffered by the originator of the theorems. You and I just went through that process. We just played the game.
It is easy to imagine the case where a structure intended to be seen under finite model theory is seen to merely be a structure under a theory extending to first-order logic or even under functions of a higher order logic depending how you play the game. It really is up to the interpreter, and is merely an intellectual exercise, which to me borders on masochism, to stay under finite model theory where the interesting things of higher order logic can otherwise be done. Certainly denying the existence of an independent interpreter fundamentally mistakes the nature of logic and games themselves.
Where all of logic is seen to be one of playing games the fundamental misconception of finite model theory is not that it is not a valid theory, just that the misconception of theorems of finite model theory by an independent observer is equally as valid under Ehrenfeucht Fraisse Games. It makes for a richer world.
— — — — — — — — — — — — — — — —
