

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/ThechromaticnumberoftheproductoftwographsHajnal/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 +
'wellorderable union of
wellorderable sets in
wellorderable' (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
wellordered set of vertices.
2. A wellknown 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 2element sets in ZF
(Zermelo Fraenkel set theory
without AC) https://www.cambridge.org/core/journals/journalofsymboliclogic/article/onramseystheoremandtheexistenceofinfinitechainsorinfiniteantichainsininfiniteposets/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 abovegeneralized
version does not imply the axiom
of choice restricted to nelement
sets in ZFA where n can be any
natural number greater than or
equal to 2.



