7
$\begingroup$

According to the Wikipedia definition (current revision), the width of a poset is the cardinality of any maximum antichain, where "maximum antichain" here means an antichain of maximal cardinality. Perhaps I'm missing something, but there is no guarantee that such an antichain exists. In these cases, do we say that the width is not defined, or take the supremum instead?

To give an example, if I have done it correctly the poset $\Bbb N\times\Bbb N$ with the product order has a sequence of maximal antichains given by $A_n=\{(i,j)\mid i+j=n\}$, so since $|A_n|=n+1$ there are arbitrarily large antichains; but conversely if $(i,j)\in A$ is an antichain then $|A|\le i+j+1$ because there is at most one representative of each column $<i$ and each row $<j$, so there are no infinite antichains and no maximum antichains. So is the width of this poset undefined, or is it $\aleph_0$?

One can ask a similar question about the height (the cardinality of a maximum cardinality chain), for example with the order on $\{(i,j)\in\Bbb N\times\Bbb N\mid i\le j\}$ given by $(i,j)\le(i',j')\leftrightarrow i\le i'\land j=j'$ (which is just the disjoint union of chains of the form $\{(0,n),(1,n),\dots,(n,n)\}$).

$\endgroup$
7
  • $\begingroup$ A remark: in Davey, Priestley: Introduction to lattices and order width is defined only for finite posets. $\endgroup$ – lisyarus Nov 11 '15 at 16:16
  • $\begingroup$ The theorems which seem to be of greatest importance about height and width, namely Dilworth's theorem and Mirsky's theorem, deal only with finite posets, too. $\endgroup$ – lisyarus Nov 11 '15 at 16:18
  • $\begingroup$ @lisyarus One context where it appeared, triggering this line of thought, was in the height of a Hilbert lattice (which obviously can be infinite in both width and height). A literal reading of "has a height at least 4" would seem to also require that the height be defined, while I believe the intended meaning is $\exists x,y,z: 0<x<y<z<1$. $\endgroup$ – Mario Carneiro Nov 11 '15 at 16:26
  • $\begingroup$ Since you say that it is according to Wikipedia, it would be good to link to the Wikipedia article where this definition is from. $\endgroup$ – Martin Sleziak Nov 11 '15 at 16:45
  • $\begingroup$ In another Wikipedia article I see cellularity defined as the supremum of the cardinalities of antichains (for Boolean algebras). $\endgroup$ – Martin Sleziak Nov 11 '15 at 16:46
1
$\begingroup$

I think this question is similar to whether $0$ belongs to the natural numbers or not. In some areas, it is convenient to include $0$ and in other areas it is not. Similarly here. If you deal with finite antichains only, you may consider the maximum. If you deal with infinite (or unbounded) antichains you want to consider the supremum.

In Set Theory for instance, where most posets are infinite, people consider the least cardinal $\kappa$ such that there is no antichain of size $\kappa$. In your example, $\kappa$ would be $\omega$. In these cases, the notion to consider is $\kappa$-chain condition.

See https://en.wikipedia.org/wiki/Countable_chain_condition

$\endgroup$
2
  • $\begingroup$ Am I to understand from this that the supremum definition is the better one? (In finite antichains they are equivalent conditions.) Do you know any circumstances when you want to emphasize that a poset with a certain (infinite) width in fact has an antichain of that width (i.e. it is a maximum, not just a supremum)? $\endgroup$ – Mario Carneiro Nov 11 '15 at 18:05
  • $\begingroup$ @MarioCarneiro Again, what is better depends on the area of Mathematics that you practice. I guess the reason people consider least cardinal κ such that there is no antichain of size κ is to avoid the problem whether supremum is attained or not. $\endgroup$ – Ioannis Souldatos Nov 11 '15 at 18:16

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.