/-
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 Mathlib.Combinatorics.SimpleGraph.Clique
public import Mathlib.Data.Sym.Sym2
public import Mathlib.SetTheory.Cardinal.Aleph
public import Mathlib.SetTheory.Ordinal.Exponential
public import FormalConjecturesForMathlib.SetTheory.Cardinal.SimpleGraph@[expose] public sectionopen Cardinal OrdinalOrdinal and cardinal partition relations (binary)
This file consolidates the binary ordinal/cardinal partition relations used in several Erdős set-theory problems:
OrdinalRamsey α β γ — α → (β, γ)²: 2-coloring of pairs of α, finding
monochromatic subsets of ordinal types β (red) or γ (blue).
OrdinalMultiColorRamsey α β γ k — α → (β, γ, …, γ)²_{k+1}: multicolor partition
with k "small" colors targeting cardinality γ and one "large" color targeting
ordinal type β.
CardinalCountableColorRamsey κ — κ → (κ, 3, 3, …)²_{ℵ₀}: countably-colored
partition relation with a large color-0 class and triangle targets in every other
color.
These complement OrdinalCardinalRamsey (see
FormalConjecturesForMathlib.SetTheory.Cardinal.SimpleGraph) which uses a cardinality
target on the blue side instead of an ordinal-type target; the bridge lemma
ordinalMultiColorRamsey_one_iff_ordinalCardinalRamsey identifies the k = 1 case of
the Sym2-coloring style with that SimpleGraph-pair style.
universe u
OrdinalRamsey α β γ asserts the ordinal Ramsey property α → (β, γ)².
It states that for any 2-coloring of the complete graph on the ordinal α,
one of the following must hold:
There is a red clique which is order-isomorphic to β (a red K_β).
There is a blue clique which is order-isomorphic to γ (a blue K_γ).
def OrdinalRamsey (α β γ : Ordinal.{u}) : Prop :=
∀ red blue : SimpleGraph α.ToType, IsCompl red blue →
(∃ s, red.IsClique s ∧ typeLT s = β) ∨
(∃ s, blue.IsClique s ∧ typeLT s = γ)
OrdinalMultiColorRamsey α β γ k asserts the multicolor partition relation
α → (β, γ, γ, …, γ)²_{k+1} (with k copies of γ).
For any function col : Sym2 α.ToType → Fin (k + 1) assigning one of k+1 colors
to each pair from α, one of the following holds:
Color 0: there is a set A ⊆ α.ToType of order type β that is monochromatic
in color 0.
Color i+1 (for some i : Fin k): there is a set A ⊆ α.ToType with #A = γ
that is monochromatic in color i.succ.
When k = 1 this reduces to the binary partition relation α → (β, γ)² on the
cardinality side (see ordinalMultiColorRamsey_one_iff_ordinalCardinalRamsey).
def OrdinalMultiColorRamsey (α β : Ordinal.{u}) (γ : Cardinal.{u}) (k : ℕ) : Prop :=
∀ col : Sym2 α.ToType → Fin (k + 1),
(∃ A : Set α.ToType,
(∀ x ∈ A, ∀ y ∈ A, x ≠ y → col s(x, y) = 0) ∧
typeLT A = β) ∨
(∃ (i : Fin k) (A : Set α.ToType),
(∀ x ∈ A, ∀ y ∈ A, x ≠ y → col s(x, y) = i.succ) ∧
#A = γ)
CardinalCountableColorRamsey κ asserts the partition relation
κ → (κ, 3, 3, …)²_{ℵ₀} with countably many colors (indexed by ℕ).
For any coloring col : Sym2 κ.ord.ToType → ℕ of pairs from the initial ordinal of κ,
one of the following holds:
Color 0 (large monochromatic set): there is a set A ⊆ κ.ord.ToType with
#A = κ such that every pair in A gets color 0.
Some positive color (triangle): there are n : ℕ and three distinct elements
x y z : κ.ord.ToType such that all three pairs are colored n + 1.
This is the countably-colored analogue of OrdinalMultiColorRamsey, replacing
Fin (k+1) with ℕ (so ℵ_0-many colors) and requiring monochromatic triangles
(rather than arbitrary monochromatic cliques) in the positive colors.
def CardinalCountableColorRamsey (κ : Cardinal.{u}) : Prop :=
∀ col : Sym2 κ.ord.ToType → ℕ,
(∃ A : Set κ.ord.ToType,
(∀ x ∈ A, ∀ y ∈ A, x ≠ y → col s(x, y) = 0) ∧
#A = κ) ∨
(∃ (n : ℕ) (x y z : κ.ord.ToType),
x ≠ y ∧ x ≠ z ∧ y ≠ z ∧
col s(x, y) = n + 1 ∧
col s(x, z) = n + 1 ∧
col s(y, z) = n + 1)
Bridge between the two coloring styles. For k = 1, the Sym2-coloring relation
OrdinalMultiColorRamsey α β γ 1 coincides with the SimpleGraph-style relation
OrdinalCardinalRamsey α β γ (a complementary pair of graphs, with an order-type
target β on the red side and a cardinality target γ on the blue side).
All goals completed! 🐙