# Finite T-uples and the axiom of Regularity

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

• Do you mean $T(n)=U(n)-U(n+1)$? Also, you haven't specified which encoding of ordered pairs you are using, but it would seem the answer might depend on it. – Joel David Hamkins Jun 8 '11 at 22:11
• YES, I mean T(n)=U(n)-U(n+1); thank you very much ! I suspected the answers could depend of how to define ordered pairs, but was not able to clearly see that. So let's say we choose the classical Kuratowski (1921) definition; but the choice of the wiener definition (1914) should also be interesting. GL – Gérard Lang Jun 8 '11 at 22:17
• I think the way I was brought up, $V*V$ would come out to be $V$ again... – Kevin Buzzard Jun 8 '11 at 22:18
• I thought that VV would be the subclass of V containing all sets that are considered as ordered pairs, so that the singleton of x that can be considered as a pair, but not as an ordered pair (or couple) is a member of V, but not of VV. Gérard Lang – Gérard Lang Jun 8 '11 at 22:45
• Gerard, I think you have a typo in the statement of (T), since you want x to be in a unique $T(n)$ rather than $U(n)$. (Also, the tag should be "set-theory", not "set" plus "theory". – Joel David Hamkins Jun 8 '11 at 22:45

The model $V(a,b,c)$ described in detail in my answer to an analogous question works here as well since $V(a,b,c)$ satisfies $ZF+T$, but not Foundation.

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

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

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.

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

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.

• Oups! I made a small correction, but I now think you meant what you originally wrote... – François G. Dorais Jun 9 '11 at 1:53
• Yes, I had meant what I wrote originally, since that is how I had conceived it, but your correction is also true, since x={x} anyway. So it doesn't matter! Indeed, we can nest in a few more layers of braces and it would be the same set! – Joel David Hamkins Jun 9 '11 at 2:01