We have observations concerning the set theoretic strength of the following combinatorial statements without the axiom of choice. 1. If in a partially ordered set, all chains are finite and all antichains are countable, then the set is countable. 2. If in a partially ordered set, all chains are finite and all antichains have size $aleph_{alpha}$, then the set has size $aleph_{alpha}$ for any regular $aleph_{alpha}$. 3. CS (Every partially ordered set without a maximal element has two disjoint cofinal subsets). 4. CWF (Every partially ordered set has a cofinal well-founded subset). 5. DT (Dilworths decomposition theorem for infinite p.o.sets of finite width). 6. If the chromatic number of a graph $G_{1}$ is finite (say $k<omega$), and the chromatic number of another graph $G_{2}$ is infinite, then the chromatic number of $G_{1}times G_{2}$ is $k$. 7. For an infinite graph $G=(V_{G}, E_{G})$ and a finite graph $H=(V_{H}, E_{H})$, if every finite subgraph of $G$ has a homomorphism into $H$, then so has $G$. Further we study a few statements restricted to linearly-ordered structures without the axiom of choice.
Download