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
    Hint: You can use any bijection $f: X \to Y$ to define a p.o. on $Y$ isomorphic to $\preceq_X$.2012-10-25
  • 0
    I've replaced the image by text. Please double check to make sure it has been correctly transcribed.2012-10-25
  • 0
    This is from Just-Weese: Discovering Modern Set Theory, Vol 1, [p.23](http://books.google.com/books?id=x74azoKzb_MC&pg=PA23). (I think that mentioning the source is a useful information - I personally prefer, when such information is contained in the post.)2012-10-25
  • 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
    I assume you assume $P \subsetneq S$. What is $S$? The von Neumann universe?2012-10-25
  • 0
    @MattN. What $S$?2012-10-25
  • 0
    If you assume there are elements outside $P$ then $P$ is a subset of something.2012-10-25
  • 0
    @MattN. Of course. If there are no sets outside of $P$, yu run into the usual problems with a set of all subsets. If there is a set $y$ outside $P$, then you can take your $S$ to be $P\cup\{y\}$ if you want.2012-10-25
  • 0
    Dear Michael, I don't understand your last comment but let me check if I understand your answer by repeating it in my own words: if $P$ is any poset then every set $y$ of the universe is contained in the (equivalent) poset $P' = P_{-x+y}$ where we swap an arbitrary element $x$ for $y$. Hence the cardinality of the equivalence class of $P$ is at least as large as the entire universe. Is that correct?2012-10-25
  • 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.