About a sentence in logic theory that I don't understand.

139 Views Asked by At

Can somebody explain to me the following terms in logic? I have to read a paper in combinatorics that says this, but I don't understand anything in this sentence, where the author speaks about logic. And this part appears to be essential for the paper. If someone has a text to indicate, I will appreciate it.

Let $T$ be a universal first-order theory with equality in a language $L$ containing only predicate symbols.

2

There are 2 best solutions below

3
On BEST ANSWER

I assume you're reading "Flag Algebras". Great! It's a wonderful paper. Being a logician myself, I very much appreciated that it was written in the language of logic, but I can see how that would put off some combinatorialists... On the other hand, if it forces them to learn some model theory, so much the better!

Let's talk about (undirected) graphs first. What is a graph? It's a set $V$ (the vertices), equipped with an edge relation $E$. For each pair of vertices $x,y$, either $x$ is connected to $y$ (we write $E(x,y)$) or not (we write $\lnot E(x,y)$).

We can think of this as working in the language $L = \{E\}$, where $E$ is a binary symbol (it accepts $2$ inputs). An $L$-structure in this language is a set together with an interpretation of the symbol $E$. That is, for every pair of vertices, we specify whether $E(x,y)$ is true or not.

But not every $L$-structure is a graph. In a graph (remember, I mean undirected graph), we expect that edges always connect distinct vertices (so we never have $E(x,x)$), and that edges are symmetric (so if $E(x,y)$, then $E(y,x)$).

We can capture these requirements with the axioms of the theory of graphs, $T_{\text{graph}}$:

  • $\forall x\,\lnot E(x,x)$
  • $\forall x\forall y\, E(x,y)\rightarrow E(y,x)$

These axioms are called universal axioms, because they have a specific logical form: a series of universal ("for all") quantifiers, followed by a statements involving just the symbols in the language ($E$), and logical symbols $=,\lnot,\land,\lor,\rightarrow,$ and the quantified variables.

$L$-structures satisfying these axioms are called models for $T_\text{graph}$. The models of this theory are exactly the (undirected) graphs.

Now Razborov wants to work in a more general setting, which can handle uniformly graphs, directed graphs, hypergraphs, partial orders, graphs omitting certain subgraphs, etc. etc.

A language $L$ containing only predicate symbols (more often called a "relational language") is a collection of symbols (like $E$ in the graphs example), each of which has an associated number of inputs. So if you're working with $3$-hypergraphs, you'll have a symbol $E(x,y,z)$.

A universal first-order theory in this language is collection of universal axioms (logical statements in the form I described above) identifying the structures you want to consider. To get comfortable with this, you should play around with this notion and try to write down universal axioms for the theories of directed graphs, $3$-hypergraphs, partial orders, linear orders, bipartite graphs, graphs not containing any triangles, etc.

For the basics of model theory, there are some excellent notes online by Dave Marker. Marker is also the author of a good textbook on the subject, Model Theory.

1
On

A first order language has sentences using $\forall,\exists,\lnot,\land,\lor$, variables and possibly function and predicate symbols. Predicate symbols denote ($n$-ary) relations for a fixed $n$. Equality is assumed to be among the binary relation symbols of $L$, and is always assumed to be interpreted as equality.

A theory is an axiom system, a set of sentences, built from the available symbols in $L$.