Skip to content

Erdős problem 501

For every x∈Rx \in \mathbb{R} let Ax⊂RA_x \subset \mathbb{R} be a bounded set of Lebesgue outer measure <1< 1. Must there be an infinite independent set, that is an infinite X⊆RX \subseteq \mathbb{R} with x∉Ayx \notin A_y for all distinct x,y∈Xx, y \in X?

Sources

The source's own material, retained exactly.

14 retained statements36c6d0fef71a

Open selected source

FormalConjectures/ErdosProblems/

501.lean

Retained formal statement8 of 13

Erdős–Hajnal (1960): arbitrarily large finite independent sets exist.

For every n : ℕ and every family A : ℝ → Set ℝ of bounded sets with Lebesgue outer measure < 1, there exists a finite independent set of size at least n.

This was proved by Erdős and Hajnal [ErHa60].

FormalConjectures/ErdosProblems/501.leanErdos501.erdos_501.variants.erdosHajnal_finite4 linesExact file
True ↔  ∀ (n : ℕ) (A : ℝ → Set ℝ),    (∀ (x : ℝ), Bornology.IsBounded (A x)) →      (∀ (x : ℝ), MeasureTheory.volume.toOuterMeasure (A x) < 1) → ∃ X, n ≤ X.card ∧ (↑X).Pairwise fun x y => x ∉ A y
SolvedStatement only, no proof