Prove the inequality $breadth(P) \leq dim(P)$

72 Views Asked by At

Definition 1: Let n be a positive integer. We say that an order P has breadth at most n if for all elements $x_0$, $x_1$, ..., $x_n$, $y_0$, $y_1$, ..., $y_n$ in P, if $x_i \leq y_j$ for all $i \neq j$ in {0, 1, ..., n}, then there exists $i \in$ {0, 1, ..., n} such that $x_i \leq y_i$. The breadth of P, in notation, breadth(P), is the least positive integer n such that P has breadth at most n if such an n exists.

Definition 2: Define the order-dimension, dim(P), of an order P as the smallest cardinal m such that P is a suborder on a product of m chains.

Actually my problem is I cannot understand definition 2. In my interpretation, product is defined as follows:

Definition 0: Given the orders P and Q, we can form the direct product $P \times Q$, consisting of all ordered pairs ($x_1, x_2$) with $x_1 \in P$ and $x_2 \in Q$, ordered componentwise, that is, $(x_1, x_2) \leq (y_1, y_2)$ if $x_1 \leq y_1$ in P and $x_2 \leq y_2$ in Q.

According to this definition of product, dimension of order is really similar to that of a vector. For example, (a, b) is 2 dimension and (a, b, c) is 3 dimension.

Is my interpretation of definition 2 correct? Please give me some hints on how to connect definition 1 and definition 2.

1

There are 1 best solutions below

0
On BEST ANSWER

From your definition, dimension doesn't seem to apply to an element, but rather to ordered sets.
So your intuition is ok, but for a formalism.

If $(a,b) \in P_1 \times P_2$ but $P_1$ and $P_2$ are not chains (and so $P_1 \times P_2$ is not a suborder of the product of two chains), then $\dim (P_1\times P_2) > 2$, and what would you mean with "$(a,b)$ is 2 dimension"?

As an aside (which might be of your interest) every ordered set $P$ is a suborder of its powerset $2^P$, so $\dim P \leq 2^{|P|}$.