1
$\begingroup$

Is there some standard or natural way to characterize the properties which can be fixed by a quantifier free formula in first order logic? By this I mean properties $P$ for which there is some quantifier free $\phi$ such that, in any structure $A$, the relation defined by $\phi$ in $A$ has $P$.

Edit: In the comments, Alex Kruckman correctly elaborates on the question as pasted below. I thought there might be some well-known or easy result about homomorphisms on Boolean algebras that provides part of a general characterisation of the properties in question.

Here's Kruckman:

"There are three reasonable ways of reading it, I think: 1. "For which properties P of relations is there some language L and some quantifier-free L-formula φ such that in any L-structure A, the relation defined by φ in A has P?" 2. "Fix a language L. For which properties P of relations is there some quantifier-free L-formula....?" 3. "Fix a language L. For which properties P on L-structures is there some quantifier-free L-formula....?" – Alex Kruckman

"The difference between 2 and 3 is that in 3 properties can take into account the underlying L-structure. I.e. I would call "R is a subrelation of the interpretation of the symbol <" is a property of relations on L-structures (i.e. it is preserved by L-isomorphism), but not a property of relations. On the other hand, here are some examples of properties of relations: Is a subrelation of equality. Doesn't depend on the first coordinate. These have the behavior that you want, witnessed by the quantifier-free formulas R(x,y)∧x=y R(x,y)∧x=y and P(y)P(y) in the variable context (x,y)(x,y)." – Alex Kruckman

$\endgroup$
  • 2
    $\begingroup$ It's not very clear what you mean by "$\phi$ in $A$ has $P$". Is $P$ a property of structures or formulas or what? $\endgroup$ – Rob Arthan Oct 29 '16 at 19:15
  • $\begingroup$ Not "$\phi$ in $A$ has $P$" ... I said "the relation defined by $\phi$ in $A$ has $P$". $P$ is a property of relations. $\endgroup$ – dizzieG Oct 30 '16 at 2:14
  • $\begingroup$ @dizzieG The properties which are defined by formulas are properties of tuples, not properties of relations. E.g. the formula $x < y$ defines the property of the tuple $(1,2)$ that $1$ is less than $2$. If you really mean $P$ to be a property of relations, then I don't understand at all what it means to say "$P$ is fixed by a quantifier free formula". Obviously I'm confused, so it's possible that I've totally misunderstood your question and my answer is useless to you. Let me know. $\endgroup$ – Alex Kruckman Oct 30 '16 at 2:23
  • 1
    $\begingroup$ Can you give an example of a property of relations that you might be interested in? Maybe my answer just says this: (In a finite relational language) The characteristic property of those relations definable by quantifier-free formulas $\varphi$ is that whether they hold of a tuple $\overline{a}$ depends only on the induced substructure on $A = \overline{a}$. $\endgroup$ – Alex Kruckman Oct 30 '16 at 2:25
  • 1
    $\begingroup$ I agree, it is not at all clear what you are asking. Maybe it would help if you gave some examples of properties you have in mind. Generally speaking, in a complete theory, any relation can be quantifier-free definable if you just expand by definitions, and with the empty theory, almost any relation can be pretty much anything depending on the structure. $\endgroup$ – tomasz Oct 30 '16 at 2:28
1
$\begingroup$

Edit: I now understand that what I wrote below answers a different question than what the OP intended. But I spend some time writing it, so I'm inclined to leave it here in case it helps someone else with a similar question in the future.

First assume we're in a finite relational language. Then a property of $n$-tuples, $P$, is definable by a quantifier-free formula $\varphi(x_1,\dots,x_n)$ if and only if whether $P$ holds of a tuple $\overline{a}$ from a structure $M$ only depends on the induced substructure $A = \{a_1,\dots,a_n\}$. That is, whenever $\overline{b}$ is another tuple from a structure $N$, such that the map $a_i\mapsto b_i$ is an isomorphism $A\cong B = \{b_1,\dots,b_n\}$, then $P$ holds of $\overline{a}$ if and only if it holds of $\overline{b}$.

Why? Well, if $P$ is definable by $\varphi(\overline{x})$ quantifier-free, then $$M\models \varphi(\overline{a})\iff A\models \varphi(\overline{a}) \iff B\models \varphi(\overline{b}) \iff N\models \varphi(\overline{b}).$$ And conversely, since we're in a finite relational language, there are only finitely many atomic formulas in the variables $x_1,\dots,x_n$ (each available relation, applied to each available tuple of variables of the appropriate length). So for each possible assignment of "true" and "false" to all the atomic formulas (e.g. $R(x,y)$ is true, $R(x,x)$ is false, etc.), we get a "complete formula": the conjunction of all the atomics, either negated or not (e.g. $R(x,y)\land \lnot R(x,x)\land \dots$). This complete formula describes the isomorphism type of a tuple of elements. So $P$ is definable by a disjunction of complete formulas: the ones describing the isomorphism types of the tuples satisfying $P$.

Incidentally, this shows that any quantifier-free formula is equivalent to a disjunction of complete formulas.

If we're in an infinite language or one with function symbols, things get a little more complicated. Note that any quantifier-free formula $\varphi(\overline{x})$ only mentions finitely many of the symbols in the language (i.e. it's a formula in the finite sublanguage $F$), and there is a finite bound $n$ on the complexity of the terms appearing (i.e. $n$ is the number of times you need to apply function symbols when building up the terms in $\varphi(\overline{x})$). When we restrict ourselves to this finite sublanguage and this term complexity, we find that there are only finitely many terms, and hence only finitely many atomic formulas (each available relation, applied to each available tuple of terms of the appropriate length), so we can play the same game as above and get "complete formulas" for $F$ and $n$.

Now applying the same argument as above, we get the following slightly awkward condition:

  • For any finite sublanguage $F$ and complexity bound $n$, given a tuple $\overline{a}$ from a structure $M$, we can look at the partial substructure $\langle \overline{a}\rangle_{F,n}$ generated by $\overline{a}$, which is the set of all elements in $M$ obtained from $\overline{a}$ and the constants in $F$ by the application of at most $n$ functions from $F$. This is the partial substructure of $M$ generated by $\overline{a}$, constrained by $F$ and $n$.

  • A property of $n$-tuples, $P$, is definable by a quantifier-free formula $\varphi(x_1,\dots,x_n)$ if and only if there is a finite sublanguage $F$ and a complexity bound $n$ such that whenever $\overline{a}$ and $\overline{b}$ are tuples from structures $M$ and $N$, and the map $\langle \overline{a}\rangle_{F,n}\to \langle \overline{b}\rangle_{F,n}$ induced by the map $a_i\mapsto b_i$ is a partial isomorphism, then $\overline{a}$ satisfies $P$ if and only if $\overline{b}$ satisfies $P$.

You could gloss this by saying that $P$ is definable by a quantifier-free formula if and only if whether $P$ holds of $\overline{a}$ just depends on the relations between the elements "close to $\overline{a}$": the ones which you can obtain from $\overline{a}$ by applying a finite set of function symbols a bounded number of times.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.