Finite Model Theory - Basic Challenges - Characterisation of A Class of Structures - 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

Other articles related to "example":

Wave Front Set - Definition - Example
... Then the projection on the first component of a distribution's wave front set is nothing else than its classical singular support, i.e ... the complement of the set on which its restriction would be a smooth function ...

Example may also refer to:

  • Example (musician), a British musician
  • Example, Florida rock band For Squirrels' sole major-label album, released in 1995
  •,,, and .example, domain names reserved for use in documentation as examples
  • HMS Example (P165), an Archer-class patrol and training vessel of the British Royal Navy
  • The Example, a 1634 play by James Shirley
  • The Example (comics), a 2009 graphic novel by Tom Taylor and Colin Wilson

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)