/- Copyright 2026 The Formal Conjectures Authors. Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at https://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License. -/ module public import FormalConjecturesUtil

Erdős Problem 1168

References:

    erdosproblems.com/1168

    [EHR65] Erdős, P., Hajnal, A. and Rado, R., Partition relations for cardinal numbers. Acta Math. Acad. Sci. Hungar. (1965), pp. 93–196.

@[expose] public sectionopen Cardinal Ordinal SimpleGraphnamespace Erdos1168

Erdős Problem 1168. Prove that $$\aleph_{\omega+1} \not\to (\aleph_{\omega+1}, \underbrace{3, 3, \ldots}{\aleph_0})^2{\aleph_0}$$ without assuming the generalized continuum hypothesis.

A problem of Erdős, Hajnal, and Rado [EHR65]: the negative arrow is known under GCH; the open problem asks for a ZFC proof. Here ω = Ordinal.omega0, so ℵ_ (ω + 1) is the successor cardinal of the singular ℵ_ω.

@[category research open, AMS 5] theorem erdos_1168 : ¬ CardinalCountableColorRamsey (ℵ_ (ω + 1)) := ⊢ ¬CardinalCountableColorRamsey (ℵ_ (ω + 1)) All goals completed! 🐙namespace erdos_1168.variants

Erdős–Hajnal–Rado theorem under GCH [EHR65]: the negative partition relation $\aleph_{\omega+1} \not\to (\aleph_{\omega+1}, 3, 3, \ldots)^2_{\aleph_0}$ holds assuming GCH.

@[category research solved, AMS 5] theorem under_GCH (hGCH : GCH) : ¬ CardinalCountableColorRamsey (ℵ_ (ω + 1)) := hGCH:GCH⊢ ¬CardinalCountableColorRamsey (ℵ_ (ω + 1)) All goals completed! 🐙⊢ ℵ_ 0 < ℵ_ (ω + 1) ⊢ 0 < ω + 1 All goals completed! 🐙

ℵ_ω < ℵ_{ω+1}: the cardinal ℵ_{ω+1} is the successor of the singular ℵ_ω.

@[category test, AMS 5] example : ℵ_ ω < ℵ_ (ω + 1) := ⊢ ℵ_ ω < ℵ_ (ω + 1) All goals completed! 🐙

GCH implies 2^(ℵ_ω) = ℵ_{ω+1} — the arithmetic fact used in the Erdős–Hajnal–Rado [EHR65] proof. Direct from the Jech-style formulation of GCH.

@[category test, AMS 5] theorem GCH_implies_power_aleph_omega (hGCH : GCH) : (2 : Cardinal.{0}) ^ ℵ_ ω = ℵ_ (ω + 1) := hGCH:GCH⊢ 2 ^ ℵ_ ω = ℵ_ (ω + 1) hGCH:GCHh:2 ^ ℵ_ ω = ℵ_ (Order.succ ω)⊢ 2 ^ ℵ_ ω = ℵ_ (ω + 1) rwa [hGCH:GCHh:2 ^ ℵ_ ω = ℵ_ (ω + 1)⊢ 2 ^ ℵ_ ω = ℵ_ (ω + 1)hGCH:GCHh:2 ^ ℵ_ ω = ℵ_ (ω + 1)⊢ 2 ^ ℵ_ ω = ℵ_ (ω + 1) at h

ℵ_{ω+1} = Order.succ (ℵ_ω): a structural fact used in partition calculus.

@[category test, AMS 5] theorem aleph_omega_succ_is_successor : ℵ_ (ω + 1) = Order.succ (ℵ_ ω) := ⊢ ℵ_ (ω + 1) = Order.succ (ℵ_ ω) All goals completed! 🐙end erdos_1168.variantsend Erdos1168