We give a simple example of applications of FMT first and then some typical examples.

Some simple examples that show how elementary the issues are that FMT cares about:

• ...

A typical application area of FMT is database theory:

• Consider a companies' database that contains all managers together with the 'is superordinate' relation amongst them. In a proper hierarchy the database should contain no circles, i.e. a manager can not be a superordinate of his superordinate. Querying this corresponds to checking a graph for cyclicity. As from above this cannot be done in First Order Logic (FO).
• Say two managers want to find out if one of them is more powerful than the other. They need to query the database if the number of their subordinates is equal, i.e. the cardinalities of the sets of subordinates (say, directly and indirectly) is equal. This can't be done in FO ("FO cannot count"). This is the reason SQL is extended by a counting function.
• Consider a database${\displaystyle F}$ of airports and connection flights among them, where${\displaystyle F(x,y)}$means there is a direct flight from airport${\displaystyle x}$ to airport${\displaystyle y}$. We can write an order-zero query of the direct reachability of airport${\displaystyle b}$ from airport${\displaystyle a}$ as

${\displaystyle q_0(a,b)=F(a,b)}$.

Now in order to query connections with one change of plane we write

${\displaystyle q_1(a,b)={\mathrm{\exists }}_{c}F(a,c)\wedge F(c,b)}$ and get${\displaystyle Q_1(a,b)=q_0(a,b)\vee q_1(a,b)}$

for connections with zero or one change. Thus in order to extend this to reachability (of no matter how many changes) we have to write

${\displaystyle Q=\underset{k\in \mathbb{N}}{\bigvee }{q}_k}$

which is not a FO expression. So we are fine with FO for a restricted reachability up to a certain k but not for reachibility asit appears in graph theory. In fact it can be shown that reachability cannot be queried in FO.

• Book:Finite Model Theory