For a structure $\mathcal{X}=(X;...)$, say that a cardinal $\kappa$ is $\mathcal{X}$-detectable iff there is some sentence $\varphi$ in the language of $\mathcal{X}$ together with a fresh unary predicate symbol $U$ such that for all $A\subseteq X$, the expansion of $\mathcal{X}$ gotten by interpreting $U$ as $A\subseteq X$ satisfies $\varphi$ iff $\vert A\vert\ge\kappa$.

For example, $\omega_1$ is $(\omega_1;<)$-detectable since the uncountable subsets of $\omega_1$ are exactly the unbounded ones. By contrast, Alex Kruckman observed that by a result of Robinson no uncountable cardinal is $\mathcal{R}=(\mathbb{R};+,\times)$-detectable.

I'm interested in the expansion $\mathcal{R}_\mathbb{N}:=(\mathbb{R};+,\times,\mathbb{N})$ of $\mathcal{R}$ gotten by adding a predicate naming the natural numbers (equivalently, adding all projective functions and relations). Since we can talk about one real enumerating a list of other reals, $\omega_1$ is $\mathcal{R}_\mathbb{N}$-detectable ("there is no real enumerating all elements of $U$"). More pathologically, if $\mathfrak{c}=2^\omega$ is regular and there is a projective well-ordering of the continuum of length $\mathfrak{c}$ then $\mathfrak{c}$ is $\mathcal{R}_\mathbb{N}$-detectable. So for example it is consistent with $\mathsf{ZFC}$ that $\omega_2$ is $\mathcal{R}_\mathbb{N}$-detectable.

I'm curious whether this type of situation is the only way to get $\mathcal{R}_\mathbb{N}$-detectability past $\omega_1$. There are multiple ways to make this precise, of course. At present the following two seem most natural to me:

  • Is it consistent with $\mathsf{ZFC}$ that there are at least two distinct regular cardinals $>\omega_1$ which are $\mathcal{R}_\mathbb{N}$-detectable?

  • Is it consistent with $\mathsf{ZFC}$ that there is a singular cardinal which is $\mathcal{R}_\mathbb{N}$-detectable?

Note that an affirmative answer to either question requires a large continuum, namely $\ge\omega_3$ and $\ge\omega_{\omega+1}$ respectively. Although my primary interest is in first-order definability, I'd also be interested in answers for other logics which aren't too powerful (e.g. $\mathcal{L}_{\omega_1,\omega}$).

  • 2
    $\begingroup$ Can there be a projective well-ordering but not one of length $\mathfrak c$? $\endgroup$ Jul 27 at 5:08
  • 2
    $\begingroup$ Sure, I am just wondering about this side remark. $\endgroup$ Jul 27 at 5:14
  • 2
    $\begingroup$ @AndrésE.Caicedo Sorry, I misread your comment (which led to a couple off-topic now-deleted comments of my own). That's a neat question - I've played with similar questions on the computability-theoretic side of things, but that's a natural one I haven't thought of at all. My instinct is that this should be possible - that is, that it is consistent with $\mathsf{ZFC}$ that there is a (genuine) well-ordering $W$ of $\mathbb{R}$ which is projective but no projective well-ordering of ordertype exactly $\mathfrak{c}$ (so the ordertype of $W$ is $>\mathfrak{c}$) - but this is really pure guesswork. $\endgroup$ Jul 27 at 5:21
  • 5
    $\begingroup$ @AndrésE.Caicedo If you force CH by $\text{Col}(\omega_1,\mathfrak{c})$, the projective wellorders of $\mathbb R$ in the extension are the same as those in ground model (since you haven't changed $\mathbb R$). So if CH failed in the ground model but the reals had a projective wellorder (consistent by Harrington's "Long Projective Wellorders"), then in the extension, there is a projective wellorder of $\mathbb R$ but none of length $\omega_1$. $\endgroup$ Jul 27 at 6:34
  • 1
    $\begingroup$ @NoahSchweber Do you know a consistency proof for $\aleph_2$ being undetectable (with $\aleph_2\leq 2^{\aleph_0}$)? $\endgroup$
    – Farmer S
    Jul 30 at 9:12

For the first question (distinct regular cardinals $>\aleph_1$): Force ZFC + MA + $2^{\aleph_0}=\aleph_3$ over $L$ in the usual way (see Jech, Theorem 16.13; note the forcing is ccc and it forces MA + $2^{\aleph_0}=\aleph_3$, which is all we need here). Then in $L[G]$, $\aleph_2$ and $\aleph_3$ are both $\mathcal{R}_{\mathbb{N}}$-detectable.

$\aleph_2$: By MA$_{\aleph_1}$, every $\omega_1$-sequence of reals is coded via almost disjoint forcing with respect to the canonical almost disjoint sequence $\left<A_\alpha\right>_{\alpha<\omega_1}$ in $L$. This a.d. sequence is lightface projective (in the standard codes for countable ordinals), so the relation "$y$ is a real enumerated in the $\omega_1$-sequence of reals $\vec{z}_x$ coded by $x$" is lightface definable (over $\mathcal{R}_{\mathbb{N}}$). So just let the statement $\varphi$ be "$A$ is uncountable and there is no real $x$ such that every element of $A$ is enumerated in $\vec{z}_x$" (the "uncountable" part is dealt with as in the original post). Then $\varphi$ is true exactly when $A\subseteq\mathbb{R}$ has cardinality $\geq\aleph_2$.

$\aleph_3$: (It doesn't seem obvious to me that there is a lightface projective wellorder of $\mathbb{R}$ in $L[G]$, so we seem to need another argument than that in the original post.) Let $A\subseteq\mathbb{R}$ with $A\in L[G]\models$"$A$ has cardinality $\leq\aleph_2$". Then we can definably talk about ordered pairs of reals and $A^2$ over $(\mathcal{R}_{\mathbb{N}},A)$, and we can talk about subsets of $A^2$ coded by reals $x$, again via disjoint forcing, but this time with respect to the set $(A^2)'$, where the prime ' means that we convert the family $A^2$ into a disjoint family $(A^2)'$ in the usual manner. I.e., although we had a wellordered family $\left<A_\alpha\right>_{\alpha<\omega_1}$ in the previous case, this is not relevant. The almost disjoint forcing for coding a subset of $A^2$ is ccc (in fact $\sigma$-centered), and there is an $\aleph_2$-sized family of dense sets which ensures that the generic real codes a given set $\subseteq A^2$, so by MA$_{\aleph_2}$ we will have a real coding any given $X\subseteq A^2$). Note that there is a wellorder of $A$ in ordertype $\leq\omega_2$, and this is a subset of $A^2$, so we have a code for it, and moreover, every proper segment of this wellorder has cardinality $\leq\aleph_1$. Since "$\geq\aleph_2$" is already known to be detectable, hence so is "$\leq\aleph_1$", so we can detect whether there is such a wellorder of a given $A$. I.e. let $\psi$ be the statement (in the augmented language with symbol $\dot{A}$) saying "there is a real $x$ which codes a subset $X\subseteq\dot{A}^2$ with respect to the family $(\dot{A}^2)'$, $X$ is a wellorder of $\dot{A}$, every proper segment of $X$ has cardinality $\leq\aleph_1$". Note that given any $A\subseteq\mathbb{R}$ in $L[G]$, we have $(\mathcal{R}_{\mathbb{N}},A)\models\psi$ iff $A$ has cardinality $\leq\aleph_2$ in $L[G]$. Therefore $\aleph_3$ is also $\mathcal{R}_{\mathbb{N}}$-delectable.

Edit: For the second question: Proceed as above but forcing MA + $2^{\aleph_0}=\aleph_{\omega+1}$. Then all cardinals $\kappa\leq\aleph_{\omega+1}$ are $\mathcal{R}_{\mathbb{N}}$-detectable in $L[G]$. For $\aleph_n$ where $n<\omega$ this is basically as above. However, the complexity of the formulas used for the $\aleph_n$'s seems to increase with $n$, when done just as above, so this doesn't seem to immediately yield $\aleph_{\omega}$. Instead we can use a slight variant. We first observe that "$\leq\aleph_\omega$" is detectable: Note that $A\subset\mathbb{R}$ has cardinality $\leq\aleph_{\omega}$ iff there is a wellorder of $A$ in order type $\leq\omega_{\omega}$, and any such wellorder will be coded by a real (via a.d. forcing as before). We can assert that the wellorder $<^*$ has ordertype $\leq\omega_{\omega}$ by saying that there is a sequence $\left<x_n\right>_{n<\omega}\subseteq A$ which is cofinal in $<^*$ and such that $x_0$ has only countably many predecessors and for each $n<\omega$ and each $y\in A$ with $x_n<^*y<^*x_{n+1}$, the set of predecessors of $y$ and the set of predecessors of $x_n$ have the same cardinality, as witnessed by a bijection coded by some real.

It follows that "$\geq\aleph_{\omega+1}$" is detectable. To get "$\geq\aleph_\omega$", note that $A$ has card $\geq\aleph_\omega$ iff $A$ has card $\geq\aleph_{\omega+1}$ or there is a wellorder of $A$ exactly in ordertype $\omega_\omega$, and the latter condition can be expressed as above, together with the extra requirement that there is no real coding a bijection between the predecessors of $x_n$ and those of $x_{n+1}$, for each $n$.

  • $\begingroup$ Fantastic, thanks! $\endgroup$ Jul 30 at 12:42
  • $\begingroup$ Is it obvious what happens under $\mathsf{ZFC+MA+2^{\aleph_0}=\aleph_{\omega_1+1}}$? $\endgroup$ Jul 31 at 8:53
  • $\begingroup$ Well "$\leq\aleph_{\omega_1}$" is detectable much like "$\leq\aleph_{\omega}$ was in the second argument above, but also using a coded subset of size $\aleph_1$ in place of the $\omega$-sequence there. We then also get that "$\geq\aleph_{\omega_1+1}$" and "$\geq\aleph_{\omega_1}$" are detectable much as there. But since there are only countably many formulas available, only countably many cardinals are detectable. The least undetectable is a limit cardinal. I don't see whether the set of detectables $<\aleph_{\omega_1}$ is transitive. $\endgroup$
    – Farmer S
    Aug 1 at 16:39
  • $\begingroup$ Yeah, I was thinking specifically about what happens below $\aleph_{\omega_1}$ in that situation - I should have specified. The transitivity question is a good one, that hadn't occurred to me. $\endgroup$ Aug 1 at 16:41
  • 1
    $\begingroup$ How crucial is it that we start with $L$? For example, is it consistent with $\mathsf{ZFC+MA_{\aleph_1}}$ that $\aleph_2$ is not detectable? My instinct is that first adding $\aleph_2$-many Cohens (per Harry West's answer) and then forcing $\mathsf{MA}_{\aleph_1}$ appropriately over that will result in $\aleph_2$ being undetectable, but I don't immediately see the details. $\endgroup$ Aug 2 at 6:04

Farmer S asked in the comments about the consistency of $\aleph_2$ being undetectable. I hope to dispel any doubt: adding enough Cohen reals does work. Specifically, adding $\kappa$ Cohen reals will ensure that no cardinal $\aleph_1<\lambda\leq \kappa$ is $\mathcal R_{\mathbb N}$-detectable, at least.

Let $\dot{G}$ be the canonical name for a function $\kappa\to\mathbb R$ enumerating the new generic reals. A name $\dot{r},$ thought of as a name for a real, is "supported by" a set $I\subseteq\kappa$ if the Boolean value of each statement "$\check{i}\in \dot{r}$" ($i\in\omega$) is invariant under permutations that fix every element of $I.$ Every name has a countable support. Countability comes from the fact that these Boolean values can be represented by a regular open set in $2^{\kappa\times\omega},$ which is the union of some countable maximal antichain of basic opens, and the indices used in the basic opens constitute a support.

For the purposes of induction I'll use a relative kind of indetectability. Fix disjoint sets $F,U,V\subseteq \kappa$ with $U,V$ uncountable, and names $\dot{r_1},\dots,\dot{r_k}$ of reals supported by $\kappa\setminus(U\cup V).$ Fix also a formula $\phi$ in prenex normal form in the language of $\mathcal R_{\mathbb N}$ with a unary predicate, translated to a statement of set theory by restricting quantifiers to the reals. The unary predicate is written as the first parameter. I will argue that $$\Vdash S\iff T\tag{*}$$ with $$S=\phi(\dot{G}[F\cup U],\dot{r_1},\dots,\dot{r_k}),$$ $$T=\phi(\dot{G}[F\cup V],\dot{r_1},\dots,\dot{r_k}).$$

To get indetectability of $\lambda$ plug in $F=\emptyset$ and $k=0,$ with $U$ a subset of $\kappa$ of cardinality $\lambda,$ and $V$ a disjoint subset of $\kappa$ of cardinality $\aleph_1.$ I think it might not be too hard to extend this to any formula $\phi$ in $L(\mathbb R)^{M[G]},$ and analogous models using HOD or symmetric extensions.

Suppose (*) does not hold. Negate $\phi$ if necessary so that the first quantifier, if any, is existential. Swapping $(S,U)$ and $(T,V)$ if necessary we can assume there is a condition $p’$ such that $p’\Vdash S\wedge \neg T.$ Let $p$ be the condition obtained by ignoring indices in $U\cup V,$ i.e. $p=p’\setminus((U\cup V)\times\omega\times 2).$ The following standard argument shows that $p\Vdash S\wedge \neg T.$ Permutations of $\kappa$ act on forcing conditions and on names by their action on the Boolean algebra of regular opens of $2^{\kappa\times \omega}.$ For any $q\leq p$ we can find a permutation $\pi$ of $\kappa$ fixing $\kappa\setminus(U\cup V)$ elementwise and fixing $U$ and $V$ setwise, so that no index $i\in U\cup V$ is used by both $q$ and by $\pi p’.$ This means that the conditions $q$ and $\pi p’$ are compatible. Applying symmetry we have $\pi p’\Vdash S\wedge \neg T$ and hence $q \cup \pi p’\Vdash S\wedge \neg T,$ and since $q$ was arbitrary we have $p\Vdash S\wedge \neg T.$

If $\phi$ is quantifier-free then (*) is easy to see. Otherwise we arranged that $\phi$ is of the form $(\exists x\in\mathbb R)\psi.$ Then there exists a name $\dot{x}$ for a real, and a condition $q\leq p,$ such that $$q\Vdash \psi(\dot{G}[F\cup U],\dot{r_1},\dots,\dot{r_k},\dot{x}).$$ Partition $U$ as $U_1\cup U’$ with $U_1$ countable, and similarly $V=V_1\cup V’,$ such that $q$ and $\dot{x}$ are supported by $\kappa\setminus(U’\cup V’)$ (extending the definition of "supported by" to conditions). By induction on quantifiers we can apply (*) to $\psi$ to get $$q\Vdash \psi(\dot{G}[F\cup U_1\cup V’],\dot{r_1},\dots,\dot{r_k}, \dot{x}).$$

Pick a permutation $\pi$ fixing each element of $\kappa\setminus(U\cup V)$ but with $\pi[U_1\cup V’]=V.$ Then $$\pi q\Vdash \psi(\dot{G}[F\cup V],\dot{r_1},\dots,\dot{r_k}, \pi\dot{x}).$$ The condition $\pi q$ and name $\pi \dot{x}$ therefore witnesses $p\not\Vdash \neg T.$

  • 1
    $\begingroup$ Great, doubts dispelled! In the definition of $p$ (from $p'$), should it be restricting to $\kappa\backslash(U\cup V)$ instead of $F$? $\endgroup$
    – Farmer S
    Aug 2 at 19:39
  • $\begingroup$ Thanks, this helps round things out! I wonder what happens with other forcing notions ... $\endgroup$ Aug 2 at 19:40
  • $\begingroup$ @FarmerS: yes, thank you $\endgroup$
    – Harry West
    Aug 3 at 5:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.