Erdős's 1954 conjectures on independent sets for set mappings of the real line with nondense, bounded-measure pictures

In 'Some remarks on set theory. III' (Michigan Mathematical Journal 2, 1953-1954), Paul Erdős studied set mappings assigning to each real number x a 'picture' S(x) contained in the reals with x not in S(x), and asked how thin the pictures must be to force an 'independent' (free) set - a set no member of which belongs to the picture of another. He proved that nowhere-dense pictures give a denumerable independent set (Theorem 6), showed that neither pictures of power below the continuum, nor nondense pictures, nor even nondense pictures of finite (unboundedly large) measure force an independent pair (Theorems 1-3), and then conjectured that nondense pictures with uniformly bounded measure force an independent pair - probably an infinite independent set - and that on [0,1] nondense pictures of measure less than 1/2 force an independent pair. He also asked whether Theorem 6 can be strengthened to an uncountable independent set, admitting he could not decide this even for denumerable pictures under the continuum hypothesis.

Background

A set mapping (in the original 1954 terminology, an assignment of pictures) on the real line is a function assigning to each real number $x$ a set $S(x) \subseteq \mathbb{R}$ (the picture of $x$). A set $E$ of reals is independent (in modern terminology, free) for the set mapping if no element of $E$ belongs to the picture of any other element of $E$; an independent pair is two distinct reals $x, y$ such that $x \notin S(y)$ and $y \notin S(x)$. A set is everywhere dense (dense in the reals) if its closure is the whole real line; nowhere dense if its closure has empty interior; 'not everywhere dense' (nondense) is the weaker condition that the closure misses some nonempty open interval. 'Bounded measure' means the Lebesgue measures $\mu(S(x))$ are bounded by one fixed constant; a set is bounded if it lies in some interval of finite length; outer measure is denoted $\mu^*$. In the 1954 terminology, the power of a set is its cardinality, and denumerable means countably infinite; a point $x$ is a two-sided limit point of $S(x)$ if every neighborhood of $x$ meets $S(x)$ on both sides. The continuum hypothesis (CH) is the assertion $2^{\aleph_0} = \aleph_1$; Martin's Axiom (MA) is the standard forcing axiom (forcing being the technique for building models of set theory), compatible with a continuum larger than $\aleph_1$. The problem originates in 'Some remarks on set theory. III' (1954), where Erdős - under the standing convention $x \notin S(x)$ - proved: if every $S(x)$ has power less than that of the continuum and is not everywhere dense, there is an independent pair but not necessarily an independent triplet (Theorem 4, via König's theorem on cardinal arithmetic); if no point is a two-sided limit point of its picture and every $S(x)$ has power below the continuum, there is an infinite independent set but not necessarily a nondenumerable one (Theorem 5); and if every picture is nowhere dense, there is a denumerable independent set (Theorem 6). The same paper's negative results (Theorems 1-3) show that pictures of power below the continuum alone, nondense pictures alone, and nondense pictures of finite but unbounded measure each fail to force an independent pair. These conjectures are the natural next step in that ladder, and the question after Theorem 6 asks for its uncountable strengthening. Erdős and Hajnal developed these questions into the free-set research programme: the conjecture was refuted under CH in 1960, restated as Problem 38 of the 1971 UCLA problem list, answered by independence results for the nowhere-dense/uncountable part (Hechler; Avraham; Newelski), and solved affirmatively for closed pictures (Gladysz; Newelski-Pawlikowski-Seredyński). The problem is listed as Problem #501 on erdosproblems.com.

Problem Statement

Definitions (following Erdős 1954, in current language). A set mapping on the reals assigns to each real number $x$ a picture $S(x) \subseteq \mathbb{R}$. Two distinct reals $x, y$ form an independent pair if $x \notin S(y)$ and $y \notin S(x)$; a set $E$ of reals is an independent (free) set for the set mapping if every two distinct elements of $E$ form an independent pair. A set is everywhere dense (dense in the reals) if its closure is the whole real line; nowhere dense if its closure has empty interior; 'not everywhere dense' (nondense) is the weaker condition that the closure misses some nonempty open interval. 'Bounded measure' means the Lebesgue measures $\mu(S(x))$ are bounded by one fixed constant; a set is bounded if it lies in some interval of finite length; $\mu^*$ denotes Lebesgue outer measure. In (Q1) and (Q3) the pictures are assumed Lebesgue-measurable, so that $\mu(S(x))$ is defined; (Q2) uses outer measure and needs no measurability assumption. Denumerable means countably infinite; $\aleph_0$ and $\aleph_1$ are the first infinite and first uncountable cardinals and $c = 2^{\aleph_0}$ is the cardinality of the continuum. ZFC is Zermelo-Fraenkel set theory with the axiom of choice.

Conventions. Erdős's 1954 paper and Erdős-Hajnal 1960 additionally require $x \notin S(x)$ for every $x$; this is the standing convention of the two original papers and is adopted for Q1 and Q3 below. The modern restatements of the descendant problem Q2 (Newelski-Pawlikowski-Seredyński 1987; erdosproblems.com Problem #501) drop this requirement and let freeness bind only distinct pairs; Q2 is stated in this exclusion-free form, which for positive results is the stronger and canonical target. The two conventions are equivalent for counterexamples: deleting $x$ from $S(x)$ preserves every hypothesis class used here (nondense, bounded measure, $\mu^* < 1$, $\mu < 1/2$, bounded) and changes no independence relation between distinct points.

The open core of the 1954 questions consists of the following problems, each to be resolved in ZFC without additional hypotheses.

(Q1) The original pair conjecture, unconditional status. If every picture $S(x)$ is not everywhere dense and $\sup_x \mu(S(x))$ is finite, must there exist an independent pair - as Erdős conjectured, probably even an infinite independent set? Known: the answer is negative under the continuum hypothesis CH (the assertion $2^{\aleph_0} = \aleph_1$) and under the weaker hypothesis $H_0$ that the reals admit a well-ordering whose proper initial segments all have measure zero (Erdős-Hajnal 1960, with pictures of measure exactly 1); it is positive in ZFC when the pictures have measure 0 (an independent pair), when they are closed (an infinite independent set, Newelski-Pawlikowski-Seredyński 1987), and when they are both closed and null. For general non-closed pictures of positive, uniformly bounded measure, no unconditional proof or refutation is known.

(Q2) The descendant problem, stated as Problem 38(C) of Erdős-Hajnal 1971 and listed as the first question of erdosproblems.com Problem #501, in the exclusion-free form. If every picture $S(x)$ is a bounded set with $\mu^*(S(x)) < 1$, must there exist an infinite independent set? Known: arbitrarily large finite independent sets exist in ZFC (Erdős-Hajnal 1960); counterexamples exist under the continuum hypothesis and under Martin's Axiom (the standard forcing axiom, compatible with a continuum larger than $\aleph_1$), the latter even with null pictures (Hechler 1972); a positive answer is asserted under the additional hypothesis that Lebesgue measure extends to all subsets of the reals. The cited status page (erdosproblems.com #501, Reference 19) reports an independence claim for this question and notes that the claim has not been examined, so the question remains open.

(Q3) The 1954 local variant, not treated separately in the later literature. If every picture $S(x)$ is not everywhere dense with $\mu(S(x)) < 1/2$, must there exist an independent pair of points both lying in the interval $[0, 1]$? Its unconditional status parallels (Q1); the continuum-hypothesis construction of Erdős-Hajnal 1960 presumably refutes it under the continuum hypothesis, but no published source treats this variant.

Resolved by independence, hence not part of the open core: the 1954 strengthening question for Theorem 6 - whether a nowhere-dense set mapping on the reals admits an uncountable independent set, in particular under the continuum hypothesis with denumerable pictures. Hechler (1972) showed that under CH the answer is negative even when every picture is a sequence whose only limit point is the point itself (precisely the case Erdős left open in 1954), while Avraham (1981) and Newelski (1987) showed that under MA the answer is positive, with free sets of every cardinality below the continuum; the statement is independent of ZFC and the 1954 question is closed. No additional restrictions (of dimensionality, definability, or regularity of the pictures) are imposed on any of the open questions beyond those stated (the measurability assumed for (Q1) and (Q3) is one of the stated conditions).

References

1. P. Erdős, 'Some remarks on set theory. III', Michigan Mathematical Journal 2 (1953-1954), 51-57. DOI: 10.1307/mmj/1028989869.
2. P. Erdős and A. Hajnal, 'Some remarks on set theory. VIII', Michigan Mathematical Journal 7 (1960), 187-191. DOI: 10.1307/mmj/1028998389, https://doi.org/10.1307/mmj/1028998389.
3. P. Erdős, 'Some unsolved problems', Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 6 (1961), 221-254. https://www.renyi.hu/~p_erdos/1961-22.pdf.
4. S. Gladysz, 'Bemerkungen über die Unabhängigkeit der Punkte in Bezug auf mengenwertete Funktionen', Acta Mathematica Academiae Scientiarum Hungaricae 13 (1962), 199-201. DOI: 10.1007/BF02033638, https://doi.org/10.1007/BF02033638.
5. A. Máté, 'On the theory of relations', Publications of the Mathematical Institute of the Hungarian Academy of Sciences 9 (1964), 331-333.
6. P. Erdős and A. Hajnal, 'Unsolved problems in set theory', in Axiomatic Set Theory, Proceedings of Symposia in Pure Mathematics, Vol. XIII, Part I, American Mathematical Society, Providence, 1971, pp. 17-48. DOI: 10.1090/pspum/013.1/0280381, https://doi.org/10.1090/pspum/013.1/0280381.
7. S. H. Hechler, 'Directed graphs over topological spaces: Some set theoretical aspects', Israel Journal of Mathematics 11 (1972), 231-248. DOI: 10.1007/BF02789314.
8. F. Bagemihl, 'The existence of an everywhere dense independent set', Michigan Mathematical Journal 20 (1973), 1-2. DOI: 10.1307/mmj/1029001004.
9. P. Erdős, A. Hajnal, and A. Máté, 'Chain conditions on set mappings and free sets', Acta Scientiarum Mathematicarum (Szeged) 34 (1973), 69-79. https://www.renyi.hu/~p_erdos/1973-03.pdf.
10. P. Erdős and A. Hajnal, 'Unsolved and solved problems in set theory', in Proceedings of the Tarski Symposium, Proceedings of Symposia in Pure Mathematics, Vol. XXV, American Mathematical Society, Providence, 1974, pp. 269-287. DOI: 10.1090/pspum/025/0357122, https://doi.org/10.1090/pspum/025/0357122.
11. U. Avraham, 'Free sets for nowhere-dense set mappings', Israel Journal of Mathematics 39 (1981), 167-176. DOI: 10.1007/BF02762863.
12. L. Newelski, J. Pawlikowski, and W. Seredyński, 'Infinite free set for small measure set mappings', Proceedings of the American Mathematical Society 100 (1987), 335-339. DOI: 10.1090/s0002-9939-1987-0884475-3.
13. L. Newelski, 'Free sets for some special set mappings', Israel Journal of Mathematics 58 (1987), 213-224. DOI: 10.1007/BF02785679.
14. K. Muthuvel, 'Nowhere dense set mappings on the generalized linear continua', Order 7 (1990), 179-182. DOI: 10.1007/BF00383765.
15. F. Bagemihl, 'Independent sets and second category', Order 7 (1990), 65-66. DOI: 10.1007/BF00383173.
16. P. Komjáth, 'A set mapping with no infinite free subsets', Journal of Symbolic Logic 56 (1991), 1400-1402. DOI: 10.2307/2275484.
17. A. Avilés and C. Piña, 'Free sets for set-mappings relative to a family of sets', Mathematical Logic Quarterly 63 (2017), 605-613. DOI: 10.1002/malq.201600100.
18. P. Komjáth, 'Set mappings with free sets which are arithmetic progressions', Mathematika 64 (2018), 71-76. DOI: 10.1112/s0025579317000353.
19. Erdős Problems, Problem #501, https://www.erdosproblems.com/501, accessed 21 September 2026; page last edited 3 September 2026.