# Is “reflexive transitive closure of relation $R$” a first-order property?

Suppose I have a language with two binary relation symbols $R$ and $R^\ast$. Suppose I have a first-order theory $T$ which says some things about $R$, but nothing about $R^\ast$. Is there a set of axioms I can add to $T$ which say that $R^\ast$ is the reflexive, transitive closure of $R$? (Ideally the axioms would make this actually be true in the model; but some sort of solution that comes short of that would also be of interest.) Clearly this can be done in second-order logic; but can it be done in first-order logic? I'm guessing it can't be done, but in that case an impossibility proof would be quite interesting to see.

-
Do you have a specific $T$ in mind? –  Asaf Karagila Feb 5 '13 at 9:27
Asaf: For the purposes of this question, no. Is there an interesting special case you have in mind? –  Nick Thomas Feb 5 '13 at 9:28
Well, not really, but I figured if you have any particular $T$ in mind it might be easier to answer if some constraints are given on $T$ (e.g. such and such property can be expressed in $T$, or so on). I'll give it some more thought... –  Asaf Karagila Feb 5 '13 at 9:30

It is fairly obvious that $R^*$ can be axiomatised in the logic $L_{\omega_1 \omega}$ using an $\omega$-indexed disjunction, but in fact it cannot be axiomatised in finitary first-order logic.

Consider the following theory $\mathbb{T}$:

1. There is a unique element $z$ such that there does not exist an element $y$ such that $y \mathrel{R} z$.

2. For each element $x$ there is a unique element $y$ such that $x \mathrel{R} y$.

3. $R^*$ is the reflexive-transitive closure of $R$.

4. For $z$ as in axiom 1, for all elements $x$, $z \mathrel{R^*} x$.

Let $M$ be a model of $\mathbb{T}$. Clearly, $M$ is countably infinite: in fact it has to be a model of second-order arithmetic. So if $\mathbb{T}$ were axiomatisable in finitary first-order logic then this would contradict the upward Löwenheim-Skolem theorem.

-

It depends completely on which first-order language you use. If you want to just use the language with only the symbols $R$ and $R^*$, you can express that $R^*$ is a reflexive transitive relation extending $R$, but you cannot express in this language that $R^*$ is the smallest relation extending $R$. The proof that this cannot be done uses the compactness theorem, and is a somewhat standard exercise for people used to such exercises. I'll put it below, in case you don't see how to do it.

If you move to the first-order language of set theory, then you certainly can express that $R^*$ is the reflexive, transitive closure of $R$. I want to point this out because it shows that the issue is entirely about the language and axioms, not about the term "first-order".

Here is the compactness proof. We will just worry about the transitive closure, for simplicity. Recall that the transitive closure $R^*$ is the union of a sequence of relations $$R = R_0 \subseteq R_1 \subseteq \cdots$$ where $R_{i+1}$ includes a pair $(a,c)$ if there is a $b$ such that $(a,b)$ and $(b,c)$ are in $R_{i}$. In other words, viewing the original $R$ as a graph, $R_{i}(a,b)$ holds if and only if there is a path of length $\leq i+1$ from $a$ to $b$ in the graph.

Let $\Gamma$ be any set of sentences in the language $(R,R^*)$ that is satisfied when $R^*$ is the transitive closure of $R$. Add two new constant symbols $a$ and $b$ to the language, and add axioms sying that $R^*(a,b)$ holds and $R(a,b)$ does not. Finally, add an infinite sequence of axioms that says that $R_1(a,b)$ is false, $R_2(a,b)$ is false, etc. Here is how to do this for $R_1$ and $R_3$, you can see the pattern: $$R_1(a,b) \equiv (\exists x)[R(a,x) \land R(x,b)]$$ $$R_3(a,b) \equiv (\exists x)( \exists y)(\exists z)[R(a,x) \land R(x,y) \land R(y,z) \land R(z,b)]$$

Now the resulting theory $T = \Gamma \cup \{\lnot R(a,b), R^*(a,b), \lnot R_1(a,b), \lnot R_2(a,b),\ldots\}$ is finitely satisfiable, because any finite subset is satisfied by starting with $R$ from a finite, linear graph of sufficient length, letting $a$ and $b$ be the endpoints and $R^*$ be the transitive closure. Thus the entire theory is satisfiable. In a model of $T$, $R^*$ is not the transitive closure of $R$ because $R^*(a,b)$ holds but, by construction, $(a,b)$ is not in the transitive closure of $R$ in that model. Thus $\Gamma$ did not ensure that $R^*$ is the transitive closure of $R$.

-
How do we avoid the problem where the model of set theory has a non-standard natural number? –  Zhen Lin Feb 5 '13 at 14:07
@Zhen Lin: there is a difference in the usual meaning of "express" when we talk about the language of set theory or arithmetic; it means that the natural language reading of the formula has the desired meaning. So ZFC proves that every relation has a transitive closure, even though in nonstandard models the closure might be "too big". Similarly PA is able to express that a number is prime, even though it has nonstandard models. The meaning of "express" for the purposes of compactness arguments like above is somewhat different, which makes the literature somewhat confusing. –  Carl Mummert Feb 5 '13 at 14:54
To be precise, I could say that the class of models in the signature $(R,R^*)$, where $R$ is a relation and $R^*$ is the transitive closure, is not an elementary class; on the other hand there is a formula in the language of set theory which expresses the concept "$R^*$ is the transitive closure of $R$". Indeed ZFC proves "every relation has a transitive closure" so ZFC would be, in a particular sense, a set of axioms that gives a positive answer to the original question. –  Carl Mummert Feb 5 '13 at 14:57