Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
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

2 Answers 2

up vote 6 down vote accepted

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.

share|improve this answer

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

share|improve this answer
    
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
1  
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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