Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Scott's trick is a method for constructing a set as a subset of a proper class. Specifically, let $A$ be a class (proper or otherwise), and let $$S(A)=\{x\in A:\forall y\in A,\operatorname{rank}(x)\le\operatorname{rank}(y)\}.$$

Then $S:\overline V\to V$ (where $\overline V$ represents the collection of all classes, a concept that cannot be formalized in ZF) satisfies three important properties: (1) $S(A)\subseteq A$, (2) $S(A)$ is a set, even if $A$ is not, and (3) $S(A)=\emptyset$ iff $A=\emptyset$.

I would like to generalize this construction to produce another function on $\overline V$ which satisfies the same properties, but does not require the Axiom of Regularity. The place where Regularity appears in the standard Scott's trick is in the proof of property (2), because assuming the negation of Regularity, there is a set $z$ with no rank, and a proper class of sets built from this set (say $z, \{z\}, \{\{z\}\}, \dots$ and continued by transfinite recursion), that also have no rank. Under the conventional definition of rank, $\operatorname{rank}(x)=\emptyset$ whenever $x$ has no rank, so if I take $A$ to be the class of sets containing $z$ described above, then all members of $A$ have the same rank, and thus $S(A)=A$ is also a proper class.

My question is if there is any way to construct a similar type of function that works even in such cases. Is it necessary to have a total order on all sets like $\operatorname{rank}$ in order for any such trickery to work? If so, I would guess that there is no way to do it without Regularity.

share|improve this question
    
Do you assume choice, or ZF without regularity? –  Asaf Karagila Feb 17 '13 at 0:28
1  
@AsafKaragila: do You sleep sometimes? :) –  Salech Alhasov Feb 17 '13 at 0:54
    
@Salech: Sometimes. –  Asaf Karagila Feb 17 '13 at 0:56
    
@Asaf I'll take an answer either way, although obviously I'd prefer to avoid Choice as well. Using choice, you could use cardinality as the "total order on all sets" I refer to, but for any (nonzero) cardinality, the collection of sets with that cardinality is a proper class, so you can't directly modify the procedure using $\operatorname{card}(x)$ in place of $\operatorname{rank}(x)$. –  Mario Carneiro Feb 17 '13 at 4:33
    
I think it might be impossible. Atoms can be used to create models of ZFA with anti-choice, but also for producing models of ZF-Reg+Anti-regularity. I think it might be possible to show that Scott tricks can always fail in some permutation model. I'm not sure though, and I need to brush up on regularity-breaking permutations. –  Asaf Karagila Feb 17 '13 at 4:36
show 2 more comments

1 Answer

Some assumption is needed: It is consistent with $\mathsf{ZFA}$ that there is a proper class of atoms, and there is no class function $C:V\to V$ with the property that $C(X)=C(Y)$ iff $|X|=|Y|$. This is due independently to Gauntt and to Lévy. Jech's The axiom of choice gives references.

On the other hand, a positive answer is possible in some situations: Assume $\mathsf{ZF}^-+\mathsf{AFA}$, that is, $\mathsf{ZF}$ with foundation replaced by the antifoundation axiom due independently to Aczel and Forti-Honsell. One can prove that any model of this theory is completely determined by its well-founded part $\mathsf{WF}$, in the sense that if $(M,\in^M)$ and $(N,\in^N)$ are models of $\mathsf{ZF}^-+\mathsf{AFA}$ and $\mathsf{WF}^M\cong\mathsf{WF}^N$, then $M\cong N$.

Let me review what $\mathsf{AFA}$ says precisely. Recall that a graph is a pair ${\mathcal G}=(G,E)$ where $G$ is a set and $E$ is a binary relation on $G$.

A decoration of ${\mathcal G}$ is an assignment $\pi$ of a set to each element of $G$ in such a way that for every $x\in G$, $\pi(x)=\{\pi(y)\colon y \mathrel E x\}$.

An apg (accessible pointed graph) is a graph $(G,E)$ with a distinguished point $p\in G$ such that every element of $G$ is accessible form $p$, (i.e., there is a finite sequence $p,p_1,\dots,p_n,q$ such that $q\mathrel E p_n\mathrel E\dots\mathrel E p_1 \mathrel E p$).

A picture of a set $x$ is an apg ${\mathcal G}$ with distinguished node $p$ admitting a decoration $\pi$ such that $\pi(p)=x$.

Working in $\mathsf{ZF}^-$, one can prove that every set has a picture. Mostowski's collapsing theorem states that every well-founded graph has a unique decoration. This easily implies that every well-founded apg is a picture of a unique set.

$\mathsf{AFA}$ is the statement that every graph has a unique decoration.

It follows from $\mathsf{AFA}$ that every apg is a picture of a unique set, and that non-well-founded sets exist. Moreover, every apg is equivalent to an apg on a well-founded set, where two apgs are equivalent iff they are pictures of the same set.

For references on antifoundation, and proofs of its consistency and the above claims, see

Peter Aczel. Non-well-founded sets. CSLI Lecture Notes 14, Stanford University, Center for the Study of Language and Information, Stanford, CA, 1988. MR0940014 (89j:03039),

and

Marco Forti, and Furio Honsell. Axioms of choice and free constructions principles, I. Bull. Soc. Math. Belg. Vol 36 (b) fasc. 1 ser. b (1984), 69-79. MR0739920 (85f:03054).

Since every apg is equivalent to a well-founded apg, we can make do in $\mathsf{ZF}^-+\mathsf{AFA}$ and indirectly implement Scott's trick: Given any class $C$ consider the class $C_{\mathsf{WF}}$ of well-founded apgs that are pictures of sets in $C$. If $C$ is non-empty, select a subset of $C_{\mathsf{WF}}$ using Scott's trick. The collection of corresponding sets is a subset of the class $C$.

share|improve this answer
1  
The lack of cardinal representatives was transferred to ZF by Pincus. He later wrote a paper about the consistency of representatives as well. –  Asaf Karagila Feb 25 '13 at 7:16
1  
The citation to Pincus paper in my previous comment is David Pincus, Cardinal representatives. Israel J. Math. 18 (1974), 321-344 (MR366666). –  Asaf Karagila Feb 25 '13 at 9:32
    
This is a well-written answer with good references, but it discusses slightly different questions than the one I posed, so I can't award the bounty just yet. If I understand you correctly, though, you are saying that a Scott's trick can be implemented in ZF-reg+(Aczel's antifoundation)? –  Mario Carneiro Feb 25 '13 at 12:50
    
Mario: The Gaunt-Lévy result shows that in ZFA, "functions" like S do not necessarily exist, even if we restrict to classes that are cardinalities, $\overline V'=\{\{B\mid |B|=|A|\}\mid A\in V\}$. The ZF-+AFA result shows that a "function" like S exists in this theory. –  Andres Caicedo Feb 25 '13 at 14:44
1  
My interpretation of your comment is that there is still some space for a proper proof or counterexample, since so far your proof requires a different version of extensionality, so I am stating for the record that I don't yet consider this question fully resolved, although you have put some work into your answer and the bounty period is almost out, so you can have this bounty. –  Mario Carneiro Mar 3 '13 at 4:32
show 5 more comments

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.