On page 222 in Enderton's Elements of Set Theory, there's a remark which is then justified as an exercise:

Show that for any order types $\rho$ and $\sigma$ there exist structures $\langle A,R\rangle$ and $\langle B,S\rangle$ of types $\rho$ and $\sigma$, respectively, such that $A\cap B=\varnothing$.

This question is related to There exist $\langle A,R \rangle $ and $\langle B,S \rangle $ of order types $\alpha$ and $\beta$ with A and B disjoint.

Essentially the isomorphism type of a partially ordered set $\langle A,<\rangle$ is the set of all partially ordered sets which are order isomorphic to $\langle A,<\rangle$ and has the least rank.

Enderton claims that we can find disjoint members from any pair of isomorphism types. I find it hard to prove this (which is a foundational for defining order type arithmetic).

NOTE: the isomorphic equivalence class is too large to be a set but Enderton used Scott's trick to make a set. Now Enderton is working with it for isomorphism type arithmetic, but the detail about finding disjoint members from any two iso-types is too elusive for me.

Can I get insight as to the proof?


HINT: The proof is based on two parts:

  1. If $A$ and $B$ are two sets, then there is some $A'$ such that $|A|=|A'|$ and $A'\cap B=\varnothing$.

  2. If $f\colon X\to Y$ is a given bijection (any given bijection), and $R$ is a relation on $X$, then there is some $R'$ such that $f$ is an isomorphism between $\langle X,R\rangle$ and $\langle Y,R'\rangle$.

  • $\begingroup$ Both parts are not difficult when you think about them. But I'll be happy to elaborate on specific parts if you want me to. $\endgroup$ – Asaf Karagila Apr 19 '15 at 21:47
  • $\begingroup$ If $(A,\prec_A)\in it(A^*,\prec_0)$ and $(B,\prec_B)\in it(B^*,\prec_1)$, then I agree that I can find $(A',\prec_{A'})$ which is order isomorphic to $(A,\prec_A)$ and disjoint from $B$. But is $(A',\prec_{A'})$ in the isomorphism type of $(A^*,\prec_0)$? They have equal isomorphism type (because they're isomorphic) but that's not what's important. I.E. how to show it has the least rank for which it's isomorphic to $(A^*,\prec_0)$. $\endgroup$ – Alberto Takase Apr 19 '15 at 21:53
  • $\begingroup$ When you say "of type" you don't mean members of the Scott set of the isomorphism class, but rather "isomorphic to an element of the Scott set of the isomorphism class". $\endgroup$ – Asaf Karagila Apr 19 '15 at 22:10
  • $\begingroup$ If you want to insist on rank minimality, you can probably show that this is false for finite partial orders, but that it is possible for infinite orders, simply because you can just "shrink" away a sufficient part whilst preserving the same cardinality (and then you apply the rank minimality to claim that you didn't decrease the rank). $\endgroup$ – Asaf Karagila Apr 19 '15 at 22:12
  • $\begingroup$ This means on page 222 Enderton made a typo? "Any member of an order type $\rho$ is said to be a linearly ordered structure of type $\rho$.'' where "An order type is the iso-type of some linearly ordered structure...We will use Greek letters $\rho,\sigma,\ldots$ for order types." $\endgroup$ – Alberto Takase Apr 19 '15 at 22:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.