Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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 V*V 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 V*V. 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
show 1 more comment

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
Thank you. Gérard Lang –  Gérard Lang Jun 9 '11 at 18:44
add comment

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.