Changing the depth of an ordered set by decomposition
Authors:
E. C. Milner and K. Prikry
Journal:
Trans. Amer. Math. Soc. 290 (1985), 773785
MSC:
Primary 03E05; Secondary 04A20, 06A05, 06A10
MathSciNet review:
792827
Fulltext 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
(47 #8310)
 [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, DordrechtBoston, Mass., 1982,
pp. 125–170. MR 661293
(83h:06004)
 [3]
R.
P. Dilworth, A decomposition theorem for partially ordered
sets, Ann. of Math. (2) 51 (1950), 161–166. MR 0032578
(11,309f)
 [4]
Ben
Dushnik and E.
W. Miller, Partially ordered sets, Amer. J. Math.
63 (1941), 600–610. MR 0004862
(3,73a)
 [5]
P.
Erdős and A.
Hajnal, On decomposition of graphs, Acta Math. Acad. Sci.
Hungar. 18 (1967), 359–377. MR 0223261
(36 #6309)
 [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, NorthHolland Publishing Co., Amsterdam, 1984. MR 795592
(87g:04002)
 [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, NorthHolland, Amsterdam,
1975, pp. 711–729. Colloq. Math. Soc. János Bolyai, Vol.
10. MR
0376355 (51 #12531)
 [8]
Thomas
Jech, Set theory, Academic Press [Harcourt Brace Jovanovich,
Publishers], New YorkLondon, 1978. Pure and Applied Mathematics. MR 506523
(80a:03062)
 [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 (84m:06004), http://dx.doi.org/10.1112/plms/s346.3.454
 [10]
E.
C. Milner and R.
Rado, The pigeonhole principle for ordinal numbers, Proc.
London Math. Soc. (3) 15 (1965), 750–768. MR 0190003
(32 #7419)
 [11]
Micha
A. Perles, On Dilworth’s theorem in the infinite case,
Israel J. Math. 1 (1963), 108–109. MR 0168497
(29 #5759)
 [12]
S. Todorčević, Private communication.
 [13]
Stevo
Todorčević, Partition relations for partially ordered
sets, Acta Math. 155 (1985), no. 12,
1–25. MR
793235 (87d:03126), http://dx.doi.org/10.1007/BF02392535
 [1]
 J. Baumgartner and A. Hajnal, A proof (involving Martin's axiom) of a partition relation, Fund. Math. 78 (1973), 193203. MR 0319768 (47:8310)
 [2]
 R. Bonnet and M. Pouzet, Linear extensions of ordered sets, Ordered Sets (I. Rival, ed.), Reidel, Dordrecht, 1982, pp. 125170. MR 661293 (83h:06004)
 [3]
 R. P. Dilworth, A decomposition theorem for partially ordered sets, Ann. of Math. (2) 51 (1950), 161166. MR 0032578 (11:309f)
 [4]
 B. Dushnik and E. W. Miller, Partially ordered sets, Amer. J. Math. 63 (1941), 600610. MR 0004862 (3:73a)
 [5]
 P. Erdős and A. Hajnal, On decompositions of graphs, Acta. Math. Acad. Sci. Hungar. 18 (1967), 359377. MR 0223261 (36:6309)
 [6]
 P. E. Erdős, A. Hajnal, A. Máté and R. Rado, Combinatorial set theory, partition relations for cardinals, NorthHolland, Amsterdam, 1984. MR 795592 (87g:04002)
 [7]
 F. Galvin, On a partition theorem of Baumgartner and Hajnal, Colloq. Math. Soc. János Bolyai 10, NorthHolland, Amsterdam, 1973, pp. 711729. MR 0376355 (51:12531)
 [8]
 T. Jech, Set theory, Academic Press, New York, 1978. MR 506523 (80a:03062)
 [9]
 E. C. Milner and K. Prikry, The cofinality of a partially ordered set, Proc. London Math. Soc. (3) 46 (1983), 454470. MR 699097 (84m:06004)
 [10]
 E. C. Milner and R. Rado, The pigeonhole principle for ordinal numbers, Proc. London Math. Soc. (3) 15 (1965), 750768. MR 0190003 (32:7419)
 [11]
 M. A. Perles, On Dilworth's theorem in the infinite case, Israel J. Math. 1 (1963), 108109. MR 0168497 (29:5759)
 [12]
 S. Todorčević, Private communication.
 [13]
 , Partition relations for partially ordered sets, Acta Math. (to appear). MR 793235 (87d:03126)
Similar Articles
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:
http://dx.doi.org/10.1090/S00029947198507928278
PII:
S 00029947(1985)07928278
Keywords:
Partial order,
depth,
width,
extendable ordinal,
partition relation,
graph,
category
Article copyright:
© Copyright 1985
American Mathematical Society
