Example
We want to show that the property that the size of an orderered structure A=(A, ≤) is even, can not be expressed in FO.
1. The idea is to pick A ∈ EVEN and B ∉ EVEN, where EVEN is the class of all structures of even size.
2. Therefore we start with 2 ordered structures A2 and B2 with universes A2 = {1, 2, 3, 4} and B2 = {1, 2, 3, 4, 5}. Obviously A2 ∈ EVEN and B2 ∉ EVEN.
3. Now we can show* that in a 2-move Ehrenfeucht-Fraisse Game (i.e. m = 2, what explains the subscrpts above) on A2 and B2 the duplicator always wins, and thus A2 and B2 cannot be discriminated in FO, i.e. A2 |= FO ⇔ B2 |= FO.
4. Next we have to scale the structures up by increasing m. For example for m = 3 we must find an A3 and B3 s.t. the duplicator wins the game. This can be achieved by A3 = {1, ..., 8} and B3 = {1, ..., 9}. More general, we choose Am = {1, ..., 2m} and Bm = {1, ..., 2m+1} where we can prove that the duplicator always wins*. Thus EVEN on finite ordered structures cannot be expressed in FO, qed.
(*) Notice that the proof of the result of the Ehrenfeucht-Fraisse Game has been omitted, since it is not the main focus here.
Read more about this topic: Finite Model Theory, Basic Challenges, Characterisation of A Class of Structures
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)