/- 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 1173

Reference: erdosproblems.com/1173

@[expose] public sectionopen Cardinal Ordinalopen scoped Cardinal Ordinalnamespace Erdos1173

The set mapping condition for f : ω_{ω+1} → 𝒫(ω_{ω+1}): self-avoidance (α ∉ f α), image bound (#(f α) ≤ ℵ_ω), and almost-disjoint images (#(f α ∩ f β) < ℵ_ω for α ≠ β).

def IsSetMapping (f : (ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToType) : Prop := (∀ α : (ω_ (ω + 1)).ToType, α ∉ f α) ∧ (∀ α : (ω_ (ω + 1)).ToType, #(f α) ≤ ℵ_ ω) ∧ (∀ α β : (ω_ (ω + 1)).ToType, α ≠ β → #(f α ∩ f β : Set (ω_ (ω + 1)).ToType) < ℵ_ ω)

A set Y ⊆ ω_{ω+1} is free for f if for all distinct α, β ∈ Y, β ∉ f α.

def IsFreeSet (f : (ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToType) (Y : Set (ω_ (ω + 1)).ToType) : Prop := ∀ α ∈ Y, ∀ β ∈ Y, α ≠ β → β ∉ f α

Erdős–Hajnal Problem 1173 [EH74]. Assume GCH. Let $f : \omega_{\omega+1} \to [\omega_{\omega+1}]^{\leq \aleph_\omega}$ be a set mapping such that $|f(\alpha) \cap f(\beta)| < \aleph_\omega$ for all $\alpha \neq \beta$. Does there exist a free set of cardinality $\aleph_{\omega+1}$?

@[category research open, question, AMS 3] theorem erdos_1173 : GCH → ∀ f : (ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToType, IsSetMapping f → ∃ Y : Set (ω_ (ω + 1)).ToType, IsFreeSet f Y ∧ #Y = ℵ_ (ω + 1) := ⊢ GCH → ∀ (f : (ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToType), IsSetMapping f → ∃ Y, IsFreeSet f Y ∧ #↑Y = ℵ_ (ω + 1) All goals completed! 🐙

The initial ordinal ω_{ω+1} has cardinality ℵ_{ω+1}.

All goals completed! 🐙

ℵ_ω < ℵ_{ω+1}: free-set size is strictly above the image-bound, making the problem non-trivial.

@[category test, AMS 3] theorem erdos_1173.sanity.aleph_omega_lt_succ : ℵ_ ω < ℵ_ (ω + 1) := ⊢ ℵ_ ω < ℵ_ (ω + 1) All goals completed! 🐙

The empty set is always free for any f.

@[category test, AMS 3] theorem erdos_1173.sanity.empty_is_free (f : (ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToType) : IsFreeSet f ∅ := f:(ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToType⊢ IsFreeSet f ∅ f:(ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToTypeα✝:(ω_ (ω + 1)).ToTypehα:α✝ ∈ ∅⊢ ∀ β ∈ ∅, α✝ ≠ β → β ∉ f α✝ All goals completed! 🐙

A singleton {α} is always free for any f (the α ≠ β premise is vacuous).

@[category test, AMS 3] theorem erdos_1173.sanity.singleton_is_free (f : (ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToType) (α : (ω_ (ω + 1)).ToType) : IsFreeSet f {α} := f:(ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToTypeα:(ω_ (ω + 1)).ToType⊢ IsFreeSet f {α} f:(ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToTypeα:(ω_ (ω + 1)).ToTypea:(ω_ (ω + 1)).ToTypeha:a ∈ {α}b:(ω_ (ω + 1)).ToTypehb:b ∈ {α}hab:a ≠ b⊢ b ∉ f a f:(ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToTypeα:(ω_ (ω + 1)).ToTypea:(ω_ (ω + 1)).ToTypeb:(ω_ (ω + 1)).ToTypehab:a ≠ bha:a = αhb:b = α⊢ b ∉ f a All goals completed! 🐙

Free sets are downward-closed under inclusion.

@[category textbook, AMS 3] theorem erdos_1173.variants.free_set_mono (f : (ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToType) {Y Z : Set (ω_ (ω + 1)).ToType} (hYZ : Z ⊆ Y) (hY : IsFreeSet f Y) : IsFreeSet f Z := f:(ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToTypeY:Set (ω_ (ω + 1)).ToTypeZ:Set (ω_ (ω + 1)).ToTypehYZ:Z ⊆ YhY:IsFreeSet f Y⊢ IsFreeSet f Z f:(ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToTypeY:Set (ω_ (ω + 1)).ToTypeZ:Set (ω_ (ω + 1)).ToTypehYZ:Z ⊆ YhY:IsFreeSet f Yα:(ω_ (ω + 1)).ToTypehα:α ∈ Zβ:(ω_ (ω + 1)).ToTypehβ:β ∈ Zhne:α ≠ β⊢ β ∉ f α All goals completed! 🐙

Under IsSetMapping f, each image has cardinality < ℵ_{ω+1}.

@[category textbook, AMS 3] theorem erdos_1173.variants.image_lt_aleph_succ (f : (ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToType) (hf : IsSetMapping f) (α : (ω_ (ω + 1)).ToType) : #(f α) < ℵ_ (ω + 1) := f:(ω_ (ω + 1)).ToType → Set (ω_ (ω + 1)).ToTypehf:IsSetMapping fα:(ω_ (ω + 1)).ToType⊢ #↑(f α) < ℵ_ (ω + 1) All goals completed! 🐙end Erdos1173