Transversals and Elementary Submodels

\( \newcommand{\wsat}{\mathrm{wsat}} \newcommand{\GH}{\mathrm{GH}} \newcommand{\REG}{\mathrm{REG}} \newcommand{\Ch}{\mathrm{Ch}} \newcommand{\reg}{\mathrm{reg}} \newcommand{\rk}{\mathrm{rk}} \newcommand{\ot}{\mathrm{ot}} \newcommand{\pcf}{\mathrm{pcf}} \newcommand{\tcf}{\mathrm{tcf}} \newcommand{\cf}{\mathrm{cf}} \newcommand{\ran}{\mathrm{ran}} \newcommand{\dom}{\mathrm{dom}} \newcommand{\nacc}{\mathrm{nacc}} \newcommand{\acc}{\mathrm{acc}} \newcommand{\Tr}{\mathrm{Tr}} \)
I want to use this post to prove some facts about the relationship between almost disjoint transversals and elementary submodels that will be useful later on. As usual, we assume that $J$ is an ideal on a cardinal $\kappa$, and that $J$ is $\sigma$-based where $\kappa^{<\sigma}<\mu$ and $\aleph_0\leq\sigma$. First, we need a proposition from a previous post:

Proposition: Suppose that $F$ is a $J$-adt. Then for any $f\in{}^\kappa\mu$, the set $\{g\in F : \neg(g\neq_J f)\}$ has cardinality at most $\kappa^{<\sigma}$.

Now let's suppose that $\chi$ is a sufficiently large regular cardinal, and let $\mathfrak{A}=(H(\chi), \in, <_\chi)$. Let $\lambda$ be a cardinal with $\mu\leq\lambda$, and fix $M\prec\mathfrak{A}$ such that $\lambda+1\subseteq M$ with $|M|=\lambda$ and $J\in M$. Suppose that $T_J(\mu)>\lambda$, and let $\mathcal{F}$ be a $J$-adt with $|\mathcal{F}|>\lambda$ such that $F\in M$. Note that if $T_J(\mu)>\lambda$, then $M$ knows this and can provide us with a witness.

Lemma: There is a function $f^*\in \mathcal{F}$ such that $f^*\neq_J g$ for each $g\in M\cap{}^\kappa\mu$.

Proof: This follows directly from the previous proposition. Since $\kappa^{<\sigma}<|M\cap{}^\kappa\mu|$, we know that $\{f\in\mathcal{F} : (\exists g\in {}^\kappa\mu\cap M)(\neg(f\neq_J g))\}$ has size $\lambda<|\mathcal{F}|$.

Lemma: Suppose that $A\subseteq \kappa$ is $J$-positive, and $B\in[\mu]^{\leq\kappa^{<\sigma}}$, then $|\{f\in\mathcal{F} : f^{-1}[B]\cap A\in J^+\}|\leq\kappa^{<\sigma}$.

Proof: First note that if $f\in {}^\kappa\mu$ is such that $f^{-1}[B]\cap A\in J^+$, then we can find $B_f\subseteq f^{-1}[B]\cap A$ such that $|B_f|<\sigma$ and $B_f\in J^+$. So then, there are $\kappa^{<\sigma}$-many possible options for the sets $B_f$. Now suppose that we are given a collection of more than $\kappa^{<\sigma}$ many $f\in {}^\kappa\mu$ with the property that $f^{-1}[B]\cap A\in J^+$. Then there will be a set of $<\kappa^{<\sigma}$ many such $f$ which share the same $B_f=:C$. On the other hand, for each such $f$, $f[C]\subseteq B$ and $|B|\leq\kappa^{<\sigma}$, which means that each $f\upharpoonright C$ can take on at most $\kappa^{<\sigma}$ many values. So there are more than $\kappa^{<\sigma}$-many $f$ in our collection which agree on $C\in J^+$. Thus, $|\{f\in\mathcal{F} : f^{-1}[B]\cap A\in J^+\}|\leq\kappa^{<\sigma}$.

Tying all of this together, suppose that we have an $f^*\in \mathcal{F}$ such that $f\neq_J g$ for each $g\in {}^\kappa\mu\cap M$. If $A\subseteq\kappa$ is such that $\ran(f\upharpoonright A)\in M$, $A\in J$.

To see this, suppose otherwise and let $B=\ran(f\upharpoonright A)$. Since $A, B\in M$, we know that $$\mathcal{F}_0:=\{f\in\mathcal{F} : f^{-1}[B]\cap A\in J^+\}\in M$$ since it's definable from $\mathcal{F}$, $A$, $B$, and $J$, all of which are in $M$. On the other hand, $|B|\leq\kappa\leq\kappa^{<\sigma}$, it follows from the above proposition that $\mathcal{F}_0|\leq\kappa^{<\sigma}$. Since $\mathcal{F}_0\in M$, $|\mathcal{F}_0|<\lambda$, and $\lambda+1\subseteq M$, we can find a function $g\in M$ which is a bijection from $|\mathcal{F}_0|$ to $\mathcal{F}_0$. As $|\mathcal{F}_0|\subseteq M$, this immediately gives us that $\mathcal{F}_0\subseteq M$ and so $f^*\upharpoonright A\in M$ (since $f^*\upharpoonright A\in \mathcal{F}_0$ as $(f^*\upharpoonright A)^{-1}[B]\cap A=A\in J^+$) which contradicts our choice of $f^*$.

With these propositions out of the way, we will need a few more facts about elementary submodels coming from pcf theory. That will follow in the next post, and then we can get to repairing the argument from section 6 of 410 (and slightly strengthening the result).

$T^4_J(\mu)$ and some motivation

\( \newcommand{\wsat}{\mathrm{wsat}} \newcommand{\GH}{\mathrm{GH}} \newcommand{\REG}{\mathrm{REG}} \newcommand{\Ch}{\mathrm{Ch}} \newcommand{\reg}{\mathrm{reg}} \newcommand{\rk}{\mathrm{rk}} \newcommand{\ot}{\mathrm{ot}} \newcommand{\pcf}{\mathrm{pcf}} \newcommand{\tcf}{\mathrm{tcf}} \newcommand{\cf}{\mathrm{cf}} \newcommand{\ran}{\mathrm{ran}} \newcommand{\dom}{\mathrm{dom}} \newcommand{\nacc}{\mathrm{nacc}} \newcommand{\acc}{\mathrm{acc}} \newcommand{\Tr}{\mathrm{Tr}} \)
Last time we defined the cardinals: $$ T^4_J(\mu)=\min\{\sup T^2_{J+(\kappa\setminus A_n)}: A_n\subseteq A_{n+1}\subseteq\kappa=\bigcup_{n<\omega}A_n, A_n\notin J\}. $$ $$ T^5_J(\mu)=\sup\{\sup T^2_{J+(\kappa\setminus A_n)}: A_n\subseteq A_{n+1}\subseteq\kappa=\bigcup_{n<\omega}A_n, A_n\notin J\}. $$ The cardinal $T^4_J(\mu)$ appears in section 6 of Sh410, and there Shelah claims that $T_J(\mu)\leq T^4_J(\mu)$. Unfortunately, it seems that the proof only works if we replace the $\min$ with a $\sup$, and so we're also defining $T^5_J(\mu)$. In this post I wanted to briefly talk about why we want to relate $T_J(\mu)$ to pcf-theoretic cardinals, and then discuss the (potentially wrong) definitions of the above defined cardinals.

I first want to recall that, assuming $J$ is a $\sigma$-based ideal on a cardinal $\kappa$ such that $\kappa^{<\sigma}<\mu$, we know that $T_J(\mu)$ is actually the cardinality of any maximal $J$-adt $\mathcal{F}$, which is a natural thing to be curious about. On the other hand, we have quite a few tools to deal with pcf-theoretic objects, so situating $|\mathcal{F}|$ among pcf-theoretic objects is useful insofar as this potentially allows us to put bounds on $|\mathcal{F}|$. Beyond that, let's suppose that $\kappa\leq \theta<\sigma$, so $J=[\kappa]^{<\theta}$ is a $\sigma$-based ideal on $\kappa$. Let $$ AD_J(\mu)=\sup\{|\mathcal{F}|: (\forall A\neq B\in\mathcal{F})(A,B\in[\mu]^{\kappa} \wedge A\neq_J B )\}. $$ In other words, $AD_J(\mu)$ is the supremum of the cardinality of $\theta$-almost disjoint families of subsets of $\mu$ with size $\kappa$. Note that given any such family $\mathcal{F}$, if we let $f_A: \kappa\to \mu$ be a faithful enumeration of $A$ for each $A\in \mathcal{F}$, then $\{f_A : A\in \mathcal{F}\}$ is a $J$-adt. On the other hand, if $\mathcal{F}$ is a $J$-adt, let $A_f=\{(i,f(i)) : i<\kappa\}$ be the graph of $f$ for each $f\in\mathcal{F}$. Then the family $\{A_f : f\in \mathcal{F}\}$ is a $\theta$-almost disjoint family. Thus, $T_J(\mu)=AD_J(\mu)$ for the above $J$. Here we see that relating $AD_J(\mu)$ to pcf-theoretic objects continues the trend in much of Shelah's work of connecting cardinals related to collections of sets (e.g. covering numbers) to cardinals related to functions (e.g. pseudo powers).

Now, back to those $T^4$ and $T^5$ numbers. One thing I want to note is that neither of the proofs given in section 6 of 410 work (as written) with the given definition of $T^4_J(\mu)$. Another thing I want to talk about is that given ideals $I\subseteq J$ on $\kappa$, we have that $T^2_I(\mu)\leq T^2_J(\mu)$. To see this, suppose that $\lambda$ is weakly $I$-representable as witnessed by the block sequence $\langle E(i) : i<\kappa\rangle$, so $\lambda\leq\max\pcf(\bigcup_{i\in A} E(i))$ for every $A\in I^+$. Since any $J$-positive set is $I$-positive as well, it follows that $\lambda\leq\max\pcf(\bigcup_{i\in A} E(i))$ for any $A\in J^+$ as well and thus that $\lambda$ is weakly $J$-representable. The inequality follows.

With this in mind, now note that if $A_0\subseteq A_1$, then the ideal $J+(\kappa\setminus A_0)$ contains the set $\kappa\setminus A_1$ since $\kappa\setminus A_1\subseteq\kappa\setminus A_0$. Thus, $J+(\kappa\setminus A_1)\subseteq J+(\kappa\setminus A_0)$ and so $T_{J+\kappa\setminus A_1}(\mu)\leq T_{J+\kappa\setminus A_0}$. But this means that given a sequence of sets $A_n\subseteq A_{n+1}\subseteq\kappa=\bigcup_{n<\omega}A_n$ with each $A_n\notin J$, the cardinal $$ \sup \{T^2_{J+(\kappa\setminus A_n)}:n<\omega\} $$ is just $T^2_{J+\kappa\setminus A_0}$. This means that $$ T^4_J(\mu)=\min\{\sup T^2_{J+(\kappa\setminus A_n)}: A_n\subseteq A_{n+1}\subseteq\kappa=\bigcup_{n<\omega}A_n, A_n\notin J\}=\min\{T^2_{J+\kappa\setminus A}: A\notin J\}. $$ $$ T^5_J(\mu)=\sup\{\sup T^2_{J+(\kappa\setminus A_n)}: A_n\subseteq A_{n+1}\subseteq\kappa=\bigcup_{n<\omega}A_n, A_n\notin J\}=\sup\{T^2_{J+\kappa\setminus A}: A\notin J\}. $$ I'm not entirely sure if this is a mistake on my part in not reading the definition correctly or getting an inequality reversed, or an oversight in Sh410. Either way, I don't know what the correct definition of $T^4_J(\mu)$ should actually be in order to make all of the claims in section 6 go through. With that said, my goal is to now repair the proof of the inequality $T_J(\mu)\leq T^4_J(\mu)$ in that section and use that to figure out what teh right version of $T^4_J(\mu)$ should be given the proof.

More on T_J numbers

\( \newcommand{\wsat}{\mathrm{wsat}} \newcommand{\GH}{\mathrm{GH}} \newcommand{\REG}{\mathrm{REG}} \newcommand{\Ch}{\mathrm{Ch}} \newcommand{\reg}{\mathrm{reg}} \newcommand{\rk}{\mathrm{rk}} \newcommand{\ot}{\mathrm{ot}} \newcommand{\pcf}{\mathrm{pcf}} \newcommand{\tcf}{\mathrm{tcf}} \newcommand{\cf}{\mathrm{cf}} \newcommand{\ran}{\mathrm{ran}} \newcommand{\dom}{\mathrm{dom}} \newcommand{\nacc}{\mathrm{nacc}} \newcommand{\acc}{\mathrm{acc}} \newcommand{\Tr}{\mathrm{Tr}} \)
The goal of this post is to relate pcf cardinals to the cardinal $T_J(\mu)$ that we defined in the previous post. Throughout, we will assume that $\kappa$ and $\mu$ are cardinals, and $J$ is a $\sigma$-based ideal on $\kappa$ such that $\kappa^{<\sigma}<\mu$. Recall the cardinals we're interested in:

$T_J(\mu)=\sup\{|F| : F\subseteq{}^\kappa\mu\text{ is a }J\text{-adt}\}$
$T^2_J(\mu)=\sup\{\lambda : \lambda\text{ is weakly }J\text{-representable}\}$
$T^3_J(\mu)=\sup\{\lambda : \lambda\text{ is }J\text{-representable}\}$

First, we establish a couple of facts about almost disjoint transversals and also show how to leverage the $\sigma$-based assumption.

Proposition: Suppose that $F$ is a $J$-adt. Then for any $f\in{}^\kappa\mu$, the set $\{g\in F : \neg(g\neq_J f)\}$ has cardinality at most $\kappa^{<\sigma}$.

Proof: Fix $F\subseteq{}^\kappa\mu$, and suppose that $f\in{}^\kappa\mu$. Note that if $g$ is in $F$ and $\neg(g\neq_J f)$, then the set $A^f_g=\{i\in \kappa : f(i)=g(i)\}\in J^+$. Since $J$ is $\sigma$-based, we may assume that $A^f_g\in[\kappa]^{<\sigma}$. Thus, there are only $\kappa^{<\sigma}$-many functions $g\in F$ such that $A^f_g\in J^+$ since $A^f_{g_1}=A^f_{g_2}\in J^+$ means that $g_1$ and $g_2$ agree on a $J$-positive set.

Proposition: The sup in $T_J(\mu)$ is achieved by a maximal family, and every maximal family has the same cardinality.

Proof: It suffices to show that, for any maximal $J$-adt $F$ and any $J$-adt family $G$, we have that $|F|\geq|G|$. With that in mind, fix a maximal $J$-adt $F\subseteq{}^\kappa\mu$ and a $J$-adt family $G$. For each $f\in G$, there is some $\Phi(f)$ such that $\neg(f\neq_J\Phi(f))$ since $F$ is maximal. By the previous lemma, we know that $|\Phi^{-1}[g]|\leq\kappa^{<\sigma}$ and thus that $|G|\leq\kappa^{<\sigma}\times |F|$. Since the constant functions form a $J$-adt, it follows that $$|G|\leq\kappa^{<\sigma}\times\mu<\mu\times\mu=\mu\leq|F|.$$

Next, we show that $T^2_J(\mu)$ and $T^3_J(\mu)$ are actually the same cardinal. Since this is mostly standard pcf tricks, I'm just going to sketch the argument and leave detail checking to less lazy folks.

Proposition: $T^2_J(\mu)=T^3_J(\mu)$

Proof: Since any $J$ representable cardinal is also weakly representable, it's clear that $T^3_J(\mu)\leq T^2_J(\mu)$. So let $\lambda$ be weakly representable as witnessed by $\langle E(i) : i< \kappa\rangle$. Since we'd like to show that $T^3_J(\mu)\geq \lambda$, we may replace $\lambda$ with the potentially larger cardinal $\lambda=\min\{\max\pcf(\bigcup_{i\in A}E(i)): A\in J^+\}$. Let $E=\bigcup_{i< \kappa}E(i)$, and note then that $\lambda\in \pcf(E)$ so we can fix a generator $B_\lambda[E]$ for $\lambda$. Now, let $E(i)=\{\lambda_{i,l} : l< n(i)\}$ and define $\lambda'_{i,l}$ as follows. If $\lambda_{i,l}\in B_\lambda[E]$, then we set $\lambda'_{i,l}=\lambda_{i,l}$. Otherwise, we let $u=\{(i,l): \lambda_{i,l}\notin B_\lambda[E]\}$ and set $$ I=\{v\subseteq u : \pcf(\{\lambda_i,l : (i,l)\in v\})\subseteq\lambda\}, $$
which is the pullback of $J_{< \lambda}[E\setminus B_\lambda[E]]$ to $u$. In particular, we know that $\prod_{(i,l)\in u}\lambda_{i,l}/I$ is $\lambda^+$-directed by some standard pcf theory since $J_{< \lambda}[E\setminus B_\lambda[E]]=J_{< \lambda^+}[E\setminus B_\lambda[E]]$. Using that, we can inductively define a $<_J$-increasing sequence $\langle f_\alpha : \alpha<\lambda\rangle$ with $<_J$-eub $f$. So defining $\lambda'_{i,l}=f(i,l)$ for $(i,l)\in u$, we get that $\tcf\prod_{(i,l)\in u}\lambda'_{i,l}/I=\lambda$. Set $E'(i)=\{\lambda'_{i,l}: l< n(i)\}$, then we claim that $\langle E'(i) : i<\kappa\rangle$ witnesses that $\lambda$ is $J$-representable.

To see this, one can check that $\max\pcf(\bigcup_{i<\kappa}E'(i)))=\lambda$. On the other hand, if $A\in J^+$, then $\lambda\in \pcf(\bigcup_{i\in A}E(i))$ again by construction. So the claim follows.

Proposition: $T^3_J(\mu)\leq T_J(\mu)$.

Proof: Suppose that $\lambda$ is $J$-representable as witnessed by $\langle E(i) : i< \kappa\rangle$, and let $E=\bigcup_{i< \kappa} E(i)$. Let $\langle f_\alpha : \alpha< \lambda$ be increasing and cofinal in $\prod E/J_{< \lambda}[E]$. Now let $Y={}^{< \omega}(\mu+1)$ and for each $\alpha< \lambda$, define $g_\alpha\in{}^\kappa Y$ by $$ g_\alpha(i)=\langle \lambda_{i,0},\ldots, \lambda_{i,n(i)}, f_\alpha(\lambda_{i,0}),\ldots f_\alpha(\lambda_{i,n(i)})\rangle. $$ Then one can check that $\{g_\alpha : \alpha<\lambda\}$ is a $J$-adt.

At this point, we know that $T^2_J(\mu)=T^3_J(\mu)\leq T_J(\mu)$. We now define two more pcf-theoretic cardinals in order to get a better picture of how $T_J(\mu)$ sits in relation to pcf theoretic objects. $$ T^4_J(\mu)=\min\{\sup T^2_{J+(\kappa\setminus A_n)}: A_n\subseteq A_{n+1}\subseteq\kappa=\bigcup_{n<\omega}A_n, A_n\notin J\}. $$ $$ T^5_J(\mu)=\sup\{\sup T^2_{J+(\kappa\setminus A_n)}: A_n\subseteq A_{n+1}\subseteq\kappa=\bigcup_{n<\omega}A_n, A_n\notin J\}. $$ I want to point out that in 410, Shelah only defines the cardinal $T^4_J(\mu)$, but we need to define $T^5_J(\mu)$ because one of the proofs in section 6 requires the sup on the outside. Our goal now will be to show that $$T^4_J(\mu)\leq T_J(\mu)\leq T^5_J(\mu).$$ But, because the definition of the $T^4_J(\mu)$ and $T^5_J(\mu)$ are a bit confusing, I'll use the next post to talk about their definitions and prove the first inequality.

Almost Disjoint Transversals

Definition: Suppose that $\kappa$ and $\mu$ are cardinals with $\kappa<\mu$, and $J$ is an ideal on $\kappa$. We say that $\mathcal{F}\subseteq {}^\kappa\mu$ is a $J$-adt (almost disjoint transversal) if for every $f\neq g\in \mathcal{F}$, we have that $f\neq_J g$.

One reason for looking at almost disjoint transversals is that they show up in the context of cardinal arithmetic quite often, as they're used to prove the first Galvin-Hajnal formula and they appear in several of Shelah's papers (e.g. 186, 410, 506, and 589). In particular, we want to consider the following cardinal:

$T_J(\mu)=\sup\{|F| : F\subseteq{}^\kappa\mu\text{ is a }J\text{-adt}\}$

I want to use the next few posts to work through a result of Shelah that, under reasonable assumptions on the ideal $J$, relates $T_J(\mu)$ to a pcf-theoretic cardinal. This is all based on the arguments in section 6 of Shelah paper 410. In the remainder of this post we will define some auxiliary invariants, with the goal of showing all of these are equal in most cases. First, we need some definitions.

Definition: Given an ideal $J$ on a set $A$, we say that $A$ is $J$-positive ($A\in J^+$) if $A$ is not in $J$.

Definition: Given a cardinal $\theta$, we say that an ideal $J$ is $\theta$-based if for any $J$-positive $A$, there is a $J$-positive $B\subseteq A$ such that $|B|<\theta$.

At this point, we will assume that our ideal $J$ is $\theta$-based where $\kappa^{<\theta}<\mu$. At the end of this series of posts, we will discuss some situations under which these assumptions are satisfied, as they are not terribly stringent. Finally, we need one more definition which is a bit ad-hoc, but will help us in defining the invariants I mentioned earlier.

Definition: We say that a cardinal $\lambda$ is weakly $J$-representable if there is a block sequence $\langle E(i) : i<\kappa\rangle$ with $E(i)\in[(\kappa^{<\sigma,}\mu]\cap\mathrm{Reg}]^{<\omega}$ such that for any $J$-positive set $A$, $\lambda\leq\max pcf\bigcup_{i\in A}E(i)$. We say that $\lambda$ is $J$-representable if instead we ask $\lambda=\max pcf\bigcup_{i\in A}E(i)$ for every $J$-positive set $A$.

$T^2_J(\mu)=\sup\{\lambda : \lambda\text{ is weakly }J\text{-representable}\}$
$T^3_J(\mu)=\sup\{\lambda : \lambda\text{ is }J\text{-representable}\}$

Note here that the above cardinals are defined in terms of a $\kappa$-sequence of finite blocks, which may seem somewhat strange initially. It's worth pointing out that this "chunky pcf" appears in a number of other places in Shelah's work primarily when Skolem Hulls and towers of elementary submnodels are involved. In a later post, we will see how the chunkyness of the pcf gets used. In the next post however, I will discuss how $T_J(\mu)$, $T^2_J(\mu)$, and $T^3_J(\mu)$ are related and define one last related invariant.