betaFeedback

WorksMathematics

A set mapping with small intersections and no large free set

Abstract

Let μ\mu be an uncountable cardinal of countable cofinality and suppose that 2μ=μ+2^\mu=\mu^+. We construct a self-avoiding set mapping on μ+\mu^+ whose values have cardinality at most μ\mu, whose distinct values have intersection of cardinality less than μ\mu, and which has no free set of cardinality μ+\mu^+. The construction combines a countable neighborhood base with an enumeration of the μ\mu-sized subsets and a schedule having fewer than μ\mu 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 ℵω+1\aleph_{\omega+1}.

Introduction and main result

Let SS be a set. A mapping F:S→P(S)F:S\to\mathcal{P}(S) is self-avoiding if x∉F(x)x\notin F(x) for every x∈Sx\in S. A subset H⊆SH\subseteq S is free for FF if

x,y∈H,x≠y⟹y∉F(x).x,y\in H,\quad x\ne y\quad\Longrightarrow\quad y\notin F(x).

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 μ=ℵω\mu=\aleph_\omega and κ=μ+\kappa=\mu^+, and requires

f:κ⟶[κ]≤μ,∣f(α)∩f(β)∣<μ(α≠β).f:\kappa\longrightarrow[\kappa]^{\le\mu},\qquad|f(\alpha)\cap f(\beta)|<\mu\quad(\alpha\ne\beta).

We give a counterexample under the weaker cardinal-arithmetic assumption 2μ=μ+2^\mu=\mu^+. Throughout, we work in ZFC, identify cardinals with their initial ordinals, and write [S]μ[S]^\mu for the family of subsets of SS of cardinality μ\mu.

Theorem 1.1. Let μ\mu be an uncountable cardinal with cf⁡(μ)=ℵ0\operatorname{cf}(\mu)=\aleph_0 and 2μ=μ+2^\mu=\mu^+. Put κ=μ+\kappa=\mu^+. There is a self-avoiding mapping f:κ→[κ]≤μf:\kappa\to[\kappa]^{\le\mu} such that

∣f(α)∩f(β)∣<μfor all distinct α,β<κ,|f(\alpha)\cap f(\beta)|<\mu\qquad\text{for all distinct }\alpha,\beta<\kappa,

but no subset of κ\kappa of cardinality κ\kappa is free for ff.

The intersection bound is pointwise: the construction does not require a single cardinal below μ\mu 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 ⟨μn:n<ω⟩\langle\mu_n:n<\omega\rangle of infinite cardinals below μ\mu with supremum μ\mu. Put κ=μ+\kappa=\mu^+.

The sequence space and its enumerations

Let X=μωX=\mu^\omega, with the product topology obtained by giving μ\mu the discrete topology. For x∈Xx\in X and n<ωn<\omega, define

Un(x)={y∈X:y↾n=x↾n}.(1)U_n(x)=\{y\in X:y\upharpoonright n=x\upharpoonright n\}. \tag*{(1)}

These sets form a decreasing neighborhood base at xx. All closures below are taken in XX. If x≠yx\ne y, then UN(x)U_N(x) and UN(y)U_N(y) are disjoint for some finite NN. The collection B\mathcal{B} of all finite-prefix cylinders is a base of cardinality μ\mu, since there are μ\mu finite sequences from an infinite alphabet of size μ\mu.

We first verify that ∣X∣=κ|X|=\kappa. If ∣X∣≤μ|X|\le\mu, list its points as ⟨zξ:ξ<μ⟩\langle z_\xi:\xi<\mu\rangle, allowing repetitions. For each nn, choose

z(n)∈μ∖{zξ(n):ξ<μn}.z(n)\in\mu\setminus\{z_\xi(n):\xi<\mu_n\}.

This choice is possible because μn<μ\mu_n<\mu. For every ξ<μ\xi<\mu, some nn satisfies ξ<μn\xi<\mu_n, and then z(n)≠zξ(n)z(n)\ne z_\xi(n). Thus zz is absent from the list, a contradiction. On the other hand,

∣X∣=μℵ0≤(2μ)ℵ0=2μ⋅ℵ0=2μ=κ.(2)|X|=\mu^{\aleph_0}\le(2^\mu)^{\aleph_0}=2^{\mu\cdot\aleph_0}=2^\mu=\kappa. \tag*{(2)}

Since κ\kappa is the successor of μ\mu, these inequalities give ∣X∣=κ|X|=\kappa. Fix a bijective enumeration X={xα:α<κ}X=\{x_\alpha:\alpha<\kappa\}.

The family [X]μ[X]^\mu also has cardinality κ\kappa. Indeed,

∣[X]μ∣≤κμ=(2μ)μ=2μ⋅μ=2μ=κ.(3)|[X]^\mu|\le\kappa^\mu=(2^\mu)^\mu=2^{\mu\cdot\mu}=2^\mu=\kappa. \tag*{(3)}

For the reverse inequality, fix B∈[X]μB\in[X]^\mu. The sets B∪{x}B\cup\{x\}, for x∈X∖Bx\in X\setminus B, are κ\kappa distinct members of [X]μ[X]^\mu. We may therefore enumerate this family as ⟨Aξ:ξ<κ⟩\langle A_\xi:\xi<\kappa\rangle.

Scheduling the requirements

For each α<κ\alpha<\kappa, choose an injection hα:α→μh_\alpha:\alpha\to\mu; this is possible because ∣α∣≤μ|\alpha|\le\mu. For ξ<α\xi<\alpha, put

dα(ξ)=min⁡{n<ω:hα(ξ)<μn}.(4)d_\alpha(\xi)=\min\{n<\omega:h_\alpha(\xi)<\mu_n\}. \tag*{(4)}

For every finite NN, injectivity of hαh_\alpha and monotonicity of the sequence ⟨μn⟩\langle\mu_n\rangle give

∣{ξ<α:dα(ξ)<N}∣≤μN<μ.(5)|\{\xi<\alpha:d_\alpha(\xi)<N\}|\le\mu_N<\mu. \tag*{(5)}

In fact, dα(ξ)<Nd_\alpha(\xi)<N implies hα(ξ)<μNh_\alpha(\xi)<\mu_N. For N=0N=0 the set on the left is empty.

The set mapping

For each α<κ\alpha<\kappa, consider the indices

Iα={ξ<α:xα∈Aξ∖{xα}}.I_\alpha=\{\xi<\alpha:x_\alpha\in A_\xi\setminus\{x_\alpha\}\}.

For every ξ∈Iα\xi\in I_\alpha, choose a point

yα,ξ∈(Aξ∖{xα})∩Udα(ξ)(xα).y_{\alpha,\xi}\in(A_\xi\setminus\{x_\alpha\})\cap U_{d_\alpha(\xi)}(x_\alpha).

The defining closure condition makes this intersection nonempty. Define

F(xα)={yα,ξ:ξ∈Iα}.(6)F(x_\alpha)=\{y_{\alpha,\xi}:\xi\in I_\alpha\}. \tag*{(6)}

Every chosen point differs from xαx_\alpha, so xα∉F(xα)x_\alpha\notin F(x_\alpha). Moreover, ∣F(xα)∣≤∣Iα∣≤∣α∣≤μ|F(x_\alpha)|\le|I_\alpha|\le|\alpha|\le\mu. By (2.5), for every α<κ\alpha<\kappa and every finite NN,

∣F(xα)∖UN(xα)∣≤μN<μ.(7)|F(x_\alpha)\setminus U_N(x_\alpha)|\le\mu_N<\mu. \tag*{(7)}

Indeed, if dα(ξ)≥Nd_\alpha(\xi)\ge N, then the selected point belongs to UN(xα)U_N(x_\alpha). Only indices of depth less than NN can contribute points outside that neighborhood. Repeated choices do not increase their number.

Pairwise intersections

Let α≠β\alpha\ne\beta. Choose a finite NN such that UN(xα)∩UN(xβ)=∅U_N(x_\alpha) \cap U_N(x_\beta) = \varnothing. Every common point of the two values of FF lies outside at least one of these neighborhoods. Hence

F(xα)∩F(xβ)⊆(F(xα)∖UN(xα))∪(F(xβ)∖UN(xβ)).F(x_\alpha) \cap F(x_\beta) \subseteq\left(F(x_\alpha) \setminus U_N(x_\alpha)\right) \cup\left(F(x_\beta) \setminus U_N(x_\beta)\right).

Applying (7), and using that μN\mu_N is infinite, we obtain

∣F(xα)∩F(xβ)∣≤μN+μN=μN<μ.(8)\lvert F(x_\alpha) \cap F(x_\beta) \rvert\le\mu_N + \mu_N = \mu_N < \mu. \tag*{(8)}

Only two exceptional sets are combined here. No estimate for a countable union of sets of size less than the singular cardinal μ\mu is used. The depth NN may depend on the pair α,β\alpha,\beta.

No large free set

Let H⊆XH \subseteq X have cardinality κ\kappa. For each basic open set B∈BB \in\mathcal{B} that meets HH, choose one point of B∩HB \cap H, and let DD be the set of chosen points. Then D⊆HD \subseteq H, ∣D∣≤μ\lvert D\rvert\le\mu, and H⊆cl⁡(D)H \subseteq\operatorname{cl}(D). Indeed, every basic neighborhood of a point of HH contains one of the chosen representatives.

Enlarge DD inside HH to a set AA of cardinality exactly μ\mu. Then H⊆cl⁡(A)H \subseteq\operatorname{cl}(A). Write A=AξA = A_\xi. Since both AA and {xα:α≤ξ}\{x_\alpha: \alpha\le\xi\} have cardinality at most μ\mu, their union cannot exhaust HH. Choose

xα∈H∖Awithα>ξ.x_\alpha\in H \setminus A \qquad\text{with} \qquad\alpha> \xi.

Because xα∉Ax_\alpha\notin A and xα∈cl⁡(A)x_\alpha\in\operatorname{cl}(A), we have

xα∈Aξ∖{xα}‾.x_\alpha\in\overline{A_\xi\setminus\{x_\alpha\}}.

Thus ξ∈Iα\xi\in I_\alpha, and the construction selected a point

yα,ξ∈F(xα)∩A⊆F(xα)∩H.y_{\alpha,\xi} \in F(x_\alpha) \cap A \subseteq F(x_\alpha) \cap H.

This point is distinct from xαx_\alpha. Hence HH is not free for FF. Since HH was arbitrary, FF has no free subset of cardinality κ\kappa.

Transfer to the ordinal domain

Use the fixed bijection α↦xα\alpha\mapsto x_\alpha to define

f(α)={β<κ:xβ∈F(xα)}.(9)f(\alpha) = \{\beta< \kappa: x_\beta\in F(x_\alpha)\}. \tag*{(9)}

The bijection preserves self-avoidance, the cardinalities of values and their intersections, and freeness. Therefore ff has all the asserted properties. □

The Erdős–Hajnal question

Corollary 3.1. Assume the generalized continuum hypothesis, and put μ=ℵω\mu= \aleph_\omega and κ=ℵω+1\kappa= \aleph_{\omega+1}. There is a self-avoiding mapping f:κ→[κ]≤μf : \kappa\to[\kappa]^{\le\mu} whose distinct values have intersection of cardinality less than μ\mu, but which has no free set of cardinality κ\kappa.

Proof. Take μ=ℵω\mu= \aleph_\omega. This cardinal has cofinality ℵ0\aleph_0, and GCH gives 2μ=μ+=ℵω+12^\mu= \mu^+ = \aleph_{\omega+1}. Theorem 1.1 applies. □

Identifying ℵω+1\aleph_{\omega+1} with its initial ordinal ωω+1\omega_{\omega+1} 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. [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

Paper details

vlnc:W_y4d3y5hf
Version
v1 · latest
Published
Fresh — published within the last 30 days
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI’s ChatGPT

View statement
Looking for related papers…
Contents