Erdős Problem #501

Erdős Problem 501: independent sets for small-measure set mappings

The two questions and their known resolution

The first assertion is independent of ZFC, in the usual relative-consistency sense; the second is a theorem, with an infinite set in place of three points. We reconstruct the CH counterexample and the closed-set theorem in detail. For the positive consistency direction we explicitly import the random-real theorem stated below. This is an exposition of known work, not a new resolution or a claim to have run Lean locally.

The construction is due to Hechler. The closed-set argument is due to Newelski, Pawlikowski and Seredyński, Infinite free set for small measure set mappings, Proc. Amer. Math. Soc. 100 $1987$, 335--339, https://doi.org/10.1090/S0002-9939-1987-0884475-3. We checked the proof against the author-linked exposition and formalization in https://github.com/elliotglazer/erdos501/blob/main/Erdos501/Closed.lean. Current problem statement: https://www.erdosproblems.com/501.

A complete counterexample under CH

If $X$ were an infinite independent set, repeatedly take the least unused ordinal index in $X$, obtaining $\alpha_0<\alpha_1<\cdots$. For $i<j$, independence says $x_{\alpha_i}\notin A_{x_{\alpha_j}}$. In view of $1$, \[ |x_{\alpha_i}|>|x_{\alpha_j}|+1. \] Iteration gives $|x_{\alpha_j}|<|x_{\alpha_0}|-j$, impossible for a sufficiently large integer $j$. Hence the first assertion fails under CH. The argument uses a countable sequence extracted from the well-order; it does not assume that all of $X$ has order type $\omega$.

Outer-measure tools for the closed case

First, for increasing sets $B_j$, $\lambda^*(\bigcup_jB_j)=\lim_j\lambda^*(B_j)$. If the limit on the right is finite, choose measurable hulls $H_j\supset B_j$ of the same outer measure and replace $H_j$ by $\bigcap_{k\ge j}H_k$. These new hulls increase, still contain $B_j$, and have measure at most $\lambda^*(B_j)$. Continuity of measure for their union proves the assertion. If the limit is infinite, monotonicity suffices.

Second, for a fixed $B$ of finite outer measure, the assignment \[ \nu(D)=\lambda^*(B\cap D) \] is a finite measure on the Borel sets $D$. This follows from the Carathéodory splitting property of measurable sets, first for finite Borel partitions and then for countable partitions. Thus it has the usual continuity from above and below. Measurable hulls of sets of finite outer measure exist by the defining interval-cover approximation to Lebesgue outer measure.

The preservation lemma

Suppose instead that every $C_Y(x)$, $x\in Y$, has finite outer measure. Set $B_x=\{t\in Y:x\notin A_t\}$. Since \[ B_x\subset C_Y(x)\cup A_x\cup\{x\}, \] each $B_x$ has finite outer measure. The sets $Y_M=\{x\in Y:\lambda^*(B_x)\le M\}$, $M\in\mathbb N$, increase to $Y$. By the first outer-measure fact, some $M$ has $\lambda^*(Y_M)>1$. Intersecting with a sufficiently large bounded interval gives $Y'\subset Y_M$ with \[ 1<a:=\lambda^*(Y')<\infty. \] Put $\eta=(a-1)/2>0$.

For each $t\in Y$, the open set $\mathbb R\setminus A_t$ is an increasing union of finite unions of open intervals with rational endpoints. The second outer-measure fact, with $B=Y'$, therefore supplies such a finite union $U_t\subset\mathbb R\setminus A_t$ with \[ \lambda^*(Y'\setminus U_t)<1+\eta=a-\eta, \qquad \lambda^*(Y'\cap U_t)>\eta. \tag{2} \] There are only countably many possible finite unions $U_t$. Enumerate them and use the first outer-measure fact again to choose a finite collection $\mathcal U$ for which \[ Z=\{t\in Y:U_t\in\mathcal U\}, \qquad \lambda^*(Z)>\frac{aM}{\eta}. \tag{3} \]

Partition $\mathbb R$ into the finitely many Borel atoms $D_\sigma$ of the Boolean algebra generated by $\mathcal U$, and put $w_\sigma=\lambda^*(Y'\cap D_\sigma)$. Their weights sum to $a$. For each positive-weight atom choose $z_\sigma\in Y'\cap D_\sigma$. Because membership in every $U\in\mathcal U$ is constant on an atom, the set \[ K_\sigma=\{t\in Z:D_\sigma\subset U_t\} \] is contained in $\{t\in Y:z_\sigma\notin A_t\}=B_{z_\sigma}$. It therefore has outer measure at most $M$. Choose a measurable hull $H_\sigma\supset K_\sigma$ of measure at most $M$ and define the measurable nonnegative function \[ g(t)=\sum_{w_\sigma>0}w_\sigma\,\mathbf1_{H_\sigma}(t). \] Its integral is at most $aM$. For each $t\in Z$, the atoms contained in $U_t$ have total weight $\lambda^*(Y'\cap U_t)>\eta$ by $2$; all their positive weights contribute to $g(t)$. Thus $Z\subset\{g>\eta\}$, and Markov's inequality gives \[ \lambda^*(Z)\le\lambda\{g>\eta\}\le\frac{aM}{\eta}, \] contradicting $3$. This proves the preservation lemma. In particular, the proof never assumes that the two-variable relation $x\in A_y$ is measurable.

An infinite independent set for closed values

This proves the second question and more. Boundedness of the individual closed sets was not needed; their uniformly bounded measures were enough.

The explicit external input for relative independence

The standard constructible-universe and forcing relative-consistency theorems now give the two conclusions. If ZFC is consistent, then ZFC+CH is consistent, and $1$ gives the negative answer there. Starting from a CH model and applying the cited random-real theorem gives the consistency of the positive answer. Thus, conditional only on consistency of ZFC, neither the assertion nor its negation is provable in ZFC. No large-cardinal assumption is imported.

Scope and correction of the earlier example

For the family $A_x=[x,x+1/2]$, an integer-spaced sequence is independent. An arbitrary decreasing sequence need not be: $x_j=1/j$ has $x_2=1/2\in A_{x_3}=[1/3,5/6]$. This corrects the earlier GPT-5.2 sanity example while preserving its original source file offline and in its original model folder.

COMPLETION ESTIMATE

1) FORMAL RESTATEMENT

Let $m^*$ denote Lebesgue outer measure on $\mathbb R$. For each $x\in\mathbb R$, suppose we are given a set $A_x\subset\mathbb R$ such that: - $A_x$ is bounded, and - $m^*(A_x)<1$.

Call a set $X\subseteq\mathbb R$ independent (for the map $x\mapsto A_x$) if for all distinct $x,y\in X$ we have $x\notin A_y$.

Question 1: Must there exist an infinite independent set $X\subseteq\mathbb R$?

Question 2: If additionally each $A_x$ is closed and has (Lebesgue) measure $m(A_x)<1$, must there exist an independent set of size $3$?

2) QUICK LITERATURE/CONTEXT CHECK

The problem statement reports: (a) Erdős--Hajnal proved existence of arbitrarily large finite independent sets under the assumptions of Question 1; (b) Gladysz proved existence of an independent set of size $2$ under the assumptions of Question 2; (c) Hechler showed Question 1 can fail under CH; (d) Newelski--Pawlikowski--Seredyński proved Question 1 has a positive answer if all $A_x$ are closed.

In what follows I do not use these results as black boxes. Instead I prove a conditional version of the finite independent-set statement under an additional measurability hypothesis.

3) ATTACK PLAN

Proof track: try to build an independent set by a measure/selection argument. The key difficulty is that the set \[E:=\{(u,v)\in\mathbb R^2:\ u\in A_v\} \] need not be measurable in $\mathbb R^2$ without extra hypotheses on the assignment $v\mapsto A_v$.

Construction/disproof track: understand how non-measurability of $E$ could obstruct Fubini-type estimates; identify where additional definability assumptions (Borel/analytic) restore them.

4) WORK

The following lemmas are conditional on a measurability assumption for the relation $E$. This is not part of the problem statement, so these are partial results only.

Assumption (measurability of the membership relation). Assume that the set $E=\{(u,v): u\in A_v\}\subset\mathbb R^2$ is Lebesgue measurable. (For example, this would hold if $(u,v)\mapsto \mathbf 1_{u\in A_v}$ were Borel measurable; the problem statement does not assume this.)

Lemma 501.1 (Independent pair under measurability). Under the measurability assumption on $E$, there exist distinct $x,y\in\mathbb R$ such that $x\notin A_y$ and $y\notin A_x$.

Proof. Fix an interval $I\subset\mathbb R$ of length $L>2$. Consider the measurable sets \[E_I:=E\cap (I\times I),\qquad E_I^T:=\{(u,v)\in I\times I : (v,u)\in E\}. \] By Fubini/Tonelli (applied to the indicator of $E_I$), \[ m_2(E_I)=\int_{v\in I} m_1(\{u\in I: (u,v)\in E\})\,dv =\int_{v\in I} m_1(A_v\cap I)\,dv. \] For each $v$, $m_1(A_v\cap I)\le m^*(A_v)<1$, hence $m_2(E_I)<\int_I 1\,dv = L$. The same argument gives $m_2(E_I^T)<L$. Therefore \[ m_2(E_I\cup E_I^T)\le m_2(E_I)+m_2(E_I^T) < 2L. \] But $m_2(I\times I)=L^2$, and since $L>2$ we have $L^2>2L$. Hence $(I\times I)\setminus (E_I\cup E_I^T)$ has positive measure and is nonempty. Pick $(x,y)$ in this complement with $x\ne y$ (the diagonal has measure $0$). Then $(x,y)\notin E$ implies $x\notin A_y$, and $(x,y)\notin E^T$ implies $y\notin A_x$. Thus $\{x,y\}$ is an independent set. $\square$

Lemma 501.2 (Arbitrarily large finite independent sets under measurability). Under the measurability assumption on $E$, for every integer $m\ge 1$ there exists an independent set $X\subset\mathbb R$ with $\lvert X\rvert\ge m$.

Proof. Fix $m\ge 1$. Choose an interval $I$ of length $L:=8m$. Let $N:=4m$ and sample $N$ i.i.d. points $X_1,\dots,X_N$ uniformly from $I$. Define an undirected graph $G$ on vertex set $\{1,\dots,N\}$ by putting an edge $\{i,j\}$ (with $i\ne j$) if either $X_i\in A_{X_j}$ or $X_j\in A_{X_i}$. If $S\subset\{1,\dots,N\}$ is an independent set in this graph, then by definition for all distinct $i,j\in S$ we have $X_i\notin A_{X_j}$ and $X_j\notin A_{X_i}$; hence $\{X_i:i\in S\}$ is an independent set in the sense of the problem.

We bound the expected number of edges in $G$. For $i\ne j$, \[ \mathbb P[X_i\in A_{X_j}] =\frac{1}{L^2}\,m_2(E\cap (I\times I)) =\frac{1}{L^2}\int_{v\in I} m_1(A_v\cap I)\,dv \le \frac{1}{L^2}\int_I 1\,dv =\frac{1}{L}. \] Similarly $\mathbb P[X_j\in A_{X_i}]\le 1/L$, so by the union bound \[\mathbb P[\{i,j\}\text{ is an edge of }G]\le \frac{2}{L}. \] Let $M$ be the number of edges of $G$. By linearity of expectation, \[ \mathbb E[M] \le \binom{N}{2}\cdot \frac{2}{L} =\frac{N(N-1)}{L} <\frac{N^2}{L}. \] With $N=4m$ and $L=8m$, this gives $\mathbb E[M]<2m$. By Markov's inequality, $\mathbb P[M\le 4m]>0$. Fix an outcome with $M\le 4m$.

For any finite graph with $N$ vertices and $M$ edges, the average degree is $\bar d=2M/N$, and there exists an independent set of size at least $N/(\bar d+1)=N^2/(2M+N)$ (this follows from the Caro--Wei bound or a simple averaging argument). Applying this with $M\le 4m$ and $N=4m$ gives \[ \alpha(G)\ge \frac{N^2}{2M+N}\ge \frac{(4m)^2}{2\cdot (4m) + 4m}=\frac{16m^2}{12m}=\frac{4m}{3}>m. \] Choosing $m$ vertices in such an independent set yields an independent set of size $m$ in $\mathbb R$. $\square$

FAST REALITY CHECK

These lemmas are not about small-$n$ computation but about measure-theoretic structure. A quick sanity example where an infinite independent set exists: if $A_x=[x,x+1/2]$ for all $x$, then any strictly decreasing infinite sequence $x_1>x_2>\cdots$ is independent, since $x_i\notin [x_j,x_j+1/2]$ whenever $i<j$.

5) VERIFICATION

Where measurability is used: Lemmas 501.1--501.2 use Fubini/Tonelli on $\mathbf 1_{E\cap (I\times I)}$. Without measurability of $E$, Fubini-type identities can fail, so these proofs do not resolve the original question.

Quantifiers: The constructed independent sets are finite (size $m$ arbitrary) and depend on the measurability assumption; they do not imply existence of an infinite independent set.

6) FINAL UNRESOLVED

(i) Strongest proved partial result here: If the membership relation $E=\{(u,v):u\in A_v\}$ is Lebesgue measurable, then there exist independent sets of arbitrary finite size (Lemma 501.2), and in particular an independent pair (Lemma 501.1).

(ii) First gap (crisp): Remove the extra hypothesis that $E$ is measurable: prove or disprove in ZFC that for every assignment $x\mapsto A_x$ with each $A_x$ bounded and $m^*(A_x)<1$ there exists an infinite independent set.

(iii) Top 3 next moves: 1. Try to show $E$ is measurable (or sufficiently definable) under natural additional hypotheses (e.g. all $A_x$ Borel/closed) and see whether the argument can be iterated transfinitely to produce an infinite independent set. 2. Attempt a direct transfinite recursion construction of an infinite independent set that avoids needing Fubini on $E$. 3. Search for explicit (ZFC) pathological set-mappings $x\mapsto A_x$ of small outer measure that might block infinite free sets; pin down whether any such construction must use additional set-theory (e.g. CH).

(iv) Minimal counterexample structure: a counterexample in ZFC to Question 1 would likely define a highly non-measurable relation $E\subset\mathbb R^2$ with all vertical sections $E_v=A_v$ of outer measure $<1$, but such that $E\cup E^T$ covers $X\times X$ for every infinite $X\subset\mathbb R$ (forcing an edge in every infinite subset).