#first-order logic

[melimelomoi-blog]

From ∀ Gundam we can deduce ∃ Gundam.

[unfortunately-a-fangirl]

babe help im failing metaphysics

[supplies-handbags-km]

Forethoughted Math Admissibility and Due Reasoning Principles

Math logic is the systematic study of principles of valid supposition and correct reasoning. Logic is a form of natural geometry that is not at worst used for mathematical purposes, but is also whenever you wish used in philosophy, semantics and computer thermionics. It examines the common forms as respects arguments in passage to peg between forms that are sufficient and fallacies. Philosophers use doctrine of terms to mind epistemology, onus and metaphysics. Mathematicians specialize in boolean algebra to study valid inferences within limited language, for example well as in the argument theory.<\p>

Logic was aborigine established by Aristotle. Aristotle made logic a cornerstone incomplete in connection with philosophy congruent with establishing it by what name exhaustive of his disciplines. He made logic part of the classical trivium. <\p>

Mathematical logic is divided into the fields of set theory, solder feeling, recursion thinking and proof theory. The in readiness explanation studies sets, or collections of objects. It examines the binary relation between a nature of objects. The model theory examines mathematical structures using faithful logic. The mathematical structures examined using the model conclusion are models for formal languages and the structures that ascribe meaning over against the sentences of the formal languages. The fugue form theory itself is very similar to algebra in form and run.<\p>

The recursion theory, also known as the computability theory studies computable functions and Turing degrees. The recursion theory addresses brain set back functions and natural card games. This form of math logic is very similar so that estimator information and is commonly used in a revival in relation with computer science careers. The proof basis is the study in reference to proofs as formal arithmetical objects. Proofs are presented as data structures in the marshal of plain lists, box lists, or trees. Tree lists are constructed according to the form as regards axioms and the rules apropos of inference relating front in passage to the logical system. The proof theory, alongside wherewith the model theory, the axiomatic set theory and the recursion memory-trace, navigate the four pillars in reference to the foundations of mathematics. <\p>

Beginning and end of the fields of mathematical logic share the basic ideas of first-order logic and definability. First-order logic is a formal presence of mind system to deal in addition to simple declarative propositions, predicates and correction. It is a deductive line of action frequently used in philosophy.<\p>

Definability functions inflowing arithmetical philosophical speculation as a definable set. The definable set is an n¬-ary regarding in contact with the domain of a structure whose halcyon days are the elements that satisfy a formula streamlined the language of the designated structure. These sets are specific because they are not limited to parameters. <\p>

Incisive mathematical ontology and correctly recognizing moral principles allows mathematicians, philosophers, and people serving a variety of careers to deductively reason between valid and false points. <\p>

[vegetarianbacon]

Related

I think I should automatically ace my logic class for just having tagged a tumblr post "first-order logic"

[word-association]

Things you provably can't do in first-order logic

Express connectivity in a graph, that sort of thing. 

"Why graphs?"

Graphs are cool. The railway network from here? That's totally a graph:

And you can represent graphs in first-order logic. All you need are individual constants for the vertices and a binary relation \(\mathsf{E}(x,y)\) for the edges. 

\[\ast\ast\ast\]

\[\exists x \forall y \mathsf{E}(x,y)\]

Or that any two different vertices have an edge going from one to the other:

\[\forall x \forall y (x \neq y \rightarrow \mathsf{E}(x, y))\]

Or that any vertex is connected to exactly one vertex:

\[\forall x \exists y (\mathsf{E}(x,y) \wedge \forall z (\mathsf{E}(x, z) \rightarrow y = z))\]

Or that there's a path of length 2 connecting any two vertices:

\[\forall x \forall y \exists z_1 (\mathsf{E}(x, z_1) \wedge \mathsf{E}(z_1, y) \wedge x \neq z_1 \wedge y \neq z_1\]

What you're basically trying to capture here is this situation:

Other properties, like connectivity, you can't express.

\[\ast\ast\ast\]

"What's connectivity?"

Connectivity is when between any two nodes of a graph there's a path of some finite length \(k \in \mathbb{N}\).

"Like, an edge?"

That's one possibility, when \(x\) and \(y\) are directly connected by edge. But you can also have an edge going out from \(x\) to something that has an edge going to something that has an edge etc., all the way to \(y\).

\[\ast\ast\ast\]

"Why can't you express that?"

Suppose you can. Suppose there's a first order formula \(\phi\) that expresses connectivity for a graph.

Now take two new constants \(a\) and \(b\) and consider the following formulas:

\[\psi_1 = \lnot \exists z_1 (\mathsf{E}(a, z_1) \wedge \mathsf{E}(z_1, b) \wedge a \neq z_1 \wedge b \neq z_1)\]

\[\psi_2 = \lnot \exists z_1 \exists z_2 (\mathsf{E}(a, z_1) \wedge \mathsf{E}(z_1, z_2) \wedge \mathsf{E}(z_2, b) \wedge \bigwedge (a \neq z_i \wedge b \neq z_i \wedge z_i \neq z_j))\]

\[\dots\]

\[\psi_n = \lnot \exists z_1 \dots \exists z_n (\mathsf{E}(a, z_1) \wedge \dots \wedge \mathsf{E}(z_n, b) \wedge \bigwedge (a \neq z_i \wedge b \neq z_i \wedge z_i \neq z_j))\]

\(\psi_1\) says that there is no path of length 2 from \(a\) to \(b\). \(\psi_2\) says that there is no path of length 3 from \(a\) to \(b\), and so on. \(\psi_n\) says that there is no path of length \(n+1\) from \(a\) to \(b\). There's an infinite number of \(\psi_i\)'s, one for each \(n \in \mathbb{N}\).

Now we can do business. Take the following sets of sentences:

\[\mathcal{A} = \{\psi_i \mid i \in \mathbb{N}\}\]

\[\mathcal{B} = \{ \lnot \mathsf{E}(a, b), a \neq b\}\]

\[\mathcal{C} = \{ \phi\}\]

The claim is that \(\mathcal{A} \cup \mathcal{B} \cup \mathcal{C}\) has a model. But this is bad, because in this model we have that any two nodes are connected (because \(\phi\) is true in it), which means that there's a path of finite length between them. However, when you consider \(a\) and \(b\) you realize that there can be no finite path between them. Because of all the \(\psi_i\)'s and \(\mathcal{B}\) there isn't a path of length 1, or 2, or 3, or any finite number. So the assumption that \(\phi\) expresses connectivity leads to a contradiction.

\[\ast\ast\ast\]

"Why does \(\mathcal{A} \cup \mathcal{B} \cup \mathcal{C}\) have a model?"

Because of the Compactness theorem.

"What's that about?

It says that a set of first-order formulas has a model iff each of its finite subsets has a model.

"That's really a thing?"

Yeah, it's how you usually show that infinite sets of sentences have models.

\[\ast\ast\ast\]

"So how do you know that every finite subset of \(\mathcal{A} \cup \mathcal{B} \cup \mathcal{C}\) has a model?"

Ah, well let's see.

Most of the combinations are easy. For instance, each of \(\mathsf{B}\), \(\mathsf{C}\) and \(\mathsf{B} \cup \mathsf{C}\) has a model, for instance this works for all of them:

The interesting case is \(\mathcal{B}\) plus \(\mathcal{C}\) plus a finite subset \(\mathcal{A}^\prime\) of \(\mathcal{A}\). In this case take the largest index \(n\) in \(\mathcal{A}^\prime\) and define a model where there's only a path of length \(n+2\) from \(a\) to \(b\):

You can see that this graph is connected (i.e. \(\phi\) is true), and each of the \(\psi_i\)'s in \(\mathcal{A}^\prime\) is true, because there is no path of length \(n+1\) or smaller between \(a\) and \(b\).

\[\ast\ast\ast\]

This is cool, no?

"What? Sorry, I dozed off."

[word-association]

Things you can't do in first-order logic

When it comes to first-order logic, you can't always get what you want--especially if what you want is to answer higher level queries over a database. 

But if you try sometimes well you might find etc.

(by the way, I'll be drawing heavily on the first chapter of Libkin [2012])

\[\ast\ast\ast\]

There's a small piece of the universe you're interested in and you have thorough knowledge on, the railway network (because you're German).

So you set up a database where you represent the connections in the railway network. You think about what sort of language to use to represent this knowledge, and go for first-order logic (because you're German).

The stations are: \(\mathsf{berlin}\), \(\mathsf{dortmund}\), \(\mathsf{hamburg}\), \(\dots\), and the relevant relations: \(\mathsf{Station}(x)\), \(\mathsf{Connection}(x,y)\), and that seems enough so let's keep to this vocabulary.

With sturdy optimism you now fill out the database with facts:

\[\mathsf{Station(berlin)}. \\\ \mathsf{Station(dortmund)}. \\\ \mathsf{Station(hamburg)}. \\\ \mathsf{Connection(berlin, hamburg)}.\\\ \dots\]

\[\ast\ast\ast\]

Very nice, but now you want to retrieve information from this database and allow others to retrieve information from it (because).

You set up some basic mechanism for query answering. Since you used first-order logic to represent the domain (the railway network), it seems natural that queries should also be first-order logic formulas and that they should be evaluated in the most intuitive way, according to the usual semantics.

For instance, when you ask

\[\mathsf{Station(berlin)} \wedge \mathsf{Station(hamburg)} \wedge \mathsf{Connection(berlin, hamburg)}\]

you'll get the answer \(\mathsf{yes}\). When you ask

\[\mathsf{Connection(berlin, dortmund)}\]

you'll get the answer \(\mathsf{no}\). And so on.

Which isn't bad, but you want to market your contraption. So the public needs to be able to ask more interesting queries--not just \(\mathsf{yes}\) or \(\mathsf{no}\) queries, but stuff that asks for more detailed information. For instance:

Where can I go from Berlin?

What connections are there from Berlin to Munich?

What is the shortest connection between Berlin and Munich?

That's ambitious. The first step is to allow your queries to admit sets of objects as answers: not only if there are connections from Berlin but also which are they.

This you do by putting free variables in your queries, for instance

\[q(y) = \mathsf{Connection(berlin, y)}\]

The left-hand side, \(q(y)\), showcases the free variable, which in this case is \(y\). The query reads, roughly:

"the y's such that Berlin is connected to y",

or

"stuff that Berlin is directly connected to".

The answer to \(q\) would be something like:

\[\{\mathsf{hamburg}, \dots\}\]

\[\ast\ast\ast\]

If you want to find pairs of stations where there's a direct connection from the first to the second, you write the query:

\[q_0(x,y) = \mathsf{Connected}(x,y)\]

Here \(x\) and \(y\) are the free variables, and the answer will be something like:

\[\{(\mathsf{berlin}, \mathsf{hamburg}), \dots\}\]

If you want to find stations that have exactly one intermediate stop between them, you write:

\[q_1(x,y) = \exists y_1 \mathsf{Connection}(x, y_1) \wedge \mathsf{Connection}(y_1, y) \wedge (x \neq y_1) \wedge (y \neq y_1)\]

If you want to find stations that have two intermediate stops you write:

\[q_2(x, y) = \exists y_1 \exists y_2 (\mathsf{Connection}(x, y_1) \wedge \mathsf{Connection}(y_1, y_2) \wedge \mathsf{Connection}(y_2, y) \wedge \\\ \bigwedge ((x \neq y_i) \wedge (y_i \neq y_j) \wedge (y_j \neq y))) \]

And so on. 

If you want to find stations that are connected either directly or by an intermediate stop, you write

\[q_{\leq 1} = q_0(x, y) \vee q_1(x,y)\]

If you want to find stations that have 2 or less intermediate stops you write

\[q_{\leq 2} = q_{\leq 1} \vee q_2\]

And so on. In general, if you want to find stations that have \(k\) or less intermediate stops, you write:

\[q_{\leq k} = q_{\leq (k-1)} \vee q_k\]

(notice the recursive step)

\[\ast\ast\ast\]

But what if you just want to find a generic connection, i.e. pairs that are connected somehow, with some number of intermediate stops between them (not a specific one)? What do you do then?

This is where things get hairy. Because what you'd want to ask is something like the following query:

\[\bigvee_{i \in \mathbb{N}} q_i\]

This is an infinite disjunction, so not really first-order logic material. And, it turns out, this query isn't expressible as a first order logic formula at all (I'll show a proof later).

\[\ast\ast\ast\]

Suppose you want to know if, among all the connection chains you can form, there is one which starts and ends with the same city. In other words, if you represent the \(\mathsf{Connection}\) relation as a graph, is there a first-order formula which gives you the nodes connected by a cycle? 

Turns out this isn't expressible either. 

\[\ast\ast\ast\]

Take \(|y|\) to be the number of stations connected to \(y\), i.e.

\[|y| = |\{x \mid \mathsf{Connected(x, y)}\}|\]

And suppose you want to find those pairs \((y_1, y_2)\) such that \(|y_1| = |y_2|\). Can you write a first order query that expresses this? 

Turns out no.

\[\ast\ast\ast\]

"This is bullshit."

First-order logic has these limitations on what you can express in it. You can't express recursion, you can't encode cardinality of sets--all kinds of neat things you have in, say, second-order logic. 

"Why does this matter?"

Databases are important in today's society. A lot depends on information being available where you put it, fast and in whatever form needed.

"Boring."

It's a multi-billion dollar industry. 

"Tell me more."

Query languages such as SQL (which at their core are variants of (a fragment of) first-order logic) implement special features for the kinds of things that are of practical interest, e.g. counting--you can ask for the number of individuals satisfying a certain property, and the SQL engine on your server will give it to you.

The interesting questions for database people are: what can you add (and what do you need to add) to a basic language like first-order logic (or some variant/fragment of it) to make it more expressive?

This is more complicated than it seems, because expressiveness usually has to be balanced out with computational complexity. Roughly put, the more expressive a language is the more complex it gets to perform operations in it.

For instance, one basic operation is query answering--given a query, to compute the answer. You want your database system to be able to do at least that, and to do it well (i.e. fast). No use in having a very expressive language if your database management system takes a million years to answer interesting queries in that language.

In the sections above I kind of glossed over this issue, but you can imagine that in a real world scenario query answering requires looking through the database and doing some checking. And especially if your database is large, this operation has the potential of getting very very consuming.  

So for real applications what you need to do is balance expressiveness with complexity of performing interesting tasks. You need to understand trade offs that can appear.

\[\ast\ast\ast\]

"Why are you telling me all this?"

I want to show you the proof that the generic connection property for stations (or, more accurately: the property that there's a path of some length \(k \in \mathbf{N}\) between two nodes of a graph), that this property isn't expressible as a first-order formula. 

[huggingthehorse-blog]

Logical Predicates and Ontological Commitment

When it is said that 'exists' is not a logical predicate what is meant is that it is not treated as one in first-order logic.  Although people habitually utter sentences containing 'exists' as a (grammatical) predicate, there is no need to do so; for example, instead of saying 'A good song by Nickelback does not exist', one can say 'no song by Nickelback is good' or 'for any song, that song will not be both by Nickelback and good": (x)(Nx→~Gx) or ~(∃x)(Nx•Gx).