%%%%%%% FOR LATEX ONLY


\documentclass[10pt]{article}

\usepackage{amssymb}
\usepackage{amsmath}


%%%%%%% END FOR LATEX ONLY
%\input StandardMacros
%\firstpagenumber{}
%\received{}

\title{Compositions of Sierpi\'{n}ski-Zygmund functions and related
combinatorial cardinals}

%\MathReviews{Primary:  26A15; Secondary: 03E75, 54A25.}
%\keywords{cardinal functions; extendable, Darboux, almost continuous
%and peripherally continuous functions; functions with perfect road. }


\author{{\small Francis Jordan}%
\thanks{AMS classification numbers: Primary 26A15;  Secondary 54A25
\endgraf  Key words and phrases: Sierpi\'{n}ski-Zygmund functions, cardinal functions, singular cardinals.
\endgraf},
\small  Department of Mathematics, Loyola University,\\
New Orleans, LA 70118}

%% Theorems, etc.
\def\integer{{\Bbb Z}}
\def\natural{{\Bbb N}}
\def\rational{{\Bbb Q}}
\def\real{{\Bbb R}}
\newcommand{\inj}{\operatorname{inj}}
\newcommand{\shel}{\operatorname{c}}
\newcommand{\cof}{\operatorname{cf}}
\newcommand{\add}{\operatorname{A}}
\newcommand{\cmp}{\operatorname{C}}
\newcommand{\bd}{\operatorname{b}}
\newcommand{\bound}{\operatorname{Bd}}
\newcommand{\cuum}{{\frak c}}
\newcommand{\D}{{\cal D}}
\newcommand{\F}{{\cal F}}
\newcommand{\G}{{\cal G}}
\newcommand{\pos}{{\Bbb P}}
\newcommand{\dar}{{\operatorname {Dar}}}
\newcommand{\conn}{{\operatorname {Con}}}
\newcommand{\acon}{{\operatorname {AC}}}
\newcommand{\ext}{{\operatorname {EXT}}}
\newcommand{\pr}{{\operatorname {PR}}}
\newcommand{\id}{{\operatorname {id}}}
\newcommand{\sz}{{\operatorname {SZ}}}
\newcommand{\diff}{{e}}
\newcommand{\same}{{d}}
\newcommand{\dom}{{D}}
\newcommand{\ireal}{{\cal N}}



%\def\qed{\hfill$\box$}
\def\qed{\hfill\vrule height6pt width6pt depth1pt\medskip}
\newcommand{\proof}{{\sc Proof.\ }}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}{Problem}
\newtheorem{example}{Example}
\newtheorem{question}{Question}

\newcommand{\thm}[2]{\begin{theorem}\label{#1}#2\end{theorem}}
\newcommand{\cor}[2]{\begin{corollary}\label{#1}#2\end{corollary}}
\newcommand{\prop}[2]{\begin{proposition}\label{#1}#2\end{proposition}}
\newcommand{\lem}[2]{\begin{lemma}\label{#1}#2\end{lemma}}
\newcommand{\quest}[2]{\begin{question}\label{#1}#2\end{question}}
\newcommand{\prob}[2]{\begin{problem}\label{#1}#2\end{problem}}
\newcommand{\ex}[2]{\begin{example}\label{#1}#2\end{example}}


%%%%%%%%%%%%%%%%%%%%%   MISCELLANEOUS

% characteristic function

     \newcommand{\charf}[1]{\mbox{\raise.48ex\hbox{$\chi$}$_{#1}$}}


\begin{document}\maketitle
\begin{abstract}
A cardinal related to compositions of Sierpi\'{n}ski-Zygmund functions will be
considered. A combinatorial characterization of the cardinal is given and is used to
answer some questions of K. Ciesielski and T. Natkaniec.  Also, a cardinal number
defined by S. Shelah is shown to be equal to the bounding number under certain
conditions.  Finally, it is shown that the bounding number of the continuum may be
strictly smaller than continuum.
\end{abstract}
\section{Preliminaries}

In what follows we will use the following terminology and notation.  Any
notation not specifically defined can be found in \cite{cibook}.  Functions will be
identified with their graphs.  The set of all functions from a set $X$ into a set $Y$
will be denoted by
$Y^{X}$.  Given sets
$X,Y,W$ and $f\in W^Y$ and $g\in Y^X$ we denote their composition by $f\circ g$.

The symbol $|X|$ will denote the
cardinality of the set $X$.  The successor of a cardinal $\kappa$ will be
denoted by $\kappa^{+}$.
We denote by $[X]^{<\kappa}$, $[X]^{\kappa}$, and
$[X]^{\leq\kappa}$ the sets of all subsets of $X$ of cardinality less than $\kappa$,
equal to $\kappa$, and less than or equal to $\kappa$, respectively.

The cardinality of the real numbers $\real$ will be denoted by
$\cuum$.  Given a cardinal number $\kappa$ we let $\cof(\kappa)$
denote the cofinality of $\kappa$.  We say a cardinal $\kappa$ is
regular provided that $\cof(\kappa)=\kappa$, otherwise we say
$\kappa$ is singular. For functions $f,g\in Y^{X}$ let $[f=g]$
denote the set $\{x\in X\colon f(x)=g(x)\}$.  We define $[f<g]$
and $[f\leq g]$ in a similar way when $\leq$ and $<$ are defined
for $Y$.



We also will consider the following cardinals related to a
cardinal~ $\kappa$.
\begin{description}
\item[ ]$\same_{\kappa}
=\min\{|F|\colon F\subseteq \kappa^{\kappa}\ \&\ (\forall g\in\kappa^{\kappa})
(\exists f\in F) (|[f=g]|=\kappa)\}$.
\item[ ]
$\bd_{\kappa}
=\min\{|F|\colon F\subseteq \kappa^{\kappa}\ \&\
(\forall g \in\kappa^{\kappa})(\exists f\in F)(|[f\geq g]|=\kappa\}$.
\end{description}
Note that $\bd_{\kappa}\leq\same_{\kappa}$.  When $\kappa=\omega$
the numbers $\bd_{\omega}$ and $\same_{\omega}$ are equal to the
bounding and eventually different numbers, respectively, both of
which have been heavily studied, e.g. \cite{BJ}.  Notice that
$\bd_{\kappa}$ is a regular cardinal and that
$\kappa<\bd_{\kappa}$ when $\kappa$ is regular.

For a cardinal $\kappa$ we let ${\cal
S}_{\kappa}=\left([\kappa]^{<\kappa}\right)^{\kappa}$.  In
\cite{SH} the following cardinal is defined
\[\shel^{-}(\kappa,\kappa)=\min\{|F|\colon F\subseteq{\cal S}_{\kappa}\ \&\ (\forall
h\in\kappa^{\kappa})(\exists f\in F)(|\{\xi\colon h(\xi)\in f(\xi)\}|=\kappa)\}.\]

We will also use the following combinatorial cardinals which turn
out to all be equal although it is not obvious that they are:
\begin{description}
\item[($\lambda_{\kappa}^1$)] $\lambda_{\kappa}^1$ is the smallest cardinality of an
$F\subseteq{\cal S}_{\kappa}$ such that for any
$g\in\kappa^{\kappa}$ there is an $f\in F$ such that
$|\bigcup\{f(\xi)\colon g(\xi)\in f(\xi)\}|=\kappa$,
\item[($\lambda_{\kappa}^2$)] $\lambda_{\kappa}^2$ is the smallest cardinality of an
$F\in{\cal R}(\kappa,\kappa)$, such that there is a
$g\in\kappa^{\kappa}$ such that for any $h\in\kappa^{\kappa}$ there is an $f\in F$
such that
$|[h\circ f=g]|=\kappa$,
\item[($\lambda_{\kappa}^3$)] $\lambda_{\kappa}^3$ is the smallest cardinality of an
$F\in{\cal R}(\kappa,\kappa)$, such that there is a $G\in
[\kappa]^{\kappa}$ such that for any $h\in\kappa^{\kappa}$ there
is a $g\in G$ and an $f\in F$ such that we have $|[h\circ
f=g]|=\kappa$
\item[($\lambda_{\kappa}^4$)] $\lambda_{\kappa}^4$ is the smallest cardinality of
an $F\in\kappa^{\kappa}$ such that  $f[[g\leq f]]$ is unbounded in $\kappa$ for any
$g\in\kappa^{\kappa}$.
\end{description}

\section{Introduction}
We say $f\in \real^{\real}$ is a Sierpi\'{n}ski-Zygmund function provided that
the restriction $f|_X$ is not continuous for any set $X\subseteq\real$ of cardinality $\cuum$.
We will be interested in resolving some problems in \cite{CN} about
Sierpi\'{n}ski-Zygmund functions.  To state the problems we will need some
definitions.  Let $X$ and $Y$ be sets and define ${\cal
R}(X,Y)=\{f\in Y^{X}\colon |f^{-1}(y)|<|X| \text{ for every
}y\in Y\}$.  In \cite[Thm. 4.9]{CN} it is shown that $f\in {\cal R}(\real,\real)$ if
and only if there is an $h\in\real^{\real}$ such that $h\circ f\in\sz$.

The following cardinal is defined in~\cite{CN}
\[
\cmp_{out}(\sz)=\min
\{|F|\colon F\subseteq {\cal R}(\real,\real)\ \&\
(\forall h\in\real^{\real})(\exists f\in F)(h\circ f\notin\sz)\}\}.
\]

The following two propositions are established in \cite{CN}:

\prop{prop:10}{If $\cuum$ is a regular cardinal, then
$\cuum<\cmp_{out}(\sz)\leq 2^{\cuum}$.  Generally,
$\cof(\cuum)\leq\cmp_{out}(\sz)\leq\cuum^{\cof(\cuum)}$.}

\prop{prop:11}{If $\cuum=\kappa^{+}$ for some $\kappa$, then
$\cmp_{out}(\sz)=\same_{\cuum}$.}


The two propositions above suggest the following two problems
about the cardinal $\cmp_{out}(\sz)$ which are posed in \cite{CN}.


\prob{prob:1}{Is the assumption that $\cuum$ is regular important in
Proposition~\ref{prop:10}?}

\prob{prob:2}{Can Proposition~\ref{prop:11} be proved for any value of $\cuum$.
What if $\cuum$ is regular?}


We first give a combinatorial characterization of
$\cmp_{out}(\sz)$ which is a corollary of the two following
general theorems.

\thm{thm:0}{If $\kappa\geq\omega$ is a cardinal, then
\[\cof(\kappa)\leq\lambda_{\kappa}^4=\lambda_{\kappa}^1=\lambda_{\kappa}^2=\lambda_{\kappa}^3.\]
}


\thm{thm:10}{If $\kappa$ is singular, then
$\cof(\kappa)\leq\lambda_{\kappa}^i\leq\cof(\kappa)^+$ for $1\leq
i\leq 4$.  If $\kappa$ is regular, then
$\lambda_{\kappa}^i=\bd_{\kappa}$ for $1\leq i\leq 4$.  In either
case $\lambda^i_{\kappa}$ is regular for $1\leq i\leq 4$.}

Recall the following result of W.~Sierpi\'{n}ski and A.~Zygmund
\cite{sezy}: \prop{prop:50}{$f\in\real^{\real}$ is in $\sz$ if and
only if $|[f=h]|<\cuum$ for every continuous function $h$ defined
on a $G_{\delta}$ set of cardinality~$\cuum$.} By
Proposition~\ref{prop:50}, if we let $J$ be the collection of
functions $f\in\real^{\real}$ such that $f|_X$ is continuous for
some $G_{\delta}$-set $X\subseteq\real$ of cardinality $\cuum$ and
zero elsewhere, then $|J|=\cuum$ and:

\medskip
($*$) $f\in\real^{\real}\in\sz$ if and only if $|f\cap j|<\cuum$ for every $j\in J$.
\medskip

We can prove the following corollary of Theorem~\ref{thm:0} and Theorem~\ref{thm:10}
which gives a partial answer to Problem~\ref{prob:2}.

\cor{cor:0}{$\lambda_{\cuum}^i=\cmp_{out}(\sz)$ for all $1\leq
i\leq 4$.} \proof Let $F\subseteq{\cal R}(\real,\real)$ witness
the definition of $\cmp_{out}(\sz)$, i.e., $|F|=\cmp_{out}(\sz)$
and
\[(\forall h\in\real^{\real})(\exists f\in F)(h\circ
f\notin\sz).\]
By ($*$) we know that $F$ has the following property,
\[(\forall h\in\real^{\real})(\exists f\in F)(\exists j\in J)(|h\circ f=j]|=\cuum).\]
It follows that $\lambda^3_{\cuum}\leq\cmp_{out}(\sz)$. Letting
$\kappa=\cuum=|\real|$ Theorem~\ref{thm:0} implies that
$\lambda_{\cuum}^i\leq\cmp_{out}(\sz)$ for all $1\leq i\leq 4$.

We will be done if we show that
$\cmp_{out}(\sz)\leq\lambda_{\kappa}^1$. Let $\ireal$ denote the
irrational numbers.  Suppose $F\subseteq
([\real]^{<\cuum})^{\real}$ and suppose $|F|<\cmp_{out}(\sz)$. We
find an $h\in\real^{\real}$ such that $|\bigcup\{f(x)\colon
h(x)\in f(x)\}]|<\cuum$ for every $f\in F$. Let
$k\colon\ireal\to\real^3$ be a continuous bijection (see exercise
7.15 of \cite{kech}).

For each $f\in F$ define the function $f_1$ on a subset of
${\real}^{3}$ by letting \[f_1(\langle x,y,z\rangle)=y\] for all
$\langle x,y,z\rangle$ such that $x\in f(y)$ and $z\in f(y)$.
Notice that $|f_1^{-1}(y)|<\cuum$ for every $y\in\real$.  We may
extend $f_1$ to a ${\cal R}(\real^3,\real)$ type function $f_1^*$
defined on $\real^{3}$.  Let $F^*=\{f_1^*\circ k\colon f\in F\}$.
Clearly, $|F^*|<\cmp_{out}(\sz)$.

Let $\pi_1$ be the projection of $\real^3$ onto the first
coordinate and $\pi_3$ be the projection of $\real^3$ onto the
third coordinate.  Since $\pi_1\circ k\colon\ireal\to\real$ is
continuous and $F^*\subseteq{\cal R}(\ireal,\real)$ has
cardinality less than $\cmp_{out}(\sz)$, there is an
$h\colon\real\to\real$ such that $|[h\circ (f_1^*\circ
k)=\pi_1\circ k]|<\cuum$ for every $f\in F$. Since $k$ is a
bijection, we have $|[h\circ f_1^*=\pi_1]|<\cuum$.

Fix $f\in F$.  We will be done if we show that
$|\bigcup\{f(x)\colon h(x)\in f(x)\}|<\cuum$. Let
$y\in\bigcup\{f(x)\colon h(x)\in f(x)\}$.  There is a $x\in\real$
such that $y\in f(x)$ and $h(x)\in f(x)$. Now,
\[(h\circ f_1^*)(\langle
h(x),x,y\rangle)=h(x)=\pi_1(\langle h(x),x,y\rangle).\] So,
$y\in\pi_3[[(h\circ f_1^*)=\pi_1]]$. Since $|[(h\circ
f_1^*)=\pi_1]|<\cuum$, we have that $|\bigcup\{f(x)\colon h(x)\in
f(x)\}|<\cuum$.  Thus,
$\cmp_{out}(\sz)\leq\lambda_{\kappa}^1$.\qed



Corollary~\ref{cor:0} tells us that the continuous functions are
as hard to avoid as any collection of $\cuum$-many functions from
$\real$ into $\real$, and that there is a single function that is
as hard to avoid as the continuous functions.  From
Corollary~\ref{cor:0} and Theorem~\ref{thm:10} we get:

\cor{cor:000}{If $\cuum$ is regular, then
$\cmp_{out}(\sz)=\bd_{\cuum}$. If $\cuum$ is singular, then
$\cof(\cuum)\leq\cmp_{out}(\sz)\leq\cof(\cuum)^+$. In particular,
$\cmp_{out}(\sz)$ is a regular cardinal.}

Corollary~\ref{cor:000} gives an affirmative answer to
Problem~\ref{prob:1}.  Since $\same_{\cuum}>\cuum$ \cite{CN},
Corollary~\ref{cor:000}, gives a negative answer to
Problem~\ref{prob:2} in the singular case.


\quest{quest:4}{Is it consistent that $\cuum$ is singular and
$\bd_{\cuum}<\same_{\cuum}$ (see the second part
Problem~\ref{prob:2})?}



\thm{thm:1}{It is consistent that $\cof(\cuum)=\cmp_{out}(\sz)$.}

\quest{quest:5}{Is it consistent that $\cuum$ is singular and
$\cmp_{out}(\sz)=\cof(\cuum)^+$?}

To prove Theorem~\ref{thm:1} we will use the following theorem.

\thm{thm:5}{$\bd_{\cof(\kappa)}<\kappa$ if and only if
$\lambda^4_{\kappa}=\cof(\kappa)$.}


\thm{thm:3}{$\bd_{\kappa}\leq\bd_{\cof(\kappa)}$ for any cardinal $\kappa\geq\omega$.  In
particular, if $\kappa$ is a singular strong limit cardinal, then
$\bd_{\kappa}<\kappa$.}

An immediate corollary of Theorem~\ref{thm:1} and
Theorem~\ref{thm:5} and Theorem~\ref{thm:3} is: \cor{cor:last}{It
is consistent that $\bd_{\cuum}<\cuum$.}

In light of Theorem~\ref{thm:5} we could rephrase
Question~\ref{quest:5} to be:  Is it consistent that $\cuum$ is
singular and $\cuum<\bd_{\cof(\cuum)}$?

Lastly, we use some ideas from the proof of Theorem~\ref{thm:0} to prove the following
combinatorial theorem.
\thm{thm:00}{$\min\{\kappa,\bd_{\kappa}\}\leq\shel^{-}(\kappa,\kappa)\leq\bd_{\kappa}$.
In particular, if $\shel^{-}(\kappa,\kappa)<\kappa$, then
$\shel^{-}(\kappa,\kappa)=\bd_{\kappa}$.  Moreover, if $\kappa$ is regular, then
$\shel^{-}(\kappa,\kappa)=\bd_{\kappa}$.}

\quest{quest:6}{Can $\shel^{-}(\kappa,\kappa)=\bd_{\kappa}$ be
proved in ZFC?}



\section{Proof of Theorem~\ref{thm:0} and Theorem~\ref{thm:10}}\label{sec:tee}

We first begin with some lemmas.

\lem{lem:20}{Let $F\in [{\cal
R}(\kappa,\kappa)]^{<\lambda^4_{\kappa}}$.  There is a bijection
$k\in\kappa^{\kappa}$ such that for every $f\in F$ and
$\alpha\in\kappa$
\[\left|\left[\bigcup_{\xi\leq\alpha}f^{-1}(k(\xi))\right]\right|<\kappa.\]}
\proof
For every $f\in F$ define $f^*\in\kappa^{\kappa}$ by
$f^*(\alpha)=|f^{-1}(\alpha)|$.   Let $F^*=\{f^*\colon f\in F\}$.  Since $|F^*|\leq
|F|<\lambda^4_{\kappa}$, there is a
$g\in\kappa^{\kappa}$ such that
\begin{equation}\label{eq:12}
f^*[[g\leq f^*]]
\end{equation}
is bounded above by some $\rho_f\in\kappa$ for every $f\in F$.  Notice that we may
assume $g$ has unbounded range, since if we define $m\in\kappa^{\kappa}$ by
$m(\xi)=\max\{g(\xi),\xi\}$, then we will have
$f^*[[m\leq f^*]]\subseteq f^*[[g\leq f^*]]$ for every $f\in F$.

Define an injection
$k^*\in\kappa^{\kappa}$ so that
$\max\{\alpha,g(\alpha)\}\leq k^*(\alpha)$
for every
$\alpha\in\kappa$.  Since
$|k^{*}[\kappa]|=\kappa$, there is an increasing onto function
$h\colon k^{*}[\kappa]\to\kappa$.  Let $k=(k^{*})^{-1}\circ h^{-1}$.

We claim $k$ is as desired.  Fix $f\in F$.  Let
$\gamma\in\kappa$.  Consider
$\alpha\leq\gamma$.  Since $h$ is increasing and $g$ has unbounded range, there is
a $\beta_{\gamma}\in\kappa$ such that
$h^{-1}(\alpha)\leq h^{-1}(\gamma)\leq g(\beta_{\gamma})$.  By definition of
$k^{*}$, we have
$(k^{*})^{-1}(h^{-1}(\alpha))\neq \zeta$ for any
$\zeta\in\kappa$ such that $g(\zeta)>g(\beta_{\gamma})$, since otherwise we would have
\[g(\beta_{\gamma})\geq
h^{-1}(\alpha)=k^*((k^*)^{-1}(h^{-1}(\alpha)))=k^{*}(\zeta)\geq
\max\{\zeta,g(\zeta)\},\]
a contradiction.  So
$k(\alpha)\neq\zeta$ for all $\alpha\leq\gamma$ and all
$\zeta\in\kappa$ such that $g(\zeta)>g(\beta_{\gamma})$.

Let $T$ be the set of all $\alpha<\gamma$ such that
$f^{*}(k(\alpha))<g(k(\alpha))$ and $S=\gamma\setminus T$.  If
$\alpha\in S$, then, by (\ref{eq:12}), $f^*(k(\alpha))\leq\rho_f$.
So, we have $|f^{-1}(k(\alpha))|\leq\rho_f$ for $\alpha\in S$.  If
$\alpha\in T$, then, by (\ref{eq:12}),
\[|f^{-1}(k(\alpha))|\leq g(k(\alpha))\leq g(\beta_{\gamma}).\]
So, for $\alpha\in T$ we have $|f^{-1}(k(\alpha))|=f^*(k(\alpha))<
g(\beta_{\gamma})$.

Thus, $|\bigcup_{\alpha\leq\gamma}f^{-1}(k(\alpha))|$ is bounded above in $\kappa$
by $\max\{\rho_f,g(\beta_{\gamma}),\gamma\}$. \qed


\lem{lem:40}{$\min\{\kappa,\lambda^4_{\kappa}\}\leq\lambda^3_{\kappa}
\leq\lambda^2_{\kappa}$.} \proof Let $F\in [{\cal
R}(\kappa,\kappa)]^{<\min\{\kappa,\lambda^4_{\kappa}\}}$.  Fix
$G\in [\kappa^{\kappa}]^{\kappa}$.  We construct an
$h\in\kappa^{\kappa}$ such that $|[h\circ f=g]|<\kappa$ for every
$g\in G$ and $f\in F$. Let $\{g_{\alpha}\colon\alpha\in\kappa\}$
be an enumeration of $G$.

By Lemma~\ref{lem:20} there is a bijection $k\in\kappa^{\kappa}$
such that for each $f\in F$ and for every $\alpha\in\kappa$ we
have
\begin{equation}\label{eq:rd2}
|\bigcup_{\xi\leq\alpha}f^{-1}(k(\xi))|<\kappa
\end{equation}
For each $f\in F$ let
$f^*(\alpha)=|\bigcup_{\xi\leq\alpha}f^{-1}(k(\xi))|$ for each
$\alpha\in\kappa$.  Since $|F|<\lambda^4_{\kappa}$ there is an
$m\in\kappa^{\kappa}$ such that for every $f\in F$ we have
$f^*[\{\xi\colon f^{*}(\xi)\geq m(\xi)\}]$ is bounded in $\kappa$.

Define $h\in\kappa^{\kappa}$ inductively so that for every $\alpha\in\kappa$ we select
$h(k(\alpha))$ from the set
\[\kappa\setminus\left\{g_{\beta}(x)\colon
x\in\bigcup\left\{\bigcup_{\xi\leq\alpha}f^{-1}(k(\xi))\colon
f^*(\alpha)<m(\alpha)\right\}\ \&\ \beta\leq\alpha\right\}.\] Note
that such choices can be made since,
\[|\bigcup_{\xi\leq\alpha}f^{-1}(k(\xi))|=f^*(\alpha)\leq m(\alpha)\]
for every $f\in F$ such that $f^*(\alpha)<m(\alpha)$. So,
\[\left|\bigcup\left\{\bigcup_{\xi\leq\alpha}f^{-1}(k(\xi))\colon
f^*(\alpha)<m(\alpha)\right\}\right|\leq\max\{|F|,m(\alpha)\}.\]


We show that $h$ is as desired.  Fix $f\in F$ and $g_{\beta}\in
G$.  For $\xi\in [h\circ f=g_{\beta}]$ pick $\alpha_{\xi}$ so that
$k(\alpha_{\xi})=f(\xi)$.  We now have
\[h(k(\alpha_{\xi}))=h(f(\xi))=g_{\beta}(\xi)\in
g_{\beta}[f^{-1}(k(\alpha_{\xi}))].\] By definition of $h$ we must
have $\alpha_{\xi}<\beta$ or $f^*(\alpha_{\xi})\geq
m(\alpha_{\xi})$.  Let $T=\{\alpha_{\xi}\colon
f^*(\alpha_{\xi})\geq m(\alpha_{\xi})\}$.

We show $T$ is bounded.  By way of contradiction, assume that $T$
is not bounded in $\kappa$.  Then,
$\kappa=\bigcup\{f^{-1}(k(\gamma))\colon (\exists t\in
T)(\gamma<t)\}\subseteq\bigcup\{f^*(t)\colon t\in T\}=\bigcup
f^*[T]\subseteq\kappa$.   So, $\bigcup f^*[T]=\kappa$. On the
other hand, we know, by our choice of $m$, that $f^*[T]$ is
bounded in $\kappa$, a contradiction.

We now have that $M=\{\alpha_{\xi}\colon\xi\in [h\circ
f=g_{\beta}]\}$ is bounded in $\kappa$.  Since $M$ is bounded, we
have, by (\ref{eq:rd2}), $|f^{-1}(k(M))|<\kappa$.

Let $\xi\in [h\circ f=g_{\beta}]$.  Then there is an
$\alpha_{\xi}\in M$ such that $f(\xi)=k(\alpha_{\xi})$.  So,
\[\xi\in f^{-1}(f(\xi))=f^{-1}(k(\alpha_{\xi}))\subseteq
f^{-1}(k[M]).\] Thus, $[h\circ f=g_{\beta}]\subseteq
f^{-1}(k[M])$. Since $|f^{-1}(k[M])]|<\kappa$, we must have
$|[h\circ f=g_{\beta}]|<\kappa$.  Thus,
$\min\{\kappa,\lambda^4_{\kappa}\}\leq\lambda^3_{\kappa}$.

That $\lambda^3_{\kappa}\leq\lambda_{\kappa}^2$ is obvious.  \qed

\lem{lem:my}{If $\cof(\kappa)<\kappa$ then
$\lambda_{\kappa}^{4}\leq\cof(\kappa)^{+}$.} \proof Let
$\{\Gamma_{\alpha}\colon\alpha\in\cof(\kappa)\}$ be a sequence of
cardinals cofinal in $\kappa$.  For every
$\rho\in\cof(\kappa)^+\setminus\cof(\kappa)$ let
$k_{\rho}\colon\rho\to\cof(\kappa)$ be a bijection.  For each
$\alpha\in\cof(\kappa)$ and
$\rho\in\cof(\kappa)^+\setminus\cof(\kappa)$ let
$f_{\alpha,\rho}\in\kappa^{\kappa}$ be defined by
\begin{equation}\notag f_{\alpha,\rho}(\beta)=
\begin{cases} \Gamma_{\alpha} & \text{if $\beta\notin\rho$;}\\
\max\{\Gamma_{\alpha},\Gamma_{k_{\rho}(\beta)}\} & \text{if
$x\beta\in\rho$.}
\end{cases}
\end{equation}
Let $F=\{f_{\alpha,\rho}\colon\alpha\in\cof(\kappa)\ \&\
\rho\in\cof(\kappa)^{+}\}$.  Clearly, $|F|=\cof(\kappa)^{+}$.

Let $h\in\kappa^{\kappa}$ be arbitrary.  We find a
$f_{\alpha,\rho}\in T$ such that $f_{\alpha,\rho}[[h\leq
f_{\alpha,\rho}]]$ is unbounded in $\kappa$. First notice that
\[\cof(\kappa)^+=\bigcup_{\alpha\in\cof(\kappa)}\{\beta\in\cof(\kappa)^+\colon
h(\beta)<\Gamma_{\alpha}\}.\]  Thus, there is an
$\alpha\in\cof(\kappa)$ such that $|\{\beta\in\cof(\kappa)^+\colon
h(\beta)<\Gamma_{\alpha}\}|=\cof(\kappa)^+$.  Pick
$W\subseteq\{\beta\in\cof(\kappa)^+\colon h(\beta)<
\Gamma_{\alpha}\}$ such that $|W|=\cof(\kappa)$.  There is a
$\rho\in\cof(\kappa)^+$ such that $W\subseteq\rho$.  Now for each
$w\in W$ we have $h(w)\leq\Gamma_{\alpha}\leq
f_{\alpha,\rho}(w)=\max\{\Gamma_{\alpha},\Gamma_{k_{\rho}(w)}\}$.
Since $|W|=\cof(\kappa)$, $\{\Gamma_{k_{\rho}(w)}\colon w\in W\}$
is unbounded in $\kappa$. Thus, $f_{\alpha,\rho}(\beta)[[h\leq
f_{\alpha,\rho}]]$ is unbounded in $\kappa$.\qed


\lem{lem:50}{$\lambda^1_{\kappa}\leq\lambda_{\kappa}^4$.} \proof
Let $F\subseteq\kappa^{\kappa}$ and suppose
$|F|<\lambda^1_{\kappa}$.  We find an $h\in\kappa^{\kappa}$ such
that $f[\{\xi\colon h(\xi)\leq f(\xi)\}]$ is bounded above by some
$\alpha_f\in\kappa$ for every $f\in F$.

For each $f\in F$ define $f_1\in{\cal S}_{\kappa}$ so that
$f_1(\xi)=\{\beta\colon\beta\leq f(\xi)+1\}$.  Let $F_1=\{f_1\colon f\in F\}$.  Since
$|F_1|\leq |F|<\lambda_{\kappa}^1$ there is an $h\in\kappa^{\kappa}$ such
that
\begin{equation}\label{eq:rd1}
|\bigcup\{f_1(\xi)\colon h(\xi)\in f_1(\xi)\}|<\kappa
\end{equation}
for every $f_1\in F_1$. Since $f_1(\xi)$ is an initial segment of
$\kappa$ for every $\xi\in\kappa$, (\ref{eq:rd1}) implies that
$\bigcup\{f_1(\xi)\colon h(\xi)\in f_1(\xi)\}$ is bounded in
$\kappa$ by some $\alpha_{f_1}\in\kappa$ for every $f_1\in F_1$.

Fix $f\in F$.  We claim that $f[\{\xi\colon h(\xi)\leq f(\xi)\}]$ is bounded above by
$\alpha_{f_1}\in\kappa$.  Let $\beta\in f[\{\xi\colon h(\xi)\leq f(\xi)\}]$.  Then,
there is a $\gamma$ such that $h(\gamma)\leq f(\gamma)$ and
$f(\gamma)=\beta$.  So,
$\beta=f(\gamma)\in f_1(\gamma)\subseteq\bigcup\{f_1(\xi)\colon h(\xi)\in
f_1(\xi)\}\subseteq\alpha_{f_1}$.  Thus,
$f[\{\xi\colon h(\xi)\leq f(\xi)\}]$ is bounded above by $\alpha_{f_1}\in\kappa$.
Thus, $\lambda^1_{\kappa}\leq\lambda^4_{\kappa}$.\qed

\lem{lem:slow}{$\lambda_{\kappa}^2\leq\lambda^1_{\kappa}$.} \proof
It should be noted that the proof of this inequality is very
similar to the proof that $\cmp_{out}(\sz)\leq\lambda_{\cuum}^1$
in Corollary~\ref{cor:0}.  The differences between the two proofs
stem from  the fact that there is no topological structure to
worry about in the proof that
$\lambda_{\kappa}^2\leq\lambda^1_{\kappa}$.

Let $F\in [{\cal S}_{\kappa}]{<\lambda_{\kappa}^2}$. We find an
$h\in\kappa^{\kappa}$ such that \[|\bigcup\{f(\xi)\colon h(\xi)\in
f(\xi)\}|<\kappa\] for every $f\in F$.  Let
$k\colon\kappa\to\kappa^3$ be a bijection.

For each $f\in F$ define the function $f_1$ on a subset of ${\kappa}^{3}$ by
letting \[f_1(\langle x,y,z\rangle)=y\] for all $\langle x,y,z\rangle$ such that
$x\in f(y)$ and $z\in f(y)$.   Notice that $|f_1^{-1}(y)|<\kappa$ for every
$y\in\kappa$.  We
may extend $f_1$ to a ${\cal R}(\kappa^3,\kappa)$ type function $f_1^*$ defined
on $\kappa^{3}$.

Let $\pi_1$ be the projection of $\kappa^3$ onto the first
coordinate and $\pi_3$ be the projection of $\kappa^3$ onto the
third coordinate. Since $\{f_1^*\circ k\colon f\in
F\}\subseteq{\cal R}(\kappa,\kappa)$ has cardinality less than
$\lambda_{\kappa}^2$, there is an $h\colon\kappa\to\kappa$ such
that $|[h\circ (f_1^*\circ k)=\pi_1\circ k]|<\kappa$ for every
$f\in F$.  Since $k$ is a bijection, we have $|[h\circ
f_1^*=\pi_1]|<\kappa$

Fix $f\in F$.  We will be done if we
show that $|\bigcup\{f(\xi)\colon h(\xi)\in f(\xi)\}|<\kappa$.
Let $\gamma\in\bigcup\{f(\xi)\colon h(\xi)\in f(\xi)\}$.
There is a $\xi\in\kappa$ such that
$\gamma\in f(\xi)$ and $h(\xi)\in f(\xi)$.
Now,
\[(h\circ f_1^*)(\langle
h(\xi),\xi,\gamma\rangle)=h(\xi)=\pi_1(\langle h(\xi),\xi,\gamma\rangle).\]
So, $\gamma\in\pi_3[[h\circ f_1^*=\pi_1]]$.
Now $|\bigcup\{f(\xi)\colon
h(\xi)\in f(\xi)\}|<\kappa$ since $|[h\circ f_1^*=\pi_1]|<\kappa$.

Thus, $\lambda^2_{\kappa}\leq\lambda_{\kappa}^1$.\qed

\lem{lem:kar}{$\lambda_{\kappa}^4\leq\bd_{\kappa}$.} \proof

Take $F\subseteq\kappa^{\kappa}$ with $|F|<\lambda^4_{\kappa}$.
For each $f\in F$ pick $f^*\in\kappa^{\kappa}$ so that
\begin{equation}\label{eq:how}
f^*(\xi)=\max\{f(\xi),\xi\}.
\end{equation}
There is a $g\in\kappa^{\kappa}$ such that for every $f\in F$ we
have $f^*[g\leq f^*]$ is bounded in $\kappa$.  Since, by
(\ref{eq:how}), $f^*$ maps unbounded sets to unbounded sets, we
must have that $[g\leq f^*]$ is bounded in $\kappa$.  Clearly,
$[g\leq f]\subseteq [g\leq f^*]$. Thus, $|[g\leq f]|<\kappa$.
Therefore, $\lambda^4_{\kappa}\leq\bd_{\kappa}$.\qed


 {\sc
Proof of Theorem~\ref{thm:0}}

Lemmas \ref{lem:50}, \ref{lem:40}, \ref{lem:kar} and
\ref{lem:slow} yield that:
\begin{equation}\label{thar}
\min\{\lambda^4_{\kappa},\kappa\}\leq\lambda^3_{\kappa}\leq\lambda^2_{\kappa}\leq\lambda^1_{\kappa}\leq\lambda^4_{\kappa}\leq\bd_{\kappa}.
\end{equation}

Suppose $\cof(\kappa)<\kappa$.  In this case we have
$\lambda^4_{\kappa}<\kappa$ by Lemma \ref{lem:my}.  So, by
(\ref{thar}), we have that
$\lambda^{i}_{\kappa}=\lambda^1_{\kappa}$ for all $1\leq i\leq 4$.

Suppose on the other hand that $\kappa$ is a regular cardinal.  It
is enough, by (\ref{thar}), to show that
$\bd_{\kappa}\leq\lambda^3_{\kappa}$.

Let $F\in [{\cal R}(\kappa,\kappa)]^{<\bd_{\kappa}}$.  Fix $G\in
[\kappa^{\kappa}]^{\kappa}$.  We construct an
$h\in\kappa^{\kappa}$ such that $|[h\circ f=g]|<\kappa$ for every
$g\in G$ and $f\in F$. Let $\{g_{\alpha}\colon\alpha\in\kappa\}$
be an enumeration of $G$.

For each $f\in F$ let $f^*(\alpha)\in\kappa$ be such that
$\bigcup_{\xi\leq\alpha}f^{-1}(\xi)\subseteq f^*(\alpha)$ for each
$\alpha\in\kappa$. Since $|F|<\bd_{\kappa}$ there is an
$m\in\kappa^{\kappa}$ such that for every $f\in F$ we have
$|[m\leq f^{*}]|<\kappa$.

Define $h\in\kappa^{\kappa}$ inductively so that for every
$\alpha\in\kappa$ we select $h(\alpha)$ from the set
\[\kappa\setminus\left\{g_{\beta}(x)\colon
x\in\bigcup\left\{\bigcup_{\xi\leq\alpha}f^{-1}(\xi)\colon
f^*(\alpha)<m(\alpha)\right\}\ \&\ \beta\leq\alpha\right\}.\] Note
that such choices can be made since,
\[\bigcup_{\xi\leq\alpha}f^{-1}(k(\xi))\subseteq f^*(\alpha)\leq m(\alpha)\]
for every $f$ such that $f^*(\alpha)<m(\alpha)$. So,
$\bigcup\left\{\bigcup_{\xi\leq\alpha}f^{-1}(\xi)\colon
f^*(\alpha)<m(\alpha)\right\}\subseteq m(\alpha)<\kappa$.


We show that $h$ is as desired.  Fix $f\in F$ and $g_{\beta}\in
G$.  For $\xi\in [h\circ f=g_{\beta}]$ we have
\[h(f(\xi))=g_{\beta}(\xi)\in
g_{\beta}[f^{-1}(f^(\xi))].\] By definition of $h$ we must have
either $f(\xi)<\beta$ or $f^*(f(\xi))\geq m(f(\xi))$. It follows
that $|f[[h\circ f=g_{\beta}]]|<\kappa$.  By regularity and the
fact that $f\in{\cal R}(\kappa,\kappa)$, we have $|[h\circ
f=g_{\beta}]|<\kappa$.  Thus,
$\bd_{\kappa}\leq\lambda_{\kappa}^3$. Which completes the case
when $\kappa$ is regular.

It is obvious that $\cof(\kappa)\leq\lambda_{\kappa}^4$. \qed

{\sc proof of Theorem~\ref{thm:10}}

When $\kappa$ is singular Lemma~\ref{lem:my} and
Theorem~\ref{thm:0} yield that
$\cof(\kappa)\leq\lambda_{\kappa}^i\leq\cof(\kappa)^+$ for $1\leq
i\leq 4$.

Suppose now that $\kappa$ is regular.  By Lemma~\ref{lem:kar}, we
have $\lambda^4_{\kappa}\leq\bd_{\kappa}$.  In the last part of
the proof of Theorem~\ref{thm:0} we show that
$\bd_{\kappa}\leq\lambda_{\kappa}^3$ when $\kappa$ is regular.
Since $\lambda_{\kappa}=\lambda_{\kappa}^4$, we have
$\lambda_{\kappa}^i=\bd_{\kappa}$ for $1\leq i\leq 4$. \qed


\section{Proof of Theorem~\ref{thm:3} and Theorem~\ref{thm:5}}
It will be useful to define some other cardinal numbers which will be shown to be
equal to the bounding number.
\begin{description}
\item[ ]$\bd(\kappa,\cof(\kappa))=\min\{|F|\colon F\subseteq \cof(\kappa)^\kappa\ $
\newline
$\&\  (\forall g\in\cof(\kappa)^\kappa)(\exists f\in F)(|[g\leq f]|=\kappa)\}.$
\item[ ]$\bd^{bd}(\kappa,\cof(\kappa))=\min\{|F|\colon F\subseteq \cof(\kappa)^\kappa\
$
\newline
$\&\ (\forall g\in\cof(\kappa)^\kappa)(\exists f\in F)([g\leq f]\ \text{is unbounded in
$\kappa$})\}.$
\end{description}

\lem{lem:666}{$\bd_{\kappa}=\bd(\kappa,\cof(\kappa))=\bd^{bd}(\kappa,\cof(\kappa))$.}
\proof
The lemma is obvious if $\kappa$ is regular so we assume that $\kappa$ is singular.
Let $P=\{\lambda_{\alpha}\colon\alpha\in\cof(\kappa)\}$ be an increasing cofinal
sequence of regular cardinals in $\kappa$ such that $\lambda_0>\cof(\kappa)$.

We first claim that $\bd_{\kappa}\leq\bd(\kappa,\cof(\kappa))$.  Let
$F\subseteq\cof(\kappa)^{\kappa}$ witness the definition of
$\bd(\kappa,\cof(\kappa))$.  For each $f\in F$ define $f^*\in\kappa^{\kappa}$ by
$f^*(\beta)=\lambda_{f(\beta)}$.  Let $F^*=\{f^*\colon f\in F\}$ and note that
$|F^*|\leq\bd(\kappa,\cof(\kappa))$.  Pick $g\in\kappa^{\kappa}$ and define
$g^1\in\cof(\kappa)^{\kappa}$ by $g^1(\beta)=\min\{\alpha\in\cof(\kappa)\colon
g(\beta)\leq\lambda_{\alpha}\}$.   There is, by definition of
$\bd(\kappa,\cof(\kappa))$, an $f\in F$ such that
$|[g^1\leq f]|=\kappa$.  If $\beta\in [g^1\leq f]$, then
$g(\beta)\leq\lambda_{g^1(\beta)}\leq\lambda_{f(\beta)}=f^*(\beta)$.  So, $|[g\leq
f^*]|=\kappa$.  Thus, $\bd_{\kappa}\leq\bd(\kappa,\cof(\kappa))$.

We now claim that $\bd(\kappa,\cof(\kappa))\leq\bd^{bd}(\kappa,\cof(\kappa))$.  Let
$H\colon\kappa\to P$ be defined by,
$H(\beta)=\min\{\lambda_{\alpha}\colon\beta\leq\lambda_{\alpha}\}$.  Let
$S=\{\langle\beta,\zeta\rangle\in\kappa\times\kappa\colon\zeta\leq H(\beta)\}$, note
that $|S|=\kappa$.  For each $\beta\in\kappa$ let
$S_{\beta}=\{\langle\xi,\zeta\rangle\in S\colon\xi=\beta\}$.  Let
$F\subseteq\cof(\kappa)^{\kappa}$ witness the definition of
$\bd^{bd}(\kappa,\cof(\kappa))$.  For each $f\in F$ let $f^*\colon S\to\cof(\kappa)$
be defined so that $f^*[S_{\beta}]=\{f(\beta)\}$ for every $\beta\in\kappa$.  Let $F^*=\{f^*\colon f\in
F\}$, note $|F^*|\leq |F|$.  Pick
$g\in\cof(\kappa)^S$.  For every $\beta\in\kappa$ we have that $|S_{\beta}|$ is
regular and strictly larger than $\cof(\kappa)$, so there is an
$\zeta_{\beta}\in\cof(\kappa)$ such that $|S_{\beta}\cap
g^{-1}(\zeta_{\beta})|=|S_{\beta}|$.   Define $g^1\in\cof(\kappa)^{\kappa}$ so that
$g^1(\beta)=\zeta_{\beta}$ for every $\beta\in\kappa$.
There is, by definition of $\bd^{bd}(\kappa,\cof(\kappa))$, an $f\in F$ such that
$[g^1\leq f]$ is unbounded in $\kappa$.  We will be done if we show that $|[g\leq
f^*]|=\kappa$.  Let $\beta\in [g^1\leq f]$.  For $x\in S_{\beta}\cap
g^{-1}(\zeta_{\beta})$ we have
$g(x)=\zeta_{\beta}=g^1(\beta)\leq f(\beta)=f^*(x)$.  So, $S_{\beta}\cap
g^{-1}(\zeta_{\beta})\subseteq [g\leq f^*]$ for $\beta\in [g^1\leq f]$.  Since
$[g^1\leq f]$ is unbounded and $|S_{\beta}\cap
g^{-1}(\zeta_{\beta})|=|S_{\beta}|\geq\beta$ we have $|[g\leq f^*]|=\kappa$.  Thus,
$\bd(\kappa,\cof(\kappa))\leq\bd^{bd}(\kappa,\cof(\kappa))$.

We show that $\bd^{bd}(\kappa,\cof(\kappa))\leq\bd_{\kappa}$.  Let
$F\subseteq\kappa^{\kappa}$ witness the definition of $\bd_{\kappa}$.  For
each $f\in F$ let $f^*\in P^{\kappa}$ be defined by $f^*(\xi)=\min\{p\in P\colon
f(\xi)\leq p\}$.  Let $F^*=\{f^*\colon f\in F\}$.  Clearly, $|F^*|\leq |F|$.  It is
easy to check that $|F^*|$ satisfies the condition in the definition of
$\bd^{bd}(\kappa,\cof(\kappa))$.  Thus,
$\bd^{bd}(\kappa,\cof(\kappa))\leq\bd_{\kappa}$.  \qed

\noindent{\sc proof of Theorem~\ref{thm:3}.}

Let $P$ be as in  Lemma~\ref{lem:666}.
By Lemma~\ref{lem:666}, it is enough to show that
$\bd^{bd}(\kappa,\cof(\kappa))\leq\bd_{\cof(\kappa)}$.  Let
$F\subseteq\cof(\kappa)^{P}$ witness the definition of
$\bd_{\cof(\kappa)}$.  For each $f\in F$ define $f^*\in\cof(\kappa)^{\kappa}$ so that
$f^*|_{P}=f|_{P}$ and arbitrarily elsewhere.  Let $F^*=\{f^*\colon f\in
F\}$, note $|F^*|\leq |F|$.  Let $g\in\cof(\kappa)^{\kappa}$.  We may find an $f\in F$
such that $[g|_{P}\leq f|_P]=\cof(\kappa)$.  It follows that $[g\leq f^*]$ is unbounded
in $\kappa$.  Thus, $\bd^{bd}(\kappa,\cof(\kappa))\leq\bd_{\cof(\kappa)}$

Therefore, $\bd_{\kappa}\leq\bd_{\cof(\kappa)}$.\qed


\noindent{\sc proof of Theorem~\ref{thm:5}.}

Let $\{\lambda_{\alpha}\colon\alpha\in\cof(\kappa)\}$ be an
increasing cofinal sequence of regular cardinals in $\kappa$.

\medskip

Suppose $\kappa<\bd_{\cof(\kappa)}$.  Let $F\subseteq
\kappa^{\kappa}$ and $|F|=\cof(\kappa)$.  Let
$\{f_{\xi}\colon\xi\in\cof(\kappa)\}$ be an enumeration of $F$. We
find a $h\in\kappa^{\kappa}$ such that $f[[h\leq f]]$ is bounded
in $\kappa$ for every $f\in F$.  For each $\alpha\in\kappa$ let
$g_{\alpha}\in\cof(\kappa)^{\cof(\kappa)}$ be defined so that
$\lambda_{g_{\alpha}(\xi)}>f_{\xi}(\alpha)$. Since
$\kappa<\bd_{\cof}(\kappa)$ there is a
$j\in\cof(\kappa)^{\cof(\kappa)}$ such that $|[j\leq
g_{\alpha}]|<\cof(\kappa)$ for every $\alpha\in\kappa$.  For each
$\alpha\in\kappa$ let $\beta_{\alpha}\in\cof(\kappa)$ be such that
\begin{equation}\label{tarq}
\beta_{\alpha}>\sup\{g_{\alpha}(\xi)\colon g_{\alpha}(\xi)\geq
j(\xi)\}. \end{equation}  Define $h\in\kappa^{\kappa}$ so that
$h(\alpha)=\lambda_{\beta_{\alpha}}$.

We show that $f[[h\leq f]]$ is bounded in $\kappa$ for every $f\in
F$.  Fix $\xi\in\cof(\kappa)$. Suppose $h(\alpha)\leq
f_{\xi}(\alpha)$.  We now have $\lambda_{\beta_{\alpha}}\leq
f_{\xi}(\alpha)<\lambda_{g_{\alpha}(\xi)}$.  It follows that
$\beta_{\alpha}<g_{\alpha}(\xi)$.  Thus, by (\ref{tarq}),
$g_{\alpha}(\xi)<j(\xi)$.  So,
$f_{\xi}(\alpha)<\lambda_{g_{\alpha}(\xi)}<\lambda_{j(\xi)}$.
Thus, $f_{\xi}[[h\leq f_{\xi}]]$ is bounded in $\kappa$.
Therefore, $\lambda^4_{\kappa}>\cof(\kappa)$.

\medskip

Now suppose $\bd_{\cof(\kappa)}<\kappa$.  Let
$\Gamma^*\subseteq\cof(\kappa)^{\cof(\kappa)}$ be such that
$|\Gamma^*|=\bd_{\cof(\kappa)}$ and for every
$f\in\cof(\kappa)^{\cof(\kappa)}$ there is a $\gamma^*\in\Gamma^*$
such that $|[f\leq\gamma^*]|=\cof(\kappa)$. Let
$\{\gamma^*_{\xi}\colon\xi\in\bd_{\cof(\kappa)}\}$ be a well
ordering of $\Gamma^*$.  Inductively, define
$\Gamma=\{\gamma_{\xi}\in\cof(\kappa)^{\cof(\kappa)}\colon\xi\in\bd_{\cof(\kappa)}\}$
so that for every $\xi\in\bd_{\cof(\kappa)}$ we have
$|[\gamma_{\xi}\leq\gamma^*_{\alpha}]|<\cof(\kappa)$ and
$|[\gamma_{\xi}\leq\gamma_{\alpha}]|<\cof(\kappa)$ for every
$\alpha<\xi$.  Notice that $\Gamma$ has the property that
\begin{equation}\label{eq:lsl} \left(\forall M\in[\Gamma]^{\bd_{\cof(\kappa)}}\right)\left(\forall f\in\cof(\kappa)^{\cof(\kappa)}\right)(\exists m\in
M)(|[f\leq m]|=\cof(\kappa)).
\end{equation}

For each $\alpha\in\cof(\kappa)$ let
$f_{\alpha}\colon\Gamma\to\kappa$ be defined by
$f_{\alpha}(\gamma)=\lambda_{\gamma(\alpha)}$.  Let
$F=\{f_{\alpha}\colon\alpha\in\cof(\kappa)\}$.

We claim that for every $A\in[\Gamma]^{\Gamma}$ there is an $f\in
F$ such that $f[A]$ is unbounded in $\kappa$.  By way of
contradiction assume that there is an $A\in[\Gamma]^{\Gamma}$ such
that $f_{\alpha}[A]$ is bounded in $\kappa$ for every
$\alpha\in\cof(\kappa)$. Then there exists for every
$\alpha\in\cof(\kappa)$ a $\beta_{\alpha}\in\cof(\kappa)$ such
that
$\lambda_{\gamma(\alpha)}=f_{\alpha}(\gamma)<\lambda_{\alpha_{\beta}}$
for every $\gamma\in A$.  In particular, we have that
$\gamma(\alpha)<\beta_{\alpha}$ for every $\gamma\in A$ and every
$\alpha\in\cof(\kappa)$, this contradicts (\ref{eq:lsl}).  So, we
have the claim.

Since $|\Gamma|<\kappa$, we may identify $\Gamma$ with a subset of
$\kappa$.  For every $f\in F$ define $f^*\in\kappa^{\kappa}$ so
that $f^*(\beta)=f(\beta)$ if $\beta\in\Gamma$ and $f^*(\beta)=0$
if $\beta\notin\Gamma$.  Let $F^*=\{f^*\colon f\in F\}$. Since
$|F^*|=\cof(\kappa)$, we will be done if we show that for every
$g\in\kappa^{\kappa}$ there is an $f^*\in F^*$ such that
$f^*[f^*\leq g]$ is unbounded in $\kappa$. Let
$g\in\kappa^{\kappa}$. Since $|\Gamma|$ is regular and
$\cof(\kappa)<|\Gamma|$ there is a $A\subseteq\Gamma$ such that
$g[A]$ is bounded in $\kappa$.  By the claim from the previous
paragraph, there is an $f\in F$ such that $f[A]$ is unbounded in
$\kappa$.  It follows that $f[[g|_{\Gamma}\leq f]]$ is unbounded
in $\kappa$.  Thus, $f^*[f^*\leq g]$ is unbounded in $\kappa$.
Therefore, $\lambda_{\kappa}^4\leq\cof(\kappa)$.

That $\cof(\kappa)\leq\lambda^4_{\kappa}$ follows from
Theorem~\ref{thm:0}.\qed

\section{Proof of Theorem~\ref{thm:00}}
\lem{lem:60}{$\shel^{-}(\kappa,\kappa)\leq\bd_{\kappa}$.  If
$\kappa$ is regular, then
$\shel^{-}(\kappa,\kappa)=\bd_{\kappa}$.} \proof Let
$F\subseteq\kappa^{\kappa}$ and suppose
$|F|<\shel^{-}(\kappa,\kappa)$.  We find an $h\in\kappa^{\kappa}$
such that $|[h\leq f]|<\kappa$ for every $f\in F$.

For each $f\in F$ define $f_1\in{\cal S}_{\kappa}$ so that
$f_1(\xi)=\{\beta\colon\beta\leq f(\xi)+1\}$.  Let $F_1=\{f_1\colon f\in F\}$.  Since
$|F_1|\leq |F|<\shel^{-}(\kappa,\kappa)$, there is an $h\in\kappa^{\kappa}$ such that
$|\{\xi\colon h(\xi)\in f_1(\xi)\}|<\kappa$ for every $f_1\in F_1$.

Fix $f\in F$.  We claim that $|[h\leq f]|<\kappa$.  Let $\xi\in\kappa$ be such that
$h(\xi)\leq f(\xi)$.  Then,
$h(\xi)\in f_1(\xi)$.  So, $\xi\in\{\xi\colon h(\xi)\in f_1(\xi)\}$.  Hence,
$|[h\leq f]|<\kappa$.

Thus, $\shel^{-}(\kappa,\kappa)\leq\bd_{\kappa}$.

\medskip

Suppose now that $\kappa$ is regular.  Let $F\subseteq {\cal S}_{\kappa}$ and suppose
$|F|<\bd_{\kappa}$.  By regularity, there is for every $f\in F$ a
$f^*\in\kappa^{\kappa}$ such that $f(\alpha)\subseteq f^*(\alpha)$ for every
$\alpha\in\kappa$.  Since $|F|<\bd_{\kappa}$, there is a $g\in\kappa^{\kappa}$ such
that $|[g\leq f^*]|<\kappa$ for every $f\in F$.  By our choice of $f^*$ we have that
$\{\xi\colon g(\xi)\in f(\xi)\}\subseteq [g\leq f^*]$.  Thus, $|\{\xi\colon g(\xi)\in
f(\xi)\}|<\kappa$.  So, $\shel^{-}(\kappa,\kappa)\geq\bd_{\kappa}$.
\qed


\lem{lem:200}{Let $F\in [{\cal S}_{\kappa}]^{<\bd_{\kappa}}$.  There
is a bijection
$k\in\kappa^{\kappa}$ such that for every $f\in F$ there is an $A_{f}\in
[\kappa]^{<\kappa}$ such that
\[|\bigcup_{\xi\in \alpha\setminus A_f}f(k(\xi))|<\kappa\]
for every
$\alpha\in\kappa$}
\proof
For every $f\in F$ define $f^*\in\kappa^{\kappa}$ by $f^*(\alpha)=|f(\alpha)|$.
Let $F^*=\{f^*\colon f\in F\}$.  Since $|F^*|\leq |F|<\bd_{\kappa}$, there is a
$g\in\kappa^{\kappa}$ such that
$|[g\leq f^*]|<\kappa$ for every $f\in F$. Notice that we may
assume $g$ has unbounded range, since if we define $m\in\kappa^{\kappa}$ by
$m(\xi)=\max\{g(\xi),\xi\}$, then we will have
$[m\leq f^*]\subseteq [g\leq f^*]$ for every $f\in F$.  Let $A^*_f=[g\leq f^*]$.

Define an injection
$k^*\in\kappa^{\kappa}$ so that
$\max\{\alpha,g(\alpha)\}\leq k^*(\alpha)$
for every
$\alpha\in\kappa$.  Since
$|k^{*}[\kappa]|=\kappa$, there is an increasing onto function
$h\colon k^{*}[\kappa]\to\kappa$.  Let $k=(k^{*})^{-1}\circ h^{-1}$.  Let
$A_f=k^{-1}(A^*_f)$.  Clearly, $A_{f}\in [\kappa]^{<\kappa}$.

We claim $A_f$ and $k$ are as desired for every $f\in F$.  Fix $f\in F$.  Let
$\gamma\in\kappa$.  Consider
$\alpha\in\gamma$.  Since $h$ is increasing and $g$ has unbounded range, there is
a $\beta_{\gamma}\in\kappa$ such that
$h^{-1}(\alpha)\leq h^{-1}(\gamma)\leq g(\beta_{\gamma})$.  By definition of
$k^{*}$, we have
$(k^{*})^{-1}(h^{-1}(\alpha))\neq\zeta$ for any
$\zeta\in\kappa$ such that $g(\zeta)>g(\beta_{\gamma})$, since otherwise we would have
\[g(\beta_{\gamma})\geq
h^{-1}(\alpha)=k^*((k^*)^{-1}(h^{-1}(\alpha)))=k^{*}(\zeta)\geq\max\{\zeta,g(\zeta)\},\]
a contradiction.    So,
$k(\alpha)\neq\zeta$ for all $\alpha\in\gamma$ and all
$\zeta\in\kappa$ such that $g(\zeta)>g(\beta_{\gamma})$.  Let $\alpha\in
\gamma\setminus A_f$.  Since $A_f=k^{-1}(A^*_f)$ and $\alpha\notin A_f$, we have
$k(\alpha)\notin A^*_f$.  Thus,
$|f(k(\alpha))|=f^*(k(\alpha))\leq g(k(\alpha))\leq
g(\beta_{\gamma})$.  Therefore,
$|\bigcup_{\xi\in \gamma\setminus A_f}f(k(\xi))|<\kappa.$
\qed

{\sc Proof of Theorem~\ref{thm:00}}

It is enough, by Lemma~\ref{lem:60}, to show that
$\min\{\kappa,\bd_{\kappa}\}\leq\shel^{-}(\kappa,\kappa)$.  Let
$F\in [{\cal S}_{\kappa}]^{<\min\{\kappa,\bd_{\kappa}\}}$.  We
construct an $h\in\kappa^{\kappa}$ such that $|\{\xi\colon
h(\xi)\in f(\xi)\}|<\kappa$ for every $f\in F$.

By Lemma~\ref{lem:200} there is a bijection $k\in\kappa^{\kappa}$
such that for each $f\in F$ there is an $A_f\in
[\kappa]^{<\kappa}$ such that for every $\alpha\in\kappa$ we have
\[|\bigcup_{\xi\in\alpha\setminus A_f}f(k(\xi))|<\kappa.\]  For each
$f\in F$ let $f^*(\alpha)=|\bigcup_{\xi\in\alpha\setminus A_f}f(k(\xi))|$ for each
$\alpha\in\kappa$.  Since
$|F|<\bd_{\kappa}$, there is a $m\in\kappa^{\kappa}$ such that for every $f\in F$ we
have
$|[m\leq f^*]|<\kappa$.

Define $h\in\kappa^{\kappa}$ inductively so for every $\alpha\in\kappa$
\[h(k(\alpha))\in\kappa\setminus\bigcup\{f(k(\beta))\colon
\beta\in\alpha\setminus A_f\ \&\ f^*(\alpha)\leq m(\alpha)\}.\] Note that such choices
can be made since
\[|\bigcup_{\beta\in\alpha\setminus
A_f}f(k(\beta))|=f^*(\alpha)\leq m(\alpha)<\kappa\] for every
$f\in F$ such that $f^*(\alpha)<m(\alpha)$.  Thus,
\[|\bigcup\{f(k(\beta))\colon \beta\in\alpha\setminus A_f\ \&\
f^*(\alpha)\leq
m(\alpha)\}|\leq\max\{\alpha,m(\alpha),|F|\}<\kappa\] so the
choice can be made.

We show that $h$ is as desired.  Fix $f\in F$.
If $h(\xi)\in f(\xi)$, then
\[h(k(k^{-1}(\xi))=h(\xi)\in f(\xi)=f(k(k^{-1}(\xi)).\]

By definition of $h$ we must have
$f^*(k^{-1}(\xi))>m(k^{-1}(\xi))$ or $k^{-1}(\xi)\in A_f$.  It follows that,
$|\{k^{-1}(\xi)\colon h(\xi)\in f(\xi)\}|<\kappa$.  Since $k$ is a bijection, we have
$|\{\xi\colon h(\xi)\in f(\xi)\}|<\kappa$.  Thus, $h$ is as desired.
Therefore, $\min\{\kappa,\bd_{\kappa}\}\leq\shel^{-}(\kappa,\kappa)$.\qed

\section{\sc proof of Theorem~\ref{thm:1}}
By Theorem~\ref{thm:5}, it is enough to find a model of ZFC such
that $\bd_{\cof(\cuum)}<\cuum$.

Let $M$ be a countable transitive model of ZFC+GCH. Let ${\cal
P}\in M$ be the poset of partial functions with finite domains
from $\omega^{M}_{\omega_1}$ into $2$ ordered by reverse
inclusion. Let $G$ be an $M$ generic filter in {\cal P}.  We claim
that $(\bd_{\cof(\cuum)}<\cuum)^{M[G]}$. Since ${\cal P}$
satisfies the countable chain condition, by \cite[Thm.
9.2.11]{cibook}, we have $\omega_1^{M}=\omega_1^{M[G]}$.  Since we
have GCH in $M$, we have $(|\omega_1^{\omega_1}|=\omega_2)^M$.  So
there is a bijection $h\colon\omega_1^{\omega_1}\to\omega_2$ in
$M$.  Since being a bijection is an absolute property we have that
$h\colon M\cap(\omega_1^{\omega_1})\to\omega_2$ is a bijection in
$M[G]$. Thus, $(|M\cap\omega_1^{\omega_1}|=\omega_2)^{M[G]}$.  We
claim that $M\cap\omega_1^{\omega_1}$ witnesses the definition of
$\bd_{\omega_1}$ in $M[G]$.  Let $g\in
(\omega_1^{\omega_1})^{M[G]}$.  Since
$\omega_1^{M[G]}=\omega_1^M\in M$, there is, by \cite[Cor.
9.2.9]{cibook}, a function $h$ in $M$ such that
$h\colon\omega_1\to[\omega_1]^{\leq\omega}$ and $g(x)\in h(x)$ for
every $x\in\omega_1$.  Define in $M$ the function
$h^*\colon\omega_1\to\omega_1$ by $h^*(x)=\sup(h(x))+1$.  Now
$h^*\in M\cap\omega_1^{\omega_1}$ and $g<h^*$.  So the claim is
established.  Thus, $(\bd_{\omega_1}=\omega_2)^{M[G]}$.  Since GCH
holds in $M$ it can be shown that
$|\omega_{\omega_1}^{\omega}|=\omega_{\omega_1}$. So by \cite[Cor.
9.4.9]{cibook} we have $(\cuum=\omega_{\omega_1})^{M[G]}$.  Thus,
$(\cof(\cuum)=\omega_1)^{M[G]}$. So,
$(\bd_{\cof(\cuum)}<\cuum)^{M[G]}$. \qed

\begin{thebibliography}{22}
\bibitem{BJ}
K. Bartoszynski and H. Judah, {\it Set Theory: on the structure of the real line},
A.K. Peters, 1995.

\bibitem{cibook}
K.~Ciesielski, {\it Set Theory for the Working Mathematician}, London Math.
Soc. student texts {\bf 39}, Cambridge Univ. Press 1997.

\bibitem{CN}
K.~Ciesielski and T.~Natkaniec, {\em Algebraic properties of the class
of Sierpi\'{n}ski-Zygmund functions},
Topology Appl. {\bf 79} (1997), 75--99.

\bibitem{kech}
A.~Kechris, {\it Classical Descriptive Set Theory}, Graduate Texts
in Mathematics {\bf 156}, springer-Verlag 1995.

\bibitem{SH}
S.~Shelah, {\em On Cielsielski's problems}, J. Appl. Anal., {\bf
3} (2) (1997), 191--209.

\bibitem{sezy}
W.~Sierpi\'{n}ski and A.~Zygmund, {\it Sur une fonction qui est
discontinue sur tout ensemble de puissance du continu}, Fund.
Math. {\bf 4} (1923), 316--318.



\end{thebibliography}
\end{document}
