Is "reflexive transitive closure of relation $R$" a first-order property?

Question

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.

Answer 1

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.

Answer 2

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$.