A Löwenheim–Skolem–Tarski-like property

Question

I am interested in the following Löwenheim–Skolem–Tarski-like property.

Given a cardinal $\kappa$, what (if any) is a property $\phi(x)$ such that if $\phi(\kappa)$ holds, then we can prove the following: for any first-order structure $B$ (in some countable language), there is a structure $A$ in the same language with $\lvert A\rvert<\kappa$, such that for any $b \in B$ there is some elementary embedding $j:A \rightarrow B$ such that $b$ is in the range of $j$?

Note that if we don't require $b$ to be in the range of $j$, then this is the usual Löwenheim–Skolem–Tarski property, so it holds as long as $\kappa \geq \aleph_1$.

Answer 1

Let me improve somewhat on Farmer's lower bound.

Theorem. If there is a cardinal $\kappa$ with the stated reflection property, then there are many measurable cardinals, measurable cardinals of very high Mitchell rank, and indeed, $1$-extendible cardinals of high Mitchell rank.

The update gives a cardinal $\bar\kappa$ that is $\alpha$-extendible for $\alpha$ much larger than many measurable cardinals above $\bar\kappa$. In particular, $\bar\kappa$ is highly partially supercompact.

Proof. Suppose that $\kappa$ has the stated reflection property. Consider some large ordinal $\theta$ and let $B=\langle V_{\theta+1},{\in}\rangle$. By the reflection property, there is some structure $A$ with lots of elementary embeddings $j:A\to B$ hitting any desired target. We may assume $A$ is a transitive set. Let $\bar\kappa$ be the smallest critical point of such an embedding. For any $X\subseteq\bar\kappa$, it is in $B$ and so there is some $x\in A$ and $j:A\to B$ with $j(x)=X$. Since $x$ and $j(x)=X$ must agree up to $\bar\kappa$, this implies $X\in A$. So $P(\bar\kappa)\subseteq A$. This implies that $\bar\kappa$ is measurable, since we can define the induced normal measure $X\in\mu\iff \bar\kappa\in j(X)$ for such a $j$ with critical point $\bar\kappa$.

So we've seen that $\bar\kappa$ is a measurable cardinal. And since $B$ also can see this, there must be measurable cardinals below $\bar\kappa$ in $A$. And indeed, the measure $\mu$ on $\bar\kappa$ will concentrate on measurables. So $\bar\kappa$ has Mitchell rank 1. But $B$ sees this, and so $\bar\kappa$ has Mitchell rank 2, and so forth, cycling around the loop for a long while to get very high Mitchell ranks.

The same idea shows that $\bar\kappa$ is 1-extendible, since we must have $V_{\bar\kappa+1}\subseteq A$ and so $j\upharpoonright V_{\bar\kappa+1}:V_{\bar\kappa+1}\to V_{j(\bar\kappa)+1}$ witnesses 1-extendibility. And since this is inside $B$, we get that $\bar\kappa$ is a limit of 1-extendibles, of high Mitchell rank again. $\Box$

If we could show $P(P(\bar\kappa))\subseteq A$, we would get $2$-extendibility, and so forth.

Update. Let me now explain, based on the arguments in the comments by Farmer and Andreas, that we can achieve higher degrees of extendibility. The main idea is to show that $V_{\bar\kappa+\alpha}\subseteq A$ for higher ordinals $\alpha$, which shows that $\bar\kappa$ is $\alpha$-extendible. The argument I've given above shows how the case $\alpha=1$ works. Let's now extend further.

Let $\bar\kappa_0=\bar\kappa$ be the least critical point that arises with $j:A\to B$, and let $\kappa_1$ be the next critical point. Such a critical point must arise because there must be $j:A\to B$ with $\bar\kappa$ in the range of $j$, and such an embedding must have critical point above $\bar\kappa$. What I claim is that $P(\bar\kappa_1)\subseteq A$. To see this, consider any $X\subseteq \bar\kappa_1$, and then find a $j:A\to B$ with $\{\bar\kappa,X\}\in\text{ran}(j)$. It follows that $\bar\kappa\in\text{ran}(j)$ and so the critical point of $j$ is at least $\bar\kappa_1$, and so $X\in A$ by the same reasoning as before.

The main point is that the embeddings $j:A\to B$ with critical point $\bar\kappa$ now are witnesses of $\bar\kappa_1$-extendibility, which is already a high degree of extendibility. And we can continue with $\kappa_\alpha$ etc. getting very high degrees of extendibility of $\bar\kappa$ this way. It seems we get that $\bar\kappa$ is $\alpha$-extendible, where $\alpha$ is the $\bar\kappa$th measurable cardinal above $\bar\kappa$. And much more.

Andreas mentioned in the comments an idea for pushing this further, and perhaps he will post an answer about that.

Another feature. There is another certain feature here I noticed that seems interesting, and we might be able to push it much harder, but I don't quite see how to use it yet. Namely, for every $\theta$ we got a small transitive set $A$ which supports the elementary embeddings $j:A\to V_{\theta+1}$. Since there are only set many such $A$, it must be that some $A$ works for unboundedly many $\theta$. That is, we have a single transitive set $A$, such that for arbitrarily large $\theta$ we have elementary embeddings $j:A\to V_{\theta+1}$ that cover the target. And there will be a $\bar\kappa$ in $A$ that is the critical point of such an embedding for arbitrarily large $\theta$. That seems powerful, but I'm not sure exactly how to use it. It isn't quite super-$1$-extendibility, since perhaps it isn't $\bar\kappa$ that is sent high, even though the target model of $A$ can be made high.

Answer 2

Here's a counterexample for $\kappa=\aleph_1$: let $B$ be the structure with underlying set $\mathbb{N}\sqcup\mathcal{P}(\mathbb{N})$, equipped with the usual ordering on $\mathbb{N}$ as well as the $\in$-relation between the $\mathbb{N}$ and $\mathcal{P}(\mathbb{N})$ parts. We need continuum-many countable structures to "cover" this $B$, since the elements of the $\mathcal{P}(\mathbb{N})$-part are elementarily distinguishable.

(FWIW a similar trick is used to whip up a countable structure - necessarily in an uncountable language - with no countable proper elementary extension.)

Answer 3

Here is an upper bound:

Suppose $\kappa$ is $2$-fold supercompact. Then the property holds at $\kappa$. (Recall that $2$-fold supcompactness means that for each ordinal $\lambda$, there is $j:V\to M$ with $\mathrm{crit}(j)=\kappa$ and $\lambda<j(\kappa)$ and ${^{j(\lambda)}M}\subseteq M$.) (This property is of course below rank-to-rank.)

So suppose $B$ is a counterexample to the property holding at $\kappa$.

Let $\lambda>\kappa$ be an inaccessible cardinal such that $B\in V_\lambda$. (There is easily a proper class of inaccessibles.) Using $2$-fold supercompactness at $\lambda$, let $j:V\to M$ with $\mathrm{crit}(j)=\kappa$ and $\lambda<j(\kappa)$ and ${^{j(\lambda)}M}\subseteq M$. It follows that $B\in V_{j(\kappa)}=V_{j(\kappa)}^M$. Note also that because ${^{j(\lambda)}M}\subseteq M$ and $\lambda$ is inaccessible, we have $V_{j(\lambda)+1}^M=V_{j(\lambda)+1}$.

Let $C=j(B)$. We have $C\in V_{j(\lambda)}\subseteq M$. Note that $C$ is a counterexample to $j(\kappa)$ having the property in $M$. Since $B\in V_{j(\kappa)}^M$, we can fix $x\in C=j(B)$ such that $M\models$"there is no elementary $\ell:B\to C$ with $x\in\mathrm{range}(\ell)$". But since $V_{j(\lambda)}\subseteq M$, therefore in fact ($*$) there is no elementary $\ell:B\to C$ with $x\in\mathrm{range}(\ell)$.

Now applying $j$ to ($*$), we get that $M\models$"there is no elementary $\ell:j(B)\to j(C)$ with $j(x)\in\mathrm{range}(\ell)$". But letting $\ell=j\upharpoonright j(B)$, we have $\ell\in M$, since ${^{j(\lambda)}M}\subseteq M$. And $x\in j(B)$, so $\ell(x)=j(x)\in\mathrm{range}(\ell)$. This is a contradiction.

---

Here is a lower bound:

If the property holds at some $\kappa$ then $0^\#$ exists.

For suppose the property holds at $\kappa$. Let $B$ be a transitive model of ZFC$^-$ with $V_\kappa\subseteq B$. Let $A$ witness the property with respect to $B,\kappa$, so in particular, $A$ has cardinality ${<\kappa}$. Let $\alpha=\mathrm{Ord}\cap A$. Let $\theta=\mathrm{card}(\alpha)$. If there is any elementary embedding $j:A\to B$ such that $\mathrm{crit}(j)<\theta$, then $0^\#$ exists (this is standard: letting $k:L_\alpha\to L_{\mathrm{Ord}^B}$ be the restriction of $j$, then $k$ is elementary, and letting $U_k$ be the normal measure derived from $k$, then $\mathrm{Ult}(L,U_k)$ is wellfounded, giving an elementary $\ell:L\to L$).

So we may assume that every $j:A\to B$ witnessing the property in question has $\theta\leq\mathrm{crit}(j)$. Now given $X\subseteq\theta$, we have $X\cup\{\theta\}\in B$, so there is $j_X:A\to B$ with $X,\theta\in\mathrm{rg}(j_X)$. Since $\theta\leq\mathrm{crit}(j_X)$, in fact then $\theta<\mathrm{crit}(j_X)$, and it follows that $X$ is definable from parameters over $A$, and since $A\models$ ZFC$^-$, therefore $X\in A$. But then every wellorder of $\theta$ is in $A$, and again since $A\models$ ZFC$^-$, it follows that $\theta^{+}\leq\mathrm{Ord}\cap A$, a contradiction.

---

Added remarks: From Joel's and Andreas's answers, if $\kappa$ has the property then there are partially extendible cardinals ${<\kappa}$, and there is $\lambda<\kappa$ such that $V_\lambda\models$ ZFC + "there are (fully) extendible cardinals". So assuming that there exist both a cardinal $\kappa$ with the property, and a (truly) extendible cardinal $\gamma$, we can ask what is the relative ordering of the least such two cardinals $\kappa_0$ and $\gamma_0$.

Prop 1: Suppose $\kappa_0$ (the least with said property) and $\gamma_0$ (the least extendible) exist. Then $\kappa_0<\gamma_0$.

Proof: First let us show that if $\kappa$ has the property and $\gamma$ is extendible, then $\gamma$ also has the property. If $\kappa\leq\gamma$ this is immediate, so suppose $\gamma<\kappa$. Let $B$ be given, and let $\alpha$ be such that $B\in V_\alpha$. Let $j:V_\alpha\to V_\beta$ be elementary with $\mathrm{crit}(j)=\gamma$ and $j(\gamma)>\kappa$. Then by the property at $\kappa$ with respect to $j(B)$, there is $A\in V_{\kappa}$ such that $A$ can be embedded into $j(B)$ with any desired $x\in j(B)$ in the range. But $V_\kappa\subseteq V_{j(\gamma)}$, and $j(B)\in V_\beta$, so all the witnessing embeddings are in $V_\beta$, so $V_\beta$ thinks that there is an appropriate $A\in V_{j(\gamma)}$ for $j(B)$. But then $V_\alpha$ thinks there is an appropriate $A\in V_\gamma$ for $B$, and this really works in $V$, as desired.

So we have $\kappa_0\leq\gamma_0$. The rest follows from the following lemma:

Lemma: If $\kappa$ is a superstrong cardinal that has the property, then there there is $\kappa'<\kappa$ with the property.

Proof: Suppose otherwise and let $f:\kappa\to V$ be a function where $f(\kappa')$ is some $B$ witnessing that the property fails at $\kappa'$, with $B$ of minimal rank to achieve this. Then note that by superstrongness (in fact just strongness) of $\kappa$, we have $f(\kappa')\in V_\kappa$ for each $\kappa'<\kappa$. Now let $j:V\to M$ witness the superstrongness of $\kappa$ and let $B=j(f)(\kappa)$. In $M$, $B$ is a counterexample to $\kappa$ having the property. But we have $B\in V_{j(\kappa)}^M=V_{j(\kappa)}$, and since $\kappa$ has the property in $V$, it follows that $B$ is actually not a counterexample in $M$, contradiction.

Prop 2: Let $\kappa_0$ be the least cardinal with the property. Suppose $V_{\kappa_0}\models$ ZFC. Then there is no $\gamma<\kappa_0$ which is $\kappa_0$-extendible (that is, there is no elementary $j:V_{\kappa_0}\to V_\beta$ (for some $\beta$) with $\mathrm{crit}(j)=\gamma<\kappa_0$ and $j(\gamma)>\kappa_0$).

Proof: Suppose otherwise. Then the property holds at $\gamma$ with respect to all $B\in V_{\kappa_0}$. (If $B$ is a counterexample, note that $V_\beta\models$"$j(B)$ is a counterexample to the property holding at $j(\gamma)$", but since $\kappa_0\leq j(\gamma)$ and the property holds at $\kappa_0$, actually $V_\beta\models$"no it's not", contradiction.) But then the property holds at $\gamma$ with respect to all structures $B$: given $B$, let $B'\in V_{\kappa_0}$ witness the property at $\kappa_0$ with respect to $B$, and now let $A\in V_\gamma$ witness it at $\gamma$ with respect to $B'$. Let $x\in B$, and let $k:B'\to B$ with $x\in\mathrm{range}(k)$. Then there is $k':A\to B'$ with $k^{-1}(x)\in\mathrm{range}(k')$. Now $k\circ k':A\to B$ works. So the property holds at $\gamma$, contradicting the minimality of $\kappa_0$.

Some related questions: Let $\kappa_0$ be the least cardinal with the property. Can/does $V_{\kappa_0}\models$ ZFC? Can/does $V_{\kappa_0}\models$"There is an extendible cardinal"?

Answer 4

Here is a lower bound that improves Joel's by a bit. If the reflection property of the post holds at $\kappa$ then there is some measurable $\lambda<\kappa$ with $$V_\lambda\models``\text{there is a proper class of extendible cardinals}".$$ In fact, we can have $\lambda$ itself somewhat extendible if we want to. Let $A, B$ be as in Joel's answer, so for any $b\in B$ there is an elementary $j_b:A\rightarrow B$ with $b\in\mathrm{ran}(j_b)$ (and say we pick $j_b$ with minimal possible critical point).

We now define an increasing sequence $\langle \bar\kappa_\beta\mid\beta<\alpha\rangle$ and only stop when we hit a limit $\alpha$ so that $\sup_{\beta<\alpha}\bar\kappa_\beta$ is measurable. By recursion, we let $$\bar\kappa_\beta:=\min\{\mathrm{crit}(j_{\{b, \langle \bar\kappa_\gamma\mid\gamma<\beta\rangle\}})\mid b\in B\}.$$ We have to show that we hit the stopping $\alpha$ before the sequence is no longer increasing. So suppose instead that we find some $\beta<\xi$ with $\bar\kappa_\xi\leq\bar\kappa_\beta$ first and let $(\xi,\beta)$ be lexicographically least so. Now we can find $j:A\rightarrow B$ with $\mathrm{crit}(j)=\bar\kappa_\xi$ and $\langle\bar\kappa_\gamma\mid\gamma<\xi\rangle$ in the range of $j$, say its preimage is $\langle \bar\lambda_\gamma\mid\gamma<\bar\xi\rangle$. If defined, we have $\bar\kappa_\xi\leq\bar\kappa_{\bar\kappa_\xi}$, so by minimality of $\beta$ necessarily $\beta\leq\bar\kappa_\xi$. If we had $\beta<\bar\kappa_\xi$ then $j(\langle\bar\lambda_\gamma\mid\gamma<\beta\rangle)=\langle \bar\kappa_\gamma\mid\gamma<\beta\rangle$ is in the range of $j$, so that $\bar\kappa_\beta=\bar\kappa_\xi$ by definition of $\bar\kappa_\beta$. But $\bar\kappa_\beta=j(\bar\lambda_\beta)$ is in the range of $j$, yet $\bar\kappa_\beta=\mathrm{crit}(j)$, contradiction. We are left with $\bar\kappa_\xi=\beta$. Joel's argument shows that $\beta$ must be measurable: We only need to see $\mathcal P(\beta)\subseteq A$. Now for $X\subseteq\beta$, $X$ is in the range of $j_{\{X,\langle \bar\kappa_\gamma\mid\gamma<\xi\rangle\}}$ and this map has critical point $\geq \beta$. This can only happen if already $X\in A$. We have $\bar\kappa_\gamma<\bar\kappa_\xi=\beta$ for $\gamma<\beta$ by minimality of $\beta$, so that $\sup_{\gamma<\beta}\bar\kappa_\gamma=\beta$ should have been our stopping point, contradiction!

So we set $\lambda=\sup_{\beta<\alpha}\kappa_\beta$ (actually $\lambda=\alpha)$ which is measurable by construction. We have that $\langle \bar\kappa_\beta\mid\beta<\lambda\rangle$ is an increasing cofinal sequence in $\lambda$ and we will show that unboundedly many of those are extendible in $V_\lambda$. Once again, $V_\lambda\subseteq A$ by applying Joel's argument to all $\bar\kappa_\beta$ for $\beta<\lambda$.

So any $\bar\kappa_\beta$ is $\lambda$-extendible, i.e. there is some $\nu_\beta$ and $k_\beta\colon V_\lambda\rightarrow V_{\nu_\beta}$ with critical point $\bar\kappa_\beta$. By Dushnik-Miller, there is some $H\in[\lambda]^\lambda$ so that $\nu_\beta\leq\nu_\gamma$ for every $\beta<\gamma$ both in $H$.

We are done once we show that $\bar\kappa_\beta$ is extendible in $V_\lambda$ for $\beta\in H$, since those $\bar\kappa_\beta$ are cofinal in $\lambda$. It is enough to show that if $\beta<\gamma$ are both in $H$ then $\bar\kappa_\beta$ is ${<}\bar\kappa_\gamma$-extendible in $V_\lambda$. Let $$\mu:=k_\beta(\bar\kappa_\gamma)<\nu_\beta\leq\nu_\gamma.$$ Then $k_\beta\upharpoonright V_{\bar\kappa_\gamma}:V_{\bar\kappa_\gamma}\rightarrow V_\mu$ is elementary, has critical point $\bar\kappa_\beta$ and is in $V_{\nu_\gamma}$. By elementarity of $k_\gamma$, we must have $V_\lambda\models``\bar\kappa_\beta\text{ is $\delta$-extendible}"$ for each $\delta<\bar\kappa_\gamma$.