WorksMathematics
A set mapping with small intersections and no large free set
Abstract
Let be an uncountable cardinal of countable cofinality and suppose that . We construct a self-avoiding set mapping on whose values have cardinality at most , whose distinct values have intersection of cardinality less than , and which has no free set of cardinality . The construction combines a countable neighborhood base with an enumeration of the -sized subsets and a schedule having fewer than requirements at each bounded depth. Under the generalized continuum hypothesis, this gives a negative answer to the free-set question of Erdős and Hajnal at .
Introduction and main result
Let be a set. A mapping is self-avoiding if for every . A subset is free for if
The question considered here asks whether small pairwise intersections of the values of a set mapping force a large free set. In the case raised by Erdős and Hajnal [1 Problem 35], one assumes the generalized continuum hypothesis, takes and , and requires
We give a counterexample under the weaker cardinal-arithmetic assumption . Throughout, we work in ZFC, identify cardinals with their initial ordinals, and write for the family of subsets of of cardinality .
Theorem 1.1. Let be an uncountable cardinal with and . Put . There is a self-avoiding mapping such that
but no subset of of cardinality is free for .
The intersection bound is pointwise: the construction does not require a single cardinal below to bound all pairwise intersections. This distinction is essential at a singular cardinal.
The use of values concentrated near their indexing points is motivated by Hechler’s construction discussed in [1 p. 279]. All ingredients needed for the construction below are proved here.
Proof of the main theorem
Proof of Theorem 1.1. Fix an increasing sequence of infinite cardinals below with supremum . Put .
The sequence space and its enumerations
Let , with the product topology obtained by giving the discrete topology. For and , define
These sets form a decreasing neighborhood base at . All closures below are taken in . If , then and are disjoint for some finite . The collection of all finite-prefix cylinders is a base of cardinality , since there are finite sequences from an infinite alphabet of size .
We first verify that . If , list its points as , allowing repetitions. For each , choose
This choice is possible because . For every , some satisfies , and then . Thus is absent from the list, a contradiction. On the other hand,
Since is the successor of , these inequalities give . Fix a bijective enumeration .
The family also has cardinality . Indeed,
For the reverse inequality, fix . The sets , for , are distinct members of . We may therefore enumerate this family as .
Scheduling the requirements
For each , choose an injection ; this is possible because . For , put
For every finite , injectivity of and monotonicity of the sequence give
In fact, implies . For the set on the left is empty.
The set mapping
For each , consider the indices
For every , choose a point
The defining closure condition makes this intersection nonempty. Define
Every chosen point differs from , so . Moreover, . By (2.5), for every and every finite ,
Indeed, if , then the selected point belongs to . Only indices of depth less than can contribute points outside that neighborhood. Repeated choices do not increase their number.
Pairwise intersections
Let . Choose a finite such that . Every common point of the two values of lies outside at least one of these neighborhoods. Hence
Applying (7), and using that is infinite, we obtain
Only two exceptional sets are combined here. No estimate for a countable union of sets of size less than the singular cardinal is used. The depth may depend on the pair .
No large free set
Let have cardinality . For each basic open set that meets , choose one point of , and let be the set of chosen points. Then , , and . Indeed, every basic neighborhood of a point of contains one of the chosen representatives.
Enlarge inside to a set of cardinality exactly . Then . Write . Since both and have cardinality at most , their union cannot exhaust . Choose
Because and , we have
Thus , and the construction selected a point
This point is distinct from . Hence is not free for . Since was arbitrary, has no free subset of cardinality .
Transfer to the ordinal domain
Use the fixed bijection to define
The bijection preserves self-avoidance, the cardinalities of values and their intersections, and freeness. Therefore has all the asserted properties. □
The Erdős–Hajnal question
Corollary 3.1. Assume the generalized continuum hypothesis, and put and . There is a self-avoiding mapping whose distinct values have intersection of cardinality less than , but which has no free set of cardinality .
Proof. Take . This cardinal has cofinality , and GCH gives . Theorem 1.1 applies. □
Identifying with its initial ordinal gives exactly the domain in the Erdős–Hajnal question. Thus the stated pointwise intersection condition does not force a free set of the required size.
Acknowledgments
Acknowledgments. The authors acknowledge the assistance of OpenAI’s ChatGPT in developing the construction and in preparing and checking the mathematical exposition.
References
References
- [1]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 25, American Mathematical Society, Providence, RI, 1974, pp. 269–287.DOI