Changing the depth of an ordered set by decomposition

Authors:
E. C. Milner and K. Prikry

Journal:
Trans. Amer. Math. Soc. **290** (1985), 773-785

MSC:
Primary 03E05; Secondary 04A20, 06A05, 06A10

DOI:
https://doi.org/10.1090/S0002-9947-1985-0792827-8

MathSciNet review:
792827

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The depth of a partially ordered set is the smallest ordinal such that does not embed . The *width* of is the smallest cardinal number such that there is no antichain of size in . We show that if and is not an infinite successor cardinal, then any partially ordered set of depth can be decomposed into parts so that the depth of each part is strictly less than . If or if is an infinite successor cardinal, then for any infinite cardinal there is a linearly ordered set of depth such that for any -decomposition one of the parts has the same depth . These results are used to solve an analogous problem about width. It is well known that, for any cardinal , there is a partial order of width which cannot be split into parts of finite width. We prove that, for any cardinal and any infinite cardinal , there is a partial order of width which cannot be split into parts of smaller width.

**[1]**J. Baumgartner and A. Hajnal,*A proof (involving Martin’s axiom) of a partition relation*, Fund. Math.**78**(1973), no. 3, 193–203. MR**0319768****[2]**R. Bonnet and M. Pouzet,*Linear extensions of ordered sets*, Ordered sets (Banff, Alta., 1981) NATO Adv. Study Inst. Ser. C: Math. Phys. Sci., vol. 83, Reidel, Dordrecht-Boston, Mass., 1982, pp. 125–170. MR**661293****[3]**R. P. Dilworth,*A decomposition theorem for partially ordered sets*, Ann. of Math. (2)**51**(1950), 161–166. MR**0032578**, https://doi.org/10.2307/1969503**[4]**Ben Dushnik and E. W. Miller,*Partially ordered sets*, Amer. J. Math.**63**(1941), 600–610. MR**0004862**, https://doi.org/10.2307/2371374**[5]**P. Erdős and A. Hajnal,*On decomposition of graphs*, Acta Math. Acad. Sci. Hungar.**18**(1967), 359–377. MR**0223261**, https://doi.org/10.1007/BF02280296**[6]**Paul Erdős, András Hajnal, Attila Máté, and Richard Rado,*Combinatorial set theory: partition relations for cardinals*, Studies in Logic and the Foundations of Mathematics, vol. 106, North-Holland Publishing Co., Amsterdam, 1984. MR**795592****[7]**F. Galvin,*On a partition theorem of Baumgartner and Hajnal*, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, North-Holland, Amsterdam, 1975, pp. 711–729. Colloq. Math. Soc. János Bolyai, Vol. 10. MR**0376355****[8]**Thomas Jech,*Set theory*, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1978. Pure and Applied Mathematics. MR**506523****[9]**E. C. Milner and K. Prikry,*The cofinality of a partially ordered set*, Proc. London Math. Soc. (3)**46**(1983), no. 3, 454–470. MR**699097**, https://doi.org/10.1112/plms/s3-46.3.454**[10]**E. C. Milner and R. Rado,*The pigeon-hole principle for ordinal numbers*, Proc. London Math. Soc. (3)**15**(1965), 750–768. MR**0190003**, https://doi.org/10.1112/plms/s3-15.1.750**[11]**Micha A. Perles,*On Dilworth’s theorem in the infinite case*, Israel J. Math.**1**(1963), 108–109. MR**0168497**, https://doi.org/10.1007/BF02759806**[12]**S. Todorčević, Private communication.**[13]**Stevo Todorčević,*Partition relations for partially ordered sets*, Acta Math.**155**(1985), no. 1-2, 1–25. MR**793235**, https://doi.org/10.1007/BF02392535

Retrieve articles in *Transactions of the American Mathematical Society*
with MSC:
03E05,
04A20,
06A05,
06A10

Retrieve articles in all journals with MSC: 03E05, 04A20, 06A05, 06A10

Additional Information

DOI:
https://doi.org/10.1090/S0002-9947-1985-0792827-8

Keywords:
Partial order,
depth,
width,
extendable ordinal,
partition relation,
graph,
category

Article copyright:
© Copyright 1985
American Mathematical Society