**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 **A _{2}** and

**B**with universes A

_{2}_{2}= {1, 2, 3, 4} and B

_{2}= {1, 2, 3, 4, 5}. Obviously

**A**∈ EVEN and

_{2}**B**∉ EVEN.

_{2}**3.** Now we can show* that in a 2-move Ehrenfeucht-Fraisse Game (i.e. m = 2, what explains the subscrpts above) on **A _{2}** and

**B**the duplicator always wins, and thus

_{2}**A**and

_{2}**B**cannot be discriminated in FO, i.e.

_{2}**A**|= FO ⇔

_{2}**B**|= FO.

_{2}**4.** Next we have to scale the structures up by increasing m. For example for m = 3 we must find an **A**_{3} and **B**_{3} s.t. the duplicator wins the game. This can be achieved by A_{3} = {1, ..., 8} and B_{3} = {1, ..., 9}. More general, we choose A_{m} = {1, ..., 2m} and B_{m} = {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":

**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**

**Example** may also refer to:

- Example (musician), a British musician
*Example*, Florida rock band For Squirrels' sole major-label album, released in 1995- example.com, example.net, example.org, example.edu 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)