28 February (Friday) 4:15 PM  Room 224

Amitayu Banerjee

Department of Logic, Institute of Philosophy Eötvös University Budapest

On the chromatic number of products of graphs, and antichains without AC

1. (Figured out with Zalan Gyenis). In 1985, Andras Hajnal applied the Compactness theorem for propositional logic (which is equivalent to UL in the context where AC fails) to prove that 'if the chromatic number of a graph G1 is finite (say a natural number k), and the chromatic number of another graph G2 is infinite, then the chromatic number of the product of G1 and G2 is k' (see/c.f. Theorem 2 of https://www.semanticscholar.org/paper/The-chromatic-number-of-the-product-of-two-graphs-Hajnal/7bce2a70e5a44bc07aafd20afdac74df6f17ecbc). We observe (and I will present the proof) that if k=3, then the above statement does not imply the axiom of choice restricted to 3 element sets in ZFA (Zermelo Fraenkel set theory in presence of atoms or urelements) and consequently does not imply UL in ZFA. Moreover, we observe that the above statement due to Hajnal is provable only under ZF + 'well-orderable union of well-orderable sets in well-orderable' (a weaker choice principle, Form 231 of 'Consequences of the Axiom of choice due to Howard/Rubin') if G1 is assumed to be a graph on a well-ordered set of vertices. 2. A well-known application of Zorn's lemma (an equivalent of AC) is that 'Any infinite poset contains either an infinite chain or an infinite antichain.' In 2016, Eleftherios Tachtsis proved that the above statement does not imply the axiom of choice restricted to 2-element sets in ZF (Zermelo Fraenkel set theory without AC) https://www.cambridge.org/core/journals/journal-of-symbolic-logic/article/on-ramseys-theorem-and-the-existence-of-infinite-chains-or-infinite-antichains-in-infinite-posets/5CDBE195B822A73E6B1ACA733989BDB8.  Another application of Zorn's lemma is a generalized version which tells that 'If in a partially ordered set, all chains are finite and all antichains are countable, then the set is countable' (see/c.f. Problem 7, Chapter 11 of Komjath/Totik's https://2n6pw521j10.blob.core.windows.net/2n6pw521j10/MTQ0MTkyMTQwMA==.pdf). I observe (and I will present the proof) that the above-generalized version does not imply the axiom of choice restricted to n-element sets in ZFA where n can be any natural number greater than or equal to 2.