Infinite combinatorics revisited in the absence of Axiom of choice

Csernák, Tamás and Soukup, Lajos (2025) Infinite combinatorics revisited in the absence of Axiom of choice. ARCHIVE FOR MATHEMATICAL LOGIC, 64 (3-4). pp. 473-491. ISSN 0933-5846

Preview

Text s00153-024-00946-1.pdf - Published Version Available under License Creative Commons Attribution. Download (360kB) | Preview

Abstract

We investigate whether classical combinatorial theorems are provable in ZF. Some statements are not provable in ZF, but they are equivalent within ZF. For example, the following statements (i)–(iii) are equivalent: cf({\omega }_1)={\omega }_1 c f ( ω 1 ) = ω 1 , {\omega }_1\rightarrow ({\omega }_1,{\omega }+1)^2 ω 1 → ( ω 1 , ω + 1 ) 2 , any family \mathcal {A}\subset [{On}]^{<{\omega }} A ⊂ [ On ] < ω of size {\omega }_1 ω 1 contains a \Delta Δ -system of size {\omega }_1 ω 1 . Some classical results cannot be proven in ZF alone; however, we can establish weaker versions of these statements within the framework of ZF, such as {{\omega }_2}\rightarrow ({\omega }_1,{\omega }+1) ω 2 → ( ω 1 , ω + 1 ) , any family \mathcal {A}\subset [{On}]^{<{\omega }} A ⊂ [ On ] < ω of size {\omega }_2 ω 2 contains a \Delta Δ -system of size {\omega }_1 ω 1 . Some statements can be proven in ZF using purely combinatorial arguments, such as: given a set mapping F:{\omega }_1\rightarrow {[{\omega }_1]}^{<{\omega }} F : ω 1 → [ ω 1 ] < ω , the set {\omega }_1 ω 1 has a partition into {\omega } ω -many F -free sets. Other statements can be proven in ZF by employing certain methods of absoluteness, for example: given a set mapping F:{\omega }_1\rightarrow {[{\omega }_1]}^{<{\omega }} F : ω 1 → [ ω 1 ] < ω , there is an F -free set of size {\omega }_1 ω 1 , for each n\in {\omega } n ∈ ω , every family \mathcal {A}\subset {[{\omega }_1]}^{{\omega }} A ⊂ [ ω 1 ] ω with |A\cap B|\le n | A ∩ B | ≤ n for \{A,B\}\in {[\mathcal {A}]}^{2} { A , B } ∈ [ A ] 2 has property B . In contrast to statement (5), we show that the following ZFC theorem of Komjáth is not provable from ZF + cf({\omega }_1)={\omega }_1 c f ( ω 1 ) = ω 1 : (6 ^* ∗ ) every family \mathcal {A}\subset {[{\omega }_1]}^{{\omega }} A ⊂ [ ω 1 ] ω with |A\cap B|\le 1 | A ∩ B | ≤ 1 for \{A,B\}\in {[\mathcal {A}]}^{2} { A , B } ∈ [ A ] 2 is essentially disjoint .

Actions (login required)

Edit Item