0
$\begingroup$

I was wondering (and could not seem to prove or disprove) if epsilon-induction could be derived from the transitive closure operator for binary relations, if we do not have the Foundation Axiom.

The induction of the transitive closure operator is of the form: If $R(x,y)\subseteq P(x,y)$ and P is a transitive relation, then $R^{+}(x,y)\subseteq P(x,y)$.

I have a hunch that this rule is strong enough to prove epsilon-induction even if we do not assume Foundation, but I may be wrong of course.(It is enought to prove the induction on N by itself). Perhaps some other weaker assumption is needed. I'd appreciate your help on this topic.

Improve this question
$\endgroup$
17
  • 1
    $\begingroup$ $\in$-induction is equivalent to Foundation; but the existence of transitive closures requires only some instance of Replacement, Infinity and Union. $\endgroup$
    – Asaf Karagila ♦
    Commented May 6, 2016 at 19:21
  • 1
    $\begingroup$ You probably mean "Can we derive epsilon-induction" from existence of transitive closure operator, yes? $\endgroup$
    – Andrej Bauer
    Commented May 6, 2016 at 20:14
  • 1
    $\begingroup$ @AsafKaragila I believe one does not even need that much - what do you really need to be able to intersect all transitive relations containing $R$? $\endgroup$
    – მამუკა ჯიბლაძე
    Commented May 6, 2016 at 20:33
  • 1
    $\begingroup$ @L.C. Once you can find any set $X$ which contains all $x$ and all $y$ satisfying $R(x,y)$, you just intersect all sets which are elements of the powerset of $X\times X$, which are transitive relations and which contain $R$. $\endgroup$
    – მამუკა ჯიბლაძე
    Commented May 7, 2016 at 7:46
  • 2
    $\begingroup$ It’s unclear if the question is about relations that are sets, or if $R$, $R^+$, $P$ are allowed to be proper classes. In the latter case, one can define $R^+(x,y)$ as “there exists $n\in\omega$ and a function $f\colon(n+1)\to V$ with $f(0)=x$, $f(n)=y$, and $R(f(i),f(i+1))$ for all $i<n$”. (I don’t need $\omega$ here to be a set.) The property in the question will require full induction on $\omega$ to prove, but that’s it, basically; it should go through with only extensionality, pairing, union, and separation. No foundation needed. $\endgroup$
    – Emil Jeřábek
    Commented May 7, 2016 at 10:16

1 Answer 1

Reset to default
5
$\begingroup$

The answer is no. Let $\newcommand\ZFC{\text{ZFC}}\ZFC^-$ be the theory $\ZFC$ without the foundation axiom. One can build models of $\ZFC^-$, which violate the foundation axioms, from any model of ZFC. For example, there are models of Aczel's anti-foundation axiom AFA, which satisfy $\ZFC^-$.

In any such model, $\in$-induction will fail, since the class of well-founded sets is inductive, but is not everything. But meanwhile, this theory proves that every set has a transitive closure, since for any set $X$, simply let $X_0=X$, $X_{n+1}=\cup X_n$, and let $Y=\bigcup_n X_n$. It follows easily that $Y$ is transitive and it is the smallest transitive set containing $X$. (This argument uses axiom of infinity, replacement and union as Asaf mentioned in the comments).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the detailed answer. I do not however see (maybe this is obvious) how from this I get a refutation to the statement I mentioned. I was referring to the transitive closure of binary relations. $\endgroup$
    – L. C.
    Commented May 7, 2016 at 7:37
  • 1
    $\begingroup$ Ah, sorry I had misunderstood. But the idea is similar for that case. As Emil explains in his comment, you can prove that every binary relation $R$ has a transitive closure, simply by saying $x$ is related to $y$, if there is a finite path from $x$ to $y$ through $R$. This new relation is transitive, and it is the smallest transitive relation containing $R$. $\endgroup$
    – Joel David Hamkins
    Commented May 7, 2016 at 11:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .