Finite T-uples and the axiom of Regularity - MathOverflow

Finite T-uples and the axiom of Regularity

2011-06-08T21:26:50Z

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

Answer by Joel David Hamkins for Finite T-uples and the axiom of Regularity

2011-06-08T22:58:27Z

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.

Answer by Ali Enayat for Finite T-uples and the axiom of Regularity

2011-06-09T16:19:51Z

Question 3 also has a negative answer (Joel Hamkins has already answered the first two questions).

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