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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> </mml:math> , $${\omega }_1\rightarrow ({\omega }_1,{\omega }+1)^2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>→</mml:mo> <mml:msup> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mi>ω</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> </mml:math> , any family $$\mathcal {A}\subset [{On}]^{&lt;{\omega }}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>⊂</mml:mo> <mml:msup> <mml:mrow> <mml:mo>[</mml:mo> <mml:mrow> <mml:mi>On</mml:mi> </mml:mrow> <mml:mo>]</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>&lt;</mml:mo> <mml:mi>ω</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> of size $${\omega }_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> contains a $$\Delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Δ</mml:mi> </mml:math> -system of size $${\omega }_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> . 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)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>→</mml:mo> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mi>ω</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> <mml:mo>)</mml:mo> </mml:mrow> </mml:mrow> </mml:math> , any family $$\mathcal {A}\subset [{On}]^{&lt;{\omega }}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>⊂</mml:mo> <mml:msup> <mml:mrow> <mml:mo>[</mml:mo> <mml:mrow> <mml:mi>On</mml:mi> </mml:mrow> <mml:mo>]</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>&lt;</mml:mo> <mml:mi>ω</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> of size $${\omega }_2$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:math> contains a $$\Delta $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>Δ</mml:mi> </mml:math> -system of size $${\omega }_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> . Some statements can be proven in ZF using purely combinatorial arguments, such as: given a set mapping $$F:{\omega }_1\rightarrow {[{\omega }_1]}^{&lt;{\omega }}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>F</mml:mi> <mml:mo>:</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>→</mml:mo> <mml:msup> <mml:mrow> <mml:mo>[</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>]</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>&lt;</mml:mo> <mml:mi>ω</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> , the set $${\omega }_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> has a partition into $${\omega }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ω</mml:mi> </mml:math> -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]}^{&lt;{\omega }}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>F</mml:mi> <mml:mo>:</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>→</mml:mo> <mml:msup> <mml:mrow> <mml:mo>[</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>]</mml:mo> </mml:mrow> <mml:mrow> <mml:mo>&lt;</mml:mo> <mml:mi>ω</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:math> , there is an F -free set of size $${\omega }_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> , for each $$n\in {\omega }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>∈</mml:mo> <mml:mi>ω</mml:mi> </mml:mrow> </mml:math> , every family $$\mathcal {A}\subset {[{\omega }_1]}^{{\omega }}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>⊂</mml:mo> <mml:msup> <mml:mrow> <mml:mo>[</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>]</mml:mo> </mml:mrow> <mml:mi>ω</mml:mi> </mml:msup> </mml:mrow> </mml:math> with $$|A\cap B|\le n$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>A</mml:mi> <mml:mo>∩</mml:mo> <mml:mi>B</mml:mi> <mml:mo>|</mml:mo> <mml:mo>≤</mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:math> for $$\{A,B\}\in {[\mathcal {A}]}^{2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mo>{</mml:mo> <mml:mi>A</mml:mi> <mml:mo>,</mml:mo> <mml:mi>B</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> <mml:mo>∈</mml:mo> <mml:msup> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>A</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> </mml:math> 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$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> </mml:math> : (6 $$ ^*$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mmultiscripts> <mml:mrow/> <mml:mrow/> <mml:mo>∗</mml:mo> </mml:mmultiscripts> </mml:math> ) every family $$\mathcal {A}\subset {[{\omega }_1]}^{{\omega }}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>⊂</mml:mo> <mml:msup> <mml:mrow> <mml:mo>[</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>]</mml:mo> </mml:mrow> <mml:mi>ω</mml:mi> </mml:msup> </mml:mrow> </mml:math> with $$|A\cap B|\le 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mo>|</mml:mo> <mml:mi>A</mml:mi> <mml:mo>∩</mml:mo> <mml:mi>B</mml:mi> <mml:mo>|</mml:mo> <mml:mo>≤</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> for $$\{A,B\}\in {[\mathcal {A}]}^{2}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mrow> <mml:mo>{</mml:mo> <mml:mi>A</mml:mi> <mml:mo>,</mml:mo> <mml:mi>B</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> <mml:mo>∈</mml:mo> <mml:msup> <mml:mrow> <mml:mo>[</mml:mo> <mml:mi>A</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> </mml:math> is essentially disjoint . A function f is a uniform denumeration on $${\omega }_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> iff $${\text {dom}}(f)={\omega }_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>dom</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>f</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> </mml:math> , and for every $$1\le {\alpha }&lt;{\omega }_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>1</mml:mn> <mml:mo>≤</mml:mo> <mml:mi>α</mml:mi> <mml:mo>&lt;</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> </mml:math> , $$f({\alpha })$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>f</mml:mi> <mml:mo>(</mml:mo> <mml:mi>α</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is a function from $${\omega }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>ω</mml:mi> </mml:math> onto $${\alpha }$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>α</mml:mi> </mml:math> . It is easy to see that the existence of a uniform denumeration of $${\omega }_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:math> implies $$cf({\omega }_1)={\omega }_1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>c</mml:mi> <mml:mi>f</mml:mi> <mml:mrow> <mml:mo>(</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>=</mml:mo> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> </mml:math> . We prove that the failure of the reverse implication is equiconsistent with the existence of an inaccessible cardinal.

Tamás Csernák

Lajos Soukup

Archive for Mathematical Logic

该杂志发表研究论文，偶尔也会发表关于数理逻辑的调查或阐述。只要数理逻辑的方法发挥重要作用，也欢迎其他相关领域的贡献，例如理论计算机科学或哲学。因此，该杂志面向对数理逻辑在各自领域的应用及其与其他研究领域的互动感兴趣的逻辑学家和数学家、计算机科学家和哲学家。

The Archive for Mathematical Logic is a journal dedicated to research in mathematical logic, primarily publishing research papers and occasionally featuring surveys or expository articles on the subject. The journal welcomes contributions from other related fields, particularly theoretical computer science and philosophy, as long as they significantly utilize methods from mathematical logic. Thus, it targets logicians, mathematicians, computer scientists, and philosophers who are interested in the applications of mathematical logic in their respective fields and its interactions with other areas of research.

《Archive for Mathematical Logic》是一本专注于数理逻辑研究的期刊，主要发表研究论文，偶尔也会刊登关于数理逻辑的综述或阐述性文章。该期刊欢迎任何在数理逻辑方法上具有重要贡献的相关领域的研究，尤其是理论计算机科学和哲学。因此，它的目标读者包括对数理逻辑在各自领域的应用及其与其他研究领域的互动感兴趣的逻辑学家、数学家、计算机科学家和哲学家。

Category	Quartile
数学	4
数学, 逻辑学	4
数学, 数学	4

Infinite combinatorics revisited in the absence of Axiom of choice

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info