# Learning Locomotion Controllers for Walking Using Deep FBSDE

Bolun Dai1, Virinchi Roy Surabhi1, Prashanth Krishnamurthy1, Farshad Khorrami1
1Control/Robotics Research Laboratory, Electrical & Computer Engineering
Department, Tandon School of Engineering (Polytechnic Institute), New York
University, Brooklyn, NY, 11201<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In this paper, we propose a deep forward-backward stochastic differential
equation (FBSDE) based control algorithm for locomotion tasks. We also include
state constraints in the FBSDE formulation to impose stable walking solutions
or other constraints that one may want to consider (e.g., energy). Our
approach utilizes a deep neural network (i.e., LSTM) to solve, in general,
high-dimensional Hamilton–Jacobi–Bellman (HJB) equation resulting from the
stated optimal control problem. As compared to traditional methods, our
proposed method provides a higher computational efficiency in real-time; thus
yielding higher frequency implementation of the closed-loop controllers. The
efficacy of our approach is shown on a linear inverted pendulum model (LIPM)
for walking. Even though we are deploying a simplified model of walking, the
methodology is applicable to generalized and complex models for walking and
other control/optimization tasks in robotic systems. Simulation studies have
been provided to show the effectiveness of the proposed methodology.

##  I Introduction

How to enable robots to perform locomotion tasks is an important problem in
robotics research given the wide applications of walking robots. Walking
robots are able to move without the existence of roads or other types of
infrastructures. Their legs makes it possible to move with small support
surfaces [1] making walking robots more appealing for tasks performed on
rugged terrains [2]. Also, movement of legged robots does not rely on the
existence of air or propellants, which makes it an ideal candidate for
extraterrestrial expeditions [3]. Additionally, the human-like figure and
motion [4] [5] makes it easier to integrate humanoids into our society.
However, given the complexity, the control of walking robots has been a
challenging task.

Traditionally, model predictive control (MPC) has been widely used in
locomotion tasks [6] [7] [8]. The authors in [9] proposed a complete solution
for walking on flat ground, which includes turning. The authors in [10] then
expanded on previous works to enable walking in 3D, e.g. walking up stairs. At
each time step, MPC-based methods rely on optimization solvers [11] to solve
for control at a given time considering the dynamics over a preview horizon.
This process can be computationally intensive especially for high dimensional
systems over long preview horizons.

To mitigate computational issues, deep learning based approaches are being
applied in locomotion tasks. Compared to the resources required for solving a
convex optimization problem, the computational cost is much less for one
forward pass through a neural network. Recently, deep reinforcement learning
has been widely applied to locomotion tasks. The role deep reinforcement
learning plays is versatile, it can be used in conjunction with a feedback
controller where the learned policy provides a reference state [12], or
provide set points to a motor PD controller [13]. However, deep reinforcement
learning methods require a well-designed-task-specific reward function, which
in the case of locomotion is hard to obtain. The reward functions in both [12]
and [13] look rather arbitrary and require exhaustive tuning to find the best
balance between different design objectives. A different line of deep learning
based approaches attempts to mimic the behavior of existing optimization-based
controllers in a supervised learning fashion [14]. However, this approach
requires access to existing optimization-based controllers or a dataset of
state-control pairs, which is not always available.

Locomotion problems are essentially optimal control problems. One method that
utilizes deep learning to solve optimal control problems is deep FBSDE. The
idea behind deep FBSDEs is to find a numerical approximation to the solution
of the HJB equation, which is the value function given with respect to a cost
function. Following the derivation in [15], the optimal control can then be
calculated as a function of the partial derivative of the value function with
respect to the state. We can formulate this problem as a FBSDE and solve it
using a neural network which has the benefit of resolving compounding-errors.
Such a method has gained traction recently. [15] first proposed the deep FBSDE
algorithm using LSTMs. On top of the vanilla LSTM-based FBSDE formulation,
[16] showed how to handle systems with control multiplicative noise and [17]
solved problems with unknown noise distribution. In our recent work [18], we
expanded deep FBSDEs to consider problems with state constraints. However,
these works only considered examples with continuous dynamics.

The present paper aims to expand the usage of deep FBSDE controllers to
locomotion tasks, which is a hybrid dynamical system. In Section II, the
walking model LIPM is introduced and the problem formulation is given. In
Section III, an outline of the deep FBSDE controller is provided. Section IV
shows the methodology for deep FBSDE controller to adapt to walking tasks, and
changes to the neural network architecture are highlighted. In Section V, we
demonstrate the efficacy of our approach on LIPM model, along with its state
constrained version, in simulation. We also compare the computation efficiency
of our method with CVX. Finally, in Section VI, the paper is concluded and a
brief discussion on extensions of this work is presented.

##  II Problem Formulation

In this section, we discuss key aspects of the LIPM walking problem. The LIPM,
under the assumption of no jumping and no large rotation movements in the
sagittal plane, is given as

$\mathbf{c}^{x,y}-\frac{c^{z}}{g^{z}}\ddot{\mathbf{c}}^{x,y}=\mathbf{p}^{x,y},$
(1)

where $\mathbf{c}^{x,y}=[c^{x}\ c^{y}]^{T}$ denotes the position of the center
of mass (CoM) in the $xy$-plane (transverse plane), $c^{z}$ is the height of
the CoM, $g^{z}$ is the vertical component of the gravitational acceleration,
$\ddot{\mathbf{c}}^{x,y}=[\ddot{\mathbf{c}}^{x}\ \ddot{\mathbf{c}}^{x}]^{T}$
denotes the acceleration of the CoM in the $xy$-plane and
$\mathbf{p}^{x,y}=[p^{x}\ p^{y}]^{T}$ denotes the position of the center of
pressure (CoP) in the $xy$-plane. If we treat the CoP location
$\mathbf{p}^{x,y}$ as the control input we can write the dynamical system as

$\ddot{\mathbf{c}}^{x,y}=\frac{g^{z}}{c^{z}}\mathbf{c}^{x,y}-\frac{g^{z}}{c^{z}}\mathbf{p}^{x,y},$
(2)

which has the form of $\dot{x}=Ax+Bu$. In matrix form, equation (2) can be
written as

$\dot{\bar{\mathbf{c}}}=\begin{bmatrix}\mathbf{0}_{2\times 2}&I_{2\times 2}\\\
g^{z}/c^{z}I_{2\times 2}&\mathbf{0}_{2\times
2}\end{bmatrix}\bar{\mathbf{c}}+\begin{bmatrix}\mathbf{0}_{2\times 2}\\\
g^{z}/c^{z}I_{2\times 2}\end{bmatrix}\mathbf{p}^{x,y},$ (3)

with $\bar{\mathbf{c}}=[c^{x}\ c^{y}\ \dot{c}^{x}\ \dot{c}^{y}]^{T}$.

The purpose of this work is to achieve stable walking behavior, thus the
phases when the robot starts from standing still and coming to a stop are not
considered. Starting from a CoM state $\bar{\mathbf{c}}_{0}=\xi$ that has an
initial velocity, we want to build a controller that is able to maintain
stable walking over an arbitrary long time period. We use the cost function

$\displaystyle\min_{\mathbf{p}_{i}^{x,y}}$
$\displaystyle\sum_{i=0}^{N-1}{\Big{[}q(\bar{\mathbf{c}_{i}})+r(\mathbf{p}_{i}^{x,y})\Big{]}}+g(\bar{\mathbf{c}}_{N})$
(4a)
$\displaystyle\bar{\mathbf{c}}_{i+1}=\bar{\mathbf{c}}_{i}+\dot{\bar{\mathbf{c}}}\Delta{t}$
(4b) $\displaystyle\bar{\mathbf{c}}_{0}=\xi$ (4c)
$\displaystyle-\frac{1}{2}l_{x}\leq p^{x}\leq\frac{1}{2}l_{x}$ (4d)
$\displaystyle-\frac{1}{2}l_{y}\leq p^{y}\leq\frac{1}{2}l_{y},$ (4e)

where $q(\bar{\mathbf{c}_{i}})$ is the state cost, $r(\mathbf{p}_{i}^{x,y})$
is the control cost, $g(\bar{\mathbf{c}}_{N})$ is the terminal state cost and
$l_{x}$ and $l_{y}$ denotes the length of the foot along the $x$, $y$
direction. The inequality constraints denotes the CoP has to be within the
support polygon.

##  III Deep FBSDE

Figure 1: Neural Network Architecture: the architecture here is for $N$
timesteps, the connection between $V^{n}$ and $x_{n}$ denotes applying control
actions, the weights are shared among each time step. Curve edged boxes
represents trainable parameters, sharp edged boxes represents intermediate
calculated values.

In this section, we outline the design of the deep FBSDE controller. For a
system with dynamics that includes disturbances, it can be described using a
stochastic differential equation (SDE),

$dx(t)=f(x(t),t)dt+G(x(t),t)u(t)dt+\Sigma(x(t),t)dw(t)$ (5)

with initial condition $x(0)=x_{0}$ and $w(t)\in\mathbb{R}^{\nu}$ being a
standard Brownian motion. The states are denoted by $x\in\mathbb{R}^{n}$, the
control input by $u\in\mathbb{R}^{m}$, and time by $0<t<T<\infty$. In (5),
$f:\mathbb{R}^{n}\times[0,T]\rightarrow\mathbb{R}^{n}$ represents the drift,
$G:\mathbb{R}^{n}\times[0,T]\rightarrow\mathbb{R}^{n\times m}$ represents the
control influence, and
$\Sigma:\mathbb{R}^{n}\times[0,T]\rightarrow\mathbb{R}^{n\times\nu}$
represents the diffusion (influence of the Brownian motion to the state). The
purpose of the deep FBSDE controller is to find $u(t)$ that minimizes an
objective function $J^{u}(x,t)\in\mathbb{R}^{+}$. The objective function is
denoted as

$J^{u}(x,t)=\mathbb{E}\Big{[}g(x(T))+\int_{t}^{T}\Big{(}q(x(s))+\frac{1}{2}u(s)^{T}Ru(s)\Big{)}ds\Big{]}$
(6)

where $g:\mathbb{R}^{n}\rightarrow\mathbb{R}^{+}$ is the terminal state cost,
$q:\mathbb{R}^{n}\rightarrow\mathbb{R}^{+}$ is the instantaneous state cost,
and the control cost matrix is $R\in\mathbb{R}^{m\times m}$, which is positive
definite. The value function $V(x,t)\in\mathbb{R}^{+}$ is defined as

$V(x,t):=\inf J^{u}(x,t)$ (7)

where the $\inf$ is computed over all control signals $u(.)$ over the time
interval $(t,T]$.

Following derivations in [18], the HJB equation is given as

$\displaystyle V_{t}(x,t)+\mathcal{L}V(x,t)+h(x,V_{x},t)$ (8a) $\displaystyle
V(x,T)=g(x).$ (8b)

The generator function $\mathcal{L}V(x,t)$ is defined as

$\mathcal{L}V=\frac{1}{2}\hbox{trace}(\Sigma\Sigma^{T}V_{xx})+f^{T}V_{x}$ (9)

with $V_{x}$ and $V_{xx}$ representing the first and second order partial
derivative of $V$ w.r.t. $x$, respectively. The Hamiltonian is defined as

$h(x,V_{x},t)\\!=\\!\inf_{u\in\mathcal{U}}\left(q(x)+(G(x,t)u)^{T}V_{x}(x,t)+\frac{1}{2}u^{T}Ru\right),$
(10)

with $\mathcal{U}$ being the admissible set of controls. By taking the minimum
of the Hamiltonian we can analytically compute the optimal control as a
function of $V_{x}$, the partial derivative of the value function with respect
to the state,

$u^{*}(x,t)=-R^{-1}G^{T}(x,t)V_{x}(x,t).$ (11)

We can solve for (11) using a deep FBSDE

$\displaystyle dy(t)=$ $\displaystyle\
\Big{(}-h\big{(}x(t),\Sigma^{T}(x(t),t)V_{x}(x(t),t;\theta),t\big{)}$
$\displaystyle+V_{x}^{T}\big{(}x(t),t;\theta\big{)}\Sigma\big{(}x(t),t\big{)}\Gamma\big{(}x(t),t\big{)}u\big{(}x(t),t\big{)}\Big{)}dt$
$\displaystyle+V_{x}^{T}\big{(}x(t),t;\theta\big{)}\Sigma\big{(}x(t),t\big{)}dw(t)$
(12a) $\displaystyle dx(t)=$ $\displaystyle\
\Big{(}f\big{(}x(t),t\big{)}+\Sigma\big{(}x(t),t\big{)}\Gamma\big{(}x(t),t)u(x(t),t\big{)}\Big{)}dt$
$\displaystyle+\Sigma\big{(}x(t),t\big{)}dw(t)$ (12b) $\displaystyle u(t)=$
$\displaystyle\
-R^{-1}\Gamma^{T}\big{(}x(t),t\big{)}\Sigma^{T}\big{(}x(t),t\big{)}V_{x}(x(t),t;\theta)$
(12c) $\displaystyle y(0)=$ $\displaystyle\ V\big{(}\phi,x_{0}\big{)}$ (12d)
$\displaystyle x(0)=$ $\displaystyle\ x_{0},$ (12e)

where $y(t)=V(x_{t})=V^{t}$ and $G(x(t),t)=\Sigma(x(t),t)\Gamma(x(t),t)$,
$\Gamma:\mathbb{R}^{n}\times[0,T]\rightarrow\mathbb{R}^{\nu\times m}$. This
shows the range of $G$ is a subset of the range of $\Sigma$, which excludes
the case of a channel containing control input without noise. The neural
network that estimates $V_{x}$ at each time step is parameterized by $\theta$
and the neural network that estimates the value function at the initial time
step $V^{0}$ is parameterized by $\phi$. The details of the neural network
architecture will be explained in the following sections.

##  IV Controller Design

Unlike canonical control examples shown in [18], the nature of locomotion
tasks creates a hybrid dynamical system, where the dynamics is discontinuous
between two steps. Additionally, stable locomotion behavior usually creates a
cyclic movement, where a region of attraction exists for the terminal state at
each step (will discuss in detail in the next section). Due to these unique
conditions, instead of training the controller over multiple steps, the
learning problem will be “normalized” if we only focus on one single step.

Using this intuition, the learned controller will be only trained using
experience from one foot step. Experiences obtained from one foot step can
have low variance, thus noise is added to the initial state of each step in
addition to the disturbances injected to state dynamics. Therefore, instead of
having a single initial state as in [18], the initial state will be sampled
from a distribution. To accommodate this change, the initial value function is
now a function of the initial state. For LSTMs, the initial hidden states
$H_{0}$, parameterized by trainable weights, also takes the initial state as
input. The overall neural network architecture is shown in Figure 1. The loss
function is defined as

$L=\frac{1}{M}\sum_{m=1}^{M}\Big{[}\|g(x_{N}^{m})-y_{N}^{m}\|_{2}^{2}+\lambda_{1}\|x_{0}^{m}-x_{N}^{m}\|_{2}^{2}\Big{]}+\lambda_{2}\|\theta\|_{2}^{2},$
(13)

where $M$ denotes the batch size, and $\lambda_{1}$ and $\lambda_{2}$
determines the weight of the stability enforcement term and the regularization
term, respectively. Compared to [18], the additional term in the loss function
is designed to encourage a cyclic motion.

##  V Experiment

Figure 2: Training Results: these two figures demonstrates the stability of
the learned policy. The “S” on the $x$-axis represents the start of each foot
step and “E” represents the end of each foot step. In both of the plots there
are 64 pairs. The value of each line on the “S” side is the velocity of the
CoM at the start of each foot step, the value on the “E” side is the velocity
of the CoM at the end of each foot step. The thick dashed line in the middle
is a nominal velocity that serves as a target during training. Since $x$ and
$y$ motion are decoupled only results of the $x$ direction are shown. Figure
3: Workflow of walking multiple steps: this figure illustrates how to used the
learned deep FBSDE controller trained on a single footstep to walk multiple
steps. The round edge boxes denotes trainable components, while the sharp edge
boxes denotes intermediate values. The dashed arrow in the middle denotes the
change in coordinate systems.

In this section, we show the efficacy of our approach on the LIPM model, with
both noiseless and noise injected state dynamics. First, we introduce the
setup of the experiments, then the training results are shown. Second, we show
this learned policy trained on a single step is able to generalize to stable
walking over multiple steps. Third, we demonstrate the capability of our
method on handling state constraints. Finally, we compare the computation
efficiency between our approach and traditional optimization based methods.
All experiments are implemented using Tensorflow.

###  V-A Experiment Setup

To align the formulation of (3) and (5) we have

$\displaystyle f$ $\displaystyle=\begin{bmatrix}\mathbf{0}_{2\times
2}&I_{2\times 2}\\\ g^{z}/c^{z}I_{2\times 2}&\mathbf{0}_{2\times
2}\end{bmatrix}$ (14a) $\displaystyle g$
$\displaystyle=\begin{bmatrix}\mathbf{0}_{2\times 2}\\\ g^{z}/c^{z}I_{2\times
2}\end{bmatrix}$ (14b) $\displaystyle x$ $\displaystyle=\bar{\mathbf{c}}.$
(14c)

Disturbances are only injected to the acceleration terms, thus
$\Sigma=\mathrm{diag}[0\ 0\ 1\ 1]$. The CoM height $c^{z}$ is fixed at $1m$
and $g^{z}=-9.81m/s^{2}$. We use quadratic costs for the state cost, controls
cost, and terminal cost defined in (4)

$\displaystyle q(\bar{\mathbf{c}_{i}})$
$\displaystyle=\mathbf{c}_{i}^{T}Q_{i}\mathbf{c}_{i}$ (15a) $\displaystyle
r(\mathbf{p}_{i}^{x,y})$
$\displaystyle=(\mathbf{p}_{i}^{x,y})^{T}R_{i}\mathbf{p}_{i}^{x,y}$ (15b)
$\displaystyle g(\bar{\mathbf{c}}_{N})$
$\displaystyle=\bar{\mathbf{c}}_{N}^{T}Q_{N}\bar{\mathbf{c}}_{N},$ (15c)

where

$\displaystyle Q_{i}$ $\displaystyle=\mathrm{diag}[1\ 1\ 1\ 1]$ (16a)
$\displaystyle R_{i}$ $\displaystyle=\mathrm{diag}[100\ 100]$ (16b)
$\displaystyle Q_{N}$ $\displaystyle=\mathrm{diag}[100\ 100\ 100\ 100].$ (16c)

The robot has a foot with the size of $0.15m\times 0.15m$. The foot step
position are pre-planned to walk along the $x=y$ line. The duration of each
footstep is $0.7s$, the step size is $0.8\sqrt{2}m$, which corresponds to
$0.8m$ in both the positive $x$ and $y$ axis. When simulating the state
dynamics we use a time step of $0.02s$. In training, we use a learning rate of
1e-3 over 10,000 iterations. To enhance the robustness of the learned policy,
a uniformly sampled disturbance is applied to the initial state on both
systems with noiseless and noisy dynamics.

###  V-B Training Results

To analyze the quality of learned policies, we treat the relationship between
the velocity of the initial state of a foot step $v_{\mathrm{S}}$ and the
velocity of the terminal state $v_{\mathrm{E}}$ as a mapping. Stable walking
behavior can be observed when this mapping maps an arbitrary $v_{\mathrm{S}}$
that is in the vicinity of the nominal velocity to a fixed $v_{\mathrm{E}}$ or
to a small $v_{\mathrm{E}}$ interval. Physically, this is equivalent to
showing under disturbances, the system is able to adjust the subsequent
control actions to drag the CoM velocity back to a desired range. The mapping
for both the noiseless and noisy systems are shown in Figure 2. For the
noiseless system, a clear region of attraction can be seen: the $v_{S}$’s are
map to a very small interval surrounding the nominal velocity. Though not
equal to the nominal velocity, this clearly shows robustness of the learned
policy. For the noisy system, such a convergence pattern is also present,
though larger than the noiseless case, the $v_{S}$’s are also mapped to a
small interval around the nominal velocity.

###  V-C Walking

Figure 4: Walking for 20 steps using the learned policy: the top three figures
shows the evolution of the CoM and CoP over 20 steps using a noiseless system,
the bottom three shows the evolution of its noisy counterpart. The CoP is
clipped between $[-0.15,0.15]$. All measurements are performed inside a local
coordinate system that is attached to the center of the foot.

In this section, we demonstrate how policy trained on a single foot step can
be utilized for walking over multiple steps. The learned policy uses states
defined in a local frame, where the origin is at the center of the foot, and
its $x$ and $y$ axis are aligned with the global frame. At the transition
between two foot steps, the states are updated to be measured in the local
body frame of the next foot step. When updating the states, the CoM velocities
stays fixed (velocities are the same when observing from static frames).
However, we can choose how big a step length to take, which changes the CoM
position in the body frame. We have tested using a fixed step size. However,
for the learned policy, especially under the presence of disturbances, this
may cause issues. If the velocity of the terminal state is slower than
desired, a fixed step size might correspond to talking too large of a step.
Instead, we made the initial position of the CoM of each step a fixed value
$(\bar{x}_{0},\bar{y}_{0})$, which corresponds to a dynamic step length. The
update rule is

$\begin{bmatrix}x_{N}&y_{N}&\dot{x}_{N}&\dot{y}_{N}\end{bmatrix}^{T}\rightarrow\begin{bmatrix}\bar{x}_{0},\bar{y}_{0}&\dot{x}_{N}&\dot{y}_{N}\end{bmatrix}^{T}.$
(17)

The overall workflow is shown in Figure 3. Using the proposed algorithm, the
walking motion is displayed in Figure 4. As can be seen, for both the
noiseless and noisy system a cyclic behavior can be maintained over 20 steps.
We tested up to 40 steps, and no deterioration is shown, due to limit space
only results for 20 steps are shown.

###  V-D State Constraint

Figure 5: Application of state constraints: this figure compares the
performance of the controller under velocity constraints. The darker blue and
green trajectories are sampled trajectories among 64 consecutive steps. The
light blue and green regions shows the bounds of maximum and minimum values of
all the 64 trajectories at each time step. The constraint boundary is shown in
black dashed lines.

Following the formulation in [18], a state constraint is applied to the CoM
velocity for it to be faster than $1.0$m/s. We simulated our controller over
64 foot steps on a noisy model. The results for both the constrained and
unconstrained setup are shown in Figure 5. We can see that for the
unconstrained case every instance goes beyond the constraint boundary. For the
constrained case, the constraint boundary is respected over all steps. Even
though the construct of this constraint is rather artificial, it shows the
capability of our method in handling state constraints.

###  V-E Computation Efficiency Comparison

Figure 6: Computation Efficiency Comparison: 420 instances of control
computation are sampled and the difference in computation time is displayed.
In both cases, a 4 dimension state is used, the CVX solution used a preview
horizon of 60 time steps. The targeted time step size is $0.02$s.

In this section, we compare the computation efficiency of our approach and of
using an optimization solver, in this case CVX. We compare the computation
time at each time step for obtaining a control action. The comparison is shown
in Figure 6. It can be seen that our proposed method is on average 6.67 times
faster and has less variance than CVX. For tasks with higher state dimensions
and requires longer preview horizon this computation acceleration will be more
significant.

##  VI Conclusion

In this paper, We consider the walking problem using a simplified model. The
locomotion problem of a LIPM model is solved using a deep FBSDE controller.
The controller is trained on walking over a single foot step and a method is
proposed to use this learned controller to generalize to walking over multiple
steps. The efficacy of our approach is demonstrated in simulation on both
noiseless and noisy systems. Additionally, we showed our proposed method is
able to handle state constraints and is computationally much faster than
optimization based methods. Potential future directions include extending to
more complex models and adaptation on real hardware and its application to a
full biped model.

## References

  * [1] Q. Nguyen, A. Hereid, J. W. Grizzle, A. D. Ames, and K. Sreenath, “3d dynamic walking on stepping stones with control barrier functions,” in _in Proceeding of 2016 IEEE 55th Conference on Decision and Control (CDC)_ , 2016, pp. 827–834.
  * [2] M. Zucker, J. Andrew Bagnell, C. G. Atkeson, and J. Kuffner, “An optimization approach to rough terrain locomotion,” in _in Proceedings of 2010 IEEE International Conference on Robotics and Automation (ICRA)_ , 2010, pp. 3589–3595.
  * [3] A. Omer, K. Hashimoto, H.-O. Lim, and A. Takanishi, “Study of bipedal robot walking motion in low gravity: Investigation and analysis,” _International Journal of Advanced Robotic Systems_ , vol. 11, no. 9, p. 139, 2014.
  * [4] P. Azad, T. Asfour, and R. Dillmann, “Toward an unified representation for imitation of human motion on humanoids,” in _Proceedings 2007 IEEE International Conference on Robotics and Automation_ , 2007, pp. 2558–2563.
  * [5] T. Asfour and R. Dillmann, “Human-like motion of a humanoid robot arm based on a closed-form solution of the inverse kinematics problem,” in _Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , vol. 2, 2003, pp. 1407–1412 vol.2.
  * [6] J. Koenemann, A. Del Prete, Y. Tassa, E. Todorov, O. Stasse, M. Bennewitz, and N. Mansard, “Whole-body model-predictive control applied to the hrp-2 humanoid,” in _in Proceedings of 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2015, pp. 3346–3351.
  * [7] M. Naveau, M. Kudruss, O. Stasse, C. Kirches, K. Mombaur, and P. Souères, “A reactive walking pattern generator based on nonlinear model predictive control,” _IEEE Robotics and Automation Letters_ , vol. 2, no. 1, pp. 10–17, 2017.
  * [8] S. Bäuerle, L. Kaul, and T. Asfour, “Linear contact modeling and stochastic parameter optimization for lqr-based whole-body push recovery,” in _in Proceedings of 2018 IEEE-RAS 18th International Conference on Humanoid Robots (Humanoids)_ , 2018, pp. 224–231.
  * [9] A. Herdt, N. Perrin, and P. Wieber, “Walking without thinking about it,” in _in Proceedings of 2010 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2010, pp. 190–195.
  * [10] C. Brasseur, A. Sherikov, C. Collette, D. Dimitrov, and P. Wieber, “A robust linear mpc approach to online generation of 3d biped walking motion,” in _in Proceedings of 2015 IEEE-RAS 15th International Conference on Humanoid Robots (Humanoids)_ , 2015, pp. 595–601.
  * [11] M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex programming, version 2.1,” 2014.
  * [12] T. Li, H. Geyer, C. G. Atkeson, and A. Rai, “Using deep reinforcement learning to learn high-level policies on the atrias biped,” in _in Proceedings of 2019 International Conference on Robotics and Automation (ICRA)_ , 2019, pp. 263–269.
  * [13] J. Siekmann, S. Valluri, J. Dao, L. Bermillo, H. Duan, A. Fern, and J. Hurst, “Learning memory-based control for human-scale bipedal locomotion,” in _Proceedings of Robotics: Science and Systems XVI (RSS), Virtual, July 12-16, 2020_.
  * [14] J. Viereck and L. Righetti, “Learning a centroidal motion planner for legged locomotion,” _CoRR_ , vol. abs/2011.02818, 2020.
  * [15] Z. Wang, M. Pereira, and E. A. Theodorou, “Learning deep stochastic optimal control policies using forward-backward SDEs,” in _Proceedings of Robotics: Science and Systems XV (RSS), Freiburg im Breisgau, Germany, June 22-26, 2019_.
  * [16] Z. Wang, M. A. Pereira, and E. A. Theodorou, “Deep 2FBSDEs for systems with control multiplicative noise,” _CoRR_ , vol. abs/1906.04762, 2019.
  * [17] Z. Wang, K. Lee, M. A. Pereira, I. Exarchos, and E. A. Theodorou, “Deep forward-backward sdes for min-max control,” in _Proccedings of 58th IEEE Conference on Decision and Control (CDC), Nice, France, December 11-13, 2019_ , pp. 6807–6814.
  * [18] B. Dai, P. Krishnamurthy, A. Papanicolaou, and F. Khorrami, “State constrained stochastic optimal control using lstms,” in _Proceedings of the American Control Conference (ACC), New Orleans, USA, May 26-28, 2021_.


# The Shape of Compact Covers

Ziqin Feng and Paul Gartside

(December 2023)

###### Abstract

For a space $X$ let $\mathcal{K}(X)$ be the set of compact subsets of $X$
ordered by inclusion. A map $\phi:\mathcal{K}(X)\to\mathcal{K}(Y)$ is a
relative Tukey quotient if it carries compact covers to compact covers. When
there is such a Tukey quotient write
$(X,\mathcal{K}(X))\geq_{T}(Y,\mathcal{K}(Y))$, and write
$(X,\mathcal{K}(X))=_{T}(Y,\mathcal{K}(Y))$ if
$(X,\mathcal{K}(X))\geq_{T}(Y,\mathcal{K}(Y))$ and vice versa.

We investigate the initial structure of pairs $(X,\mathcal{K}(X))$ under the
relative Tukey order, focussing on the case of separable metrizable spaces.
Connections are made to Menger spaces.

Applications are given demonstrating the diversity of free topological groups,
and related free objects, over separable metrizable spaces. It is shown a
topological group $G$ has the countable chain condition if it is either
$\sigma$-pseudocompact or for some separable metrizable $M$, we have
$\mathcal{K}(M)\geq_{T}(G,\mathcal{K}(G))$.

Keywords: Tukey order, compact covers, separable metrizable space.

MSC Classification: 03E04, 06A07, 22A05, 54D30, 54D45, 54E35, 54H11.

##  1 Introduction

The purpose of this paper is to uncover the possible ‘shapes’ of compact
covers of topological spaces, in particular separable metrizable spaces.
Applications are made to distinguish free topological groups of separable
metrizable spaces, and to show that a wide class of topological groups have
the countable chain condition (ccc), including those with a compact cover with
the same ‘shape’ as that of a separable metrizable space.

The main technical tool - which makes precise the notion of ‘shape’ of a
compact cover - is that of the relative Tukey order and equivalence. This line
of thought continues work of the authors and others on the Tukey structure of
directed sets of the form $\mathcal{K}(X)$, which is the set of compact
subsets of a space $X$ ordered by inclusion [9, 10]. It also encompasses work,
arising from functional analysis, studying spaces with a ‘$P$-ordered compact
cover’ (see the survey [5]).

Let $P$ be a directed set, and $P^{\prime}$ any subset. A subset $C$ of $P$ is
_cofinal_ for $P^{\prime}$ (in $P$) if for every $p^{\prime}\in P^{\prime}$
there is $c$ from $C$ such that $c\geq p^{\prime}$. Naturally we abbreviate
$(P,P)$ by $P$. For a space $X$ we have natural pairs $(X,\mathcal{K}(X))$ and
$(\mathcal{F}(X),\mathcal{K}(X))$, where $\mathcal{F}(X)$ is the set of all
finite subsets of $X$ (also denoted $[X]^{<\omega}$) and (abusing notation)
the ‘$X$’ in $(X,\mathcal{K}(X))$ means the singletons of $X$. Observe that
the cofinal sets for $X$ in $\mathcal{K}(X)$ are precisely the compact covers
of $X$. To compare two pairs, say $(P^{\prime},P)$ and $(Q^{\prime},Q)$ we
write $(P^{\prime},P)\geq_{T}(Q^{\prime},Q)$, and say ‘$(P^{\prime},P)$ Tukey
quotients to $(Q^{\prime},Q)$’ if and only if there is a map (called a
relative Tukey quotient) $\phi:P\to Q$ which takes subsets of $P$ cofinal for
$P^{\prime}$ to subsets of $Q$ cofinal for $Q^{\prime}$. If
$(P^{\prime},P)\geq_{T}(Q^{\prime},Q)$ and
$(Q^{\prime},Q)\geq_{T}(P^{\prime},P)$ then the pairs are said to be _Tukey
equivalent_ , denoted $(P^{\prime},P)=_{T}(Q^{\prime},Q)$.

Observe that a space $X$ is compact if and only if
$(X,\mathcal{K}(X))=_{T}\mathbf{1}$, and is $\sigma$-compact but not compact
if and only if $(X,\mathcal{K}(X))=_{T}\omega$. Further a space $X$ has a
$P$-ordered compact cover if and only if $P\geq_{T}(X,\mathcal{K}(X))$.

We start in Section 2 by determining when each of $(X,\mathcal{K}(X))$,
$(\mathcal{F}(X),\mathcal{K}(X))$ and $\mathcal{K}(X)$ does, or does not,
Tukey quotient to $\omega$. In our case of particular interest, separable
metrizable spaces, it turns out that each of them does not Tukey quotient to
$\omega$ precisely when the space is compact.

We continue in Section 3 by uncovering the initial structure of the Tukey
order on $(M,\mathcal{K}(M))$’s and $(\mathcal{F}(M),\mathcal{K}(M))$’s where
$M$ is separable metrizable. Actually the first few steps are known, see [9,
Theorem 3.4]. Denote by $(\mathcal{M},\mathcal{K}(\mathcal{M}))$ all pairs
$(M,\mathcal{K}(M))$, and by
$(\mathcal{F}(\mathcal{M}),\mathcal{K}(\mathcal{M}))$ all pairs
$(\mathcal{F}(M),\mathcal{K}(M))$, both ordered by the Tukey order.

Then the initial structure of $(\mathcal{M},\mathcal{K}(\mathcal{M}))$ starts:
(1) the minimum Tukey equivalence class in
$(\mathcal{M},\mathcal{K}(\mathcal{M}))$ is
$[(\mathbf{1},\mathcal{K}(\mathbf{1}))]_{T}$, and $(M,\mathcal{K}(M))$ is in
this class if and only if $M$ is compact; (2) it has a unique successor,
$[(\omega,\mathcal{K}(\omega))]_{T}$ , which consists of all
$(M,\mathcal{K}(M))$ where M is $\sigma$-compact but not compact; and (3) this
has
$[(\omega^{\omega},\mathcal{K}(\omega^{\omega}))]_{T}=\\{(M,\mathcal{K}(M)):M$
is analytic but not $\sigma$-compact$\\}$ as a successor. The initial
structure of $(\mathcal{F}(\mathcal{M}),\mathcal{K}(\mathcal{M}))$ starts
identically.

Now the questions are: (1) what are the $(M,\mathcal{K}(M))$ Tukey-above
$(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$? and (2) are there any
$(M,\mathcal{K}(M))$ strictly Tukey-above $(\omega,\mathcal{K}(\omega))$ but
_not_ above $(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$? At this point
Menger spaces enter the discussion. A space is _Menger_ if for every sequence
of open covers, $(\mathcal{U}_{n})_{n}$, one can select finite
$\mathcal{V}_{n}\subseteq\mathcal{U}_{n}$ so that their union,
$\bigcup_{n}\mathcal{V}_{n}$, cover. A space is _strong Menger_ if every
finite power is Menger. Clearly, $\sigma$-compact spaces are strong Menger,
but there are, in ZFC, non-$\sigma$-compact strong Menger subsets of the
reals. Then Theorem 3.4 says, for a separable metrizable $M$, that
$(M,\mathcal{K}(M))\not\geq_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$
precisely when $M$ is Menger, and
$(\mathcal{F}(M),\mathcal{K}(M))\not\geq_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$
if and only if $M$ is strong Menger. This is conceptually an illuminating
result. The Menger property was isolated in an (unsuccessful) attempt to
characterize $\sigma$-compact spaces in terms of a covering property. Our
characterization of separable metrizable Menger spaces manages to connect them
back to compact covers. Theorem 3.7 says that, consistently at least, there
are many distinct Tukey classes of $(M,\mathcal{K}(M))$ and
$(\mathcal{F}(M),\mathcal{K}(M))$ where $M$ is strong Menger. It is not clear
whether $(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$ has any successors.
One candidate (guided by the authors results for $\mathcal{K}(M)$’s) is
$(\mathcal{K}(\mathbb{Q}),\mathcal{K}(\mathcal{K}(\mathbb{Q}))$. We obtain
partial results on what pairs $(M,\mathcal{K}(M))$ lie Tukey above, below or
are incomparable with
$(\mathcal{K}(\mathbb{Q}),\mathcal{K}(\mathcal{K}(\mathbb{Q}))$.

In Section 4 we turn to applications. First we connect the Tukey structure of
compact covers of a space $X$ (specifically,
$(\mathcal{F}(X),\mathcal{K}(X))$, which helps explain our interest in this
pair) with those of its free topological group, $F(X)$, and related free
algebraic objects. This allows us to show that there is a
$2^{\mathfrak{c}}$-sized family of separable metrizable spaces whose free
topological groups (et cetera) are all pairwise non homeomorphic; and,
consistently, large families of strong Menger separable metrizable spaces with
pairwise non homeomorphic free topological groups. Second we prove a result
implying that $\sigma$-pseudocompact topological groups and topological groups
with a $\mathcal{K}(M)$-ordered compact cover are ccc, generalizing results of
Tkachenko and Uspenskii.

##  2 Core Results on Relative Tukey Order

For a general overview of relative Tukey quotients the reader is referred to
[9]. If $\phi$ is a map from $P$ to $Q$ which is order-preserving and
$\phi(P^{\prime})$ is cofinal for $Q^{\prime}$ in $Q$ then it is a relative
Tukey quotient. Conversely, provided $Q$ is Dedekind complete, then if
$(P^{\prime},P)\geq_{T}(Q^{\prime},Q)$ then there is a $\phi$ a map from $P$
to $Q$ which is order-preserving and $\phi(P^{\prime})$ is cofinal for
$Q^{\prime}$ in $Q$. We note that $\mathcal{K}(X)$ is Dedekind complete. Thus
we may, and usually do, assume any given Tukey quotient is order-preserving.
This justifies our claim above that a space $X$ has a ‘$P$-ordered compact
cover’, which means there is a compact cover $\\{K_{p}:p\in P\\}$ such that
$K_{p}\subseteq K_{p^{\prime}}$ when $p\leq p^{\prime}$, if and only if
$P\geq_{T}(X,\mathcal{K}(X))$. Also note that, as $P$ is directed,
$P\geq_{T}(X,\mathcal{K}(X))$ if and only if
$P\geq_{T}(\mathcal{F}(X),\mathcal{K}(X))$.

We record some basic Tukey equivalences. When computing Tukey order relations
we will replace, for example, $(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$
with $\omega^{\omega}$, without further comment.

######  Lemma 2.1.

(1) $(\omega,[\omega]^{<\omega})=_{T}[\omega]^{<\omega}=_{T}\omega$, and (2)
$(\omega^{\omega},\mathcal{K}(\omega^{\omega}))=_{T}(\mathcal{F}(\omega^{\omega},)\mathcal{K}(\omega^{\omega}))=_{T}\omega^{\omega}$.

###  2.1 Relative $k$-Calibres

The purpose of the next two results is to determine when one of our pairs must
Tukey quotient to a countably infinite pair. The non-existence of such a
quotient is connected to the space being almost compact. This is key to
eliminating ‘$\times\omega$’ factors in later Tukey calculations.

A space $X$ is _countably compact_ if every countable open cover has a finite
subcover, or equivalently if every closed discrete subset is finite. A space
$X$ is _totally countably compact_ if for every sequence
$(x_{n})_{n\in\omega}$ on $X$ there is an infinite $A\subseteq\omega$ such
that $\overline{\\{x_{n}:n\in A\\}}$ is compact. We introduce a strengthening
of total countable compactness as follows. A space $X$ is _totally countably
compact for finite sets_ if for every sequence $(F_{n})_{n\in\omega}$ of
finite subsets of $X$ there is an infinite $A\subseteq\omega$ such that
$\overline{\bigcup\\{F_{n}:n\in A\\}}$ is compact. A space $X$ is _$\omega$
-bounded_ if every countable subset has compact closure.

Clearly $\omega$-bounded implies totally countably compact for finite sets,
which implies totally countably compact, which, in turn, implies countably
compact.

######  Problem 2.2.

(1) Find an example of a space which is totally countably compact for finite
sets but not $\omega$-bounded.

(2) Find an example of a space which is totally countably compact but not
totally countably compact for finite sets.

Recall that a directed set $P$ is countably directed (every countable subset
has an upper bound) if and only if $P\not\geq_{T}\omega$.

######  Proposition 2.3.

Let $X$ be a space. Then:

(1) $X$ is totally countably compact if and only if
$(X,\mathcal{K}(X))\not\geq_{T}[\omega]^{<\omega}$,

(2) $X$ is totally countably compact for finite sets

if and only if
$(\mathcal{F}(X),\mathcal{K}(X))\not\geq_{T}[\omega]^{<\omega}$, and

(3) $X$ is $\omega$-bounded if and only if

there is a directed set $P$ such that $P\geq_{T}(X,\mathcal{K}(X))$ and
$P\not\geq_{T}\omega$.

###### Proof.

We prove (2). The argument for (1) is similar and simpler.

Suppose, first, that $X$ is not totally countably compact for finite sets. So
there is a sequence $(F_{i})_{i\in\omega}$ of finite subsets such that for
every infinite $A\subseteq\omega$ we have $\overline{\bigcup\\{F_{n}:n\in
A\\}}$ not compact. This is the same as saying that for every compact subset
$K$ of $X$, for only finitely many $n$ do we have $F_{n}\subseteq K$. Define
$\phi:\mathcal{K}(X)\to[\omega]^{<\omega}$ by
$\phi(K)=\\{n\in\omega:F_{n}\subseteq K\\}$. This is well-defined and order-
preserving. For each $n$ in $\omega$, clearly $F_{n}$ is compact and
$n\in\phi(F_{n})$. As $\mathcal{F}(X)$ is directed it follows that the image
of $\phi$ is cofinal in $[\omega]^{<\omega}$. In other words, $\phi$ is a
relative Tukey quotient of $(\mathcal{F}(X),\mathcal{K}(X))$ to
$[\omega]^{<\omega}$.

Now suppose we are given $\phi$ a relative Tukey quotient of
$(\mathcal{F}(X),\mathcal{K}(X))$ to $[\omega]^{<\omega}$. We can assume
$\phi$ is order-preserving and has image cofinal for $\mathcal{F}(X)$ in
$\mathcal{K}(X)$. In particular, for each $n$ in $\omega$ there is a finite
$F_{n}$ such that $\phi(F_{n})\supseteq\\{n\\}$. This gives a sequence
$(F_{n})_{n\in\omega}$ of finite subsets of $X$. It witnesses that $X$ is not
totally countably compact for finite sets. To see this, take any infinite
$A\subseteq\omega$. If $K=\overline{\bigcup\\{F_{n}:n\in A\\}}$ were compact
then, as $F_{n}\subseteq K$ for every $n$ in $A$, $\phi(K)$ would contain the
infinite set set $A$, contradicting $\phi$ mapping into the finite subsets of
$\omega$. Thus $\overline{\bigcup\\{F_{n}:n\in A\\}}$ is not compact, as
required.

Now for (3). Suppose $X$ is $\omega$-bounded. Then $P=\\{\overline{C}:C$ is
countable$\\}$ is a countably directed (by inclusion) compact cover.
Conversely, suppose $\mathcal{K}=\\{K_{p}:p\in P\\}$ is a $P$-ordered compact
cover of $X$ where $P\not\geq_{T}\omega$. Then $P$ is countably directed. Take
any countable subset $C$ of $X$, for each $x$ in $C$ pick $p_{x}$ such that
$x\in K_{p_{x}}$. Then $\\{p_{x}:x\in C\\}$ has an upper bound, say
$p_{\infty}$, and $C\subseteq K_{p_{\infty}}$, which is compact. ∎

###  2.2 Products, Powers and Complements

We collect here useful facts concerning products, powers and complements of
Tukey pairs $(X,\mathcal{K}(X))$ and $(\mathcal{F}(X),\mathcal{K}(X))$. Proofs
are largely left to the reader. These will be used, mostly without further
comment, in the sequel.

######  Lemma 2.4.

For any spaces $X$ and $Y$:

(1) $(X\times Y,\mathcal{K}(X\times
Y))=_{T}(X,\mathcal{K}(X))\times(Y,\mathcal{K}(Y))$ and $(\mathcal{F}(X\times
Y),\mathcal{K}(X\times
Y))=_{T}(\mathcal{F}(X),\mathcal{K}(X))\times(\mathcal{F}(Y),\mathcal{K}(Y))$,

(2)
$(\mathcal{F}(X),\mathcal{K}(X))=_{T}(\mathcal{F}(X),\mathcal{K}(X))\times(\mathcal{F}(X),\mathcal{K}(X))$,
and

(3) $(X,\mathcal{K}(X))=_{T}(X\oplus X,\mathcal{K}(X\oplus X))$.

From claim (1) we have in particular that
$(X^{2},\mathcal{K}(X^{2}))=_{T}(X,\mathcal{K}(X))^{2}$. In contrast to claim
(2) we can not add Tukey equivalence to $(X,\mathcal{K}(X))$, see Remark 3.6.

######  Example 2.5.

Consistently there is a separable metrizable $M$ such that,
$(M,\mathcal{K}(M))$ is not Tukey equivalent to
$(M,\mathcal{K}(M))\times(M,\mathcal{K}(M))$.

######  Lemma 2.6.

Let $\gamma X$ and $\delta X$ be compactifications of a space $X$. Then
$(\mathcal{S}(\gamma X\setminus X),\mathcal{K}(\gamma X\setminus
X)=_{T}(\mathcal{S}(\delta X\setminus X),\mathcal{K}(\delta X\setminus X)$ for
$\mathcal{S}=\mathcal{I},\mathcal{F}$ and $\mathcal{K}$.

###### Proof.

By transitivity of Tukey equivalence, we may suppose $\delta X=\beta X$ the
Stone-Cech compactification of $X$. Then the identity map $i_{X}:X\to X$
extends to a map $f:\beta X\to\gamma X$ which is a Wadge reduction
($f^{-1}X=X$) and the claimed Tukey equivalences follow (witnessed by
$\phi(K)=f(K)$ and $\psi(L)=f^{-1}L$). ∎

Let $X$ be a space with compactification $\gamma X$. Set $\widecheck{X}=\gamma
X\setminus X$, the remainder of $X$ in $\gamma X$. By the previous lemma – up
to Tukey equivalence - $\widecheck{X}$ does not depend on the choice of
compactification. Observe that $\mathcal{K}(\gamma X)$ is a compactification
of $\mathcal{K}(X)$. Set $\widecheck{\mathcal{K}(X)}=\mathcal{K}(\gamma
X)\setminus\mathcal{K}(X)$, the corresponding remainder of $\mathcal{K}(X)$.

######  Lemma 2.7.

Let $X$ be a space. Then

$(\widecheck{X},\mathcal{K}(\widecheck{X}))=_{T}(\widecheck{\mathcal{K}(X)},\mathcal{K}(\widecheck{\mathcal{K}(X)})).$

###### Proof.

Since $X$ embeds as a closed set in $\mathcal{K}(X)$, we see $\widecheck{X}$
embeds as a closed set in $\widecheck{\mathcal{K}(X)}$, so we have
$(\widecheck{\mathcal{K}(X)},\mathcal{K}(\widecheck{\mathcal{K}(X)}))\geq_{T}(\widecheck{X},\mathcal{K}(\widecheck{X}))$.

For the converse define
$\phi:\mathcal{K}(\widecheck{X})\to\mathcal{K}(\widecheck{\mathcal{K}(X)})$ by
$\phi(K)=\\{\\{z\\}\cup L:z\in K\,\&\,L\in\mathcal{K}(\gamma X)\\}$. This is
well-defined because: $K\neq\emptyset$ so each $\\{z\\}\cup L$ in $\phi(K)$ is
a compact subset of $\gamma X$ not contained in $X$, and the family $\phi(K)$
is the continuous image of $K\times\mathcal{K}(\gamma X)$ and so compact.
Clearly $\phi$ is order-preserving. Take any $L$ in
$\widecheck{\mathcal{K}(X)}$. Then $L$ is a compact subset of $\gamma X$
meeting $\widecheck{X}$, say at $z$. And now we see, $z$ is in $\widecheck{X}$
and $L=\\{z\\}\cup L\in\phi(\\{z\\})$, as required for a relative Tukey
quotient. ∎

##  3 Compact Covers of Separable Metrizable

We expose the initial, section 3.1, and cofinal, section 3.2, Tukey order
structure of $(M,\mathcal{K}(M))$’s and $(\mathcal{F}(M),\mathcal{K}(M))$’s,
for separable metrizable spaces, $M$. We start by giving an alternative
characterization of the Tukey order in this context.

######  Theorem 3.1.

Let $M$ and $N$ be separable metrizable, $\mathcal{C}\subseteq\mathcal{K}(M)$
and $\mathcal{D}\subseteq\mathcal{K}(N)$. Then the following are equivalent:

(1) $(\mathcal{C},\mathcal{K}(M))\geq_{T}(\mathcal{D},\mathcal{K}(N))$, and

(2) there is a compact metrizable space $Z$, closed subset $D$ of
$\mathcal{K}(M)\times Z$ and continuous $f:D\to N$ such that for every
$L\in\mathcal{D}$ there is a compact subset $K^{\prime}=\\{C\\}\times K$ of
$D$ where $C\in\mathcal{C}$ and $f(K^{\prime})\supseteq L$.

###### Proof.

To show that (2) implies (1), define $\phi:\mathcal{K}(M)\to\mathcal{K}(N)$
via $\phi(K)=f((\mathcal{K}(K)\times Z)\cap D)$. Then $\phi$ is clearly well-
defined and order-preserving. Take any $L$ in $\mathcal{D}$. Then we know
there is a $\\{C\\}\times K$ as in the statement of (2). Now $C$ is in
$\mathcal{C}$ and $\phi(C)\supseteq f(\\{C\\}\times K)\supseteq L$, as
required.

Suppose, then, that (1) holds, and $\phi:\mathcal{K}(M)\to\mathcal{K}(N)$ is
an order preserving relative Tukey quotient. Let $Z$ be any metrizable
compactification of $N$. Let
$C_{0}=\\{(K,L)\in\mathcal{K}(M)\times\mathcal{K}(N):L\subseteq\phi(K)\\}$.
Let $C$ be the closure of $C_{0}$ in $\mathcal{K}(M)\times\mathcal{K}(Z)$.

We know that $C[\mathcal{K}(M)]=\\{K\subseteq Z:\exists\,L\in\mathcal{K}(M)\
\text{with}\ (L,K)\in C\\}\subseteq\mathcal{K}(N)$ (see Lemma 21 in [10]). Let
$D=C\cap(\mathcal{K}(M)\times Z)$. Then $D$ is a closed subset of
$\mathcal{K}(M)\times Z$. By the previous remark $D$ also equals
$C\cap(\mathcal{K}(M)\times N)$. Let $f$ be the projection map from
$\mathcal{K}(M)\times Z$ to $Z$ restricted to $D$. We verify that $f$ has the
property in (2).

Take any compact set $L$ in $\mathcal{D}$. As $\phi$ is a relative Tukey
quotient there is a $K$ in $\mathcal{C}$ such that $\phi(K)\supseteq L$. Let
$L_{0}=\\{K\\}\times\phi(K)$. Then $L_{0}$ is a subspace of
$\mathcal{K}(M)\times Z$ homeomorphic to $\phi(K)$, which is compact. Now we
see that $L_{0}$ is a compact subset of $C_{0}$, and hence a compact subset of
$C$. Also it is clear from the definitions of $D$ and $L_{0}$ that $L_{0}$ is
a (compact) subset of $D$, and $f$ carries $L_{0}$ to $\phi(K)$ which contains
$L$. ∎

###  3.1 The Initial Structure of $(\mathcal{M},\mathcal{K}(\mathcal{M}))$ and
$(\mathcal{F}(\mathcal{M}),\mathcal{K}(\mathcal{M}))$

Recall that a space is Menger if for every sequence of open covers,
$(\mathcal{U}_{n})_{n}$, one can select finite
$\mathcal{V}_{n}\subseteq\mathcal{U}_{n}$ so that their union,
$\bigcup_{n}\mathcal{V}_{n}$, cover. While a space is strong Menger if every
finite power is Menger. The Menger property is preserved by: multiplication
with a compact space, closed subsets (hence perfect pre-images), countable
unions, and continuous images. By a standard argument we deduce the following
lemma.

######  Lemma 3.2.

A separable metrizable space $M$ is strong Menger if and only if
$\mathcal{F}(M)$ (with the standard, Vietoris, topology) is Menger.

Next we connect the Menger property to compact covers.

######  Lemma 3.3.

Let $M$ and $N$ be separable metrizable spaces.

(1) If $(M,\mathcal{K}(M))\geq_{T}(N,\mathcal{K}(N))$ and $M$ is Menger then
$N$ is also Menger.

(2) If
$(\mathcal{F}(M),\mathcal{K}(M))\geq_{T}(\mathcal{F}(N),\mathcal{K}(N))$ and
$M$ is strong Menger then $N$ is strong Menger.

###### Proof.

We prove part (1). Part (2) follows similarly using Lemma 3.2.

As $(M,\mathcal{K}(M))\geq_{T}(N,\mathcal{K}(N))$, we know from Theorem 3.1
there is a compact metrizable space $Z$, closed subset $D$ of
$\mathcal{K}(M)\times Z$ and continuous map $f$ of $D$ into $N$ satisfying
condition (2) of the theorem. Let $D^{\prime}=D\cap(M\times Z)$ and
$f^{\prime}:D^{\prime}\to N$ be $f$ restricted to $D^{\prime}$. Then the
covering property of $f$ implies $f^{\prime}$ is surjective. If $M$ is Menger,
then so are, in turn, $M\times Z$, $D$ and $N$ (via $f^{\prime}$). ∎

######  Theorem 3.4.

Let $M$ be separable metrizable. Then:

(1) $\mathcal{K}(M)\not\geq_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$
if and only if $M$ is locally compact (equivalently, $\mathcal{K}(M)$ Menger),

(2)
$(M,\mathcal{K}(M))\not\geq_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$
if and only if $M$ is Menger, and

(3)
$(\mathcal{F}(M),\mathcal{K}(M))\not\geq_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$
if and only if $M$ is strong Menger.

###### Proof.

For (1): Since
$\mathcal{K}(M)=_{T}(\mathcal{K}(M),\mathcal{K}(\mathcal{K}(M)))$, by part
(2), we know that
$\mathcal{K}(M)\not\geq_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$ if
and only if $\mathcal{K}(M)$ is Menger. Recall that $\mathcal{K}(M)$ is
$\sigma$-compact only when $M$ is locally compact. On the other hand, $M$ is
not locally compact if and only if it contains a closed copy of the metric
fan, $\mathbb{F}$. Noting that $\mathcal{K}(\mathbb{F})$ is not Menger (it is
Polish but not $\sigma$-compact) completes the argument.

For (2): As the space of irrationals, $\omega^{\omega}$, is not Menger, by
Lemma 3.3(1), if
$(M,\mathcal{K}(M))\geq_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$
then $M$ is not Menger.

Now we assume
$(M,\mathcal{K}(M))\not\geq_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$
and show $M$ Menger. Take any sequence of open covers
$(\mathcal{U}_{n})_{n\in\omega}$. As $M$ is Lindelöf we can assume each
$\mathcal{U}_{n}$ is countable, say
$\mathcal{U}_{n}=\\{U^{n}_{m}:m\in\omega\\}$. For $x$ in $M$ define
$f_{x}\in\omega^{\omega}$ by
$f_{x}(n)=\min\\{m:x\in\bigcup_{i=0}^{m}U^{n}_{m}\\}$. Define
$\phi^{\prime}:M\to\omega^{\omega}$ by $\phi^{\prime}(x)=f_{x}$.

Take any compact subset $K$ of $M$. We show $\phi^{\prime}(K)$ is bounded in
$\omega^{\omega}$. To see this note that for each $n$, $\mathcal{U}_{n}$
covers $K$, so we can pick $f(n)=m$ such that
$\\{U^{n}_{0},\ldots,U^{n}_{m}\\}$ cover $K$. Now $\phi^{\prime}(K)\leq f$.

Since
$(M,\mathcal{K}(M))\not\geq_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$
we see that $\phi^{\prime}(M)$ is not cofinal in $\omega^{\omega}$. So there
is an $f$ such that for every $x$ in $M$ there is an $n_{x}$ such that
$f_{x}(n_{x})<f(n_{x})$. For each $n$ let
$\mathcal{V}_{n}=\\{U^{n}_{0},\ldots,U^{n}_{f(n)}\\}$, a finite subcollection
of $\mathcal{U}_{n}$. We complete the proof by showing
$\bigcup_{n}\bigcup\mathcal{V}_{n}$ covers. Well take any $x$ in $M$, then
$f_{x}(n_{x})<f(n_{x})$, so $x\in U^{n}_{f_{x}(n_{x})}\in\mathcal{V}_{n_{x}}$.

For (3): To see this recall Lemmas 3.3(2) and 3.2, and apply the argument for
part (2) to the space $\mathcal{F}(M)$ in place of $M$. ∎

######  Question 3.5.

Let $X$ be a Lindelöf space. Is it the case that $X$ is Menger if and only if
$(X,\mathcal{K}(X))\not\geq_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$?
And is $X$ strong Menger if and only if
$(\mathcal{F}(X),\mathcal{K}(X))\not\geq_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$?

Note that the proof given above shows for any Lindelöf $X$,
$(X,\mathcal{K}(X))\not\geq_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$
implies $X$ is Menger. But the converse depends on Theorem 3.1 which requires
metrizability.

######  Remark 3.6.

Consistently [13] there are Menger sets, $M$, such that $M^{2}$ is not Menger.
For such an $M$ we have
$(M,\mathcal{K}(M))\not\geq_{T}(\omega,\mathcal{K}(\omega^{\omega}))$ but
$(M^{2},\mathcal{K}(M)^{2})\geq_{T}(\omega,\mathcal{K}(\omega^{\omega}))$. In
particular,
$(M,\mathcal{K}(M))\not=_{T}(M^{2},\mathcal{K}(M^{2}))=_{T}(M,\mathcal{K}(M))^{2}$.

At least consistently there are many strong Menger sets whose families of
compact subsets are distinct up to Tukey equivalence.

######  Theorem 3.7.

If $2^{\mathfrak{b}}>\mathfrak{c}$ then there is a family $\mathcal{S}$ of
$2^{\mathfrak{b}}$-many strong Menger sets such that
$(\mathcal{F}(M),\mathcal{K}(M))\not=_{T}(\mathcal{F}(N),\mathcal{K}(N))$ for
distinct $M$ and $N$ from $\mathcal{S}$.

###### Proof.

We review a method, see [3], of constructing non $\sigma$-compact strong
Menger sets. Write $[\mathbb{N}]^{<\infty}$ and $[\mathbb{N}]^{\infty}$ for
the set of finite and, respectively, infinite subsets of $\mathbb{N}$. For
$a\in[\mathbb{N}]^{\infty}$ and $n$ in $\mathbb{N}$, $a(n)$ denotes the $n$th
element of $a$ in its increasing enumeration. For $a,b$ in
$[\mathbb{N}]^{\infty}$, $a\leq^{*}b$ means $a(n)\leq b(n)$ for all but
finitely many $n$. A $\mathfrak{b}$-scale is an unbounded set,
$B=\\{b_{\alpha}:\alpha<\mathfrak{b}\\}$, in
$([\mathbb{N}]^{\infty},\leq^{*})$ such that $\alpha<\beta$ implies
$b_{\beta}\not\leq^{*}b_{\alpha}$. It is straight forward to see that
$\mathfrak{b}$-scales exist in ZFC. Then $X_{B}=[\mathbb{N}]^{<\infty}\cup B$,
considered as a subspace of $P(\mathbb{N})$ (all subsets of $\mathbb{N}$,
identified with the Cantor set, $\\{0,1\\}^{\mathbb{N}}$), is a strong Menger
set which is not $\sigma$-compact. (Actually [3] showed $X_{B}$ is a so called
Hurewicz set. See [4] for the proof that all finite powers of these sets are
Menger.)

Observe that any subset $B^{\prime}$ of $B$ which has size $\mathfrak{b}$ is
also a $\mathfrak{b}$-scale, and so $X_{B^{\prime}}$ is a strong Menger set.
Thus there are at least $2^{\mathfrak{b}}$-many subsets of the reals that are
strong Menger. However we know, see [9], that for any separable metrizable
space $M$ the set
$\\{N\subseteq\mathbb{R}:(\mathcal{F}(M),\mathcal{K}(M))=_{T}(\mathcal{F}(N),\mathcal{K}(N))\\}$
has size $\mathfrak{c}$. It follows that when $2^{\mathfrak{b}}>\mathfrak{c}$
there are indeed $2^{\mathfrak{b}}$-many strong Menger sets as in the
statement of the theorem. ∎

Naturally we would like to remove the hypothesis
‘$2^{\mathfrak{b}}>\mathfrak{c}$’ from the preceding theorem. It seems
plausible that the members of the given $2^{\mathfrak{b}}$-sized family of
separable metrizable strong Menger spaces have pairwise Tukey inequivalent
$(\mathcal{F}(M),\mathcal{K}(M))$ in ZFC. In general what can we say in ZFC
about the number of Tukey classes of pairs $(M,\mathcal{K}(M))$ and
$(\mathcal{F}(M),\mathcal{K}(M))$ where $M$ is a separable metrizable (strong)
Menger space?

######  Question 3.8.

In ZFC:

Are there at least $2^{\mathfrak{b}}$-many Tukey inequivalent
$(\mathcal{F}(M),\mathcal{K}(M))$ pairs where $M$ is strong Menger? Are there
at least $2^{\mathfrak{d}}$-many Tukey inequivalent $(M,\mathcal{K}(M))$ pairs
where $M$ is Menger?

Is $2^{\mathfrak{d}}$ an upper bound on the number of Tukey inequivalent
$(M,\mathcal{K}(M))$ pairs where $M$ is Menger?

Is it consistent that there are strictly fewer, up to Tukey equivalence, pairs
$(\mathcal{F}(M),\mathcal{K}(M))$ where $M$ is strong Menger than
$(M,\mathcal{K}(M))$ pairs where $M$ is Menger?

Our next task is to determine the position of
$(\mathcal{K}(\mathbb{Q}),\mathcal{K}(\mathcal{K}(\mathbb{Q})))$, which is
Tukey equivalent to $\mathcal{K}(\mathbb{Q})$. First a constraint on pairs
$(M,\mathcal{K}(M))$ above $\mathcal{K}(\mathbb{Q})$. Recall that a space is
_hereditarily Baire_ if every closed subspace satisfies the conclusion of the
Baire category theorem. For separable metrizable spaces, being hereditarily
Baire is equivalent to not containing a closed copy of $\mathbb{Q}$.

######  Proposition 3.9.

Let $M$ be separable metrizable. If
$(M,\mathcal{K}(M))\geq_{T}\mathcal{K}(\mathbb{Q})$ then $M$ is not
hereditarily Baire.

###### Proof.

There are compact metrizable $Z$, closed $D$ in $\mathcal{K}(M)\times Z$ and
continuous $f:D\to\mathbb{Q}$ as in Theorem 3.1(2). Let
$D^{\prime}=D\cap(M\times Z)$ and $f^{\prime}$ be $f$ restricted to
$D^{\prime}$. Then the covering property on $f$ implies that $f^{\prime}$ is
compact-covering. Suppose, for a contradiction, that $M$ is hereditarily
Baire. Since $f^{\prime}$ is compact-covering to $\mathbb{Q}$ by [JustWicke]
$f^{\prime}$ is inductively perfect, say when restricted to some closed
$D^{\prime\prime}$. But now $D^{\prime\prime}$ is $\sigma$-compact and
hereditarily Baire, hence Polish, so its perfect image, $\mathbb{Q}$, is also
Polish, which is false. ∎

Next a characterization of pairs $(M,\mathcal{K}(M))$ Tukey-below
$\mathcal{K}(\mathbb{Q})$. Recall that a separable metrizable space that is
the continuous image of a Polish space is _analytic_ , the complement of an
analytic set in a Polish space is _coanalytic_ , and continuous images of
coanalytic is _$\Sigma_{1}^{2}$_.

######  Proposition 3.10.

Let $M$ be separable metrizable. We have
$\mathcal{K}(\mathbb{Q})\geq_{T}(M,\mathcal{K}(M))$ if and only if $M$ is
$\Sigma^{1}_{2}$.

###### Proof.

If $\mathcal{K}(\mathbb{Q})\geq_{T}(M,\mathcal{K}(M))$ then there are a
compact, metrizable $Z$, closed $D\subseteq\mathcal{K}(\mathbb{Q})\times Z$
and continuous surjection $f:D\to M$. Since $\mathcal{K}(\mathbb{Q})$ is co-
analytic, so is $D$, and hence $M$, as the continuous image of co-analytic, is
$\Sigma^{1}_{2}$.

Conversely, suppose $M$ is $\Sigma^{1}_{2}$. Then there is a co-analytic $N$
such that $M$ is the continuous image of $N$. Hence
$(N,K(N))\geq_{T}(<,\mathcal{K}(M))$. But, as $N$ is co-analytic, we know
$\mathcal{K}(\mathbb{Q})\geq_{T}\mathcal{K}(N)$. Recalling that
$\mathcal{K}(N)\geq_{T}(N,\mathcal{K}(N))$ (via the identity map), by
transitivity of $\geq_{T}$, we are done. ∎

There are pairs Tukey-incomparable with $\mathcal{K}(\mathbb{Q})$ and
Proposition 3.9 does not characterize the pairs not Tukey-above
$\mathcal{K}(\mathbb{Q})$.

######  Example 3.11.

There are separable metrizable spaces $M_{1}$ and $M_{2}$ such that both
$(M_{1},\mathcal{K}(M_{1}))$ and $(M_{2},\mathcal{K}(M_{2}))$ are Tukey above
$(\omega^{\omega},\mathcal{K}(\omega^{\omega}))$ and Tukey-incomparable with
$(\mathcal{K}(\mathbb{Q}),\mathcal{K}(\mathcal{K}(\mathbb{Q})))$, and $M_{1}$
is hereditarily Baire while $M_{2}$ is not hereditarily Baire.

###### Proof.

Let $M_{1}$ be a Bernstein set and $M_{2}=M_{1}\oplus\mathbb{Q}$. Note $M_{1}$
is hereditarily Baire. As $M_{2}$ contains a closed copy of $\mathbb{Q}$, it
is not hereditarily Baire. As $M_{1}$ is not compact, while $\mathbb{Q}$ is
$\sigma$-compact, we see that
$(M_{2},\mathcal{K}(M_{2}))=_{T}(M_{1},\mathcal{K}(M_{1}))\times\omega=_{T}(M_{1},\mathcal{K}(M_{1}))$.
It suffices, then, to show that $(M_{1},\mathcal{K}(M_{1}))$ has the required
position in the Tukey order. As $M_{1}$ is not Menger, we have
$(\omega^{\omega},\mathcal{K}(\omega^{\omega}))\leq_{T}(M_{1},\mathcal{K}(M_{1}))$.
As $M_{1}$ is not $\Sigma^{1}_{2}$, we have
$(M_{1},\mathcal{K}(M_{1}))\not\leq_{T}(\mathcal{K}(\mathbb{Q}),\mathcal{K}(\mathcal{K}(\mathbb{Q})))$.
∎

What remains unclear is whether there are (interesting) pairs
$(M,\mathcal{K}(M))$ strictly Tukey-below $\mathcal{K}(\mathbb{Q})$.

######  Question 3.12.

Is there in ZFC a separable metrizable space $M$ such that

$\omega^{\omega}=_{T}(\omega^{\omega},\mathcal{K}(\omega^{\omega}))<_{T}(M,\mathcal{K}(M))<_{T}\mathcal{K}(\mathbb{Q})?$

Such an $M$ is $\Sigma^{1}_{2}$ but not analytic. We know [11] under
$\mathbb{V}=\mathbb{L}$ there is an example, indeed where $M=\mathcal{K}(N)$.
It is consistent [10] that such an $M$ which is also hereditarily Baire does
not exist. Hence the interest is whether there is a ZFC example, or whether
consistently no such $M$ exist (for example, because they must be hereditarily
Baire).

We have seen that - among separable metrizable spaces - those for which we
have $(M,\mathcal{K}(M))\not\geq_{T}\omega^{\omega}$ are precisely the Menger
spaces. We have observed that for Lindelöf spaces $X$, the Tukey relation
$(X,\mathcal{K}(X))\not\geq_{T}\omega^{\omega}$ implies $X$ is Menger. This
raises some intriguing questions.

######  Question 3.13.

Let $M$ be separable metrizable. Is there a covering property (analogous to
that defining Menger space) characterizing when
$(M,\mathcal{K}(M))\not\geq_{T}\mathcal{K}(\mathbb{Q})$? What if we generalize
to Lindelöf spaces?

Menger spaces have some interesting properties, do they extend to Lindelöf
spaces $X$ such that $(X,\mathcal{K}(X))\not\geq_{T}\mathcal{K}(\mathbb{Q})$?
For example, Menger spaces are $D$ [2].

######  Question 3.14.

Let $X$ be Lindelöf. If
$(X,\mathcal{K}(X))\not\geq_{T}\mathcal{K}(\mathbb{Q})$ then is $X$ a
$D$-space? Is $X$ a $D$-space if
$(X,\mathcal{K}(X))\not\geq_{T}\mathcal{K}(M)$, for some separable metrizable
$M$?

###  3.2 The Cofinal Structure

It is known [9, 2.10 & 2.11] that for any spaces $X$ and $Y$ we have
$\mathcal{K}(X)\geq_{T}(\mathcal{F}(X),\mathcal{K}(X))\geq_{T}(X,\mathcal{K}(X))$
and each of ‘$\mathcal{K}(X)\geq_{T}\mathcal{K}(Y)$’,
‘$(\mathcal{F}(X),\mathcal{K}(X))\geq_{T}(\mathcal{F}(Y),\mathcal{K}(Y))$’ and
‘$(X,\mathcal{K}(X))\geq_{T}(Y,\mathcal{K}(Y))$’ are equivalent. Hence the
cofinal structure of $(M,\mathcal{K}(M)$’s and
$(\mathcal{F}(M),\mathcal{K}(M))$’s are the same as that of
$\mathcal{K}(M)$’s, where $M$ is separable metrizable. The reader is referred
to [9, 10] for details of the cofinal structure of $\mathcal{K}(M)$’s. But for
later use we record the existence of Tukey anti-chain of maximal size which
follows from [9, Theorem 3.11].

######  Theorem 3.15.

There is a $2^{\mathfrak{c}}$-sized family, $\mathcal{M}$ of separable
metrizable spaces such that if $M,N$ are distinct elements of $\mathcal{M}$
then $(M,\mathcal{K}(M))\not\geq_{T}(N,\mathcal{K}(N))$ (and vice versa) and
$(\mathcal{F}(M),\mathcal{K}(M))\not\geq_{T}(\mathcal{F}(N),\mathcal{K}(N))$
(and vice versa).

##  4 Applications

###  4.1 Diversity of Free Topological Groups and Relatives

For a space $X$ the _free topological group_ of $X$ (respectively, the _free
Abelian topological group_ of $X$), denoted $F(X)$ ($A(X)$), is the free group
(free Abelian group) on $X$ with the coarsest topological group topology so
that for every continuous map $f$ from $X$ into a (commutative) topological
group the canonical extension over the free (Abelian) group is continuous.
Similarly, the _free locally convex topological space_ of $X$, denoted $L(X)$,
is the vector space on $X$ with the coarsest locally convex topological vector
space topology so that for every continuous map $f$ from $X$ into a locally
convex topological vector space the canonical linear extension over $L(X)$ is
continuous. Finally, denote by $L_{p}(X)$ the vector space as above but only
requiring continuous real valued maps on $X$ to have continuous canonical
extension.

Here we connect the Tukey structure of compact covers of a space $X$ with
those of $F(X),A(X),L(X)$ and $L_{p}(X)$. To start we only need the following
standard fact.

######  Lemma 4.1.

Let $X$ be a space. Then for $G$ any of $F$, $A$, $L$ or $L_{p}$, the space
$G(X)$ has two properties: (1) $X$ embeds as a closed subset and (2) $G(X)$ is
a countable union of continuous images of a product of a compact space and a
finite power of $X$.

###### Proof.

For $G$ either $F$ or $A$, observe that $G(X)$ is the (countable) union over
all free words of continuous images of finite powers of $X$. While for $G$
either $L$ or $L_{p}$, note that $G(X)$ is the union of the sets
$\\{\sum_{i=1}^{n}\lambda_{i}x_{i}:\lambda_{1},\ldots,\lambda_{n}\in[-n,n]$
and $(x_{1},\ldots,x_{n})\in X^{n}\\}$. ∎

######  Proposition 4.2.

Let $X$ be a space, and $G(X)$ another space such that (1) $X$ embeds as a
closed subset in $G(X)$ and (2) $G(X)$ is a countable union of continuous
images of a product of a compact space and a finite power of $X$. Then
$(\mathcal{F}(G(X)),\mathcal{K}(G(X)))\geq_{T}(\mathcal{F}(X),\mathcal{K}(X))$
and
$(\mathcal{F}(X\times\omega),\mathcal{K}(X\times\omega))\geq_{T}(\mathcal{F}(G(X)),\mathcal{K}(G(X)))$.

If $X$ is not totally countably compact for finite sets then

$(\mathcal{F}(X),\mathcal{K}(X))=_{T}(\mathcal{F}(G(X)),\mathcal{K}(G(X))).$

In particular, the above Tukey relations hold when $G$ is any of $F$, $A$, $L$
or $L_{p}$.

###### Proof.

Fix $X$ and $G(X)$. The first Tukey relation is immediate from property (1)
($K\mapsto K\cap X$ is the desired relative Tukey quotient). We show the
second Tukey relation. Using property (2), write $G(X)=\bigcup_{n}G_{n}$ where
$G_{n}=f_{n}(L_{n}\times X^{m_{n}})$, $L_{n}$ is compact, $m_{n}$ from
$\mathbb{N}$ and $f_{n}$ is a continuous map from $L_{n}\times X^{m_{n}}$ into
$G(X)$. Define $\phi:\mathcal{K}(X\times\omega)\to\mathcal{K}(G(X))$ by
$\phi(K^{\prime})=f_{n}(L_{n}\times K^{m_{n}})$, where $K=\pi_{1}(K^{\prime})$
and $n=\max\pi_{2}(K^{\prime})$. Note that $\phi$ is well defined and clearly
order-preserving. To see $\phi(\mathcal{F}(X))$ covers $G(X)$, take any $g$ in
$G(X)$, then $g$ is in some $G_{n}$, so
$g=f_{n}(\ell,x_{1},\ldots,x_{m_{n}})$, and now we see $\phi(F\times\\{n\\})$
contains $g$ where $F=\\{x_{1},\ldots,x_{m_{n}}\\}$.

Now suppose, $X$ is not totally countably compact for finite sets. It remains
to show
$(\mathcal{F}(X),\mathcal{K}(X))\geq_{T}(\mathcal{F}(G(X)),\mathcal{K}(G(X)))$.
But by Proposition 2.3 we know
$(\mathcal{F}(X)),\mathcal{K}(X))\geq_{T}\omega$ and we compute (applying
Lemma 2.4 for the first equivalence):

$\displaystyle(\mathcal{F}(X),\mathcal{K}(X))=_{T}(\mathcal{F}(X),\mathcal{K}(X))\times(\mathcal{F}(X),\mathcal{K}(X))$
$\displaystyle\geq_{T}(\mathcal{F}(X),\mathcal{K}(X))\times(\omega,\omega)=_{T}(\mathcal{F}(X\times\omega),\mathcal{K}(X\times\omega)).$

Now our claim follows from the first part. ∎

Applying this result to the $2^{\mathfrak{c}}$-sized anti-chain of Theorem
3.15 we see there is wide variety of free topological groups et cetera of
separable metrizable spaces.

######  Example 4.3.

There is a $2^{\mathfrak{c}}$-sized family, $\mathcal{M}$ of separable
metrizable spaces such that if $M,N$ are distinct elements of $\mathcal{M}$
then: (1) $G(M)$ does not embed as a closed set in $G(N)$ and (2) $G(M)$ is
not the continuous image of $G(N)$, for $G$ any of $F$, $A$, $L$ or $L_{p}$.

This should be compared with a result from [8] where it is shown that there is
a $2^{\mathfrak{c}}$-sized family, $\mathcal{A}$ of separable metrizable
spaces such that if $M,N$ are distinct elements of $\mathcal{A}$ then: (1′)
$A(M)$ does not embed in $A(N)$ and (2′) $A(M)$ is not the continuous open
image of $A(N)$. Here (1′) is stronger that (1) above, while (2′) is weaker
than (2). The results from [8] give much more information about the topology
of the free Abelian topological group, including its character, but they only
apply to the free Abelian case.

Applying the proposition to the consistent family of strong Menger sets of
Theorem 3.7 we obtain a large family of ‘small’ (close to $\sigma$-compact)
separable metrizable spaces with diverse free topological algebraic objects.

######  Example 4.4.

If $2^{\mathfrak{b}}>\mathfrak{c}$ then there is a $2^{\mathfrak{b}}$-sized
family, $\mathcal{S}$, of strong Menger sets such that if $M$ and $N$ are
distinct elements of $\mathcal{S}$ then $G(M)$ and $G(N)$ are not
homeomorphic, for $G$ any of $F$, $A$, $L$ or $L_{p}$.

Reformulating the proposition above in terms of $P$-ordered covers we
immediately deduce the first part of the next lemma. The second part follows
from the fact that each of $F(X)$, $A(X)$, $L(X)$ and $L_{p}(X)$ contains an
infinite closed discrete subset, hence they are not $\omega$-bounded, and the
claim follows from Proposition 2.3. To see that they do all contain an
infinite closed discrete set, for $L(X)$ and $L_{p}(X)$ note they contain
closed copies of $\mathbb{R}$, while for $A(X)$ and $F(X)$, apply [1,
Corollary 7.4.3].

######  Lemma 4.5.

(1) If a space $X$ has a $P$-ordered compact covering then each of $F(X)$,
$A(X)$, $L(X)$ and $L_{p}(X)$ has a $P\times\omega$-ordered compact covering.

(2) If any of $F(X)$, $A(X)$, $L(X)$, or $L_{p}(X)$ has a $Q$-ordered compact
cover then $Q\geq_{T}\omega$ (so $Q=_{T}Q\times\omega$).

The following example serves two purposes. It shows the necessity of the
$\omega$ factor in the preceding lemma. And it gives an example of a
topological group which is not Lindelöf $\Sigma$ but does have a
$\mathcal{K}(M)$-ordered compact cover, where $M$ is separable metrizable (see
the next section). (Note it is well known that
$\mathcal{K}(\mathbb{Q})\geq_{T}\omega_{1}\times\omega$.)

######  Example 4.6.

The space $\omega_{1}$ has an $\omega_{1}$-ordered compact cover. Hence
$A(\omega_{1})$ is a topological group with an
$(\omega_{1}\times\omega)$-ordered compact cover, and so a
$\mathcal{K}(\mathbb{Q})$-ordered compact cover. However $A(\omega_{1})$ is
not Lindelöf $\Sigma$ and does not have an $\omega_{1}$-ordered compact cover.

In our last result on the free topological group and its relatives, and
compact covers we investigate invariance. It is almost immediate from
Proposition 4.2 but we have to deal with the potential of extra $\omega$
factors.

######  Proposition 4.7.

If $G(X)$ and $G(Y)$ are topologically isomorphic, for $G$ one of $F$, $A$,
$L$ or $L_{p}$, then
$(\mathcal{F}(X),\mathcal{K}(X))=_{T}(\mathcal{F}(Y),\mathcal{K}(Y))$.

###### Proof.

Suppose $G(X)$ and $G(Y)$ are topologically isomorphic. We show there is a
Tukey quotient from $(\mathcal{F}(X),\mathcal{K}(X)$ to
$(\mathcal{F}(Y),\mathcal{K}(Y))$. Symmetry gives the full result.

If $X$ is not totally countably compact for finite sets then by Proposition
4.2 $(\mathcal{F}(X),\mathcal{K}(X))$ is Tukey equivalent to
$(\mathcal{F}(G(X)),\mathcal{K}(G(X)))$ and since $Y$ is a closed subset of
$G(Y)$, which is homeomorphic to $G(X)$, we see indeed that
$(\mathcal{F}(X),\mathcal{K}(X))\geq_{T}(\mathcal{F}(Y),\mathcal{K}(Y))$.

Now suppose $X$ is totally countably compact for finite sets. Then $X$ is
pseudocompact. As pseudocompactness is $G$-invariant (for each $G$) we see $Y$
is pseudocompact. When $G$ is either $F$ or $A$, by [1, Corollary 7.5.4], $Y$
is contained as a closed subset in some $B_{n}(X)$, the set of words of
reduced length $\leq n$. As $B_{n}(X)$ is the continuous image of a finite sum
of finite powers of $X$ we see
$(\mathcal{F}(X),\mathcal{K}(X))\geq_{T}(\mathcal{F}(B_{n}(X)),\mathcal{K}(B_{n}(X)))$.
And so, as above,
$(\mathcal{F}(X),\mathcal{K}(X))\geq_{T}(\mathcal{F}(Y),\mathcal{K}(Y))$. A
minor modification of [1, Corollary 7.5.4] gives the result when $G$ is $L$ or
$L_{p}$. ∎

###  4.2 When Topological Groups are CCC

Since compact groups carry the Haar measure they are clearly ccc (every
pairwise disjoint family of non-empty open sets is countable). Interesting
extensions of this result were obtained by Tkachenko [15] who showed that
$\sigma$-compact topological groups are ccc, and then Uspenskii who showed
Lindelöf $\Sigma$ groups [17], are ccc. Below we prove a result which
generalizes those of Tkachenko and Uspenskii, and implies that
$\sigma$-pseudocompact groups and groups with a $\mathcal{K}(M)$-ordered
compact cover, where $M$ is separable metrizable, are ccc. (Recall Lindelöf
$\Sigma$ spaces have a $\mathcal{K}(M)$-ordered compact cover, where $M$ is
separable metrizable.)

A subspace $X$ of a space $Y$ has _relative calibre $(\kappa,\lambda,\mu)$ (in
$Y$)_ if every family of open sets in $Y$, each meeting $X$, of size $\kappa$
contains a subfamily of size $\lambda$ whose every $\mu$-sized subcollection
has non-empty intersection. A space $X$ has _calibre $(\kappa,\lambda,\mu)$_
if it has relative calibre $(\kappa,\lambda,\mu)$ in itself. Note that a space
is ccc if and only if it has calibre $(\omega_{1},2,2)$, and has the Knaster
property (aka ‘property K’) if it has calibre $(\omega_{1},\omega_{1},2)$.
Observe that $X$ has calibre $(\kappa,\lambda,\mu)$ if and only if $X$ has the
same relative calibre in $Y$ (for any $\kappa,\lambda,\mu$) _provided_ either
$X$ is a retract of $Y$, or $X$ is dense in $Y$ and $\mu$ is finite.

Define $M_{G}(X)$ to be the set $\\{xy^{-1}z:x,y,z\in X\\}$ considered as a
subspace of the free topological group on $X$, $F(X)$. Let $q:X^{3}\to
M_{G}(X)$ be the natural map. Denote by $\mathcal{U}_{X}$ the universal
uniformity on $X$. Set $W(A,B)=q\left((A\times B)\cup(B\times A)\right)$ where
$A\subseteq X$ and $B$ is a symmetric subset of $X^{2}$ containing the
diagonal. Then in [12] it is shown:

######  Lemma 4.8 (Claim 10).

For each $x$ in a space $X$, the family of all sets $W(O,U)$, where $O$ is an
open neighborhood of $x$ and $U$ is in $\mathcal{U}_{X}$, is a local base at
$x$ in $M_{G}(X)$.

Recall that for any cover $\mathcal{U}$ of a space, and any subset $O$, the
_star of $O$ in $\mathcal{U}$_ is
$\mathop{st}(O,\mathcal{U})=\bigcup\\{U\in\mathcal{U}:O\cap
U\neq\emptyset\\}$. Another open cover $\mathcal{V}$ _star refines_
$\mathcal{U}$ if the collection of stars,
$\\{\mathop{st}(V,\mathcal{V}):V\in\mathcal{V}\\}$, refines $\mathcal{U}$.
Then an open cover $\mathcal{U}$ is _normal_ if there is a sequence of covers,
$(\mathcal{V}_{n})_{n}$, such that $\mathcal{V}_{0}=\mathcal{U}$ and for every
$n$ we have that $\mathcal{V}_{n+1}$ star refines $\mathcal{V}_{n}$.
Equivalently, ([16] and see [7, 5.4H(c)]), and more usefully here, an open
cover is normal if it has a locally finite open refinement by cozero sets.
Recall that the collection $\\{U(\mathcal{U}):\mathcal{U}$ is an open normal
cover of $X\\}$ is a base of the universal uniformity, $\mathcal{U}_{X}$,
where $U(\mathcal{U})=\bigcup\\{V\times V:V\in\mathcal{U}\\}$. Combining this
with the observation that $W(O_{1},U(\mathcal{U}_{1}))\cap
W(O_{2},U(\mathcal{U}_{2}))\neq\emptyset$ if and only if
$\mathop{st}(O_{1},\mathcal{U}_{2})\cap\mathop{st}(O_{2},\mathcal{U}_{1})\neq\emptyset$,
we deduce:

######  Lemma 4.9.

Let $X$ be a space. Then the following are equivalent:

(1) $(TG_{\kappa,\lambda,2})$ for any families
$\\{O_{\alpha}:\alpha<\kappa\\}$ of non-empty open sets and
$\\{\mathcal{U}_{\alpha}:\alpha<\kappa\\}$ of open normal covers, there is a
subset $A$ of $\kappa$ of size $\lambda$ such that
$\mathop{st}(O_{\alpha},\mathcal{U}_{\beta})\cap\mathop{st}(O_{\beta},\mathcal{U}_{\alpha})\neq\emptyset$
for any $\alpha,\beta\in A$;

(2) for any families $\\{O_{\alpha}:\alpha<\kappa\\}$ of non-empty open sets
and $\\{U_{\alpha}:\alpha<\kappa\\}\subseteq\mathcal{U}_{X}$, there is a
subset $A$ of $\kappa$ of size $\lambda$ such that
$W(O_{\alpha},U_{\alpha})\cap W(O_{\beta},U_{\beta})\neq\emptyset$ for any
$\alpha,\beta\in A$;

(3) $X$ is relative calibre $(\kappa,\lambda,2)$ in $M_{G}(X)$.

A space is _retral_ if it can be embedded as a retract in a topological group.
Obviously every topological group is retral. Every retral space $X$ is a
retract of $M_{G}(X)$ and conversely (see [12]). Combining the above we
deduce:

######  Theorem 4.10.

A retral space $X$ has calibre $(\kappa,\lambda,2)$ if and only if it has
$(TG_{\kappa,\lambda,2})$.

A collection $\mathcal{N}$ of subsets of a space $X$ is a _network_ for
another collection, $\mathcal{C}$ say, if whenever some $C$ in $\mathcal{C}$
is contained in an open set $U$, there is an element $N$ from $\mathcal{N}$
such that $C\subseteq N\subseteq U$. Then a space is $\Sigma(\aleph_{0})$ if
it has a cover by countably compact sets and a countable network for this
cover. Let us say that a space is $\Sigma^{-}(\aleph_{0})$ if it has a cover
by pseudocompact sets and a countable network for this cover. Observe that a
locally finite open cover of a pseudocompact (hence also, countably compact)
space is finite. In the next result we combine these observations with the
ideas behind the proof of Tkachenko’s theorem.

######  Theorem 4.11.

Let $X$ be a $\Sigma^{-}(\aleph_{0})$ retral space. Then $X$ has calibre
$(\omega_{1},\omega_{1},2)$.

###### Proof.

Fix the cover $\mathcal{K}$ of $X$ by pseudocompact sets, and countable family
$\mathcal{N}$ such that whenever $K\subseteq U$, where $K\in\mathcal{K}$ and
$U$ is open, there is an $N\in\mathcal{N}$ such that $K\subseteq N\subseteq
U$.

It suffices to check the condition $(TG_{\omega_{1},\omega_{1},2})$ above. Fix
a family of open sets $\\{O_{\alpha}:\alpha<\omega_{1}\\}$ and normal open
covers $\\{\mathcal{U}_{\alpha}:\alpha<\omega_{1}\\}$. Observe that
$(TG_{\kappa,\lambda,2})$ holds if it is true when we replace each
$\mathcal{U}_{\alpha}$ by any open refinement. So, by definition of ‘normal’
cover, we may assume that every $\mathcal{U}_{\alpha}$ is locally finite.
Picking a point $x_{\alpha}$ in $O_{\alpha}$, it suffices to show there is a
$\omega_{1}$-sized subset $A$ of $\omega_{1}$ such for any distinct
$\alpha,\beta$ from $A$ we have
$\mathop{st}(x_{\alpha},\mathcal{U}_{\beta})\cap\mathop{st}(x_{\beta},\mathcal{U}_{\alpha})\neq\emptyset$.

For each $x_{\alpha}$ pick $K_{\alpha}$ from $\mathcal{K}$ containing
$x_{\alpha}$. As $\mathcal{U}_{\alpha}$ is locally finite and $K_{\alpha}$ is
pseudocompact pick a finite subcollection $\mathcal{V}_{\alpha}$ of
$\mathcal{U}_{\alpha}$ covering $K_{\alpha}$. Let
$V_{\alpha}=\bigcup\mathcal{V}_{\alpha}$. Pick $N_{\alpha}$ in $\mathcal{N}$
such that $K_{\alpha}\subseteq N_{\alpha}\subseteq V_{\alpha}$.

As $\mathcal{N}$ is countable there is an uncountable
$A^{\prime}\subseteq\omega_{1}$ such that $N_{\alpha}=N$ for all $\alpha\in
A^{\prime}$. Note $\\{x_{\alpha}:\alpha\in A^{\prime}\\}$ is contained in $N$.
Passing to an uncountable subset we can suppose that all
$\mathcal{V}_{\alpha}$ have size $\leq k$, for some fixed $k$. Color the pairs
$[A^{\prime}]^{2}$ so that $\\{\alpha,\beta\\}$ has color $0$ if
$\mathop{st}(x_{\alpha},\mathcal{V}_{\beta})\cap\mathop{st}(x_{\beta},\mathcal{V}_{\alpha})\neq\emptyset$
and $1$ otherwise. If there is an uncountable subset $A$ of $A^{\prime}$ whose
pairs are all colored $0$ then we are done: for all distinct $\alpha,\beta$ in
$A$ we have that
$\mathop{st}(x_{\alpha},\mathcal{U}_{\beta})\cap\mathop{st}(x_{\beta},\mathcal{U}_{\alpha})$
contains
$\mathop{st}(x_{\alpha},\mathcal{V}_{\beta})\cap\mathop{st}(x_{\beta},\mathcal{V}_{\alpha})$
which is non-empty.

By Erdös-Dushnik-Miller, if there is no uncountable $0$-homogeneous set then
there must be an infinite $1$-homogeneous set. However Tkachenko proved: for
any set $Y$, and $\\{\mathcal{V}_{\alpha}:\alpha<\omega\\}$ a family of open
covers of $Y$ such that each $|\mathcal{V}_{\alpha}|\leq k$ ($k$ fixed) and
$\\{x_{\alpha}:\alpha<\omega\\}\subseteq Y$ there is an infinite
$B\subseteq\omega$ such that any distinct $\alpha,\beta\in B$ satisfy
$\mathop{st}(x_{\alpha},\mathcal{V}_{\beta})\cap\mathop{st}(x_{\beta},\mathcal{V}_{\alpha})\neq\emptyset$.
Taking $Y=N$ and $\mathcal{V}_{\alpha}$ and $x_{\alpha}$ for $\alpha$ from an
infinite $1$-homogeneous set gives a contradiction. ∎

Since $\sigma$-pseudocompact spaces (ones that are a countable union of
pseudocompact subspaces) are $\Sigma^{-}(\aleph_{0})$ we deduce:

######  Corollary 4.12.

Every $\sigma$-pseudocompact group is calibre $(\omega_{1},\omega_{1},2)$, and
hence is ccc.

Recall [6] that if a space has $\mathcal{K}(M)$-ordered compact cover then it,
and every closed subspace, is $\Sigma(\aleph_{0})$, and noting that a subspace
of a space is calibre $(\omega_{1},\omega_{1},2)$ if and only if its closure
has the same calibre, we deduce:

######  Corollary 4.13.

Every subgroup of a topological group with a $\mathcal{K}(M)$-ordered compact
cover, where $M$ is separable metrizable, has calibre
$(\omega_{1},\omega_{1},2)$, and hence is ccc.

Combining the preceding corollary with Proposition 4.2 we see:

######  Corollary 4.14.

If $X$ has a $\mathcal{K}(M)$-ordered compact cover, where $M$ is separable
metrizable, then $A(X)$, $F(X)$, $L(X)$ and $L_{p}(X)$, and all their
subgroups, have calibre $(\omega_{1},\omega_{1},2)$, and so are ccc.

Corollaries 4.12 and 4.13 differ because the latter claims the ccc property
for all subgroups, but the former does not.

######  Question 4.15.

Is every subgroup of a $\sigma$-pseudocompact group ccc?

Note that if $G$ is a pseudocompact group then $\beta G$ is a (compact) group
containing $G$ as a subgroup, hence if $H$ is a subgroup of $G$ then the
closure of $H$ in $\beta G$ is a compact group, so ccc, and thus $H$ is ccc.

A space $X$ is a _Maltsev_ space if there is a continuous map $M:X^{3}\to X$
such that $M(x,y,y)=x=M(y,y,x)$ for all $x,y\in X$. Retral spaces are Maltsev
(if $r$ is a retraction from a group $G$ onto $X$ then set
$M(x,y,z)=r(xy^{-1}z)$). Pseudocompact Maltsev spaces are retral [14] but not
all Maltsev spaces are retral [12].

######  Question 4.16.

(i) Is every $\sigma$-pseudocompact Maltsev space ccc? Retral?

(ii) Is every Maltsev space with a $\mathcal{K}(M)$-ordered compact cover,
where $M$ is separable metrizable, ccc? Retral?

(iii) Is every $\Sigma^{-}(\aleph_{0})$ Maltsev space ccc? Retral?

## References

  * [1] A. Arhangel’skií and M. Tkachenko.  Topological Groups and Related Structures.  Atlantis Press and World Sci., Paris, 2008.
  * [2] L. Aurichi.  D-Spaces, Topological Games, and Selection Principles.  Topology Proceedings, 36:107–122, 2010.
  * [3] T. Bartoszyński and S. Shelah.  Continuous images of sets of reals.  Topology and its Applications, 116:243–253, 2001.
  * [4] T. Bartoszyński and B. Tsaban.  Hereditary topological diagonalizations and the Menger–Hurewicz conjectures.  Proceedings of the American Mathematical Society, 134:605–615, 2006\.
  * [5] B. Cascales and J. Orihuela.  A biased view of topology as a tool in functional analysis, pages 93–164.  Atlantis Press, Paris, 2014.
  * [6] B. Cascales, J. Orihuela, and V. Tkachuk.  Domination by second countable spaces and Lindelöf ${\Sigma}$ property.  Topology Appl., pages 204–214, 2011.
  * [7] R. Engelking.  General Topology.  Heldermann Verlag, 1989.
  * [8] P. Gartside.  Tukey order and diversity of free Abelian topological groups.  Journal of Pure and Applied Algebra, 225(10):106712.
  * [9] P. Gartside and A. Mamatelashvili.  Tukey order on compact subsets of separable metric spaces.  Journal of Symbolic Logic, 81(1):181–200, 2016.
  * [10] P. Gartside and A. Mamatelashvili.  Tukey order, calibres and the rationals.  Annals of Pure and Applied Logic, 172(1), 2021.
  * [11] P. Gartside, A. Medini, and L. Zdomskyy.  preprint.
  * [12] P. Gartside, E. Reznichenko, and O. Sipacheva.  Maltsev and retral spaces.  Topology and its Applications, 80:115–129, 1997.
  * [13] W. Just, A. Miller, M. Scheepers, and P. Szeptycki.  The combinatorics of open covers II.  Topology Appl., pages 241–266, 1996.
  * [14] E. Reznichenko and V. Uspenskij.  Pseudocompact Mal’tsev spaces.  Topol. Appl., 86:83–104, 1998.
  * [15] M. Tkachenko.  On the Souslin property in free topological groups over compact Hausdorff spaces.  Math Notes, 34:790–793, 1983.
  * [16] J. Tukey.  Convergence and Uniformity in Topology, volume No. 2 of Annals of Mathematics Studies.  Princeton University Press, Princeton, NJ, 1940.
  * [17] V. Uspenskii.  Topological groups generated by a Lindelöf ${\Sigma}$-space has the Souslin property.  Soviet Math. Dokl., 26:166–169, 1982.


Table 7: Summary of results for the HVRPD instances. Inst | $n$ | $m$ |  $\left\\{q^{0}\right\\}$ |  $\mathcal{Q}_{B}$ |  $\mathcal{Q}_{F}$ |  $\mathcal{Q}_{E}^{\text{ax}}$ |  $\mathcal{Q}_{E}^{\text{gen}}$ |  $\mathcal{Q}_{G}$ |  $\mathcal{Q}_{S}$
---|---|---|---|---|---|---|---|---|---
13 | 50 | 6 |  1,432.57 |  1,517.84 |  1,502.24 |  1,481.13 |  1,482.49 |  1,517.84 |  1,468.83
14 | 50 | 3 |  584.38 |  606.67 |  603.02 |  596.53 |  597.54 |  606.67 |  596.63
15 | 50 | 3 |  961.41 |  1,015.29 |  1,012.64 |  991.70 |  991.70 |  1,015.29 |  984.85
16 | 50 | 3 |  1,085.06 |  1,144.94 |  1,133.16 |  1,120.57 |  1,121.38 |  1,144.94 |  1,110.41
17 | 75 | 4 |  1,009.48 |  1,061.96 |  1,052.28 |  1,021.50 |  1,023.99 |  1,061.96 |  1,020.28
18 | 75 | 6 |  1,761.88 |  1,823.58 |  1,812.32 |  1,783.93 |  1,788.38 |  1,823.58 |  1,777.02
19 | 100 | 3 |  1,093.23 |  1,120.34 |  1,120.34 |  1,101.64 |  1,116.47 |  1,120.34 |  1,101.64
20 | 100 | 3 |  1,472.97 |  1,534.17 |  1,533.62 |  1,501.53 |  1,514.39 |  1,534.17 |  1,508.31
Table 8: Summary of results for the FSMFD instances. Inst | $n$ | $m$ |  $\left\\{q^{0}\right\\}$ |  $\mathcal{Q}_{B}$ |  $\mathcal{Q}_{F}$ |  $\mathcal{Q}_{E}^{\text{ax}}$ |  $\mathcal{Q}_{E}^{\text{gen}}$ |  $\mathcal{Q}_{G}$ |  $\mathcal{Q}_{S}$
---|---|---|---|---|---|---|---|---|---
3 | 20 | 5 |  986.93 |  1,144.22 |  1,118.76 |  1,106.84 |  1,106.65 |  1,144.22 |  1,092.59
4 | 20 | 3 |  6,377.28 |  6,437.33 |  6,432.25 |  6,413.06 |  6,413.06 |  6,437.33 |  6,392.34
5 | 20 | 5 |  1,167.40 |  1,322.26 |  1,298.72 |  1,287.48 |  1,287.48 |  1,322.26 |  1,249.08
6 | 20 | 3 |  6,416.11 |  6,516.47 |  6,500.82 |  6,499.74 |  6,499.74 |  6,516.47 |  6,470.82
13 | 50 | 6 |  2,711.61 |  2,964.65 |  2,935.40 |  2,906.68 |  2,873.24 |  2,964.65 |  2,908.96
14 | 50 | 3 |  8,582.05 |  9,126.90 |  8,644.00 |  8,618.16 |  8,618.16 |  9,126.90 |  8,618.16
15 | 50 | 3 |  2,450.82 |  2,634.96 |  2,608.61 |  2,590.47 |  2,591.86 |  2,634.96 |  2,591.93
16 | 50 | 3 |  2,906.71 |  3,168.92 |  3,137.50 |  3,061.09 |  3,070.34 |  3,168.92 |  3,052.39
17 | 75 | 4 |  1,872.49 |  2,004.48 |  1,969.64 |  1,932.82 |  1,946.09 |  2,004.48 |  1,925.47
18 | 75 | 6 |  2,918.45 |  3,153.09 |  3,100.08 |  3,056.88 |  3,064.50 |  3,152.16 |  3,063.70
19 | 100 | 3 |  8,094.97 |  8,662.86 |  8,649.99 |  8,132.14 |  8,409.14 |  8,662.86 |  8,134.19
20 | 100 | 3 |  3,839.11 |  4,165.91 |  4,138.25 |  4,046.05 |  4,085.22 |  4,168.44 |  4,054.18
Table 9: Summary of results for the FSMF instances. Inst | $n$ | $m$ |  $\left\\{q^{0}\right\\}$ |  $\mathcal{Q}_{B}$ |  $\mathcal{Q}_{F}$ |  $\mathcal{Q}_{E}^{\text{ax}}$ |  $\mathcal{Q}_{E}^{\text{gen}}$ |  $\mathcal{Q}_{G}$ |  $\mathcal{Q}_{S}$
---|---|---|---|---|---|---|---|---|---
3 | 20 | 5 |  887.99 |  954.37 |  949.79 |  921.23 |  927.96 |  951.61 |  918.63
4 | 20 | 3 |  6,327.60 |  6,437.33 |  6,432.25 |  6,413.06 |  6,413.06 |  6,437.33 |  6,379.27
5 | 20 | 5 |  919.86 |  1,005.27 |  980.57 |  961.63 |  963.63 |  988.63 |  949.85
6 | 20 | 3 |  6,353.72 |  6,516.47 |  6,500.82 |  6,499.74 |  6,499.74 |  6,516.47 |  6,448.52
13 | 50 | 6 |  2,223.70 |  2,399.20 |  2,365.21 |  2,305.17 |  2,327.57 |  2,406.36 |  2,304.11
14 | 50 | 3 |  8,562.41 |  9,119.03 |  8,644.00 |  8,618.16 |  8,618.16 |  9,119.03 |  8,618.16
15 | 50 | 3 |  2,360.49 |  2,586.37 |  2,561.65 |  2,475.63 |  2,492.99 |  2,586.37 |  2,463.19
16 | 50 | 3 |  2,506.66 |  2,721.40 |  2,697.88 |  2,610.03 |  2,646.51 |  2,720.43 |  2,612.59
17 | 75 | 4 |  1,621.25 |  1,734.53 |  1,712.24 |  1,658.29 |  1,680.08 |  1,734.53 |  1,657.43
18 | 75 | 6 |  2,195.13 |  2,369.65 |  2,322.62 |  2,272.55 |  2,294.51 |  2,369.65 |  2,267.88
19 | 100 | 3 |  8,094.97 |  8,662.86 |  8,649.99 |  8,129.33 |  8,382.79 |  8,662.86 |  8,135.02
20 | 100 | 3 |  3,714.44 |  4,043.97 |  3,973.46 |  3,862.99 |  3,911.89 |  4,060.73 |  3,874.70
Table 10: Summary of results for the FSMD instances. Inst | $n$ | $m$ |  $\left\\{q^{0}\right\\}$ |  $\mathcal{Q}_{B}$ |  $\mathcal{Q}_{F}$ |  $\mathcal{Q}_{E}^{\text{ax}}$ |  $\mathcal{Q}_{E}^{\text{gen}}$ |  $\mathcal{Q}_{G}$ |  $\mathcal{Q}_{S}$
---|---|---|---|---|---|---|---|---|---
3 | 20 | 5 |  555.66 |  623.22 |  609.51 |  604.02 |  604.02 |  623.22 |  585.02
4 | 20 | 3 |  369.77 |  378.70 |  373.24 |  369.77 |  373.24 |  380.71 |  373.24
5 | 20 | 5 |  713.62 |  742.87 |  737.36 |  736.90 |  736.90 |  742.85 |  721.00
6 | 20 | 3 |  391.42 |  414.66 |  415.03 |  396.26 |  405.46 |  406.19 |  396.26
13 | 50 | 6 |  1,405.87 |  1,491.86 |  1,488.78 |  1,468.28 |  1,471.82 |  1,491.86 |  1,460.06
14 | 50 | 3 |  575.63 |  603.21 |  601.71 |  583.94 |  588.64 |  603.21 |  583.94
15 | 50 | 3 |  944.96 |  999.82 |  997.98 |  979.40 |  985.19 |  999.82 |  974.59
16 | 50 | 3 |  1,078.67 |  1,131.00 |  1,114.78 |  1,110.88 |  1,111.69 |  1,131.00 |  1,107.74
17 | 75 | 4 |  1,006.50 |  1,036.54 |  1,029.75 |  1,017.52 |  1,020.50 |  1,038.60 |  1,016.64
18 | 75 | 6 |  1,746.53 |  1,800.80 |  1,795.02 |  1,778.61 |  1,785.58 |  1,800.80 |  1,775.35
19 | 100 | 3 |  1,073.71 |  1,106.17 |  1,101.07 |  1,084.54 |  1,099.69 |  1,105.44 |  1,093.74
20 | 100 | 3 |  1,468.79 |  1,530.52 |  1,525.33 |  1,495.31 |  1,514.46 |  1,533.24 |  1,497.01
Table 11: Summary of results for the SDVRP instances. Inst | $n$ | $m$ |  $\left\\{q^{0}\right\\}$ |  $\mathcal{Q}_{B}$ |  $\mathcal{Q}_{F}$ |  $\mathcal{Q}_{E}^{\text{ax}}$ |  $\mathcal{Q}_{E}^{\text{gen}}$ |  $\mathcal{Q}_{G}$ |  $\mathcal{Q}_{S}$
---|---|---|---|---|---|---|---|---|---
1 | 50 | 3 |  609.52 |  640.32 |  634.19 |  621.50 |  624.77 |  640.32 |  623.37
2 | 50 | 2 |  563.85 |  598.10 |  593.59 |  569.45 |  577.70 |  598.10 |  569.45
3 | 75 | 3 |  899.90 |  954.32 |  938.11 |  908.95 |  922.33 |  954.32 |  908.95
4 | 75 | 2 |  806.72 |  854.43 |  843.73 |  831.60 |  836.25 |  854.43 |  825.27
5 | 100 | 3 |  963.09 |  1,003.57 |  993.64 |  977.14 |  978.00 |  1,003.57 |  976.01
6 | 100 | 2 |  965.86 |  1,028.52 |  1,016.95 |  987.88 |  1,000.59 |  1,028.52 |  983.46
7 | 27 | 3 |  391.30 |  391.30 |  391.30 |  391.30 |  391.30 |  391.30 |  391.30
8 | 54 | 3 |  664.46 |  664.46 |  664.46 |  664.46 |  664.46 |  664.46 |  664.46
9 | 81 | 3 |  948.23 |  948.23 |  948.23 |  948.23 |  948.23 |  948.23 |  948.23
10 | 108 | 3 |  1,189.69 |  1,218.75 |  1,218.75 |  1,208.74 |  1,208.74 |  1,218.75 |  1,200.34
13 | 54 | 3 |  1,150.31 |  1,194.18 |  1,194.18 |  1,162.85 |  1,171.58 |  1,194.18 |  1,171.58
14 | 108 | 3 |  1,873.74 |  1,960.88 |  1,960.88 |  1,886.53 |  1,908.76 |  1,960.88 |  1,889.59
23 | 100 | 3 |  764.19 |  803.29 |  803.29 |  781.81 |  784.83 |  803.29 |  781.81
Table 12: Summary of results for the MDVRP instances. Inst | $n$ | $m$ |  $\left\\{q^{0}\right\\}$ |  $\mathcal{Q}_{B}$ |  $\mathcal{Q}_{F}$ |  $\mathcal{Q}_{E}^{\text{ax}}$ |  $\mathcal{Q}_{E}^{\text{gen}}$ |  $\mathcal{Q}_{G}$ |  $\mathcal{Q}_{S}$
---|---|---|---|---|---|---|---|---|---
1 | 50 | 4 |  560.63 |  576.87 |  570.81 |  570.81 |  570.81 |  576.87 |  575.36
2 | 50 | 4 |  464.35 |  473.53 |  473.01 |  464.48 |  464.48 |  473.22 |  464.48
3 | 75 | 5 |  623.79 |  640.65 |  635.93 |  629.86 |  630.98 |  641.19 |  629.67
4 | 100 | 2 |  951.28 |  999.21 |  997.20 |  973.68 |  982.38 |  999.21 |  978.74
5 | 100 | 2 |  725.55 |  750.03 |  747.29 |  731.27 |  741.44 |  750.03 |  732.17
6 | 100 | 3 |  838.00 |  876.50 |  871.47 |  864.49 |  867.39 |  877.26 |  865.93
7 | 100 | 4 |  843.30 |  881.97 |  871.31 |  855.39 |  860.65 |  881.97 |  855.55
12 | 80 | 2 |  1,290.93 |  1,318.95 |  1,314.36 |  1,314.36 |  1,314.36 |  1,318.95 |  1,301.68
15 | 160 | 4 |  2,463.14 |  2,505.42 |  2,505.42 |  2,505.42 |  2,505.42 |  2,505.42 |  2,492.55