What are some applications of Mathematical Logic?

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?

Advertisements

Leave a comment

Filed under Life

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s