Skip to main content
MathOverflow

Return to Answer

minor typos
Source Link
James E Hanson
James E Hanson
  • 12.4k
  • 3
  • 37
  • 67

I believe you don't need this, but assume that there is a strongly inaccessible cardinal $\kappa$. Fix a first-order completion $T$ of $\mathsf{PA}$ and let $\mathcal{M}$ be a saturated model of $T$ of cardinality $\kappa$. I will show that $\mathcal{M}$ has no $\Delta^1_1$-with-parameters-definable cuts.

Claim. For any $\Sigma^1_1(a)$ formula $\varphi(x,a)$, there is a closed set $F_\varphi \subseteq S_{x}(a)$ of types such that $\mathcal{M} \models \varphi(b,a)$ if and only if $\mathrm{tp}(b/a) \in F_\varphi$ (where $\mathrm{tp}(x/y)$ is the first-order type of $x$ over $y$).

Proof. Given $\varphi(x,a)$, by compactness, there is a set of formulas $\Lambda(x,a)$ such that for any $b \in \mathcal{M}$,

  • there exists an elementary extension $\mathcal{N} \succeq \mathcal{M}$ for which $\mathcal{N} \models \varphi(b,a)$

if and only if $\mathcal{M} \models \Lambda(b,a)$. Since $\mathcal{M}$ is saturated, it is resplendent, and if there is such an elementary extension for a given $b$, then we actually have that $\mathcal{M} \models \varphi(b,a)$ (since some expansion of $\mathcal{M}$ by a predicate satisfies the part of $\varphi(x,a)$$\varphi(b,a)$ after the set quantifier). Clearly the other direction holds, so we have that $F_\varphi$ is the set of types corresponding to the partial type $\Lambda(x,a)$. $\square_{\text{claim}}$

Assume that there is a $\Delta^1_1$-with-parameters-definable cut, so in other words, assume that we have two $\Sigma^1_1$ formulas $\varphi(x,a)$ and $\psi(x,a)$ such that $\varphi(\mathcal{M},a)$ is the cut and $\psi(\mathcal{M},a)$ is the complement of the cut. Let $F_\varphi$ and $F_\psi$ be as in the claim.

Since $\mathcal{M}$ is saturated, it is $\omega$-saturated. This implies that $F_\varphi$ and $F_\psi$ are disjoint (otherwise a type in their intersection would be realized) and cover $S_x(a)$ (otherwise a type in the complement of their union would be realized). Therefore, they are actually clopen, and correspond to some first-order formula $\chi(x,a)$ and its negation, but then $\chi(x,a)$ is a definable cut, which cannot happen, as $T$ is an extension of $\mathsf{PA}$. $\square$

As for getting rid of the inaccessible, I believe a special model will be sufficient, since they are resplendent for finite expansions. I, actually think a computably saturated model might be sufficient too, since the first-order theory we're trying to expand to is c.e. (finitely axiomatizable, even).

I believe you don't need this, but assume that there is a strongly inaccessible cardinal $\kappa$. Fix a first-order completion $T$ of $\mathsf{PA}$ and let $\mathcal{M}$ be a saturated model of $T$ of cardinality $\kappa$. I will show that $\mathcal{M}$ has no $\Delta^1_1$-with-parameters-definable cuts.

Claim. For any $\Sigma^1_1(a)$ formula $\varphi(x,a)$, there is a closed set $F_\varphi \subseteq S_{x}(a)$ of types such that $\mathcal{M} \models \varphi(b,a)$ if and only if $\mathrm{tp}(b/a) \in F_\varphi$ (where $\mathrm{tp}(x/y)$ is the first-order type of $x$ over $y$).

Proof. Given $\varphi(x,a)$, by compactness, there is a set of formulas $\Lambda(x,a)$ such that for any $b \in \mathcal{M}$,

  • there exists an elementary extension $\mathcal{N} \succeq \mathcal{M}$ for which $\mathcal{N} \models \varphi(b,a)$

if and only if $\mathcal{M} \models \Lambda(b,a)$. Since $\mathcal{M}$ is saturated, it is resplendent, and if there is such an elementary extension for a given $b$, then we actually have that $\mathcal{M} \models \varphi(b,a)$ (since some expansion of $\mathcal{M}$ by a predicate satisfies the part of $\varphi(x,a)$ after the set quantifier). Clearly the other direction holds, so we have that $F_\varphi$ is the set of types corresponding to the partial type $\Lambda(x,a)$. $\square_{\text{claim}}$

Assume that there is a $\Delta^1_1$-with-parameters-definable cut, so in other words, assume that we have two $\Sigma^1_1$ formulas $\varphi(x,a)$ and $\psi(x,a)$ such that $\varphi(\mathcal{M},a)$ is the cut and $\psi(\mathcal{M},a)$ is the complement of the cut. Let $F_\varphi$ and $F_\psi$ be as in the claim.

Since $\mathcal{M}$ is saturated, it is $\omega$-saturated. This implies that $F_\varphi$ and $F_\psi$ are disjoint (otherwise a type in their intersection would be realized) and cover $S_x(a)$ (otherwise a type in the complement of their union would be realized). Therefore, they are actually clopen, and correspond to some first-order formula $\chi(x,a)$ and its negation, but then $\chi(x,a)$ is a definable cut, which cannot happen, as $T$ is an extension of $\mathsf{PA}$. $\square$

As for getting rid of the inaccessible, I believe a special model will be sufficient, since they are resplendent for finite expansions. I, actually think a computably saturated model might be sufficient too, since the first-order theory we're trying to expand to is c.e. (finitely axiomatizable, even).

I believe you don't need this, but assume that there is a strongly inaccessible cardinal $\kappa$. Fix a first-order completion $T$ of $\mathsf{PA}$ and let $\mathcal{M}$ be a saturated model of $T$ of cardinality $\kappa$. I will show that $\mathcal{M}$ has no $\Delta^1_1$-with-parameters-definable cuts.

Claim. For any $\Sigma^1_1(a)$ formula $\varphi(x,a)$, there is a closed set $F_\varphi \subseteq S_{x}(a)$ of types such that $\mathcal{M} \models \varphi(b,a)$ if and only if $\mathrm{tp}(b/a) \in F_\varphi$ (where $\mathrm{tp}(x/y)$ is the first-order type of $x$ over $y$).

Proof. Given $\varphi(x,a)$, by compactness, there is a set of formulas $\Lambda(x,a)$ such that for any $b \in \mathcal{M}$,

  • there exists an elementary extension $\mathcal{N} \succeq \mathcal{M}$ for which $\mathcal{N} \models \varphi(b,a)$

if and only if $\mathcal{M} \models \Lambda(b,a)$. Since $\mathcal{M}$ is saturated, it is resplendent, and if there is such an elementary extension for a given $b$, then we actually have that $\mathcal{M} \models \varphi(b,a)$ (since some expansion of $\mathcal{M}$ by a predicate satisfies the part of $\varphi(b,a)$ after the set quantifier). Clearly the other direction holds, so we have that $F_\varphi$ is the set of types corresponding to the partial type $\Lambda(x,a)$. $\square_{\text{claim}}$

Assume that there is a $\Delta^1_1$-with-parameters-definable cut, so in other words, assume that we have two $\Sigma^1_1$ formulas $\varphi(x,a)$ and $\psi(x,a)$ such that $\varphi(\mathcal{M},a)$ is the cut and $\psi(\mathcal{M},a)$ is the complement of the cut. Let $F_\varphi$ and $F_\psi$ be as in the claim.

Since $\mathcal{M}$ is saturated, it is $\omega$-saturated. This implies that $F_\varphi$ and $F_\psi$ are disjoint (otherwise a type in their intersection would be realized) and cover $S_x(a)$ (otherwise a type in the complement of their union would be realized). Therefore, they are actually clopen, and correspond to some first-order formula $\chi(x,a)$ and its negation, but then $\chi(x,a)$ is a definable cut, which cannot happen, as $T$ is an extension of $\mathsf{PA}$. $\square$

As for getting rid of the inaccessible, I believe a special model will be sufficient, since they are resplendent for finite expansions. I actually think a computably saturated model might be sufficient too, since the first-order theory we're trying to expand to is c.e. (finitely axiomatizable, even).

Source Link
James E Hanson
James E Hanson
  • 12.4k
  • 3
  • 37
  • 67

I believe you don't need this, but assume that there is a strongly inaccessible cardinal $\kappa$. Fix a first-order completion $T$ of $\mathsf{PA}$ and let $\mathcal{M}$ be a saturated model of $T$ of cardinality $\kappa$. I will show that $\mathcal{M}$ has no $\Delta^1_1$-with-parameters-definable cuts.

Claim. For any $\Sigma^1_1(a)$ formula $\varphi(x,a)$, there is a closed set $F_\varphi \subseteq S_{x}(a)$ of types such that $\mathcal{M} \models \varphi(b,a)$ if and only if $\mathrm{tp}(b/a) \in F_\varphi$ (where $\mathrm{tp}(x/y)$ is the first-order type of $x$ over $y$).

Proof. Given $\varphi(x,a)$, by compactness, there is a set of formulas $\Lambda(x,a)$ such that for any $b \in \mathcal{M}$,

  • there exists an elementary extension $\mathcal{N} \succeq \mathcal{M}$ for which $\mathcal{N} \models \varphi(b,a)$

if and only if $\mathcal{M} \models \Lambda(b,a)$. Since $\mathcal{M}$ is saturated, it is resplendent, and if there is such an elementary extension for a given $b$, then we actually have that $\mathcal{M} \models \varphi(b,a)$ (since some expansion of $\mathcal{M}$ by a predicate satisfies the part of $\varphi(x,a)$ after the set quantifier). Clearly the other direction holds, so we have that $F_\varphi$ is the set of types corresponding to the partial type $\Lambda(x,a)$. $\square_{\text{claim}}$

Assume that there is a $\Delta^1_1$-with-parameters-definable cut, so in other words, assume that we have two $\Sigma^1_1$ formulas $\varphi(x,a)$ and $\psi(x,a)$ such that $\varphi(\mathcal{M},a)$ is the cut and $\psi(\mathcal{M},a)$ is the complement of the cut. Let $F_\varphi$ and $F_\psi$ be as in the claim.

Since $\mathcal{M}$ is saturated, it is $\omega$-saturated. This implies that $F_\varphi$ and $F_\psi$ are disjoint (otherwise a type in their intersection would be realized) and cover $S_x(a)$ (otherwise a type in the complement of their union would be realized). Therefore, they are actually clopen, and correspond to some first-order formula $\chi(x,a)$ and its negation, but then $\chi(x,a)$ is a definable cut, which cannot happen, as $T$ is an extension of $\mathsf{PA}$. $\square$

As for getting rid of the inaccessible, I believe a special model will be sufficient, since they are resplendent for finite expansions. I, actually think a computably saturated model might be sufficient too, since the first-order theory we're trying to expand to is c.e. (finitely axiomatizable, even).