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.

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!

share|improve this question
    
Hint: You can use any bijection $f: X \to Y$ to define a p.o. on $Y$ isomorphic to $\preceq_X$. –  Lord_Farin Oct 25 '12 at 8:30
    
I've replaced the image by text. Please double check to make sure it has been correctly transcribed. –  Arthur Fischer Oct 25 '12 at 10:02
    
This is from Just-Weese: Discovering Modern Set Theory, Vol 1, p.23. (I think that mentioning the source is a useful information - I personally prefer, when such information is contained in the post.) –  Martin Sleziak Oct 25 '12 at 10:07
    
@Martin: Good idea. –  Arthur Fischer Oct 25 '12 at 10:18

4 Answers 4

up vote 4 down vote accepted

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.

share|improve this answer
    
I assume you assume $P \subsetneq S$. What is $S$? The von Neumann universe? –  Rudy the Reindeer Oct 25 '12 at 9:08
    
@MattN. What $S$? –  Michael Greinecker Oct 25 '12 at 10:20
    
If you assume there are elements outside $P$ then $P$ is a subset of something. –  Rudy the Reindeer Oct 25 '12 at 10:35
    
@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. –  Michael Greinecker Oct 25 '12 at 10:38
    
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? –  Rudy the Reindeer Oct 25 '12 at 17:31

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.

share|improve this answer

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!

share|improve this answer

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.

share|improve this answer

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.