Chromatic number of the product of graphs, graph homomorphisms, antichains and cofinal subsets of posets without AC

In set theory without the axiom of choice (AC), we observe new relations of the following statements with weak choice principles. ◦ If in a partially ordered set, all chains are finite and all antichains are countable, then the set is countable.If in a partially ordered set, all chains are finite and all antichains have size Nα, then the set has size Nα for any regular Nα. Every partially ordered set without a maximal element has two disjoint cofinal sub sets – CS. Every partially ordered set has a cofinal well-founded subset – CWF. Dilworth’s decomposition theorem for infinite partially ordered sets of finite width – DT. We also study a graph homomorphism problem and a problem due to A. Hajnal without AC. Further, we study a few statements restricted to linearly-ordered structures without AC. © 2021, Commentationes Mathematicae Universitatis Carolinae. All Rights Reserved