Timeline for Can epsilon-induction be derived from the transitive closure operator?
Current License: CC BY-SA 3.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 8, 2016 at 21:20 | comment | added | Emil Jeřábek | The comments show that your property is provable in a weak fragment of set theory without epsilon induction, hence it is of no help whatsoever to prove epsilon induction. So the other axioms you need are epsilon induction itself, or foundation, or any other its equivalent formulation. | |
| May 7, 2016 at 14:30 | comment | added | L. C. | By epsilon induction I of course mean: $(\forall x(\forall y\in x.\psi(y)\rightarrow \psi(x)))\rightarrow\forall x \psi(x)$ | |
| May 7, 2016 at 14:30 | comment | added | L. C. | Thanks for all of your comments, but I am afraid I still don't see how they answer my (intended) question. Perhaps I should be more accurate. Assume that for any given binary relation $R$ (or for every first-order formula with two variables for that matter), its transitive closure is available, denote it by $R^{+}$. A key property of $R^{+}$ is the one mentioned in my original post: If $R(x,y)\subseteq P(x,y)$ and P is transitive, then $R^{+}(x,y)\subseteq P(x,y)$. My question is, what (if any) other axioms are needed in order to prove epsilon induction? (If this is at all possible) | |
| May 7, 2016 at 11:20 | comment | added | მამუკა ჯიბლაძე | @EmilJeřábek Thanks for the correction, yes, I (should) mean $\bigcup\bigcup$. | |
| May 7, 2016 at 10:16 | comment | added | Emil Jeřábek | 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. | |
| May 7, 2016 at 8:40 | review | Close votes | |||
| May 12, 2016 at 3:02 | |||||
| May 7, 2016 at 8:30 | comment | added | Emil Jeřábek | You mean $\bigcup\bigcup R$. | |
| May 7, 2016 at 7:51 | comment | added | მამუკა ჯიბლაძე | On the afterthought - one may, if there is a wish, use union instead of separation: $\bigcup R$ may serve as one such $X$ (with the Kuratowski style ordered pairs, i. e. if $R(x,y)$ is taken to mean $\{\{x\},\{x,y\}\}\in R$). | |
| May 7, 2016 at 7:46 | comment | added | მამუკა ჯიბლაძე | @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$. | |
| May 7, 2016 at 7:27 | comment | added | L. C. | I do mean transitive closure of relations, not of sets. The form of induction I stated for the transitive closure basically states that $R^{+}$ is the minimal transitive relation that contains $R$.I do not see however why seperation and powerset suffice in this case. Could you please elaborate some more? Many thanks! | |
| May 6, 2016 at 23:45 | answer | added | Joel David Hamkins | timeline score: 5 | |
| May 6, 2016 at 22:38 | comment | added | Asaf Karagila♦ | @მამუკაჯიბლაძე: Oh, you're right. I didn't notice that. In this case probably separation and power set suffice. | |
| May 6, 2016 at 22:36 | comment | added | მამუკა ჯიბლაძე | I thought it was about transitive relations, not sets. That is, any relations, not necessarily coinciding with membership. Is not this the case? | |
| May 6, 2016 at 22:26 | comment | added | Asaf Karagila♦ | @მამუკაჯიბლაძე: Not necessarily. But also how does that ensure that you can find a transitive set containing $R$? | |
| May 6, 2016 at 22:19 | comment | added | მამუკა ჯიბლაძე | @AsafKaragila $R\subseteq X^2$ for some set $X$, no? | |
| May 6, 2016 at 20:46 | comment | added | Asaf Karagila♦ | @მამუკაჯიბლაძე: And there are such sets because? | |
| May 6, 2016 at 20:33 | comment | added | მამუკა ჯიბლაძე | @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$? | |
| May 6, 2016 at 20:14 | comment | added | Andrej Bauer | You probably mean "Can we derive epsilon-induction" from existence of transitive closure operator, yes? | |
| May 6, 2016 at 19:21 | comment | added | Asaf Karagila♦ | $\in$-induction is equivalent to Foundation; but the existence of transitive closures requires only some instance of Replacement, Infinity and Union. | |
| May 6, 2016 at 19:18 | history | asked | L. C. | CC BY-SA 3.0 |