First-order Logic and the Star-Free Languages

[DRAFT]

String models

Before we define our logic, we have to define strings in a bit more detail. That is, it is necessary to encode all the information that is necessary to identify a particular string. To do this we use model theory, the mathematical structure of language.

Continuing to fix our alphabet to \(\Sigma=\{a,b,c\}\), what information do we need to identify a particular string in \(\Sigma^*\) from any other? The model will be a representation of this information.

First, think about the string \(aaaa\) as opposed to \(aaaaaa\). What distinguishes the former from the latter, clearly, is that there are four symbols in \(aaaa\) whereas there are six in \(aaaaaa\). So we need to distinguish the number of elements in a string.

We do that by establishing a domain (also referred to as a universe) (D) of elements in the string. This is a finite set of objects that represent the elements in our structure. By convention, we will use an initial sequence of natural numbers, i.e. \[D=\{1,2,3,4,...,n\}\] for some finite \(n\). Thus, for example, the domain of the model for \(aaaa\) will be \(\{1,2,3,4\}\) and the domain for the model for \(aaaaaa\) will be \(\{1,2,3,4,5,6\}\).

Note: While we use numbers, there is no inherent order on these objects. We could instead be using symbols like \(\{\square,\triangle,\bigcirc,\diamondsuit\}\). But numbers are just easier.

Of course, \(\Sigma^*\) does not only contain strings of all \(a\)s. The string \(aaaa\) must also be distinguished from, say \(abaa\). So we have to specify the symbols that are associated with elements in the string. We do this using relations on the domain in the model. A relation \(R\) is a unary relation (or property) or simply a subset of the domain: \[R\subseteq D\]

So we can add a unary relation \(R_b\) that indicates which elements are (b)s. Thus the model for \(aaaa\) would be \[M(aaaa)=\langle D=\{1,2,3,4\}; R_b=\{\}\rangle\] and the model for \(abaa\) would be \[M(abaa)=\langle D=\{1,2,3,4\}; R_b=\{2\}\rangle.\]

We are not yet done though. Consider \(abaa\) and \(aaba\). These are distinct strings, but their models will be equivalent: \[M(abaa)=\langle D=\{1,2,3,4\}; R_b=\{2\}\rangle\] \[M(aaba)=\langle D=\{1,2,3,4\}; R_b=\{3\}\rangle\] Note that the element in \(R_b\) is different in each of these models, given our numbering scheme, but these elements do not have any inherent order. So \(\langle D=\{1,2,3,4\}; R_b=\{3\}\rangle\) is isomorphic to \(\langle D=\{1,2,3,4\}; R_b=\{2\}\rangle\). That is, given the information available in the model, there is no way to tell the two apart.

So, we add a binary relation \(R_<\) that orders the elements in the model. A binary relation \(R\) consists of pairs of elements in the domain; i.e. \[R\subseteq D\times D\]

For example, for \(abaa\) we have \[M(abaa)=\langle D=\{1,2,3,4\}; R_b=\{2\}, R_<=\{(1,2),(2,3),(1,3),(1,4),(2,4),(3,4)\}\rangle\] and for \(aaba\) we have \[M(aaba)=\langle D=\{1,2,3,4\}; R_b=\{3\}, R_<=\{(1,2),(2,3),(1,3),(1,4),(2,4),(3,4)\}\rangle.\]

Now these are different (i.e., non-equivalent) models! In \(M(abaa)\), the element in \(R_b\) is only preceded by one other element; in \(M(aaba)\), the element in \(R_b\) is preceded by two. So now we have a way to distinguish strings in \(a\)s and \(b\)s, with one relation marking the \(b\)s and an ordering relation on the elements of the domain.

To also capture \(c\)s, we need to add another relation, \(R_c\). In fact, for any string signature, it's most straightforward to have a unary relation for each symbol in the alphabet. Thus, in this particular case, for any string model we'll need the unary relations \(R_a,R_b,R_c\) and the binary relation \(R_<\).

This set of relations \(R_1,R_2...,R_n\) is called a signature. We'll use calligraphic capital letters, e.g. \(\mathcal{S}\), to indicate signatures.

The signature we will use to represent strings in an arbitrary finite alphabet \(\Sigma=\{\sigma_1,\sigma_2,...,\sigma_n\}\) is as follows.

\[\mathcal{S}^<=\{R_{\sigma_1},R_{\sigma_2},...,R_{\sigma_n},R_<\}\]

To recap, a (finite) model is a mathematical object that lets us describe other objects. Formally, it is a tuple consisting of a set of elements or domain (or universe) \(D\) and a series of relations \(R_1,R_2,..., R_n\) on the domain.

\[\langle D; R_1, R_2, ..., R_n\rangle\]

The name of a particular set of relations that we use to model some set of structures is a signature.