Prove or disprove collection is a set

88 Views Asked by At

In my set theory exam the following question was proposed:

Determine if, $\{x|\exists \text{y so that }(x,y)=x\}$ is a set or not.(In ZFC) I think it should not be, but I don't know how to prove it. Any is appreciated :)

Edit: $(x,y)=\{x,\{x,y\}\}$. That is, the ordered pair of x and y

2

There are 2 best solutions below

2
On BEST ANSWER

Given the Axiom of Foundation (aka. Regularity) and the (short) Kuratowskiy definition of ordered pair, this class is the empty set: If $x=(x,y)=\{x,\{x,y\}\}$, then $x$ contains itself. We consider $a:=\{x\}$ and note that $$ x\cap a=\{x,\{x,y\}\}\cap \{x\}\ni x,$$ hence none of the elements of the non-empty set $a$ is disjoint form $a$, whereas the Axiom of Foundation postulates otherwise.

Remark: The result would be the same with any sensible definition of ordered pair as some set construction, for in one way or other, $(x,y)$ will contain $x$ somewhere in itself, though perhaps at a deeper level, which is still forbidden by the Axiom of Foundation.

4
On

Hagen von Eitzen correctly answers that your collection is the empty set in ordinary ZFC (which is assumed to contain an Axiom of Regularity).

However, the Axiom of Regularity is sometimes presented as an "optional" ingredient of ZFC. If your ZFC doesn't contain it (which would arguably a more natural setting for asking about this collection in the first place), then the collection may or may not be a set.

It may be the empty set, because it might well be that Regularity just happens to hold without being required as an axiom.

On the other hand, ZFC$-$Reg allows us to add an anti-foundation axiom without losing consistency. With this axiom, for each set $A$ we'd be able to find a solution to the equation $x = \{x,\{x,A\}\}$, and all of those solutions would be in your collection. In particular, if your collection was a set, then the union of its union would contain every possible $A$, from which a contradiction would follow by Russell's paradox in the usual way.

So ZFC$-$Reg+AFA (which is equiconsistent with ZFC) proves that your collection is not a set.