Explain this: Where an ordered pair (x, y) is a set $ \{x, \{x, y\}\} $, the class of all ordered pairs is not a set.
In ZF (and related) set‐theories, one often defines the ordered pair $(x,y)$ à la Kuratowski by
$$ (x,y)\;=\;\{\,x,\;\{x,y\}\}. $$
Let’s call
$$ P \;=\;\bigl\{\,w : \exists\,x,y\bigl[w=\{x,\{x,y\}\}\bigr]\bigr\} $$
the class of all such ordered pairs. We claim $P$ cannot itself be a set but must be a proper class. Here’s the standard argument:
1. Suppose for contradiction that $P$ is a set.
2. Define the first‐projection map
$$ \pi_1\bigl(\{x,\{x,y\}\}\bigr)\;=\;x. $$
Because $\pi_1$ is a definable “function” on ordered pairs, the Axiom Schema of Replacement tells us that
$$ \pi_1[P]\;=\;\{\,x : \exists\,y\bigl((x,y)\in P\bigr)\} $$
must also be a set.
3. But $\pi_1[P]$ is in fact the universe of all sets.
- For every set $x$, just take $y=x$. Then $\bigl(x,x\bigr)$ is an ordered pair, so belongs to $P$.
- Hence every $x$ appears as the first coordinate of something in $P$.
Thus
$$ \pi_1[P]\;=\;\{\,x : x\text{ is a set}\}\;=\;V, $$
the class of all sets.
4. But in ZF the universe $V$ is not a set.
If $V$ were a set, one would immediately violate Cantor’s theorem (e.g.\ its power set $\mathcal P(V)$ would have strictly larger cardinality than $V$ itself), or more directly it contradicts the axiom of foundation and the cumulative‐hierarchy conception. In any case, the theory forbids “the set of all sets.”
5. Conclusion
Since assuming $P$ is a set forces $V$ to be a set (via Replacement), which is impossible, we must reject the assumption. Therefore
The class of all Kuratowski‐ordered pairs is too large to be a set; it is a proper class.
Alternative (union) argument
One can also observe that
$$ \bigcup\!\bigl(\bigcup P\bigr) \,=\, \bigcup\,\bigl\{\,x,\{x,y\}:x,y\in V\bigr\} \,=\,V. $$
If $P$ were a set then so would be its double–union $\bigcup\bigl(\bigcup P\bigr)$, again forcing $V$ to be a set. Same contradiction.
A set f is called a function if all its elements are ordered pairs and for each set a there is at most one set b such that that $(a, b) \in f$. Show that the class of all functions is not a set.
Here is a direct “size‐too‐large” argument showing the class
$$ \mathcal F \;=\;\{\,f : f \text{ is a function (i.e.\ a set of ordered pairs with unique first–coordinates)}\} $$
cannot itself be a set in ZF.
1. For each set $a$, cook up a tiny function $f_{a}$
Define
$$ f_{a} \;=\; \{\,(a,a)\,\}. $$
Clearly:
- $(a,a)$ is an ordered pair (e.g.\ Kuratowski’s $\{a,\{a,a\}\}$),
- $f_{a}$ is a set of ordered pairs,
- no two pairs in $f_{a}$ share the same first coordinate. Hence $f_{a}\in\mathcal F$.
2. If $\mathcal F$ were a set, then so would be $\bigcup\!\bigcup\mathcal F$
- By the Axiom of Union, if $\mathcal F$ is a set then $\displaystyle U:=\bigcup\mathcal F$ is a set (the union of all functions).
- Then again by Union, $\displaystyle \bigcup U=\bigcup\!\bigl(\bigcup\mathcal F\bigr)$ is also a set.
3. But $\bigcup\!\bigl(\bigcup\mathcal F\bigr)=V$, the universe of all sets
-
First, $U=\bigcup\mathcal F$ contains every ordered‐pair component: for each $f_{a}$ we have $(a,a)\in f_{a}\subset U$, so
$$ U\;\supset\;\{a,\{a,a\}\} \;=\;\{a,\{a\}\}. $$
-
Now
$$ \bigcup U \;=\; \bigcup\bigl\{\{a,\{a\}\}:a\in V\bigr\} \;=\; \bigl\{\,a : a\in V\bigr\}\;\cup\;\bigl\{\,x : x\in\{a\}\text{ for some }a\in V\bigr\} \;=\; V. $$
Concretely, every set $a$ appears among the first‐coordinates, and every set $x$ appears as the unique member of $\{a\}$ for some $a$.
Hence if $\mathcal F$ were a set, we would have built the set $\bigcup\!\bigl(\bigcup\mathcal F\bigr)$, which must equal $V$. But ZF forbids $V$ from being a set (one way to see this is Cantor’s theorem: $\mathcal P(V)$ would strictly exceed $V$ in size).
4. Conclusion
Because assuming $\mathcal F$ is a set forces $V$ to be a set, we reach a contradiction. Therefore
The class of all functions is not a set; it is a proper class.
No comments:
Post a Comment