3
$\begingroup$

I'm trying to do the following (original image):

EXERCISE 25(R):(a) Argue on the grounds of the architect's view of set theory (which was outlined in the Introduction) that $\mathbf{PO}$ cannot be a set.
(b) Moreover, show that for each given p.o. $\langle X , \preceq_X \rangle$, if $X \neq \emptyset$, then the collection of all p.o.'s $\langle Y , \preceq_y \rangle$ that are order-isomorphic to $\langle X , \preceq_X \rangle$ is not a set.

(This is from W. Just and M. Weese, Discovering Modern Set Theory, vol.1, p.23.)

(a) was rather easy: Since $\mathbf{PO}$ is itself a partial order with respect to $\subseteq$, $\mathbf{PO}$ would have to contain itself and hence cannot be a set.

But now I'm stuck with (b). Can someone show me how to do (b)? Thank you!

  • 0
    @Martin: Good idea.2012-10-25

4 Answers 4

4

Let $(P,\leq)$ be a poset with $P\neq\emptyset$. Let $x$ be any element of $P$ and $y$ be any element not in $P$. Replace $x$ by $y$ and you have an isomorphic poset containing $y$. So every set is contained in some equivalent poset and the class of equivalent posets cannot be bounded above in the cumulative hierarchy.

  • 0
    @Matt: That is the essence of this idea.2012-10-25
4

Another way: for each set $y$ let $X_y=X\times\{y\}$, and let $\preceq_y=\Big\{\big\langle \langle x,y\rangle,\langle z,y\rangle\big\rangle:x,z\in X\text{ and }x\preceq_Yz\Big\}\;;$ then $\langle X_y,\preceq_y\rangle$ is isomorphic to $\langle X,\preceq_X\rangle$, and if $y\ne y'$ then $X_y\ne X_{y'}$. Thus, $y\mapsto\langle X_y,\preceq_y\rangle$ is a bijection between the universe of sets and a subcollection of the collection of partial orders isomorphic to $\langle X,\preceq_Y\rangle$, which therefore cannot be a set.

3

A somewhat informal argument, making use of Just and Weese's "architect's view of set theory" is as follows.

Suppose that the collection of all posets isomorphic to $\langle X , \preceq_X \rangle$ were a set, and write this set as $\mathcal{X} = \{ \langle X_i , \preceq_i \rangle : i \in I \}$, where $I$ is some index set. For each $i \in I$ choose an order-isomorphism $f_i : \langle X , \preceq_X \rangle \to \langle X_i , \preceq_i \rangle$.

By $Y$ denote the set $ \{ \langle f_i (x) \rangle_{i \in I} : x \in X \} = \{ \langle x_i \rangle_{i \in I} \in \textstyle{\prod_{i \in I}} X_i : ( \exists x \in X ) ( \forall i \in I ) ( x_i = f_i(x) ) \} .$ We may define a relation $\preceq$ on $Y$ by $\langle f_i (x) \rangle_{i \in I} \preceq \langle f_i (y) \rangle_{i \in I}$ iff $x \leq y$. It is easy to see that $\langle Y , \preceq \rangle$ is order-isomorphic to $\langle X , \leq \rangle$, and therefore $\langle Y , \preceq \rangle \in \mathcal{X}$, i.e., $\langle Y , \preceq \rangle = \langle X_j , \preceq_j \rangle$ for some $j \in I$.

Given any $\langle x_i \rangle_{i \in I} \in Y$ it must be that each $x_i$ was constructed strictly before $\langle x_i \rangle_{i \in I}$, in particular $x_j \in X_j = Y$ was constructed strictly before $\langle x_i \rangle_{i \in I}$. But $x_j = \langle x^{(1)}_i \rangle_{i \in I}$, and so each of these components were constructed strictly before $x_j$; in particular $x^{(1)}_j \in X_j = Y$. etc. etc. ad infinitum.

We then have an infinite sequence of objects/sets, $\langle x_i \rangle_{i \in I} = x^{(0)} , x^{(0)}_j = x^{(1)}, x^{(1)}_j = x^{(2)} , \ldots$ and for each $n$ the object/set $x^{(n+1)}$ must be constructed strictly before $x^{(n)}$. But this means that at no point were any of the $x^{(n)}$ ready to be constructed!

1

Here is yet another approach.

Let us show that if $(X,\leq)$ is a non-empty partially ordered set then there is a proper class of orders $(P,\preceq)$ which can be embedded into $(X,\leq)$.

Note that a singleton makes a partially ordered set $(\{\bullet\},=)$. Since $X$ is non-empty fix some $x\in X$, and let $f(\bullet)=x$ be a function from $\{\bullet\}$ into $X$. Trivially this is an order embedding.

Now all that is left is to verify that there is a proper class of singletons. That, of course, is immediate from the fact that the collection of all sets is not a set.

If, on the other hand, one wishes to show that there are only set-many equivalence classes of posets which can be embedded into $(X,\leq)$ then one can show that every such equivalence class has a representative which is a subset of $X$, and we can bound everything within a couple of iterations of the power set construction.