Finite T-uples and the axiom of Regularity - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T04:36:51Z http://mathoverflow.net/feeds/question/67312 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/67312/finite-t-uples-and-the-axiom-of-regularity Finite T-uples and the axiom of Regularity Gérard Lang 2011-06-08T21:26:50Z 2011-06-09T16:19:51Z <p>Let V be the universe of sets (the class of all sets). Let U(0)=V, U(1)=V*V, the class that is cartesian product of the class V=U(0) with V, and for n>=1, let U(n+1)=U(n)*U(0); For every natural integer n, let T(n)=U(n+1)/U(n) be the class that is the difference of the class U(n+1) and of the class U(n). We are interested with the proposition (T): "For every member set x of V, there exists an unique natural number n such that x is a member element of U(n)." Question 1: Let ZFC be our set theory; does ZFC prove (T)? Question 2: Suppose that the answer to question 1 is YES, and let now our set theory be ZF- (I mean, ZF with omission of the axiom of regularity/foundation); does ZF- prove (T)? Question 3: suppose the answer to question 3 is NO; does ZF- prove the equivalence of (T) with the axiom of Regularity ? Gérard Lang</p> http://mathoverflow.net/questions/67312/finite-t-uples-and-the-axiom-of-regularity/67322#67322 Answer by Joel David Hamkins for Finite T-uples and the axiom of Regularity Joel David Hamkins 2011-06-08T22:58:27Z 2011-06-09T01:49:25Z <p>One can show inductively that $U(n+1)\subseteq U(n)$, and so the $T(n)$ are the differences in the descending hierarchy; thus, the question (T) amounts to whether the intersection of the $U(n)$ is empty. As you indicated in the comments, let's suppose that you use the usual Kuratowski encoding of ordered pair. In this case, both $x$ and $y$ are elements-of-elements of $\langle x,y,\rangle$. (And for most of the encodings of ordered pair, $x$ and $y$ are both in the transitive closure of $\langle x,y,\rangle$, which is the critical point.) </p> <p>The answer to question 1 is Yes. If a set $a$ is in every $U(n)$, then we may unwrap $a$, since it is pair $a=\langle a_0,b_0\rangle$, and $a_0=\langle a_1,b_1\rangle$, and so on, with $a_n=\langle a_{n+1},b_{n+1}\rangle$, and $a_{n+1}\in\in a_n$, meaning that it is an element of an element, and this violates the well-foundedness of the $\in$ relation, contrary to the foundation axiom. </p> <p>Similarly to your other recent question, the answer to question 2 is No. This is because it is relatively consistent with ZF- that there is a set $x$ such that $x=\{x\}$; such sets exist under the anti-foundation axiom. Note that $x=\{\{x\}\}=\{\{x\},\{x,x\}\}$, which is the same as $\langle x,x\rangle$. So $x$ is in every $U(n)$, violating (T). </p> <p>I don't know the answer to question 3, but I expect that a solution will similarly as in your other question, which seems more fundamental to me.</p> http://mathoverflow.net/questions/67312/finite-t-uples-and-the-axiom-of-regularity/67353#67353 Answer by Ali Enayat for Finite T-uples and the axiom of Regularity Ali Enayat 2011-06-09T16:19:51Z 2011-06-09T16:19:51Z <p>Question 3 also has a negative answer (Joel Hamkins has already answered the first two questions).</p> <p>The model $V(a,b,c)$ described in detail in my answer to an analogous <a href="http://mathoverflow.net/questions/67310/finitely-nested-singletons-and-the-axiom-of-regularity" rel="nofollow">question</a> works here as well since <em>$V(a,b,c)$ satisfies $ZF+T$, but <strong>not</strong> Foundation</em>.</p> <p>The reason that $T$ holds in $V(a,b,c)$ is similar to the reason that $S$ holds in the other question: any infinite descending epsilon sequence must eventually hit one of the elements $a$, $b$, or $c$, none of which is a Kuratowski-ordered pair (indeed, they are not ordered pairs in the sense of Wiener either).</p>