2
$\begingroup$

On Page 32, Set Theory, Jech(2006):

Let $\kappa$ be a limit ordinal. A subset $X \subset \kappa $ is bounded if $\operatorname{sup}{X} < \kappa$, and unbounded if $\operatorname{sup}{X} =\kappa$.

It seems to me, in the class of all ordinals, only limit ordinals can have unbounded subset. But what can we say about a partial-ordered set?

One problem to me is the absence of "universal class" which is expected to play the same role as the class of all ordinals.

So are we only able to focus on those POSETs isomorphic to a unbounded subset of a limit ordinal, and assume we have defined a "universal class" by isomorphism ex ante?

  • 0
    @AsafKaragila: Thank you very much. I've fixed it.2012-12-08

2 Answers 2

2

The notion of an unbounded family can be made very general. Suppose that $R$ is any relation on a set $X$. We could define a subset $A \subseteq X$ to be unbounded if for each $x \in X$ there is an $a \in A$ such that $a \not\mathrel{R} x$ -- that is, no single $x \in X$ serves as an upper bound for $A$. Of course, there are situations where this notion may not be too meaningful.

Example. Consider any partially ordered set $( P , \leq )$ containing two elements $a, b$ which have no common upper bound. Then $\{ a , b \}$ is an unbounded subset of the partial order, irrespective of the lengths of chains that might exist in $P$. In particular, if $\kappa$ is any cardinal, then the partial order consisting of two disjoint copies of $\kappa$ under the usual order will be of this type.

To make this notion somewhat more meaningful we may assume that given any two $x , y \in X$ there is a $z \in X$ such that $x \mathrel{R} z$ and $y \mathrel{R} z$ both hold.

An important set-theoretic/combinatorial notion related to this is the bounding number. Consider the family $\omega^\omega$ of all functions from $\omega$ to itself. We define a relation $\leq^*$ on $\omega^\omega$ by declaring $f \leq^* g \quad \Leftrightarrow \quad ( \exists N )( \forall n \geq N ) ( f(n) \leq g(n) ),$ (i.e., the relation $f(n) > g(n)$ holds for at most finitely many $n$). It is not too difficult to show that $( \omega^\omega , \leq^* )$ has the property described above: given $f,g \in \omega^\omega$ define $h(n) = \max \{ f(n) , g(n) \}$.

According to the above, an unbounded family is then a subset $B \subseteq \omega^\omega$ such that for each $g \in \omega^\omega$ there is a $f \in B$ such that $f \nleq^* g$, i.e., $f(n) > g(n)$ holds for infinitely many $n$. Clearly $\omega^\omega$ is itself an unbounded family, and so we may ask about the minimum cardinality of such a set. This is called the bounding number, and is usually denoted by $\mathfrak{b}$. It is easy to show that $\aleph_1 \leq \mathfrak{b} \leq \mathfrak{c} = 2^{\aleph_0}$, but the exact value of this cardinal, as well as how it sits between $\aleph_1$ and $\mathfrak{c}$, is independent from the ZFC. Much has been written about this and other so-called cardinal characteristics of the continuum, many of which can be given a similar definition. (Perhaps surprisingly the value $\mathfrak{b}$ puts some bounds on some notions related to Lebesgue measure are Baire category.)

  • 0
    You are right. I should have thought about bounding numbers and whatnot as well. Much more useful than what I wrote!2012-12-08
3

Note that all partially ordered sets embed into $(V,\subseteq)$ (by realizing every point as its closed cut, i.e. $a\mapsto\{x\leq a\}$).

So we do have a universal class to embed everything into.

In partially ordered sets which are not necessarily well-founded chain need not be well-ordered, and then chains are unbounded if they do not have a proper upper bound. E.g. $\mathbb R$ in the real numbers, or so on. If the order is well-founded then chains are well-ordered and then have order type of ordinals, and therefore unbounded sets have order types of limit ordinals.

Not all is lost in non well-founded sets, though. The cofinality principle (which is provable from the axiom of choice) says that every linearly ordered set contains a cofinal well-ordered set. This implies that one can find cofinal sub-chains which are unbounded and well-ordered. If so, one can "measure" (so to speak) what is the least ordinal which can be embedded cofinally, or what is the least ordinal which cannot be embedded at all, into the chain or the order.

Apart from that the theory of orders can be quite complicated when leaving well-founded sets (or something else relatively tame, like scattered orders).


Arthur discussed the bounding number and other invariants of a partial order. These often discuss cardinal invariants, much like cofinality in ordinals "how large is the minimal chain which is cofinal" these are the correct generalization (in some sense, of course) of cofinality. There is another interesting question, what is the least order-type of such cofinal/dominated/unbounded family.

The problem is that partial orders do not have the Cantor-Bernstein property that well-orders do. It is not hard to find examples of partial orders which embed into one another, but are not isomorphic (those can be linear orders, or well-founded orders, or neither -- but not both of course).

  • 0
    Oh, no! That doesn't work.2012-12-09