One application, particularly of finite model theory, is in databases.

For example, if you think of a relational database as a structure, where elements in the columns of the db form the structure's universe and tables form the relations, then you can ask what kinds of db queries are or aren't expressible.

Here's an illustration. Suppose you have a Quora-like database that contains a single "Following" table, where (Alice, Bob) is a row in the table if Alice is following Bob. A query like "give me all the people following Alice" is expressed in SQL by

select follower from following

where followed = 'alice'

and in first-order logic by

q(x)=Following(x,"Alice") q(x) = Following(x, "Alice")

But what if we want to ask a more complicated query, like "is the follow graph connected?" or "give me all the followers of Alice, the followers of followers of Alice, the followers of followers of followers of Alice, etc."? (In graph-theoretic terms, we want to express graph connectivity and directed reachability.)

Finite model theory can help answer whether these queries are expressible in SQL (they're not), how we would need to design a db language in order to express these queries (e.g., first-order logic alone can't ask whether Alice and Bob have the same number of followers, but SQL has first-order logic plus counting, so it can), and what we would lose and gain by using this other language.

Answer by Edwin Chen:

One application, particularly of finite model theory, is in databases.

For example, if you think of a relational database as a structure, where elements in the columns of the db form the structure's universe and tables form the relations, then you can ask what kinds of db queries are or aren't expressible.

Here's an illustration. Suppose you have a Quora-like database that contains a single "Following" table, where (Alice, Bob) is a row in the table if Alice is following Bob. A query like "give me all the people following Alice" is expressed in SQL by

select follower from following

where followed = 'alice'and in first-order logic by

[math] q(x) = Following(x, "Alice") [/math]

But what if we want to ask a more complicated query, like "is the follow graph connected?" or "give me all the followers of Alice, the followers of followers of Alice, the followers of followers of followers of Alice, etc."? (In graph-theoretic terms, we want to express graph connectivity and directed reachability.)

Finite model theory can help answer whether these queries are expressible in SQL (they're not), how we would need to design a db language in order to express these queries (e.g., first-order logic alone can't ask whether Alice and Bob have the same number of followers, but SQL has first-order logic

plus counting, so it can), and what we would lose and gain by using this other language.

What are some applications of Mathematical Logic?