# Bayesian Optimization for Fast Radio Mapping and Localization with an
Autonomous Aerial Drone

Paul S. Kudyba, Qin Lu, and Haijian Sun  School of Electrical and Computer
Engineering, University of Georgia, Athens, GA, USA
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

This paper explores how a flying drone can autonomously navigate while
constructing a narrowband radio map for signal localization. As flying drones
become more ubiquitous, their wireless signals will necessitate new wireless
technologies and algorithms to provide robust radio infrastructure while
preserving radio spectrum usage. A potential solution for this spectrum-
sharing localization challenge is to limit the bandwidth of any transmitter
beacon. However, location signaling with a narrow bandwidth necessitates
improving a wireless aerial system’s ability to filter a noisy signal,
estimate the transmitter’s location, and self-pilot to improve the location
estimate. By showing results through simulation, emulation, and a final drone
flight experiment, this work provides an algorithm using a Gaussian process
for radio signal estimation and Bayesian optimization for drone automatic
guidance. This research supports advanced radio and aerial robotics
applications in critical areas such as search-and-rescue, last-mile delivery,
and large-scale platform digital twin development.

###### Index Terms:

Radio Mapping, Bayesian Optimization, Gaussian Process, Wireless Localization,
Autonomous Aerial Robotics

##  I Introduction

Advances in aerial robotics offer engineers new opportunities to collect radio
information with increased speed and cost efficiency [1]. Within this
revolution in capability lies unique engineering insights that could prove
foundational to providing the next generation of wireless infrastructure. Such
insights are already well established as areas of active wireless research,
such as efficient and accurate radio cartography and radio mapping, which can
be used to drive improved communication coverage and spectrum occupancy [2].
Furthermore, radio data, once collected or during collection, can be used to
drive further valuable inferences, such as transmitter location [3]. However,
these spatial radio mapping techniques rely on broadband transmissions,
leaving the receiver to decompose the channel response, which compounds the
effects of large- and small-scale fading [1, 4]. In contrast to a broadband
transmitter, an extremely narrowband transmission (ratio of bandwidth to
carrier frequency $\ll 1$) can be leveraged to simplify the channel modeling
while also increasing the spectrum efficiency of a localization inference.
These combined radio mapping and localization inferences can be used in
applications such as last-mile delivery, search-and-rescue, and development of
digital twins [5].

A common element in many of these radio insights and inferences is the
societal demand to simultaneously produce novel radio technologies and robust
standards as infrastructure [6]. This nexus of aerial robotics, wireless
technology, and machine learning allows researchers to explore new solution
spaces and gain new insights that can, in turn, create new radio algorithm
frameworks to be easily and rapidly deployed after thorough testing. Our
experiment used the Aerial Experimentation and Research Platform for Advanced
Wireless (AERPAW) to quickly iterate our algorithm design within an emulated
digital twin environment and collect real-world data on the testbed.

Figure 1: This figure shows the AERPAW boundaries for the AFAR challenge. The
blue area indicates the aerial vehicle boundary limits. The green area
indicates the possible locations of the rover. The numbered red points
indicate where the rover was hidden, similar to Fig. 1 of [7]. The white
waypoints indicate the locations sampled within our algorithm’s startup
routine for each run.

This paper brings forward a combined system implementation of aerial mobility,
Software-Defined Radio (SDR), and machine learning into a fully deployable
top-level algorithm that uses a Gaussian Process (GP) to produce a
nonparametric 2D tomographic narrowband channel radio map on AERPAW. As the
aerial drone collects samples, the GP radio map forms a best approximation, or
surrogate, of the unknown radio map spatial field. A Bayesian Optimization
(BO) Acquisition Function (AF) infers the best next location to collect a new
radio sample. Our methodology first simulated robot behavior with various
pathloss functions, added signal noise, GP kernels, and BO AF. A Laboratory
testbed enabled signal analysis on the narrowband receiver and the development
of a filter to reject deep fading. The final algorithm integrated all previous
heuristics and analysis to run successfully on the AERPAW emulator and
testbed.

The rest of the paper is structured as follows. The AERPAW challenge that
enabled and guided this effort is described in Section I-A. In Section I-B, a
general structure of GP and how it is applied to construct an evolving radio
map as samples are collected is presented. Section I-C gives a relation to how
the kernel function and its optimization impact on the GP radio map. Section
I-D shows how once the GP has established a pathloss gradient, inference can
be determined with BO. The methods used to create and deploy the final
algorithm are established in Section II with the results shown in Section III.
Finally, concluding remarks are given in Section IV.

###  I-A AERPAW Find A Rover Challenge

Participation in the first AERPAW challenge111https://aerpaw.org/aerpaw-afar-
challenge/ provided an opportunity to address some of the active research
questions mentioned above. The goal of the challenge was to use the platform
emulator and testbed to locate a nonmoving “rover” within three and ten
minutes across an area of 19.7 acres using only a repeating BPSK pseudorandom
pilot at 3.24 GHz with a 125 KHz bandwidth. A USRP B-210 mini SDR with a radio
front end and filters was used to provide the best (lowest) mean error across
three randomly chosen locations. Drone log estimates determined two results at
the three- and ten-minute, marked from takeoff. Figure 1 illustrates the
boundaries and each of the final locations of the rover transmitter. The final
submissions were qualified by running them within the AERPAW emulator. If the
emulator showed safe flight operation, the algorithm was used on the testbed
to determine the final result.

To facilitate radio-based localization, the AERPAW team provided a channel-
sounding script that used GNU Radio to interface with the SDR. This script ran
a cross-correlation with the transmitted pseudorandom pilot and provided an
output channel power in dB and a normalized SNR quality value.

###  I-B Gaussian Process for Spatial Coverage Radio Mapping

Kriging, emerging from practical use in geostatistics, was formalized into a
canonical method called GP [8]. As is used here, a typical application employs
a time-invariant surrogate spatial field mapping as stochastic processes or a
Gaussian distribution of functions. The effectiveness of reducing a time
dimension in a geostatistical context can be easily apparent by producing a
cartography or spatial map. However, this particular dimension reduction
assumption (e.g., a time-invariant channel) can cause issues in a mobility
context. Knowingly, we use a more traditional movement-agnostic signal-
processing receiver provided by AERPAW. Nevertheless, this exercise remains
important in elucidating an assumption of static dimensionality in a novel
system design context and its upstream implications for the system inference
task. Any channel impairment processes not directly accounted for within the
receiver design must be considered noise for upstream system insights. This
includes temporal noise, such as multipath, Doppler, and sample jitter; even
if some of these effects are relatively small, they are combined within our
received signal. In this sense, the radio map we construct will forgo the
time-varying dimension of a channel for a direct spatial alignment with radio
communication as coverage and regard any temporal inconsistencies as noise.

Figure 2: This figure shows the final results of a robotarium trial showing
the GP mean (left) similar to Fig. 4a of [7], and the GP uncertainty as a mean
squared error (right). Yellow is a high value, and blue is a low value for
both images.

With $\mathbf{x}_{i}$ being the coordinates of the $i$th location,
$f(\mathbf{x}_{i})$ is the unknown radio map density function, which, upon
being corrupted by additive Gaussian white noise $v_{i}$, yields the noisy
observation $p_{i}$. Mathematically, this can be described by the following
observation model

$p_{i}=f(\mathbf{x}_{i})+v_{i}\;.$ (1)

To efficiently learn the radio map density function $f$, we will model it with
a GP prior, namely

$f(\cdot)\sim\mathcal{GP}(m(\cdot),k(\cdot,\cdot))\;$ (2)

where the mean function $m(\cdot)$ is set to a constant $g$, representing the
default channel gain corresponding to no signal or receiving incoherent noise,
and the covariance or kernel function $k(\cdot,\cdot)$ measures the
correlation or pairwise similarity of any two function values through their
inputs, i.e., ${\rm cov}[f({\bf x}),f({\bf
x}^{\prime})]:=k(\mathbf{x},\mathbf{x}^{\prime})$. Here, the covariance
function $k$ is characterized by some hyperparameters, which can be estimated
via the marginal likelihood maximization as described in the next subsection.

Notably, this GP prior describes a probability distribution of the radio map
functions $f(\cdot)$, which, upon collecting the set of data sampling
$\\{({\bf x}_{i},p_{i})_{i}\\}$, yields the function posterior

$p(f({\bf x})|\\{({\bf x}_{i},p_{i})_{i}\\})=\mathcal{N}(f({\bf x});\mu({\bf
x}),\sigma({\bf x}))$ (3)

with the mean $\mu({\bf x})$ and standard deviation $\sigma({\bf x})$ of the
estimated radio map at any location ${\bf x}$. In our case, $f(\cdot)$
resembles a pathloss, and our expectation is that it should match an
exponential decay, but the actual decay exponent remains an unknown parameter
(due to the novel system and environment). Thus, this pathloss exponent will
be found at run-time as a hyperparameter.

With the correct kernel and hyperparameters, the true spatial field channel,
$f(\cdot)$, will be drawn from the GP distribution of radio maps as the mean.
This regression, with an output indicating the most probable radio map and
associated uncertainty, is how we generate a parsimonious and robust atemporal
channel estimate map. Additionally and intuitively, the location of the signal
peak within the estimated radio map, when all the dimensionality reduction
assumptions and noise rejections hold, is the transmitter’s true location.

###  I-C Kernel Functions and Maximum Likelihood Algorithm

The positive and semi-definite kernel function $k(\cdot,\cdot)$ plays a
performance-critical role in GP modeling. Notably, the commonly used kernel is
the Rational Basis Function (RBF) function, whose expression is given by

$k_{\mathrm{RBF}}({\bf x},{\bf
x}^{\prime})=\gamma^{2}\exp\biggl{(}-\frac{\|{\bf x}-{\bf
x}^{\prime}\|_{2}^{2}}{2\ell^{2}}\biggr{)}\;.$ (4)

Intuitively, the value of $k({\bf x},{\bf x}^{\prime})$ will become larger as
the distance between ${\bf x}$ and ${\bf x}^{\prime}$ becomes smaller. This
inherently produces a distribution of infinitely smooth functions that
exponentially decay as expected from any free space pathloss function.
However, the RBF, used alone, would also fit any noise incorrectly to the
posterior as part of the pathloss. Fortunately, with the addition of a white
noise kernel, each posterior sample will now include a hyperparameter of noise
within each sample collected, allowing the entire radio map distribution to
have more flexibility for inconsistencies in the input sampling. Combined, the
starting kernel Python code is given as kernel = (C(1) * RBF(0.00276,
(0.001,0.004)) + WhiteKernel(noise_level=0.33). This shows an RBF with a
$\ell$ value of 0.00276 being bounded between 0.001 and 0.004.

Each kernel comes with a specific set of hyperparameters; see, e.g., the
scaling factor $\gamma$ and lengthscale $\ell$ in the RBF kernel in Eq. 4.
These hyperparameters are obtained by maximizing the marginal likelihood via
the Limited-memory Broyden-Fletcher-Goldfarb-Shanno with Bound constraints
(L-BFGS-B) algorithm. Here, the bounding is used to ensure an applicable
resulting lengthscale at all times during the flight.

###  I-D Navigation with Acquisition

The GP modeling yields a posterior distribution of the radio map function as
in (3). A consideration for mapping/localization is the time penalty,
opportunity cost, or regret to produce each reliable sample [9]; the drone
simply cannot sample the entire field, and yet it needs to know the best next
location to fly towards and sample. The GP is also very likely to change as
samples are added, especially at the beginning of any flight. These properties
disallow many traditional forms of optimization; however, because our radio
map has an associated uncertainty provided by our GP kernel function, BO can
be used to infer an optimal future sample location. This future location will
be selected from the GP “black box” surrogacy, from which a maximum can be
chosen according to an AF. BO, therefore, links our GP output of a mean
($\mu$) and uncertainty ($\sigma$) to a balanced tradeoff of where to collect
a new sample. BO accomplishes this with an AF that balances two objectives:
exploring uncertain positions to find the global optimum and exploiting the
best yet known mean value. Here, we adopt the upper confidence bound (UCB)
based AF, given by

$\mathrm{UCB}({\bf x};\beta_{n})=\mu({\bf x})+\beta_{n}\sigma({\bf x})$ (5)

where $\beta_{n}$ is a non-negative exponentially decreasing sequence updated
after collecting each sample. We choose $\beta_{n}=d^{s}$ with $0<d<1$. This
choice, in effect, reduces the exploration term as the flight progresses and
samples are taken.

##  II Experimental Methodology

The production of a final AFAR submission consisted of three stages of
research and development: simulation via Robotarium [10], receiver testing
with an in-lab setup, and emulation with AERPAW. The results of each stage
gave valuable insight into the next, building into a cohesive and successful
deployment.

Figure 3: This figure shows the output of the quality-variance filter along
with the signal intensity given from the AERPAW narrowband channel sounder
script. This data was collected in a lab setting that resembles the AERPAW
setup without any RF front end. The receiver was placed on a moving platform,
which was moved from 16 ft to 4 ft and then back to 16 ft from the
transmitter. This figure is adapted from Fig. 4.2f of [5].

A 2D robotic simulator was used to analyze the expected self-guided robot
behavior in controlled scenarios, and pathloss functionality was added to
facilitate autonomous development. For example, a 2D normal distribution as a
basic pathloss function allowed control of the mean as a transmitter’s
location and the standard deviation to control the decay. The platform enabled
many tests with varying pathloss models and signal-to-noise levels. It was
also seen that two predefined routines before and after autonomous BO were
beneficial to stability, efficiency, and accuracy. The robot would start with
a predefined circle routine wide enough to establish a stable gradient and
resolve any noise for BO to give stable guidance. Secondly, after a stable
global maximum was repeatedly chosen as the optimal location, a routine could
be triggered to circle that point, further refining the transmitter’s
location. Lastly, the simulation allowed experimentation with different AF,
leading to the selection of UCB for the final deployment. Figure 2 shows the
mean and uncertainty radio maps resulting from BO with uniform noise added to
the robot’s receiver. A 2D grid was constructed to facilitate getting discrete
spatial field points of the GP mean and maximum squared error. The AF could be
computed from this grid, and the maximum would then be selected as the new
target waypoint.

To ensure that the GP receives no outlier radio data that could not be
described as Gaussian noise, a non-linear filter was shown to be necessary
from laboratory testing and data from a previous testbed run. A large
discriminator was observed by binning the receiver quality signal and taking
the variance of these readings. By removing any readings with an excessive
quality-variance, large signal noise swings could be rejected as invalid
samples and excluded from the GP. However, this threshold needed to be
determined at flight time due to limited empirical data. Laboratory testing
also indicated that receiver movement influenced the signal’s tendency to
encounter noise. The binning of the quality metric in a lab setup where the
receiver periodically moves towards and away from the transmitter is shown in
Figure 3.

A final AERPAW algorithm was then created to perform emulation testing and for
the final deployment on AERPAW. Two grids are created using the latitude and
longitude for both the flying boundary and the rover location boundary. The
flying boundary grid is then used for all navigational inputs, and the rover’s
final estimates are given from the second rover grid. Both grids are sampled
from the same GP. The drone then takes off to 40 m for the entire trial. Once
at the correct altitude, the drone attempts to take the first radio sample
binning data for 6 s while stationary and always facing northwest. If the
quality-variance of the first sample is higher than the threshold, the sample
is retaken with an exponentially higher set threshold until this first sample
is accepted. The drone then flies to three predefined waypoints shown in
Figure 1. These waypoint samples give a stable GP and BO for autonomous
flight. The drone then flies its mission according to the same AF UCB policy
chosen in the simulation. Two possible criteria can trigger an auxiliary
routine that creates a circle of waypoints from the drone’s current position
(observing the boundary limits). The first criterion is that the AF has
repeatedly chosen very spatially similar points to investigate. This is
similar to the simulation ending routine, which indicates the drone is close
to the maximum channel gain. The second is if the drone rejects a maximum
number of measurements throughout the mission. This is a failsafe that was
seen to benefit the mission while testing within the AERPAW emulator. If the
drone cannot navigate autonomously to points that provide valid radio samples
for the GP, a circular routine of waypoints ensures that the radio will be
given a broad spatial set of sample locations, which might recover a gradient
towards the transmitter. During the mission, a mission timer tracks the
duration and logs the final predicted location from the rover grid space for
the three- and ten-minute estimates.

##  III Results and Analysis

TABLE I: The three-run simulation and testbed results. The bracketed number indicates the trial number corresponding to the hidden locations given in Figure 1. 3-min (T.1) | 3-min (T.2) | 3-min (T.3) | 3-min Average | 10-min (T.1) | 10-min (T.2) | 10-min (T.3) | 10-min Average
---|---|---|---|---|---|---|---
Simulation Results
71.7m | 265m | 174m | 170.23m | 52.8m | 17m | 19m | 29.6m
Testbed Results
40.5m | 239.1m | 232.4m | 170.7m | 41.6m | 27.8m | 130.4m | 66.6m

Table I presents the results from the AERPAW emulator and testbed
environments. The first testbed mission shows how quickly the GP can fit a
transmitter that is relatively close (125 m) from the drone’s starting
location. However, the drone could not resolve a better 10-minute location
estimate due to receiver gain saturation. While a consistently high gain is
generally desired for communication, corresponding to an ideal channel, in
this case, the signal ’clipping’ makes a spatial ’plateau.’ This spatial
feature makes resolving a transmitter location nearly impossible when within
this region. Seeing this within the emulator, the radius for the auxiliary
circle was set expecting to encounter this signal behavior; however, in this
case, the auxiliary path was not wide enough to provide sufficient
localization information. Additionally, critical points were missed on the
northwest side of the auxiliary path due to noise and correctly excluded by
the quality-variance filter.

(a)

(b)

Figure 4: This figure shows the first and second run reconstructions of the
final GP estimates over the search spaces shown in figure 1. The actual rover
location is shown as a red dot. The green dot shows the final ten-minute
estimate, and the blue dot indicates the three-minute estimate. This GP
reconstruction uses the final kernel hyperparameters indicated by the vehicle
log. Part of this figure is adapted from Fig. 4c of [7].

The second trial, shown in Figure 4(b), gives the best 10-minute result of
27.8 m. The 3-minute result did not provide quite enough time for the drone to
establish a proper gradient and travel to the transmitter 330 m from takeoff.
However, the drone was able to establish a proper optimal trajectory toward
the transmitter and perform the auxiliary path maneuver while staying within
the boundary conditions. The auxiliary path was wide enough to provide
additional localization to the GP, and the quality-variance filter was working
appropriately to filter excessive noise. This result shows the ideal behavior
of the drone in this situation. To provide a better three-minute GP estimate
with this starting routine, a kernel that supplied more information about the
signal from this starting distance (as a prior) would need to be considered.

During the third trial, the drone encountered a confluence of issues, which
resulted in degraded estimation performance. However, the mission was not a
failure; the drone was able to produce locations for both timed estimates from
a starting distance of 286 m. Log analysis revealed that the quality-variance
filter threshold (set with the first sample) was set to exclude any variance
above 35. This was different from the second run, which allowed samples with a
less strict value of 67. This disallowed many of the first critical direction-
finding waypoints from being included within the GP. The drone then generated
the auxiliary path due to missing too many sample measurements. From this
waypoint path, two samples were accepted. These samples greatly increased the
accuracy of the location estimate. The drone reestablished an optimal path but
was unable to collect any more samples due to the time limit.

##  IV Conclusion

The results of the three trials show significant robustness in the GP-based BO
approach for drone-based localization. The quality-variance filter identified
and removed outlier noise values from the narrowband receiver. Unfortunately,
the drone was unable to find the correct filter parameter value from the start
of the third trial. This alone shows a necessity for bridging the gap between
the AERPAW emulator and real-world radio data. If the emulation noise and the
testbed had a reliable digital-twin agreement, the filter parameter could be
safely studied and set within the emulator, similar to how the auxiliary path
area was tested and adopted. This would save mission time and prevent mission-
hazardous calibrations. Additionally, by more closely integrating the digital
twin emulation/testbed environment, various “black box” pathloss regression
estimators for mapping and localization could be trained and trialed within an
emulated environment with accurate synthetic radio data.

## References

  * [1] D. Romero and S.-J. Kim, “Radio Map Estimation: A data-driven approach to spectrum cartography,” _IEEE Signal Process. Mag_., vol. 39, no. 6, pp. 53–72, Nov. 2022, doi: 10.1109/MSP.2022.3200175.
  * [2] R. Shrestha _et al._ , “Radio Map Estimation in the Real-World: Empirical Validation and Analysis,” in _IEEE Conference on Antenna Measurements and Applications_ , pp. 169–174, 2023.
  * [3] H. Kwon and I. Guvenc, “RF Signal Source Search and Localization Using an Autonomous UAV with Predefined Waypoints,” in _2023 IEEE 97th Vehicular Technology Conference (VTC2023-Spring)_ , Jun. 2023, pp. 1–6. doi: 10.1109/VTC2023-Spring57618.2023.10200783.
  * [4] G. Matz and F. Hlawatsch, “Fundamentals of Time-Varying Communication Channels,” in _Wireless Communications Over Rapidly Time-Varying Channels_. Elsevier, pp. 1–63, 2021.
  * [5] P. Kudyba, “Rapid Autonomous Narrow-band Wireless Localization via Gaussian Process and Bayesian Optimization”, M.S. thesis, Sch. of Electr. and Comput. Eng., University of Georgia, Athens, GA, June 2024.
  * [6] V. Marojevic _et al._ , “Advanced wireless for unmanned aerial systems: 5g standardization, research challenges, and aerpaw architecture,” _IEEE Vehicular Technology Magazine_ , vol. 15, no. 2, pp. 22–30, 2020.
  * [7] P. Kudyba et al., “A UAV-assisted wireless localization challenge on AERPAW” submitted for publication in _IEEE Communications Magazine_ , Special Call on Experimentation in Large-Scale Wireless Community Testbeds, May, 2024.
  * [8] C. E. Rasmussen and C. K. I. Williams, Gaussian processes for machine learning. in _Adaptive computation and machine learning. Cambridge, Mass: MIT Press_ , 2006.
  * [9] M. Santos _et al._ , “Multi-robot Learning and Coverage of Unknown Spatial Fields,” in _International Symposium on Multi-Robot and Multi-Agent Systems_ , pp. 137–145, 2021.
  * [10] D. Pickem _et al._ , “The Robotarium: A remotely accessible swarm robotics research testbed,” in _IEEE International Conference on Robotics and Automation_. IEEE, pp. 1699–1706, 2017.


# On strong chains of sets and functions

Tanmay C. Inamdar  Department of Mathematics, Bar-Ilan University, Ramat-Gan
5290002, Israel.

###### Abstract.

Shelah has shown that there are no chains of length $\omega_{3}$ increasing
modulo finite in ${}^{\omega_{2}}\omega_{2}$. We improve this result to sets.
That is, we show that there are no chains of length $\omega_{3}$ in
$[\omega_{2}]^{\aleph_{2}}$ increasing modulo finite. This contrasts with
results of Koszmider who has shown that there are, consistently, chains of
length $\omega_{2}$ increasing modulo finite in $[\omega_{1}]^{\aleph_{1}}$ as
well as in ${}^{\omega_{1}}\omega_{1}$. More generally, we study the depth of
function spaces ${}^{\kappa}\mu$ quotiented by the ideal $[\kappa]^{<\theta}$
where $\theta<\kappa$ are infinite cardinals.

###### Key words and phrases:

Depth, increasing chain, order modulo ideal, meeting numbers.

###### 2020 Mathematics Subject Classification:

Primary 03E04; Secondary 03E05, 03E17

##  1\. Introduction

Throughout this paper $\theta,\kappa,\lambda$ are infinite cardinals with
$\theta\leq\kappa$ and $\mu$ is a (possibly finite) cardinal.

An important part of set theory has been the study of ${}^{\omega}{\omega}$
and $[\omega]^{\omega}$ quotiented by the ideal $[\omega]^{<\omega}$ of finite
subsets of the natural numbers, the area of cardinal characteristics of the
continuum (see for example [2]). Another area, recently receiving more
attention than previously, is a similar study performed for an arbitrary
infinite cardinal $\kappa$, perhaps with the addition of extra cardinal
arithmetic assumptions. That is, the study of ${}^{\kappa}{\kappa}$ and
$[\kappa]^{\kappa}$ quotiented by the ideal $[\kappa]^{<\kappa}$, the area of
higher cardinal invariants(see for example [12] and its extensive
bibliography). Another natural ideal to consider for $\kappa$ an uncountable
regular cardinal is the ideal of non-stationary subsets of $\kappa$ (see for
example [8]).

In this paper we focus on ideals of the form $[\kappa]^{<\theta}$ where
$\theta$ and $\kappa$ are infinite cardinals, and $\theta$ is strictly less
than $\kappa$. Before we describe our results, let us mention some other
results in the literature on this topic.

Baumgartner in his thesis proved the following.

######  Theorem 1.1 ([3]).

Assume $GCH$. Let $\theta\leq\kappa\leq\lambda$ be infinite cardinals with
$\theta$ regular. Then there is a cardinal-preserving forcing $\mathbb{P}$
such that in the generic extension by $\mathbb{P}$ we have a
$(<\theta)$-almost disjoint family $\\{A_{\alpha}\mid\alpha<\lambda\\}$
contained in $[\kappa]^{\kappa}$: for every $\alpha<\beta<\lambda$,
$|A_{\alpha}\cap A_{\beta}|<\theta$.

Baumgartner’s proof in particular shows that it is consistent that there there
are arbitrarily large families in $[{\omega_{1}}]^{{\aleph_{1}}}$ and even in
$[{\omega_{2}}]^{{\aleph_{2}}}$ which are $(<{\aleph_{0}})$-almost disjoint,
that is, almost disjoint modulo finite.

Using the Erdős-Rado-Kurepa Theorem (also sometimes called the Erdős-Rado
Theorem), we see that for example, a $\lambda$-sized $(<{\aleph_{0}})$-almost
disjoint family in $[{\omega_{1}}]^{\aleph_{1}}$ implies that
$2^{\aleph_{0}}\geq\lambda$. In [4] it is also shown that a generic extension
obtained by adding arbitrarily many Cohen reals to a model of
$2^{\aleph_{0}}={\aleph_{1}}$ does not contain an $(<{\aleph_{0}})$-almost
disjoint family in $[{\omega_{1}}]^{\aleph_{1}}$ of size ${\aleph_{2}}$.

Zapletal in his thesis (see [34]) proved a related result about such
‘strongly’ almost disjoint families with some additional properties, but we do
not go into the details here. We do however mention the motivation for
Zapletal as it will allow us to introduce the next result we shall discuss.

The result of Baumgartner’s suggests a general investigation of the possible
quasiorders contained within spaces of the form $[\kappa]^{\kappa}$ or
${}^{\kappa}\kappa$ modulo the ideal $[\kappa]^{<\theta}$. Hechler’s Theorem
(see [10]) solves this question completely for the usual Baire space and see
[5] and [7] for similar results for the other spaces we have mentioned.

Then Baumgartner’s result can be interpreted as a result about the ‘width’ of
such spaces, so Hajnal and Szentmiklóssy asked the next natural question, what
about their ‘depth’? In order to make things precise we need to introduce some
notation which we shall use throughout this article.

Let $X,Y$ be sets of ordinals, $X$ infinite, and let $\theta$ be an infinite
cardinal such that $\theta<|X|$. For $f,g\in{}^{X}{Y}$, let $f\ll_{\theta}g$
denote that $|\\{\xi\in X\mid f(\xi)\geq g(\xi)\\}|<\theta$. Note that in this
case $|\\{\xi\in X\mid f(\xi)<g(\xi)\\}|=|X|$.

The question of Hajnal and Szentmiklóssy which motivated Zapletal was the
following.

######  Question 1.2 (pg. 435 of [24]).

Is it consistent that there is a chain in
$({}^{\omega_{1}}\omega_{1},\ll_{\aleph_{0}})$ of length $\omega_{2}$? That
is, is it consistent that there is a sequence $\langle
f_{\alpha}\mid\alpha<\omega_{2}\rangle$ of elements in
${}^{\omega_{1}}\omega_{1}$ such that $\alpha<\beta<\omega_{2}$ implies that
$f_{\alpha}\ll_{\aleph_{0}}f_{\beta}$?

Note that while we use the term ‘chain’ above and throughout the paper as it
is more intuitively clear, the term ‘depth’ is also used for a related
concept, for example in [32]. To translate between the two, the depth is the
supremum of the length of well-ordered chains in a partially ordered set. In
particular, the above question could be phrased as asking if it is consistent
that the depth of the partial order
$({}^{\omega_{1}}\omega_{1},\ll_{\aleph_{0}})$ is greater than $\omega_{2}$.
We shall however always use the term ‘chain’ but since we shall only be
interested in well-ordered chains, it is straightforward to translate between
our terminology and Shelah’s.

Hajnal also mentions another related question.

######  Question 1.3 (pg. 435 of [24]).

Is it consistent that there is a chain of sets $\left\langle
X_{\alpha}\mid\alpha<{\omega_{2}}\right\rangle$ in
$[{\omega_{1}}]^{\aleph_{1}}$ such that for $\alpha<\beta<{\omega_{2}}$,
$X_{\alpha}\setminus X_{\beta}$ is finite, and $|X_{\beta}\setminus
X_{\alpha}|={\aleph_{1}}$?

As pointed out by Hajnal, given a family as above, $\\{X_{\beta+1}\setminus
X_{\beta}\mid\beta<{\omega_{2}}\\}$ is an almost disjoint modulo finite family
in $[{\omega_{1}}]^{\aleph_{1}}$ as in Baumgartner’s Theorem 1.1.

In order to see the relation between the two questions, consider the following
weakening of $\ll_{\theta}$: for $f,g\in{}^{X}{Y}$, let $f<_{\theta}g$ denote
that $|\\{\xi\in X\mid f(\xi)>g(\xi)\\}|<\theta$ and $|\\{\xi\in X\mid
f(\xi)<g(\xi)\\}|=|X|$. It is clear then that $f\ll_{\theta}g$ implies that
$f<_{\theta}g$, and that Question 1.3 asks about the consistent existence of
an $\omega_{2}$-chain in $({}^{\omega_{1}}2,<_{\aleph_{0}})$.

In [13] Koszmider was able to answer Question 1.3 affirmatively.

######  Theorem 1.4 ([13]).

Assuming $\square_{\omega_{1}}$, there is a ccc forcing which adds an
${\omega_{2}}$ length chain in $({}^{{\omega_{1}}}{2},<_{\aleph_{0}})$ which
is to say, adds a sequence of sets $\langle
X_{\alpha}\mid\alpha<{\omega_{2}}\rangle$ in $[{\omega_{1}}]^{\aleph_{1}}$
such that for $\alpha<\beta<{\omega_{2}}$, $X_{\alpha}\setminus X_{\beta}$ is
finite, and $|X_{\beta}\setminus X_{\alpha}|={\aleph_{1}}$. In particular, it
is consistent that there is an ${\omega_{2}}$ length chain in
$({}^{\omega_{1}}{\omega_{1}},<_{{\aleph_{0}}})$.

We do not give the definition of $\square_{\omega_{1}}$ here as we will not
require it in what follows. Later, Koszmider was able to answer Question 1.2
as well.

######  Theorem 1.5 ([14]).

It is consistent that $({}^{\omega_{1}}{\omega_{1}},\ll_{{\aleph_{0}}})$
contains an ${\omega_{2}}$ length chain.

We point out that Mitchell [20], and Veličković [33] following Mitchell, have
given alternate presentations of the result of Koszmider using the method of
‘models of two types’ (see [21]). The former starting from ${\mathsf{L}}$, the
latter assuming the negation of a weak form of Chang’s Conjecture (we do not
define this exact weak form as we will not require it, but in Definition 3.1
we define Chang’s Conjecture).

In contrast to the results of Baumgartner, the results of Koszmider are
specific to the ideal $[{\aleph_{1}}]^{<{\aleph_{0}}}$, so in particular an
ideal of the form $[\kappa]^{<\theta}$ when $\theta^{+}=\kappa$. Is it
possible to prove a result as general as Baumgartner’s for chains without the
assumption of $\theta^{+}=\kappa$?

All the results in this paper are negative answers to questions in this
spirit. Our starting point was a result of Shelah which implies that one
cannot have $\ll_{\theta}$-chains in situations where the size of the gap
between $\theta$ and $\kappa$ is finite but larger than one. Focusing on the
smallest case where Shelah’s theorem applies we have the following.

######  Theorem 1.6 ([32]).

For every infinite cardinal $\theta$, there are no chains in
$\left({}^{\theta^{++}}{\theta^{++}},\ll_{\theta}\right)$ of length
$\theta^{+++}$.

We strengthen this result to $<_{\theta}$-chains and hence to sets.

######  Theorem A.

Let $\theta$ be an infinite cardinal.

  1. (i)

There are no chains in $({}^{\theta^{++}}{\theta^{++}},<_{\theta})$ of length
$\theta^{+++}$.

  2. (ii)

In particular, there is no sequence $\langle
S_{\alpha}\mid\alpha<\theta^{+++}\rangle$ of sets in
$[\theta^{++}]^{\theta^{++}}$ such that, for all $\alpha<\beta<\theta^{+++}$:

    1. (a)

$|S_{\alpha}\setminus S_{\beta}|<\theta$;

    2. (b)

$|S_{\beta}\setminus S_{\alpha}|=\theta^{++}$.

Taking $\theta=\aleph_{0}$ this tells us that there cannot be an
${\omega_{3}}$ chain of sets in $[{\omega_{2}}]^{\aleph_{2}}$ strongly
increasing modulo finite. Shelah’s result implies that there are no
${\omega_{3}}$ chains of functions in
$({}^{{\omega_{2}}}{{\omega_{2}}},\ll_{\aleph_{0}})$.

We prove some related results. As we have hinted above, one can phrase a
general form of the question of Hajnal and Szentmiklóssy.

######  Question 1.7.

Let $\theta<\kappa$ be infinite cardinals. What are the possible lengths of
chains in $({}^{\kappa}\kappa,\ll_{\theta})$?

In response, we have the following.

######  Theorem B.

Let $\theta<\kappa$ be infinite cardinals with $\kappa$ a limit cardinal but
not a cardinal fixed point. Then there are no chains in
$({}^{\kappa}\kappa,\ll_{\theta})$ of length $\kappa^{+}$.

We point out that the hypotheses in this theorem imply that in fact
$\theta^{+}<\kappa$, and this is crucial. Except for one case each in Theorem
3.3 and Theorem 3.4, none of the results proved in this article apply to the
situation when $\theta^{+}=\kappa$, and about these two exceptions see the
discussion of Theorem 3.2.

Shelah has made the following conjecture.

######  Conjecture 1.8 ([32]).

Let $\theta$ be an infinite successor cardinal. For every $\mu\geq\theta$,
there are no chains in $({}^{\theta^{++}}\mu,\ll_{\theta})$ of length
$\mu^{+}$.

Here our progress is quite meagre and in particular does not apply to the
situation from PCF Theory which possibly motivated Shelah, when $\mu$ is the
limit of an increasing $\theta^{++}$-sequence of regular cardinals greater
than $\theta$. We remind the reader that for $\theta$ a cardinal and $\nu$ an
ordinal, $\theta^{+\nu}$ denotes the $\nu$th cardinal after $\theta$. That is,
if $\theta=\aleph_{\xi}$, then $\theta^{+\nu}:=\aleph_{\xi+\nu}$.

######  Theorem C.

Let $\theta\leq\mu$ be infinite cardinals with
$\mu<\theta^{+{(\theta^{++})}}$. Then there are no chains in
$({}^{\theta^{++}}\mu,\ll_{\theta})$ of length $\mu^{+}$.

Apart from the remaining cases of Question 1.7 and Conjecture 1.8, whether
Koszmider’s results can be improved upon by constructing longer chains in
$\left({}^{\omega_{1}}2,<_{\aleph_{0}}\right)$ and
$({}^{\omega_{1}}{\omega_{1}},\ll_{{\aleph_{0}}})$ remains open as well. In
[34] and [32] one may find more open problems. Two other papers on topics
related to this paper which we have not mentioned are [17] and [15]. In the
former, Laver shows, among other things, why one cannot approach the question
of Hajnal and Szentmiklóssy in the usual way as in the Baire space, which is
to say, by iteratively adding functions dominating modulo finite. In the
latter, Koszmider studies the morasses which he used to prove Theorem 1.5 in
greater detail.

We now describe the organisation of the paper. In Section 2 we collect the
tools we will use throughout the paper. In Section 3 we shall focus on the
space $({}^{\kappa}\mu,<_{\theta})$ and prove Theorem A. In Section 4 we focus
on the space $({}^{\kappa}\mu,\ll_{\theta})$ and prove Theorem B and Theorem
C.

##  2\. Preparatory lemmata

Our notation is standard for set theory. We shall use the Greek letters
$\theta$, $\kappa$, $\mu$, $\lambda$, $\varkappa$, $\rho$, $\chi$, $\vartheta$
for cardinals, of which we remind the reader that the letters $\varkappa$ and
$\vartheta$ are, respectively, variants of $\kappa$ and $\theta$. Except for
$\mu$ which may occasionally be finite, all the others will always denote
infinite cardinals, and of these $\lambda$ will always denote an infinite
regular cardinal. We shall use the Greek letter $\pi$, possibly with
subscripts, for bijections, and all other Greek letters (save for $\omega$) as
well as $i$ and $j$ for ordinals, possibly finite.

For $f$ a function and $X$ a subset of its domain, $f\restriction X$ denotes
the function obtained by restricting the domain of $f$ to $X$. If
$f,f^{\prime}$ are two functions with the same domain, when we say that $f\leq
f^{\prime}$ _everywhere_ we mean that for every element $x$ of their common
domain, $f(x)\leq f^{\prime}(x)$.

###  2.1. Cardinal invariants

We introduce some cardinal invariants we shall use in what follows.

######  Definition 2.1.

Let $\theta,\chi,\rho,\kappa$ be infinite cardinals with $\theta<\chi$ and
$\theta\leq\rho$ and $\theta\leq\kappa$. Let
$\operatorname{m}(\kappa,\chi,\rho,\theta)$ denote the least size of a family
$\mathcal{B}$ in $[\kappa]^{<\chi}$ such that for every
$A\in[\kappa]^{\geq\rho}$ there is some $B\in\mathcal{B}$ such that $|B\cap
A|\geq\theta$. As important special cases, let
$\operatorname{m}^{-}(\kappa,\theta)$ denote
$\operatorname{m}(\kappa,\theta^{+},\kappa,\theta)$, let
$\operatorname{m}(\kappa,\rho,\theta)$ denote
$\operatorname{m}(\kappa,\theta^{+},\rho,\theta)$, and let
$\operatorname{m}(\kappa,\theta)$ denote
$\operatorname{m}(\kappa,\theta^{+},\theta,\theta)$.

######  Definition 2.2.

Let $\theta$ and $\kappa$ be infinite cardinals with $\theta\leq\kappa$. Let
$\operatorname{cof}([\kappa]^{\theta})$ denote the least size of a family
$\mathcal{B}$ in $[\kappa]^{\theta}$ such that for every
$A\in[\kappa]^{\theta}$ there is some $B\in\mathcal{B}$ with $A\subseteq B$.

The cardinal $\operatorname{cof}([\kappa]^{\theta})$ is the cofinality of the
partially ordered set $([\kappa]^{\theta},\subseteq)$. It is also sometimes in
the context of PCF theory called
$\operatorname{cov}(\kappa,\theta^{+},\theta^{+},2)$. One may find a detailed
treatment of it in [27, Chapter II, §5]. The cardinal
$\operatorname{m}(\kappa,\chi,\rho,\theta)$ is somewhat less common: in the
notation of [30],
$\operatorname{m}(\kappa,\chi^{+},\rho,\theta)=\operatorname{ecf}_{\rho,\chi,\theta}(\kappa,\chi)$
(see [30, Claim 4.5(2)]); particular instances of
$\operatorname{m}(\kappa,\chi,\rho,\theta)$ appear, for example, in [27,
Chapter IX,§5]; see also the cardinal $\mathbf{U}_{J}[\mu]$ from (among
others) [31]. The cardinal $\operatorname{m}(\kappa,\theta)$ is more
frequently found, especially the instances of it which follow from Shelah’s
Revised GCH ([29])—see for example [1, Theorem 8.21] and [5, Theorem 8]. In
[16] a Galvin-Hajnal theorem for $\operatorname{m}(\kappa,\theta)$ is proved.
In our notation we have followed [19] where the invariant
$\operatorname{m}(\kappa,\theta)$ was considered (though we order the
parameters so as to follow Shelah’s convention for the covering numbers from
[27]). In particular, the letter ‘m’ stands for ‘meeting’. In [23] a related
cardinal invariant for ‘meeting’ functions was considered.

We calculate the values of these cardinal invariants in some simple
circumstances. We were informed of the following lemma by Assaf Rinot. Below,
when we talk about a family ‘witnessing’ some instance of these cardinal
invariants, we shall mean the following: in case the value of the invariant or
an upper bound for it is known beforehand (though not necessarily specified),
then the family is chosen so that it has size equal to this invariant; in case
the value of the invariant is not known (so that we are in the process of
obtaining a bound on its size), then we shall mean that the family satisfies
the properties required to be a candidate for witnessing the invariant, so
that the value of the invariant is at most the size of this family.

Recall that for $\theta$ a cardinal and $\nu$ an ordinal, $\theta^{+\nu}$
denotes the $\nu$th cardinal after $\theta$. That is, if
$\theta=\aleph_{\xi}$, then $\theta^{+\nu}:=\aleph_{\xi+\nu}$.

######  Lemma 2.3.

Let $\theta<\mu<\kappa$ be infinite cardinals.

  1. (i)

$\operatorname{m}(\kappa^{\prime},\chi^{\prime},\rho^{\prime},\theta^{\prime})\geq\operatorname{m}(\kappa,\chi,\rho,\theta)$
for infinite cardinals $\kappa^{\prime}\geq\kappa$, $\chi^{\prime}\leq\chi$,
$\rho^{\prime}\leq\rho$, and $\theta^{\prime}\geq\theta$.

  2. (ii)

$\operatorname{m}^{-}(\theta^{+},\theta)=\operatorname{m}(\theta^{+},\theta)=\theta^{+}$.

  3. (iii)

$\kappa\leq\operatorname{m}^{-}(\kappa,\theta)\leq\operatorname{m}(\kappa,\theta)\leq\operatorname{cof}([\kappa]^{\theta})$.

  4. (iv)

Let $\chi$ be a cardinal such that $\operatorname{m}^{-}(\mu,\theta)\leq\chi$
and $\operatorname{m}^{-}(\kappa,\mu)\leq\chi$. Then
$\operatorname{m}^{-}(\kappa,\theta)\leq\chi$.

  5. (v)

If $\rho\in[\theta,\mu)\cap\operatorname{Card}$, then
$\operatorname{m}(\mu^{+},\rho,\theta)\leq\mu^{+}\cdot\operatorname{m}(\mu,\rho,\theta)$.

  6. (vi)

If $\rho\in[\theta,\kappa)\cap\operatorname{Card}$ and
$\kappa<\theta^{+{\operatorname{cf}(\rho)}}$, then
$\operatorname{m}(\kappa,\rho,\theta)=\kappa$. In particular, if
$\kappa<\theta^{+\operatorname{cf}(\theta)}$, then
$\operatorname{m}(\kappa,\theta)=\kappa$.

  7. (vii)

If $\kappa$ is a limit cardinal and $\operatorname{m}(\chi,\theta)\leq\kappa$
for a tail of $\chi\in(\theta,\kappa)\cap\operatorname{Card}$, then
$\operatorname{m}^{-}(\kappa,\theta)=\kappa$.

  8. (viii)

If there are no cardinal fixed points in $(\theta,\kappa]$, then
$\operatorname{m}^{-}(\kappa,\theta)=\kappa$.

  9. (ix)

If $\kappa$ is uncountable and not a cardinal fixed point then there is some
$\chi<\kappa$ such that $\operatorname{m}^{-}(\kappa,\chi)=\kappa$.

  10. (x)

$\operatorname{cof}([\theta^{+}]^{\theta})=\theta^{+}$.

  11. (xi)

Let $\chi$ be a cardinal such that
$\operatorname{cof}([\mu]^{\theta})\leq\chi$ and
$\operatorname{cof}([\kappa]^{\mu})\leq\chi$ then
$\operatorname{cof}([\kappa]^{\theta})\leq\chi$.

  12. (xii)

If $\kappa<\theta^{+\omega}$, then
$\operatorname{cof}([\kappa]^{\theta})=\kappa$.

  13. (xiii)

Let $\chi:=\kappa^{<\theta}$. Then
$\operatorname{cof}([\kappa]^{\theta})\leq\operatorname{m}(\chi,\theta)$.

###### Proof.

  1. (i)

Clear from the definitions.

  2. (ii)

Since $\theta^{+}$ itself witnesses $\operatorname{m}^{-}(\theta^{+},\theta)$
and $\operatorname{m}(\theta^{+},\theta)$.

  3. (iii)

The first inequality is the only one which does not follow automatically from
the definitions. So let $\langle S_{i}\mid i<\kappa\rangle$ be pairwise
disjoint elements of $[\kappa]^{\kappa}$. Now if $\mathcal{B}$ witnesses
$\operatorname{m}^{-}(\kappa,\theta)$ and $|\mathcal{B}|=\chi<\kappa$ then we
get a contradiction since $\chi\cdot\theta<\kappa$ so for some $i<\kappa$,
$S_{i}$ has empty intersection with every element of $\mathcal{B}$.

  4. (iv)

Let $\\{B_{\xi}\mid\xi<\chi\\}$ witness
$\operatorname{m}^{-}(\mu,\theta)\leq\chi$ and let $\\{C_{\nu}\mid\nu<\chi\\}$
witness $\operatorname{m}^{-}(\kappa,\mu)\leq\chi$. For each $\nu<\chi$ let
$\pi_{\nu}:\mu\leftrightarrow C_{\nu}$ be a bijection. Then
$\\{\pi_{\nu}``[B_{\xi}]\mid\nu<\chi,\xi<\chi\\}$ witnesses
$\operatorname{m}^{-}(\kappa,\theta)\leq\chi$.

  5. (v)

Since $\mu^{+}$ is regular, any element of $[\mu^{+}]^{\rho}$ is bounded in
$\mu^{+}$. So let $\chi:=\operatorname{m}(\mu,\rho,\theta)$ and let
$\\{B_{\xi}\mid\xi<\chi\\}$ witness this and for every $\nu\in[\mu,\mu^{+})$
let $\pi_{\nu}:\mu\leftrightarrow\nu$ be a bijection. Then
$\\{\pi_{\nu}[B_{\xi}]\mid\nu\in[\mu,\mu^{+}),\xi<\chi\\}$ witnesses
$\operatorname{m}(\mu^{+},\rho,\theta)\leq\mu^{+}\cdot\chi$ by our
observation.

  6. (vi)

We prove this by induction on $\kappa$. The base case is clear by (ii) and the
successor case is clear by (v). For the limit case, as
$\kappa<\theta^{+\operatorname{cf}(\rho)}$, we have that
$\operatorname{cf}(\kappa)<\operatorname{cf}(\rho)$. It follows that if
$A\in[\kappa]^{\rho}$, then for some $\chi<\kappa$, $|A\cap\chi|\geq\rho$. So
now by the induction hypothesis for each
$\chi\in(\theta,\kappa)\cap\operatorname{Card}$, let
$\\{B^{\chi}_{\xi}\mid\xi<\chi\\}$ witness that
$\operatorname{m}(\chi,\rho,\theta)=\chi$. So we then have that
$\\{B^{\chi}_{\xi}\mid\chi\in(\theta,\kappa)\cap\operatorname{Card},\xi<\chi\\}$
witnesses that $\operatorname{m}(\kappa,\rho,\theta)=\kappa$ by the
observation.

  7. (vii)

Let $\mathfrak{a}$ be an end segment of
$(\theta,\kappa)\cap\operatorname{Card}$ such that for every
$\chi\in\mathfrak{a}$, $\operatorname{m}(\chi,\theta)\leq\kappa$ as witnessed
by some $\\{B^{\chi}_{\xi}\mid\xi<\kappa\\}$. Let us verify that
$\\{B^{\chi}_{\xi}\mid\chi\in\mathfrak{a},\xi<\kappa\\}$ witnesses that
$\operatorname{m}^{-}(\kappa,\theta)=\kappa$. So let $A\in[\kappa]^{\kappa}$.
Then there is some $\chi\in\mathfrak{a}$ such that $|A\cap\chi|\geq\theta$. So
there is some $\xi<\kappa$ such that $|B^{\chi}_{\xi}\cap
A\cap\chi|\geq\theta$.

  8. (viii)

We shall prove this by induction on $\kappa$. The base case is clear by (ii)
and the successor case is clear by (iv). So suppose that $\kappa$ is a limit
cardinal, which is not a cardinal fixed point by our assumptions. Suppose that
$\kappa=\aleph_{\xi}>\xi$. Let $\chi\in(\theta,\kappa)\cap\operatorname{Card}$
be a regular cardinal such that $\xi<\chi$. So then
$\chi<\kappa<\chi^{+\chi}$. So for all
$\rho\in(\chi,\kappa)\cap\operatorname{Card}$ we have by (vi) that
$\operatorname{m}(\rho,\chi)=\rho$. So, by (vii) we have that
$\operatorname{m}^{-}(\kappa,\chi)=\kappa$. Now, the induction hypothesis
tells us that $\operatorname{m}^{-}(\chi,\theta)=\chi$. So we use (iii) and
(iv) to conclude that $\operatorname{m}^{-}(\kappa,\theta)=\kappa$ and
continue the induction.

  9. (ix)

If $\kappa$ is not a cardinal fixed point, then it is not a limit of cardinal
fixed points either. So we can find a $\chi<\kappa$ such that there are no
cardinal fixed points in $(\chi,\kappa]$. Then
$\operatorname{m}^{-}(\kappa,\chi)=\kappa$ by (viii).

  10. (x)

Again, $\theta^{+}$ serves as a witness.

  11. (xi)

Let $\\{B_{\xi}\mid\xi<\chi\\}$ witness
$\operatorname{cof}([\mu]^{\theta})\leq\chi$ and let
$\\{C_{\nu}\mid\nu<\chi\\}$ witness
$\operatorname{cof}([\kappa]^{\mu})\leq\chi$. For each $\nu<\chi$ let
$\pi_{\nu}:\mu\leftrightarrow C_{\nu}$ be a bijection. Then
$\\{\pi_{\nu}``[B_{\xi}]\mid\nu<\chi,\xi<\chi\\}$ witnesses
$\operatorname{cof}([\kappa]^{\theta})\leq\chi$.

  12. (xii)

By induction using (iii) and (x) and (xi).

  13. (xiii)

Let $\pi:{}^{<\theta}\kappa\rightarrow\chi$ be a bijection. Let $\mathcal{B}$
be a family witnessing $\operatorname{m}(\chi,\theta)$. Define

$\mathcal{C}:=\\{\bigcup\operatorname{im}[\pi^{-1}[B]]\mid
B\in\mathcal{B}\\}.$

We claim that $\mathcal{C}$ witnesses $\operatorname{cof}([\kappa]^{\theta})$.
It is easy to see that $\mathcal{C}\subseteq[\kappa]^{\theta}$. To verify the
rest, suppose that $A\in[\kappa]^{\theta}$. Let $h:\theta\rightarrow\kappa$ be
a function such that $\operatorname{im}(h)=A$. Let
$Y:=\\{\pi(h\restriction\xi)\mid\xi<\theta\\}$. So then $Y\in[\chi]^{\theta}$.
So there is some $B\in\mathcal{B}$ such that $|B\cap Y|\geq\theta$. It follows
that

$Z:=\\{\xi<\theta\mid
h\restriction\xi\in\pi^{-1}[B]\\}=\\{\xi<\theta\mid\pi(h\restriction\xi)\in
B\\}$

has size $\theta$, and in particular is unbounded in $\theta$. Now supposing
that $\gamma\in A$, then there is some $\xi\in Z$ such that
$\gamma\in\operatorname{im}(h\restriction\xi)$. It follows that
$A\subseteq\bigcup\operatorname{im}[\pi^{-1}[B]]$.∎

Beyond Lemma 2.3 and the other results we have hinted at, the following result
connects the cardinals $\operatorname{m}(\kappa,\theta)$ and
$\operatorname{cof}([\kappa]^{\theta})$ to a standard hypothesis from PCF
Theory. Below, the equivalence between (i) and (ii) is due to Shelah [26,
Theorem 6.3] and their equivalence with (iii) is due to Rinot [22]. The reader
may consult either of these papers for undefined notions.

######  Theorem 2.4 ([26, 22]).

The following are equivalent:

  1. (i)

Shelah’s Strong Hypothesis, that is, $\operatorname{pp}(\kappa)=\kappa^{+}$
for every singular cardinal $\kappa$;

  2. (ii)

for every pair of cardinals $\theta<\kappa$,
$\operatorname{cof}([\kappa]^{\theta})=\kappa$ if
$\operatorname{cf}(\theta)>\operatorname{cf}(\kappa)$ and $\kappa^{+}$
otherwise;

  3. (iii)

for every pair of cardinals $\theta<\kappa$,
$\operatorname{m}(\kappa,\theta)=\kappa$ if
$\operatorname{cf}(\theta)\neq\operatorname{cf}(\kappa)$ and $\kappa^{+}$
otherwise.

One may extract further bounds on these cardinals in terms of PCF-theoretic
invariants from the literature, see for example the covering numbers in [27,
Chapter II, §5] and [28, Claim 1.2]. Lastly, Magidor proved in [18] that
assuming the consistency of certain large cardinals, it is consistent that
$\operatorname{cof}([\aleph_{\omega}]^{\aleph_{0}})>\aleph_{\omega+1}$, and
Shelah proved in [25] that for every countable ordinal $\alpha$, it is
consistent assuming the consistency of large cardinals that
$\operatorname{cof}([\aleph_{\omega}]^{\aleph_{0}})>\aleph_{\alpha}$. It is
known that large cardinals are required. See [9] for details.

###  2.2. Convex equivalence relations

We shall say that an equivalence relation $\equiv$ on a linear order $L$ is
_convex_ if its equivalence classes are convex: if $x<_{L}y<_{L}z$ are
elements of $L$ and $x\equiv z$, then in fact $x\equiv y\equiv z$. Convex
equivalence relations of the sort which appear in Lemma 2.9 are the core idea
in [32] and here as well.

The following lemma is easy to prove and often occurs in PCF theory, but we
give a proof anyway. Recall that for $E$ a set of ordinals,
$\operatorname{cl}(E)$ denotes the closure of $E$ in $\sup(E)$, which is to
say,
$\operatorname{cl}(E):=E\cup\\{\alpha<\sup(E)\mid\alpha=\sup(E\cap\alpha)\\}$.

######  Lemma 2.5.

Let $\lambda$ be an uncountable regular cardinal.

  1. (i)

If $\equiv$ is a convex equivalence relation on $\lambda$ and there is some
$E\subseteq\lambda$ unbounded in $\lambda$ and consisting of pairwise
inequivalent elements (that is, ${[E]^{2}}\cap{\equiv}=\emptyset$), then there
is some $D\subseteq\lambda$ which is a club consisting of pairwise
inequivalent elements: ${[D]^{2}}\cap{\equiv}=\emptyset$.

  2. (ii)

If $\equiv$ is a convex equivalence relation on $\lambda$, then there is
$D\subseteq\lambda$ a club such that either ${[D]^{2}}\subseteq{\equiv}$ or
${[D]^{2}}\cap{\equiv}=\emptyset$.

  3. (iii)

If $\mathcal{E}$ is a family of convex equivalence relations on $\lambda$ of
cardinality less than $\lambda$, then there is $D\subseteq\lambda$ a club such
that for every ${\equiv}\in{\mathcal{E}}$ either ${[D]^{2}}\subseteq{\equiv}$
or ${[D]^{2}}\cap{\equiv}=\emptyset$.

###### Proof.

Assuming that we have proved (i), the proof of (ii) is easy: given $\equiv$ a
convex equivalence relation on $\lambda$, in case there is some
$E\subseteq\lambda$ an unbounded set consisting of pairwise inequivalent
elements, then there is a club consisting of pairwise inequivalent elements.
If there is no unbounded subset of $\lambda$ consisting of inequivalent
elements, then there must be an equivalence class of $\equiv$ which is an end
segment of $\lambda$, and then this end segment is of course a club as well.
Obtaining (iii) from (ii) is clear. So we only need to prove (i).

So, suppose that $E\subseteq\lambda$ is unbounded in $\lambda$ and consists of
pairwise inequivalent elements. We can assume that if $\alpha\in E$, then for
every $\beta<\alpha$, $\beta\not\equiv\alpha$. We shall show that
$\operatorname{cl}(E)$ will be a club of $\lambda$ as required. So let, if
possible, $\alpha\in\operatorname{cl}(E)\setminus E$. If $\beta\in
E\cap\alpha$, then there is some $\gamma\in(\beta,\alpha)\cap E$. By the
choice of $E$, $\beta\not\equiv\gamma$. So, as $\equiv$ is convex, for every
$\beta<\alpha$, $\beta\not\equiv\alpha$. This implies that $\alpha$ is not
equivalent to any element of $E\cap\alpha$. Now if $\beta\in
E\setminus\alpha=E\setminus(\alpha+1)$, then by the choice of $E$,
$\alpha\not\equiv\beta$. So $\operatorname{cl}(E)$ is a club as required. ∎

We note that the proof of (i) in fact tells us that if a convex equivalence
relation $\equiv$ on a regular cardinal $\lambda$ has unboundedly many
equivalence classes, then the natural ‘selector’ for $\lambda/{\equiv}$, the
set of least elements of each equivalence class, is in fact a club. We shall
refer to a club with a property as in (iii) as having the _0-1 property_ with
respect to the family of convex equivalence relations $\mathcal{E}$.

We come to the point at which we define the specific convex equivalence
relations we shall use. Before this, let us mention that in all that follows
in this article we shall have $\vec{f}=\langle
f_{\alpha}\mid\alpha<\lambda\rangle$ a $<_{\theta}$-chain in
${}^{\kappa}{\mu}$, which is to say that for all $\alpha<\beta<\lambda$,

  1. (i)

$|\\{\xi<\kappa\mid f_{\alpha}(\xi)>f_{\beta}(\xi)\\}|<\theta$;

  2. (ii)

$|\\{\xi<\kappa\mid f_{\alpha}(\xi)<f_{\beta}(\xi)\\}|=\kappa$.

At some points $\vec{f}$ will have some extra properties as well, but what
follows in this section is based on the above assumption on $\vec{f}$. In
particular, the convex equivalence relations we define will be on $\lambda$,
which we remind the reader by our convention is always a regular cardinal.

######  Definition 2.6.

Let $g\in{}^{\kappa}\mu$ and $Y\subseteq\mu$. Then $g^{Y}:\kappa\rightarrow
Y\cup\\{\mu\\}$ is the function defined as follows:

$g^{Y}(\xi):=\min((Y\cup\\{\mu\\})\setminus g(\xi)).$

We shall use the following fact several times without mentioning.

######  Observation 2.7.

Let $g,g^{\prime}\in{}^{\kappa}\mu$ be functions, $X\subseteq\kappa$ and
$Y\subseteq\mu$. Suppose that $g\restriction X\leq g^{\prime}\restriction X$
everywhere. Then $g^{Y}\restriction X\leq g^{Y}\restriction X$ everywhere.

######  Definition 2.8.

Given $X\subseteq\kappa$ and $Y\subseteq\mu$, let $\equiv_{X}^{Y}$ denote the
following relation on $\lambda$:

$\\{(\alpha,\beta)\mid\alpha,\beta<\lambda\ \&\ |\\{\xi\in X\mid
f^{Y}_{\alpha}(\xi)\neq f^{Y}_{\beta}(\xi)\\}|<\theta\\}.$

######  Lemma 2.9.

Let $X\subseteq\kappa$ and $Y\subseteq\mu$. Then $\equiv_{X}^{Y}$ is a convex
equivalence relation.

###### Proof.

As $\theta$ is an infinite cardinal, it is clear that $\equiv^{Y}_{X}$ is an
equivalence relation. Suppose $\alpha<\beta<\gamma<\lambda$ and
$\alpha\equiv_{X}^{Y}\gamma$. Let $x\in[\kappa]^{<\theta}$ be such that for
all $\xi\in\kappa\setminus x$, $f_{\alpha}(\xi)\leq f_{\beta}(\xi)\leq
f_{\gamma}(\xi)$. As $\alpha\equiv_{X}^{Y}\gamma$, we can also assume that $x$
is large enough that $\\{\xi\in X\mid f^{Y}_{\alpha}(\xi)\neq
f^{Y}_{\gamma}(\xi)\\}\subseteq x$. Now, for all $\xi\in X\setminus x$, we get
that $f^{Y}_{\alpha}(\xi)=f_{\gamma}^{Y}(\xi)$, so that the interval
$(f_{\alpha}(\xi),f_{\gamma}(\xi))$ has empty intersection with $Y$, and hence
$f_{\alpha}^{Y}(\xi)=f_{\beta}^{Y}(\xi)=f_{\gamma}^{Y}(\xi)$.

Thus $\\{\xi\in X\mid f^{Y}_{\alpha}(\xi)\neq f^{Y}_{\beta}(\xi)\\}$ and
$\\{\xi\in X\mid f^{Y}_{\beta}(\xi)\neq f^{Y}_{\gamma}(\xi)\\}$ are both
subsets of $x$. In particular, $\alpha\equiv_{X}^{Y}\beta$ and
$\beta\equiv_{X}^{Y}\gamma$. ∎

In what follows, we shall pick $\mathcal{B}$ a collection of subsets of
$\kappa$ and $\mathcal{C}$ a collection of subsets of $\mu$, and then
$\\{\equiv^{C}_{B}\mid B\in\mathcal{B},C\in\mathcal{C}\\}$ will be the family
of convex equivalence families of interest to us. We end this section with a
simple observation.

######  Observation 2.10.

Let $\chi,\rho$ be infinite cardinals. Let $X\in[\kappa]^{\chi}$ and
$Y\in[\mu]^{\rho}$ be such that $\equiv^{Y}_{X}$ has $\lambda$-many
equivalence classes. Then $\chi^{\rho}\geq\lambda$.

##  3\. The space $({}^{\kappa}\mu,<_{\theta})$

######  Definition 3.1.

Let $\lambda,\mu,\kappa$ be ordinals.

  1. (i)

The partition relation $\lambda\rightarrow[\mu]^{2}_{\kappa,\mathrm{bdd}}$
asserts that for every $c:[\lambda]^{2}\rightarrow\kappa$, there is some
$I\in[\kappa]^{\mu}$ and $\epsilon<\kappa$ such that
$c``[I]^{2}\subseteq\epsilon$.

  2. (ii)

Recall that _Chang’s Conjecture_ , denoted $\operatorname{CC}$, states that
$\omega_{2}\rightarrow[\omega_{1}]^{2}_{{\omega_{1}},\mathrm{bdd}}$.

We point out that our definition of $\operatorname{CC}$ is a little non-
standard and that it is a result of Erdős and Hajnal [6, pg. 275] (or see [11,
Proposition 8.2]) that the above formulation is equivalent to the more
standard definition. Before starting with Theorem 3.3 and Theorem 3.4, we
mention the following two results, the first due to Koszmider, the second due
to Veličković, which they imply as special cases.

######  Theorem 3.2 ([14], [33]).

  1. (i)

$\operatorname{CC}$ implies that there is no chain in
$({}^{\omega_{1}}2,<_{\aleph_{0}})$ (that is, a chain of sets) of length
$\omega_{2}$.

  2. (ii)

$\operatorname{CC}$ implies that there is no chain in
$({}^{\omega_{1}}{\omega_{1}},\ll_{\aleph_{0}})$ of length $\omega_{2}$.

######  Theorem 3.3.

Let $\theta,\kappa,\mu,\lambda$ be infinite cardinals with $\lambda$ being
regular. Suppose also that

  1. (i)

$\theta\leq\kappa,\mu$ and $\theta\leq\operatorname{cf}(\kappa)$;

  2. (ii)

$\operatorname{m}^{-}(\kappa,\theta)<\lambda$;

  3. (iii)

$\operatorname{cof}([\mu]^{\theta})<\lambda$;

  4. (iv)

one of the following occurs:

    1. (a)

$\theta^{+}<\operatorname{cf}(\kappa)$, or

    2. (b)

$\lambda\rightarrow[\theta^{+}]^{2}_{\kappa,\mathrm{bdd}}$.

Then there are no chains in $({}^{\kappa}\mu,<_{\theta})$ of length $\lambda$.

###### Proof.

Note that the hypotheses imply that $\mu,\kappa<\lambda$. Suppose towards a
contradiction that $\langle f_{\alpha}\mid\alpha<\lambda\rangle$ is such a
chain. Let $\mathcal{B}$ be a family witnessing
$\operatorname{m}^{-}(\kappa,\theta)<\lambda$, and since
$\kappa\leq\operatorname{m}^{-}(\kappa,\theta)$ we can assume that
$\mathcal{B}$ is closed under taking end segments. Let $\mathcal{C}$ be a
family witnessing that $\operatorname{cof}([\mu]^{\theta})<\lambda$. As the
family $\\{\equiv^{C}_{B}\mid B\in\mathcal{B},C\in\mathcal{C}\\}$ of convex
equivalence relations has size less than $\lambda$, we can find a club
$D\subseteq\lambda$ which has the 0-1 property with respect to it by Lemma
2.5. Let $\langle i_{\alpha}\mid\alpha<\lambda\rangle$ be the increasing
enumeration of $D$.

######  Claim 3.3.1.

For any $\epsilon<\kappa$, there are $B\in\mathcal{B}$ and $C\in\mathcal{C}$
such that $B\subseteq\kappa\setminus\epsilon$ and all the elements of $D$ are
in distinct classes of $\equiv^{C}_{B}$.

###### Proof.

As $f_{i_{0}}<_{\theta}f_{i_{1}}$ the set
$S:=\\{\xi\in\kappa\setminus\epsilon\mid f_{i_{0}}(\xi)<f_{i_{1}}(\xi)\\}$ has
size $\kappa$, so there is some $B\in\mathcal{B}$ such that $|B\cap
S|\geq\theta$. Since $\mathcal{B}$ is closed under taking end segments we can
also assume that $B\subseteq\kappa\setminus\epsilon$. Let $C\in\mathcal{C}$ be
such that $f_{i_{0}}``[B]\subseteq C$. Then $i_{0}\not\equiv^{C}_{B}i_{1}$, so
by the 0-1 property of $D$ we can finish. ∎

As $\theta\leq\operatorname{cf}(\kappa)$ we are justified in defining the
following function $h:[\lambda]^{2}\rightarrow\kappa$ via
$h(\alpha,\beta):=\epsilon$ where $\epsilon<\kappa$ is the least
$\varepsilon<\kappa$ such that

$\\{\xi<\kappa\mid
f_{i_{\alpha}}(\xi)>f_{i_{\beta}}(\xi)\\}\subseteq\varepsilon.$

We now have to make a case distinction to finish the proof.

Case 1: $\operatorname{cf}(\kappa)>\theta^{+}$. Let
$\epsilon:=\sup\\{h(\alpha,\beta)\mid\alpha<\beta<\theta^{+}\\}$ which we note
is bounded below $\kappa$. By Claim 3.3.1, we can find $B\in\mathcal{B}$ and
$C\in\mathcal{C}$ such that $B\subseteq\kappa\setminus\epsilon$ and such that
all the elements of $D$ are in distinct classes of $\equiv^{C}_{B}$. This
implies that for every $\alpha<\beta<\theta^{+}$,
$f_{i_{\alpha}}^{C}\restriction B\leq f_{i_{\beta}}^{C}\restriction B$
everywhere but also, $i_{\alpha}\not\equiv^{C}_{B}i_{\beta}$.

So for each $\alpha<\theta^{+}$ we can find $\tau_{\alpha}\in B$ and
$\zeta_{\alpha}\in C$ such that

$f_{i_{\alpha}}^{C}(\tau_{\alpha})=\zeta_{\alpha}<f_{i_{\alpha+1}}^{C}(\tau_{\alpha}).$

As $|B\times C|<\theta^{+}$, for some $(\tau^{*},\zeta^{*})\in B\times C$ we
can find $\alpha<\beta<\theta^{+}$ such that
$\tau_{\alpha}=\tau^{*}=\tau_{\beta}$ and
$\zeta_{\alpha}=\zeta^{*}=\zeta_{\beta}$. But this implies that

$f_{i_{\alpha}}^{C}(\tau^{*})=\zeta^{*}<f_{i_{\alpha+1}}^{C}(\tau^{*})\leq
f_{i_{\beta}}(\tau^{*})=\zeta^{*}$

which is not possible.

Case 2: $\lambda\rightarrow[\theta^{+}]^{2}_{\kappa,\mathrm{bdd}}$. The proof
is similar. Suppose towards a contradiction that
$\lambda\rightarrow[\theta^{+}]^{2}_{\kappa,\mathrm{bdd}}$. Applying it to the
function $h:[\lambda]^{2}\rightarrow\kappa$, we get an $\epsilon<\kappa$ and
an $I\in[\lambda]^{\theta^{+}}$ such that $h``[I]^{2}\subseteq\epsilon$.
Appealing to Claim 3.3.1 we again find $B$ and $C$ as above with
$B\subseteq\kappa\setminus\epsilon$.

The rest of the proof is similar, except that we must consider consecutive
elements of $I$ in the increasing enumeration instead of consecutive elements
of $\theta^{+}$ as in the previous case. That is, for each $i\in I$, let
$i^{+}:=\min(I\setminus(i+1))$. Then we find $(\tau_{i},\zeta_{i})\in B\times
C$ such that

$f_{i}^{C}(\tau_{i})=\zeta_{i}<f_{i^{+}}^{C}(\tau_{i}).$

We reach a contradiction in the same way. ∎

We point out that in the above, we required the hypothesis
$\operatorname{cof}([\mu]^{\theta})<\lambda$ whereas in the forthcoming
Theorem 4.2 we will be able to make do with weaker hypotheses such as
$\operatorname{m}(\mu,\theta)$ so that we suffice ourselves not with covering
a set but merely with having large intersection with it. Comparing clauses
(vi) and (xii) of Lemma 2.3 makes clear the benefit of such a change. The
reason we could not be as parsimonious here was that in the proof above we
were not able to obtain large subsets of the image as in the forthcoming Claim
4.2.1. Indeed, a chain of sets, that is, a chain in
$({}^{\kappa}2,<_{\theta})$ is also a chain in $({}^{\kappa}\mu,<_{\theta})$
for any $\mu\geq 2$. In contrast to this, the forthcoming Proposition 4.1
shows that if $\theta,\mu<\kappa$, then there are no chains in
$({}^{\kappa}\mu,\ll_{\theta})$ of length $\mu+1$. Finally, if one is
interested not in $({}^{\kappa}\mu,<_{\theta})$ but the subspace of it
consisting of increasing or even just non-decreasing functions, then one can
reduce the hypotheses from those about covering to meeting. However, as these
results are not well-motivated we do not include them here.

The difference in the previous theorem and the next theorem are the
requirements on $\mu$. In the former, we required that $\theta\leq\mu$ and
$\operatorname{cof}([\mu]^{\theta})<\lambda$ (by Definition 2.2 the first of
these is required in order for $\operatorname{cof}([\mu]^{\theta})$ to be
defined). In what follows we replace these hypotheses by
$\mu<\operatorname{cf}(\kappa)$.

######  Theorem 3.4.

Let $\theta,\kappa,\mu,\lambda$ be infinite cardinals with $\lambda$ being
regular. Suppose also that

  1. (i)

$\theta\leq\operatorname{cf}(\kappa)$;

  2. (ii)

$\operatorname{m}^{-}(\kappa,\theta)<\lambda$;

  3. (iii)

$\mu<\operatorname{cf}(\kappa)$;

  4. (iv)

one of the following occurs:

    1. (a)

$\theta^{+}<\operatorname{cf}(\kappa)$, or

    2. (b)

$\lambda\rightarrow[\theta^{+}]^{2}_{\kappa,\mathrm{bdd}}$.

Then there are no chains in $({}^{\kappa}\mu,<_{\theta})$ of length $\lambda$.

###### Proof.

The proof is almost exactly the same as that of Theorem 3.3 except the
definition of $\mathcal{C}$ and also Claim 3.3.1 which needs to be slightly
modified. As before, let $\mathcal{B}$ be a family witnessing
$\operatorname{m}^{-}(\kappa,\theta)<\lambda$ which is closed under taking end
segments. Let $\mathcal{C}:=[\mu]^{1}$. The following is the analogue of Claim
3.3.1.

######  Claim 3.4.1.

For any $\epsilon<\kappa$, there are $B\in\mathcal{B}$ and $C\in\mathcal{C}$
such that $B\subseteq\kappa\setminus\epsilon$ and all the elements of $D$ are
in distinct classes of $\equiv^{C}_{B}$.

###### Proof.

As $f_{i_{0}}<_{\theta}f_{i_{1}}$ the set
$S:=\\{\xi\in\kappa\setminus\epsilon\mid f_{i_{0}}(\xi)<f_{i_{1}}(\xi)\\}$ has
size $\kappa$. As $\mu<\operatorname{cf}(\kappa)$, there is a $\zeta<\mu$ such
that $S^{\zeta}:=\\{\xi\in S\mid f_{i_{0}}(\xi)=\zeta\\}$ has size $\kappa$.
So there is some $B\in\mathcal{B}$ such that $|B\cap S^{\zeta}|\geq\theta$ and
$B\subseteq\kappa\setminus\epsilon$. Let $C:=\\{\zeta\\}$. So then $B$ and $C$
are as required. ∎

The rest of the proof is exactly the same. ∎

The next two corollaries together prove Theorem A.

######  Corollary 3.5.

There are no $\theta^{+++}$ chains in
$({}^{\theta^{++}}{\theta^{++}},<_{\theta})$ for every infinite cardinal
$\theta$.

###### Proof.

Suppose that there is such a chain. Then by Lemma 2.3, for
$(\mu,\kappa,\lambda):=(\theta^{++},\theta^{++},\theta^{+++})$,

$\theta^{+++}=\lambda>\operatorname{m}^{-}(\kappa,\theta)=\operatorname{m}^{-}(\theta^{++},\theta)=\theta^{++}$

and

$\theta^{+++}=\lambda>\operatorname{cof}([\mu]^{\theta})=\operatorname{cof}([\theta^{++}]^{\theta})=\theta^{++}.$

So by Theorem 3.3 we conclude that
$\operatorname{cf}(\kappa)=\operatorname{cf}(\theta^{++})=\theta^{++}\leq\theta^{+}$
which is absurd. ∎

######  Corollary 3.6.

For every infinite cardinal $\theta$, there is no sequence $\langle
S_{\alpha}\mid\alpha<\theta^{+++}\rangle$ of sets in
$[\theta^{++}]^{\theta^{++}}$ such that, for all $\alpha<\beta<\theta^{+++}$:

  1. (i)

$|S_{\alpha}\setminus S_{\beta}|<\theta$;

  2. (ii)

$|S_{\beta}\setminus S_{\alpha}|=\theta^{++}$.

###### Proof.

If there were such a sequence, then we would get a $\theta^{+++}$ length chain
in $({}^{\theta^{++}}2,<_{\theta})$ and hence in
$({}^{\theta^{++}}{\theta^{++}},<_{\theta})$ as well, which we now know to be
impossible. Alternately, we could use Theorem 3.4 for the parameters
$(\mu,\kappa,\lambda):=(2,\theta^{++},\theta^{+++})$ to get a contradiction. ∎

##  4\. The space $({}^{\kappa}\mu,\ll_{\theta})$

The following proposition shows that when considering chains in
$({}^{\kappa}\mu,\ll_{\theta})$, the requirement that $\mu\geq\kappa$ is quite
natural. This is in contrast to the space $({}^{\kappa}\mu,<_{\theta})$ for
which one of the most important cases is when $\mu=2$, that is we are
considering chains of sets. Indeed, one may compare it with Theorem 1.4 of
Koszmider.

######  Proposition 4.1.

Suppose that $\theta,\kappa$ are infinite cardinals, and $\mu$ is a cardinal
which is possibly finite. Suppose that $\mu<\kappa$ and $\theta<\kappa$. Then
there are no chains in $({}^{\kappa}\mu,\ll_{\theta})$ of length $\mu+1$.

###### Proof.

Suppose towards a contradiction that $\langle
f_{\alpha}\mid\alpha\leq\mu\rangle$ is such a chain. Then the following set

$S:=\\{\xi<\kappa\mid\exists\alpha,\beta\leq\mu\ [\alpha<\beta\ \&\
f_{\alpha}(\xi)\geq f_{\beta}(\xi)]\\}$

has size at most $\mu\cdot\theta$, so in particular less than $\kappa$. So now
let $\xi\in\kappa\setminus S$. Then the function $\alpha\mapsto
f_{\alpha}(\xi)$ defined for $\alpha\leq\mu$ is strictly increasing in
$\alpha$ and has image contained in $\mu$. However the image of this function
has ordertype $\mu+1$ which leads to a contradiction. ∎

The following theorem is the main result of this section. As it has a large
number of parameters, we mention two important instantiations of the theorem.
The first is when $\chi=\rho=\theta^{+}$ and $\vartheta=\theta$, this being
the content of Corollary 4.3. The second is when $\chi=\rho=\vartheta^{+}$ for
some regular $\vartheta\in(\theta,\kappa)$ such that
$\kappa<\vartheta^{+\vartheta}$, assuming such a $\vartheta$ can be found.
This is the content of Corollary 4.4.

######  Theorem 4.2.

Suppose that $\mu,\kappa,\theta,\lambda$ are infinite cardinals with
$\theta<\theta^{+}<\kappa\leq\mu$ and $\lambda$ being regular. Suppose also
that there are infinite cardinals $\chi,\rho,\vartheta$ such that

  1. (i)

$\theta<\chi,\rho<\kappa$;

  2. (ii)

$\operatorname{m}(\kappa,\rho,\vartheta,\theta)<\lambda$;

  3. (iii)

$\operatorname{m}(\mu,\chi,\kappa,\vartheta)<\lambda$.

Then there are no chains in $({}^{\kappa}\mu,\ll_{\theta})$ of length
$\lambda$.

###### Proof.

Let $\varkappa:=\chi+\rho$, so that $\varkappa<\kappa$. Note that the
hypotheses imply that $\lambda>\mu,\kappa$. Suppose towards a contradiction
that $\langle f_{\alpha}\mid\alpha<\lambda\rangle$ is such a chain. Let
$\mathcal{S}=\langle S_{\eta}\mid\eta<\kappa\rangle$ be a partition of
$\kappa$ into $\kappa$-many pairwise disjoint sets of size $\kappa$. Let
$\mathcal{B}$ be a witness to
$\operatorname{m}(\kappa,\rho,\vartheta,\theta)<\lambda$ and we furthermore
can assume that $\mathcal{B}$ is closed under taking intersections with
elements of $\mathcal{S}$. Let $\mathcal{C}$ be a witness to
$\operatorname{m}(\mu,\chi,\kappa,\vartheta)<\lambda$. Then the family of
convex equivalence relations $\\{\equiv^{C}_{B}\mid
B\in\mathcal{B},C\in\mathcal{C}\\}$ has size less than $\lambda$, so let
$D\subseteq\lambda$ be a club with the 0-1 property with respect to it by
Lemma 2.5. Let $\langle i_{\alpha}\mid\alpha<\lambda\rangle$ be the increasing
enumeration of $D$. As $\varkappa<\kappa$, the set

$\\{\xi<\kappa\mid\exists\alpha,\beta<\varkappa\ [\alpha<\beta\ \&\
f_{i_{\alpha}}(\xi)\geq f_{i_{\beta}}(\xi)]\\}$

has size less than $\kappa$, so we can fix an $\eta<\kappa$ such that

$S_{\eta}\cap\\{\xi<\kappa\mid\exists\alpha,\beta<\varkappa\ [\alpha<\beta\
\&\ f_{i_{\alpha}}(\xi)\geq f_{i_{\beta}}(\xi)]\\}=\emptyset.$

######  Claim 4.2.1.

There are sequences $\langle j(\alpha)\mid\alpha<\kappa\rangle$ and
$\langle\xi_{\alpha}\mid\alpha<\kappa\rangle$ such that

  1. (i)

$\langle j(\alpha)\mid\alpha<\kappa\rangle$ consists of ordinals less than
$\kappa$ and possibly contains repetitions;

  2. (ii)

$\langle\xi_{\alpha}\mid\alpha<\kappa\rangle$ are all distinct and contained
in $S_{\eta}$;

  3. (iii)

for every $\alpha<\kappa$, $f_{i_{0}}(\xi_{\alpha})\leq
f_{i_{j(\alpha)}}(\xi_{\alpha})<f_{i_{\kappa}}(\xi_{\alpha})$;

  4. (iv)

the function $\alpha\mapsto f_{i_{j(\alpha)}}(\xi_{\alpha})$ defined for
$\alpha<\kappa$ is injective.

###### Proof.

We construct the sequences $\langle j(\alpha)\mid\alpha<\kappa\rangle$ and
$\langle\xi_{\alpha}\mid\alpha<\kappa\rangle$ by recursion on $\alpha<\kappa$.
The base case is easy to perform: set $j(0)=0$, and since
$f_{i_{0}}\ll_{\theta}f_{i_{\kappa}}$ and $|S_{\eta}|=\kappa>\theta$ we can
find a $\xi_{0}\in S_{\eta}$ such that
$f_{i_{0}}(\xi_{0})=f_{i_{j(0)}}(\xi_{0})<f_{i_{\kappa}}(\xi_{0})$.

So suppose that $\nu<\kappa$ and we have constructed $\langle
j(\alpha)\mid\alpha<\nu\rangle$ and $\langle\xi_{\alpha}\mid\alpha<\nu\rangle$
which satisfy the requirements up to $\nu$ and let
$Y_{\nu}:=\\{f_{i_{j(\alpha)}}(\xi_{\alpha})\mid\alpha<\nu\\}$ which we note
has size $|\nu|$. Let $\gamma:=\operatorname{otp}(Y_{\nu})$ and note that
$\gamma<\kappa$. Let $Z:=[0,\gamma+1)\cup\\{\kappa\\}$. As $|Z|<\kappa$, the
set $S^{*}$ defined as follows

$S^{*}:=\\{\xi\in S_{\eta}\mid\exists\alpha,\beta\in Z\ [\alpha<\beta\ \&\
f_{i_{\alpha}}(\xi)\geq f_{i_{\beta}}(\xi)]\\}$

has size less than $\kappa$. In particular, we can find a $\xi^{*}\in
S_{\eta}\setminus(Y_{\nu}\cup S^{*})$.

Now, the function

$\beta\mapsto f_{i_{\beta}}(\xi^{*})$

defined for $\beta<\gamma+1$ is strictly increasing in $\beta$ and has image
contained in $[f_{i_{0}}(\xi^{*}),f_{i_{\kappa}}(\xi^{*}))$ by the choice of
$\xi^{*}$. Since the image has ordertype $\gamma+1$, it follows that for some
$\beta<\gamma+1$ we have that $f_{i_{\beta}}(\xi^{*})\notin Y_{\nu}$. So now
taking $j(\nu):=\beta$ and $\xi_{\nu}:=\xi^{*}$ we can continue the recursive
construction. ∎

Let $\langle j(\alpha)\mid\alpha<\kappa\rangle$ and
$\langle\xi_{\alpha}\mid\alpha<\kappa\rangle$ be as in the claim and let

$Y:=\\{f_{i_{j(\alpha)}}(\xi_{\alpha})\mid\alpha<\kappa\\}.$

Now as $\mathcal{C}$ witnesses $\operatorname{m}(\mu,\chi,\kappa,\vartheta)$,
there is some $C\in\mathcal{C}$ such that $|C\cap Y|\geq\vartheta$. Let

$X:=\\{\xi_{\alpha}\mid\alpha<\kappa,\ f_{i_{j(\alpha)}}(\xi_{\alpha})\in
C\cap Y\\}$

and we note that it is in $[\kappa]^{\geq\vartheta}$. As $\mathcal{B}$
witnesses $\operatorname{m}(\kappa,\rho,\vartheta,\theta)$, there is some
$B\in\mathcal{B}$ such that $|B\cap X|\geq\theta$. As $\mathcal{B}$ is closed
under intersections with $S_{\eta}$ and $X\subseteq S_{\eta}$, we can also
assume that $B\subseteq S_{\eta}$.

######  Claim 4.2.2.

$i_{0}\not\equiv^{C}_{B}i_{\kappa}$.

###### Proof.

For every $\alpha$ such that $\xi_{\alpha}\in X$ we have that

$f_{i_{0}}(\xi_{\alpha})\leq
f_{i_{j(\alpha)}}(\xi_{\alpha})<f_{i_{\kappa}}(\xi_{\alpha}),$

and since $f_{i_{j(\alpha)}}(\xi_{\alpha})\in C\cap Y$ this implies that

$f_{i_{0}}^{C}(\xi_{\alpha})\leq
f_{i_{j(\alpha)}}(\xi_{\alpha})<f_{i_{\kappa}}^{C}(\xi_{\alpha}).$

Since $|B\cap X|\geq\theta$ we finish. ∎

By the 0-1 property of $D$, this tells us that all the elements of $D$ are
inequivalent with respect to $\equiv^{C}_{B}$ and in particular this is true
of $\\{i_{\alpha}\mid\alpha<\varkappa\\}$. As $B\subseteq S_{\eta}$ we also
have that for every $\alpha<\beta<\varkappa$, $f^{C}_{i_{\alpha}}\restriction
B\leq f^{C}_{i_{\beta}}\restriction B$ everywhere.

So, for every $\alpha<\varkappa$ we can find $\tau_{\alpha}\in B$ and
$\zeta_{\alpha}\in C$ such that

$f^{C}_{i_{\alpha}}(\tau_{\alpha})=\zeta_{\alpha}<f^{C}_{i_{\alpha+1}}(\tau_{\alpha}).$

As $|B|<\rho$ and $|C|<\chi$, we have that $|B\times
C|<\rho\cdot\chi\leq\varkappa$. This means that for some
$(\tau^{*},\zeta^{*})\in B\times C$ we can find $\alpha<\beta<\varkappa$ such
that $\tau_{\alpha}=\tau^{*}=\tau_{\beta}$ and
$\zeta_{\alpha}=\zeta^{*}=\zeta_{\beta}$. But then

$f_{i_{\alpha}}^{C}(\tau^{*})=\zeta^{*}<f_{i_{\alpha+1}}^{C}(\tau^{*})\leq
f_{i_{\beta}}^{C}(\tau^{*})=\zeta^{*}.$

This cannot be. ∎

######  Corollary 4.3.

Let $\theta<\theta^{+}<\kappa$ be infinite cardinals and $\lambda$ an infinite
regular cardinal. Suppose that $\operatorname{m}(\kappa,\theta)<\lambda$. Then
there are no chains in $({}^{\kappa}\kappa,\ll_{\theta})$ of length $\lambda$.

###### Proof.

As
$\operatorname{m}^{-}(\kappa,\theta)\leq\operatorname{m}(\kappa,\theta)<\lambda$
by Lemma 2.3(iii), we can appeal to Theorem 4.2 with $\chi=\rho=\theta^{+}$
and $\vartheta=\theta$ to obtain the desired conclusion. ∎

We can compare this with the analogous corollary from [32, Theorem 5] where
instead of $\operatorname{m}(\kappa,\theta)<\lambda$ the slightly stronger
hypothesis of $\operatorname{cof}([\kappa]^{\theta})<\lambda$ would have been
used to obtain the same conclusion. It is also clear that proving this
corollary using Theorem 3.3 would require further assumptions.

However, glancing at Lemma 2.3 and the discussion following it, it is clear
that for the most important case of $\lambda=\kappa^{+}$, assuming the
consistency of enough large cardinals there are models of set theory where the
hypotheses of Corollary 4.3 may not hold even for very small $\kappa$ such as
$\aleph_{\omega}$. The next result, which proves Theorem B, remedies some of
these scenarios.

######  Corollary 4.4.

Let $\theta<\kappa$ be infinite cardinals where $\kappa$ is a limit cardinal
which is not a cardinal fixed point. Then there are no chains in
$({}^{\kappa}\kappa,\ll_{\theta})$ of length $\kappa^{+}$.

###### Proof.

Suppose that $\xi<\kappa$ is such that $\kappa=\aleph_{\xi}$. Let
$\vartheta\in(\theta,\kappa)$ be a regular cardinal such that $\vartheta>\xi$.
Then $\vartheta<\kappa<\vartheta^{+\vartheta}$. So by Lemma 2.3(vi) and Lemma
2.3(iii) we have that

$\kappa=\operatorname{m}(\kappa,\vartheta)=\operatorname{m}^{-}(\kappa,\vartheta)=\operatorname{m}(\kappa,\vartheta^{+},\kappa,\vartheta).$

Also, as $\vartheta>\theta$, by Lemma 2.3(i) we have that

$\kappa=\operatorname{m}(\kappa,\vartheta)=\operatorname{m}(\kappa,\vartheta^{+},\vartheta,\vartheta)=\operatorname{m}(\kappa,\vartheta^{+},\vartheta,\theta).$

So we appeal to Theorem 4.2 with $\chi=\rho=\vartheta^{+}$ to finish. ∎

While the previous two corollaries were focused on Question 1.7, the next
corollary focuses on the most general problem, and the one after, which proves
Theorem C, on Conjecture 1.8.

######  Corollary 4.5.

Let $\theta<\theta^{+}<\kappa\leq\mu$ be infinite cardinals. Suppose that

  1. (i)

$\kappa<\theta^{+\operatorname{cf}(\theta)}$;

  2. (ii)

$\mu<\theta^{+\operatorname{cf}(\kappa)}$.

Then there are no chains in $({}^{\kappa}\mu,\ll_{\theta})$ of length
$\mu^{+}$.

###### Proof.

By Lemma 2.3(vi) the hypotheses imply that
$\operatorname{m}(\kappa,\theta)=\kappa$ and
$\operatorname{m}(\mu,\theta^{+},\kappa,\theta)=\mu$ hold. So we apply Theorem
4.2 with $\vartheta=\theta$ and $\chi=\rho=\theta^{+}$ to finish. ∎

######  Corollary 4.6.

Let $\theta\leq\mu<\theta^{+(\theta^{++})}$ be infinite cardinals. Then there
are no chains in $({}^{\theta^{++}}\mu,\ll_{\theta})$ of length $\mu^{+}$.

###### Proof.

In case $\mu<\theta^{++}$ then we can appeal to Proposition 4.1. So, we can
assume that $\theta^{++}\leq\mu$. By Lemma 2.3(vi) we have that
$\operatorname{m}(\mu,\theta^{+},\theta^{++},\theta)=\mu$ and
$\operatorname{m}(\theta^{++},\theta^{+},\theta,\theta)=\theta^{++}$ holds. So
we apply Theorem 4.2 with $\vartheta=\theta$ and $\chi=\rho=\theta^{+}$ to
finish. ∎

##  5\. Acknowledgements

The debt to [32] should be clear to any reader who makes it to this point. My
interest in the results of Koszmider began when my teachers David Asperó and
Mirna Džamonja suggested reading [14] to start my doctoral studies. Some of
this research was done when I was a postdoctoral researcher at the Instituto
Tecnológico Autónomo de México. After listening to a talk on Theorem A in
February 2020, Assaf Rinot emphasised isolating the cardinals from Section 2.1
and focusing on the space $({}^{\kappa}\mu,<_{\theta})$ and also informed me
of Lemma 2.3. The emphasis on $({}^{\kappa}\mu,<_{\theta})$ makes it clear
that the results of Section 3 are more general than the results in [32]. This
article has benefited greatly from his suggestions, his notes, and his
interest. A conversation with Ido Feldman helped inspire the discovery of
Theorem 4.2. While working on the article at Bar-Ilan University I was
supported by a postdoctoral fellowship funded by the Israel Science Foundation
(grant agreement 2066/18).

## References

  * [1] Abraham, U., and Magidor, M. Cardinal arithmetic.  In Handbook of set theory. Vols. 1, 2, 3. Springer, Dordrecht, 2010, pp. 1149–1227.
  * [2] Bartoszyński, T., and Judah, H. Set theory.  A K Peters, Ltd., Wellesley, MA, 1995.  On the structure of the real line.
  * [3] Baumgartner, J. E. Almost-disjoint sets, the dense set problem and the partition calculus.  Ann. Math. Logic 9, 4 (1976), 401–439.
  * [4] Baumgartner, J. E., and Shelah, S. Remarks on superatomic Boolean algebras.  Ann. Pure Appl. Logic 33, 2 (1987), 109–129.
  * [5] Cummings, J., and Shelah, S. Cardinal invariants above the continuum.  Ann. Pure Appl. Logic 75, 3 (1995), 251–268.
  * [6] Erdős, P., and Hajnal, A. Unsolved and solved problems in set theory.  In Proceedings of the Tarski Symposium (Proc. Sympos. Pure Math., Vol. XXV, Univ. California, Berkeley, Calif., 1971) (1974), pp. 269–287.
  * [7] Fernandes, G., Moreno, M., and Rinot, A. Inclusion modulo nonstationary.  Monatsh. Math. 192, 4 (2020), 827–851.
  * [8] Galvin, F., and Hajnal, A. Inequalities for cardinal powers.  Ann. of Math. (2) 101 (1975), 491–498.
  * [9] Gitik, M., and Magidor, M. The singular cardinal hypothesis revisited.  In Set theory of the continuum (Berkeley, CA, 1989), vol. 26 of Math. Sci. Res. Inst. Publ. Springer, New York, 1992, pp. 243–279.
  * [10] Hechler, S. H. On the existence of certain cofinal subsets of ${}^{\omega}\omega$.  In Axiomatic set theory (Proc. Sympos. Pure Math., Vol. XIII, Part II, Univ. California, Los Angeles, Calif., 1967) (1974), pp. 155–173.
  * [11] Kanamori, A. The higher infinite, second ed.  Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2003.  Large cardinals in set theory from their beginnings.
  * [12] Khomskii, Y., Laguzzi, G., Löwe, B., and Sharankou, I. Questions on generalised Baire spaces.  MLQ Math. Log. Q. 62, 4-5 (2016), 439–456.
  * [13] Koszmider, P. On the existence of strong chains in $P(\omega_{1})/{\rm Fin}$.  J. Symbolic Logic 63, 3 (1998), 1055–1062.
  * [14] Koszmider, P. On strong chains of uncountable functions.  Israel J. Math. 118 (2000), 289–315.
  * [15] Koszmider, P. On constructions with 2-cardinals.  Arch. Math. Logic 56, 7-8 (2017), 849–876.
  * [16] Lambie-Hanson, C. A Galvin-Hajnal theorem for generalized cardinal characteristics, 2022\.
  * [17] Laver, R. Adding dominating functions mod finite.  Period. Math. Hungar. 35, 1-2 (1997), 35–41.
  * [18] Magidor, M. On the singular cardinals problem. II.  Ann. of Math. (2) 106, 3 (1977), 517–547.
  * [19] Matet, P. Towers and clubs.  Arch. Math. Logic 60, 6 (2021), 683–719.
  * [20] Mitchell, W. J. Notes on a proof of Koszmider, 2003.
  * [21] Neeman, I. Forcing with sequences of models of two types.  Notre Dame J. Form. Log. 55, 2 (2014), 265–298.
  * [22] Rinot, A. A topological reflection principle equivalent to Shelah’s strong hypothesis.  Proc. Amer. Math. Soc. 136, 12 (2008), 4413–4416.
  * [23] Rinot, A. On the ideal $J[\kappa]$.  Ann. Pure Appl. Logic 173, 2 (2022), Paper No. 103055, 13.
  * [24] Sauer, N. W., Woodrow, R. E., and Sands, B., Eds.  Finite and infinite combinatorics in sets and logic (1993), vol. 411 of NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences, Kluwer Academic Publishers Group, Dordrecht.
  * [25] Shelah, S. The singular cardinals problem: independence results.  In Surveys in set theory, vol. 87 of London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, 1983, pp. 116–134.
  * [26] Shelah, S. Advances in cardinal arithmetic.  In Finite and infinite combinatorics in sets and logic (Banff, AB, 1991), vol. 411 of NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci. Kluwer Acad. Publ., Dordrecht, 1993, pp. 355–383.
  * [27] Shelah, S. Cardinal arithmetic, vol. 29 of Oxford Logic Guides.  The Clarendon Press, Oxford University Press, New York, 1994.  Oxford Science Publications.
  * [28] Shelah, S. Further cardinal arithmetic.  Israel J. Math. 95 (1996), 61–114.
  * [29] Shelah, S. The generalized continuum hypothesis revisited.  Israel J. Math. 116 (2000), 285–321.
  * [30] Shelah, S. PCF and infinite free subsets in an algebra.  Arch. Math. Logic 41, 4 (2002), 321–359.
  * [31] Shelah, S. Middle diamond.  Arch. Math. Logic 44, 5 (2005), 527–560.
  * [32] Shelah, S. On long increasing chains modulo flat ideals.  MLQ Math. Log. Q. 56, 4 (2010), 397–399.
  * [33] Veličković, B., and Venturi, G. Proper forcing remastered.  In Appalachian set theory 2006–2012, vol. 406 of London Math. Soc. Lecture Note Ser. Cambridge Univ. Press, Cambridge, 2013, pp. 331–362.
  * [34] Zapletal, J. Strongly almost disjoint functions.  Israel J. Math. 97 (1997), 101–111.