From Chang and Keisler's "Model Theory", section 7.2, we know that:

1) There is a sentence $\sigma$ in a suitable language $L$ such that for all infinite cardinals $\alpha$, $\sigma$ admits $(\alpha^+,\alpha)$ iff there exists a tree $T$ of height $\alpha^+$, with at most $\alpha$ elements at each level $\xi<\alpha^+$, and with no branch of length $\alpha^+$.

2) There is a sentence $\sigma$ in a suitable language $L$ such that for all infinite cardinals $\alpha$, $\sigma$ admits $(\alpha^{++},\alpha)$ iff there is a (Kurepa) family $F$ of subsets of $\alpha^+$ such that $|F|=\alpha^{++}$ and for every $\xi<\alpha^+$, $|\{X\cap\xi|X\in F\}|=\alpha.$

My question: Are there any "natural" statements that would be equivalent to a sentence $\sigma$ admitting $(\alpha^{+n},\alpha)$, $3\le n<\omega$? For Chang and Keisler, $\sigma$ has to be first-order. For our purposes, even $L_{\omega_1,\omega}$ is good enough.

Addition: Definition A sentence $σ$ in a language with a unary predicate $P$ admits $(κ,λ)$, if $σ$ has a model $M$ such that $|M|=κ$ and $|P^M|=λ$. Of course, λ≤κ. So, not only we need a model of a specific size, but we need the predicate P to have a specific size too.

  • $\begingroup$ Does $2^\alpha\geq\alpha^{+n}$ qualify? $\endgroup$ – Péter Komjáth May 15 '12 at 4:36
  • $\begingroup$ For the problem we are working on, we assume GCH. Nevertheless, I would be interested to hear what you have in mind. $\endgroup$ – Ioannis Souldatos May 15 '12 at 12:14
  • $\begingroup$ Can you remind us what it means to "admit $(\kappa,\lambda)$"? Does it mean that the language has a predicate and you are asking for a model of size $\kappa$, where the predicate has size $\lambda$? $\endgroup$ – Joel David Hamkins May 15 '12 at 13:13
  • 2
    $\begingroup$ I wonder if using a morass instead of a Kurepa tree might be a source of examples, since here one uses a system of small structures to approximate a large structure. The gap-n morass case is similar to your question, with a gap-n difference in the cardinals. $\endgroup$ – Joel David Hamkins May 15 '12 at 15:11
  • 2
    $\begingroup$ See en.wikipedia.org/wiki/Morass_(set_theory) for some information and a list of references. $\endgroup$ – Joel David Hamkins May 15 '12 at 21:08

Letting $\alpha$ be an infinite cardinal and $3\leq n\lt\omega$, I think Peter Komjath's proposed statement $2^\alpha\geq\alpha^{+n}$ is the simplest and most natural equivalent of a first-order sentence admitting $(\alpha^{+n},\alpha)$: just let $\sigma$ say a binary relation is extensional with domain given by a predicate and range equal to the universe. However, you asked for a GCH example in your comment, so I suggest the following statement, that a generalized kind of Kurepa family exists.

  • $(*_{\alpha,n})$ says there exists $\mathcal{X}\subset\mathcal{P}(\alpha^{+n-1})$ of size $\alpha^{+n}$ such that $|\{X\cap A: X\in\mathcal{X}\}|\leq\alpha$ for all $A\subset\alpha^{+n-1}$ of size $\leq\alpha$.

To get our first-order sentence $\sigma$, we use the fact that $[\alpha^{+n-1}]^{\leq\alpha}$ has nice cofinal subsets, and the equivalence of $(*_{\alpha,n})$ to its formal weakenings where $A$ is quantified over a cofinal set. Our first-order sentence $\sigma$ says that

  1. the universe is $L_n$,
  2. $(L_0,\lt_0),\ldots,(L_n,\lt_n)$ are linear orders,
  3. $f_i(x,\bullet)\colon L_i \rightarrow \{ y : y\leq_{i+1} x\}$ is always onto,
  4. $g(x,\bullet)\colon L_{n-1}\rightarrow \{0,1\}$ for all $x\in L_n$,
  5. $g(x,\bullet)\not=g(y,\bullet)$ for all $x\not= y$,
  6. $h(x_{n-1},\ldots,x_0,\bullet)\colon L_0\rightarrow 2$ for all $x\in\prod_{i=0}^{n-1} L_i$, and
  7. every $g(x_n,f_{n-2}(x_{n-1},f_{n-3}(x_{n-2},\cdots,f_0(x_1,\bullet)\cdots)))$ equals some $h(x_{n-1},\ldots,x_0,\bullet)$.

$(*_{\alpha,n})$ holds iff $\sigma$ has a model with size $\alpha^{+n}$ with $L_0$ of size $\alpha$.

Jensen proved that something stronger than $(*_{\alpha,n})$ holds if $V=L$.

  • KH($\kappa,\lambda$) says that there exists $\mathcal{F}\subset\mathcal{P}(\kappa)$ of size $\kappa^+$ such that $|\{X\cap A:X\in\mathcal{F}\}|\leq|A|+\aleph_0$ for all $A\subset\kappa$ of size $\lt\lambda$.

Clearly, KH($\alpha^{+n-1},\alpha^+$) implies $(*_{\alpha,n})$.

Jensen proved that if $V=L$, then KH($\kappa,\lambda$) holds for all regular uncountable $\kappa$ and all uncountable $\lambda<\kappa$. In particular, $(*_{\alpha,n})$ is always true in $L$. Jensen proved that $V=L$ also implies KH($\kappa,\kappa$) for all regular uncountable cardinals that are not ineffable. Jensen and Kunen proved that if $\kappa$ is ineffable, then KH($\kappa,\kappa$) fails. Devlin's exposition of the proofs is available here; see the chapter "Ineffable cardinals and the generalised Kurepa hypothesis."

On the other hand, $(*_{\alpha,n})$ is directly refuted by the Chang conjecture variant $(\alpha^{+n},\alpha^{+n-1})\twoheadrightarrow(\alpha^+,\alpha)$. For regular $\alpha$, we can force this Chang conjecture easily using the method of Levinski-Magidor-Shelah (MR1045371). Assume GCH and epsilon more than a huge embedding: $j\colon V\prec N\supset {}^{\lambda^+}N$ where $\kappa=cp(j)$ and $\lambda=j(\kappa)$. Since $N$ knows that $j''\mathfrak{A}\prec j(\mathfrak{A})$ for all structures $\mathfrak{A}$ of the form $(H(\lambda^+),\in,P)$, we have $(\lambda^+,\lambda)\twoheadrightarrow (\kappa^+,\kappa)$ in $V$ by elementarity of $j$. The two-step iteration $\mathbb{P}=\mathrm{Coll}(\alpha,\kappa)*\mathrm{Coll}(\kappa^{+n-2},\lt\lambda)$ preserves GCH and forces $(\alpha^{+n},\alpha^{+n-1})\twoheadrightarrow(\alpha^+,\alpha)$. The key point is that because there are only $\lambda$-many nice $\mathbb{P}$-names for elements of $\lambda$, this set of names Chang-transfers to a $\kappa$-sized set of names for elements of $\lambda$, implying our desired transfer from $\alpha^{+n-1}$ to $\alpha$ in the generic extension $V[G]$: if in $V$ we have

  • $\mathbb{P}\in M\prec(H(\lambda^+),\in,\dot{P})$,
  • $|M|=\kappa^+$, and
  • $|M\cap\lambda|=\kappa$,

then in $V[G]$ we have

  • $M[G]\prec(H(\lambda^+),\in,\dot{P}_G)=(H(\alpha^{+n}),\in,\dot{P}_G)$,
  • $|M[G]|=\kappa^+=\alpha^+$, and
  • $|M[G]\cap\alpha^{+n-1}|=|M[G]\cap\lambda|=|\kappa|=\alpha$.
  • $\begingroup$ @David Milovich: Sorry I was gone for vacations and didn't see your answer until now. Give me a few days and I will be back to it. $\endgroup$ – Ioannis Souldatos Jun 30 '12 at 13:34
  • $\begingroup$ Very nice answer. This is what I was looking for. Just to clarify one point: In clause (7), where you define $\sigma$, I am assuming that $x_{n-1},\ldots,x_1$ name the same elements in both functions ($g(x_n,f_{n-2}(x_{n-1},\ldots,f_0(x_1,\cdot)\ldots)))$ and $h(x_{n-1},\ldots,x_0,\cdot)$. So, the difference is that the first function contains $x_1,\ldots,x_n$, while the the second function contains the (same) $x_1,\ldots,x_{n-1}$ and $x_0$. Do we agree here? $\endgroup$ – Ioannis Souldatos Jul 10 '12 at 17:31
  • $\begingroup$ Yes, we agree. A more formal version of (7) would start with "for all $x_n,\ldots, x_1$, there exists $x_0$ such that..." $\endgroup$ – David Milovich Jul 10 '12 at 20:10

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.