Skip to main content
Bounty Ended with 200 reputation awarded by Noah Schweber
Improved lower bounds section, and corrected statement re one constant / set-many.
Source Link
Farmer S
  • 9.9k
  • 24
  • 42

editEdit 4 (previous edits done over): Now regarding lower bounds (and cf. If kappaNoah's comments below)...

Say that a (possibly beyond 1st order) logic (I'm not sure of what the formal definition of "logic" is inaccessiblehere, but it doesn't really matter; I only use it in a limited sense below which is clear enough) is $\kappa$-compact iff whenever $T$ is a set-sized theory in that logic and weall subtheories of size ${<\kappa}$ have compactness at kappa with respect toa model, then $T$ also has a model.

Now consider the logic which includes the full first$\mathcal{L}$ in the (first order) language of set theory together with, where we have available a proper class of constant symbolsymbols, plus theand an extra predicate symbol (second orderwhich can be taken to code multiple predicates/functions below), together with the second-order statement “I``I am wellfounded”wellfounded''. (Remark: I mistakenly said "one" constant symbol in an earlier version; but I used set-many. Actually for the purposes below we can restrict the number of constants available to something like the cardinality of $V_{\kappa+2}$, thenwhere $\kappa$ is the cardinal in question.)

Claim: Let $\kappa$ be a cardinal and suppose that $\mathcal{L}$ as above is $\kappa$-compact. Then there is a measurable less than or equal to kappacardinal $\leq\kappa$. For consider the theory T in the language of set theory plus

Proof: First suppose that $\kappa$ is inaccessible. Consider the constant symbol mu$\mathcal{L}$-dot,theory $T$ which includes the full first order theory of $V_{\kappa+1}$ in parameters, the formulas “alpha < mu-dot < kappa”$\alpha < \dot{\mu} < \kappa$, for each alpha < kappa$\alpha < \kappa$, where $\dot{\mu}$ is a new constant, and the (2nd order) formula “I am wellfounded”. If that has$M$ is a (wellfounded) model of $T$, then it’s truly wellfoundednote that there is an elementary $j:V_{\kappa+1}\to M$, the critical point $\mathrm{crit}(j)$ of $j$ exists, and it follows there’sis a measurable less or equal to kappacardinal $\leq\kappa$. So we just need to see the small subtheories have models, but this easily follows easily from the inaccessibility of $\kappa$ (consider elementary substructures of $V_{\kappa+1}$).

edit 2Now suppose $\kappa$ is singular. Suppose we have compactness at Let $\kappa=\gamma^+$ for the language as above$f:\eta\to\kappa$ be cofinal, with constant symbol X. Then there is a measurable cardinalwhere $\leq\gamma$$\eta<\kappa$. For considerConsider the theory $T$ consisting of the first order theory in parameters of $H=\mathcal{H}_{\kappa}$$V_\kappa$, plus “I am wellfounded”and using function symbols $\dot{f},\dot{g}$, plus “Xthe statement "$\dot{f}:\eta\to\mathrm{Ord}$ is a wellorder of $\gamma$“ pluscofinal", the statements “$\alpha<$equations "$\dot{f}(\alpha)=\beta$" for each $\alpha,\beta$ such that $f(\alpha)=\beta$, and the ordertype of X”statement "$\dot{g}$ is a surjection from some ordinal onto $\mathrm{Ord}$", and (2nd order) "I am wellfounded". Then for each $\alpha<\kappa$. Clearly$\theta<\kappa$, each fragment $\bar{T}$ of size $<\kappa$ subtheory$\theta$ is satisfiable, since we may assume $\eta<\theta$, and we can find an elementary substructure of $(X,f\cap X)\preceq(V_\kappa,f)$ of cardinality $\theta$, with $\theta+1\subseteq X$, and then the transitive collapse $(M,\bar{f},g)$ is a model, where we take $g:\theta\to\mathrm{Ord}^M$ a surjection. But ifSo we get a wellfounded model $M$ satisfies$(M,f',g')$ of the wholefull theory then. Let $M\neq H$$j:V_\kappa\to M$ be the resulting elementary embedding. Note that $\mathrm{crit}(j)<\kappa$, because otherwise $f'=f$, so by cofinality, $\kappa=\mathrm{Ord}^M$, so $M=V_\kappa$, so $g':\gamma\to\kappa$ is a surjection for some $\gamma<\kappa$, contradiction. But then $\mathrm{crit}(j)<\kappa$ is measurable.

Finally suppose that $\gamma<\kappa\leq 2^\gamma$. Then consider the theory consisting of the first order theory in parameters of $X^M$$\mathcal{H}_{(2^\gamma)^+}$, "I am wellfounded", and the statement "$\dot{f}:\mathcal{P}(\gamma)\to\mathrm{Ord}$ is surjective". Any sub-theory of size $<\kappa$ is satisfiable (in fact, any sub-theory of size $\leq 2^\gamma$ is satisfiable), so we have an elementary $\pi:H\to M$a model, and note it hasgives a critical pointmeasurable $\leq\gamma$.

(This leaves $\omega$, whichbut it's easy to see this is measurableimpossible; also cf. Noah's comments in the question and below.)

edit. If kappa is inaccessible and we have compactness at kappa with respect to the logic which includes the full first order language of set theory together with a constant symbol, plus the (second order) statement “I am wellfounded”, then there is a measurable less than or equal to kappa. For consider the theory T in the language of set theory plus the constant symbol mu-dot, which includes the full first order theory of $V_{\kappa+1}$ in parameters, the formulas “alpha < mu-dot < kappa”, for each alpha < kappa, and the (2nd order) formula “I am wellfounded”. If that has a model, then it’s truly wellfounded, and it follows there’s a measurable less or equal to kappa. So we just need to see the small subtheories have models, but this easily follows from inaccessibility.

edit 2. Suppose we have compactness at $\kappa=\gamma^+$ for the language as above, with constant symbol X. Then there is a measurable cardinal $\leq\gamma$. For consider the theory consisting of the first order theory in parameters of $H=\mathcal{H}_{\kappa}$, plus “I am wellfounded”, plus “X is a wellorder of $\gamma$“ plus the statements “$\alpha<$ the ordertype of X”, for each $\alpha<\kappa$. Clearly each size $<\kappa$ subtheory is satisfiable. But if $M$ satisfies the whole theory then $M\neq H$, because of $X^M$, and we have an elementary $\pi:H\to M$, and it has a critical point, which is measurable.

Edit 4 (previous edits done over): Now regarding lower bounds (and cf. Noah's comments below)...

Say that a (possibly beyond 1st order) logic (I'm not sure of what the formal definition of "logic" is here, but it doesn't really matter; I only use it in a limited sense below which is clear enough) is $\kappa$-compact iff whenever $T$ is a set-sized theory in that logic and all subtheories of size ${<\kappa}$ have a model, then $T$ also has a model.

Now consider the logic $\mathcal{L}$ in the (first order) language of set theory, where we have available a proper class of constant symbols, and an extra predicate symbol (which can be taken to code multiple predicates/functions below), together with the second-order statement ``I am wellfounded''. (Remark: I mistakenly said "one" constant symbol in an earlier version; but I used set-many. Actually for the purposes below we can restrict the number of constants available to something like the cardinality of $V_{\kappa+2}$, where $\kappa$ is the cardinal in question.)

Claim: Let $\kappa$ be a cardinal and suppose that $\mathcal{L}$ as above is $\kappa$-compact. Then there is a measurable cardinal $\leq\kappa$.

Proof: First suppose that $\kappa$ is inaccessible. Consider the $\mathcal{L}$-theory $T$ which includes the full first order theory of $V_{\kappa+1}$ in parameters, the formulas $\alpha < \dot{\mu} < \kappa$, for each $\alpha < \kappa$, where $\dot{\mu}$ is a new constant, and the (2nd order) formula “I am wellfounded”. If $M$ is a (wellfounded) model of $T$, note that there is an elementary $j:V_{\kappa+1}\to M$, the critical point $\mathrm{crit}(j)$ of $j$ exists, and is a measurable cardinal $\leq\kappa$. So we just need to see the small subtheories have models, but this follows easily from the inaccessibility of $\kappa$ (consider elementary substructures of $V_{\kappa+1}$).

Now suppose $\kappa$ is singular. Let $f:\eta\to\kappa$ be cofinal, where $\eta<\kappa$. Consider the theory $T$ consisting of the first order theory in parameters of $V_\kappa$, and using function symbols $\dot{f},\dot{g}$, the statement "$\dot{f}:\eta\to\mathrm{Ord}$ is cofinal", the equations "$\dot{f}(\alpha)=\beta$" for each $\alpha,\beta$ such that $f(\alpha)=\beta$, and the statement "$\dot{g}$ is a surjection from some ordinal onto $\mathrm{Ord}$", and (2nd order) "I am wellfounded". Then for each $\theta<\kappa$, each fragment $\bar{T}$ of size $\theta$ is satisfiable, since we may assume $\eta<\theta$, and we can find an elementary substructure of $(X,f\cap X)\preceq(V_\kappa,f)$ of cardinality $\theta$, with $\theta+1\subseteq X$, and then the transitive collapse $(M,\bar{f},g)$ is a model, where we take $g:\theta\to\mathrm{Ord}^M$ a surjection. So we get a wellfounded model $(M,f',g')$ of the full theory. Let $j:V_\kappa\to M$ be the resulting elementary embedding. Note that $\mathrm{crit}(j)<\kappa$, because otherwise $f'=f$, so by cofinality, $\kappa=\mathrm{Ord}^M$, so $M=V_\kappa$, so $g':\gamma\to\kappa$ is a surjection for some $\gamma<\kappa$, contradiction. But then $\mathrm{crit}(j)<\kappa$ is measurable.

Finally suppose that $\gamma<\kappa\leq 2^\gamma$. Then consider the theory consisting of the first order theory in parameters of $\mathcal{H}_{(2^\gamma)^+}$, "I am wellfounded", and the statement "$\dot{f}:\mathcal{P}(\gamma)\to\mathrm{Ord}$ is surjective". Any sub-theory of size $<\kappa$ is satisfiable (in fact, any sub-theory of size $\leq 2^\gamma$ is satisfiable), so we have a model, and note it gives a measurable $\leq\gamma$.

(This leaves $\omega$, but it's easy to see this is impossible; also cf. Noah's comments in the question and below.)

Added remarks on cardinal successor compactness
Source Link
Farmer S
  • 9.9k
  • 24
  • 42

I think that if you have a logic $\mathcal{L}$ which has downward Lowenheim-Skolem (for theories of arbitrary cardinality, i.e. if $T$ has cardinality $\lambda$ and $N$ is a model $A$ of size $\theta\geq\lambda$, and $\lambda\leq\gamma\leq\theta$, then we can find a sub-model of size $\gamma$ which is elementary in $A$ (w.r.t. the relevant formulas of the logic)), then its strong compactness number is $\leq$ the least supercompact $\kappa$.

For suppose $T$ is a theory in $\mathcal{L}$ such that all subsets of $T$ of size ${<\kappa}$ have a model. Let $\lambda$ be the cardinality of $T$; we consider $T\subseteq\lambda$. Let $j:V\to M$ with $\mathrm{crit}(j)=\kappa$ and $\mathcal{P}(\lambda)\subseteq M$ and $j\upharpoonright\lambda\in M$. Then $M$ thinks that every sub-theory of $j(T)$ of size $<j(\kappa)$ has a model. But we have $T\in M$ and $T\subseteq\lambda$, and note that $T$ is equivalent to $j``T\in M$, and this has size $\lambda<j(\kappa)$ in $M$. So $T$ has a model $B$ in $M$. But by Lowenheim-Skolem, then it has a model of size $\lambda$ in $M$. Since $\mathcal{P}(\lambda)\subseteq M$, this is truly a model in $V$.

edit. If kappa is inaccessible and we have compactness at kappa with respect to the logic which includes the full first order language of set theory together with a constant symbol, plus the (second order) statement “I am wellfounded”, then there is a measurable less than or equal to kappa. For consider the theory T in the language of set theory plus the constant symbol mu-dot, which includes the full first order theory of $V_{\kappa+1}$ in parameters, the formulas “alpha < mu-dot < kappa”, for each alpha < kappa, and the (2nd order) formula “I am wellfounded”. If that has a model, then it’s truly wellfounded, and it follows there’s a measurable less or equal to kappa. So we just need to see the small subtheories have models, but this easily follows from inaccessibility.

edit 2. Suppose we have compactness at $\kappa=\gamma^+$ for the language as above, with constant symbol X. Then there is a measurable cardinal $\leq\gamma$. For consider the theory consisting of the first order theory in parameters of $H=\mathcal{H}_{\kappa}$, plus “I am wellfounded”, plus “X is a wellorder of $\gamma$“ plus the statements “$\alpha<$ the ordertype of X”, for each $\alpha<\kappa$. Clearly each size $<\kappa$ subtheory is satisfiable. But if $M$ satisfies the whole theory then $M\neq H$, because of $X^M$, and we have an elementary $\pi:H\to M$, and it has a critical point, which is measurable.

I think that if you have a logic $\mathcal{L}$ which has downward Lowenheim-Skolem (for theories of arbitrary cardinality, i.e. if $T$ has cardinality $\lambda$ and $N$ is a model $A$ of size $\theta\geq\lambda$, and $\lambda\leq\gamma\leq\theta$, then we can find a sub-model of size $\gamma$ which is elementary in $A$ (w.r.t. the relevant formulas of the logic)), then its strong compactness number is $\leq$ the least supercompact $\kappa$.

For suppose $T$ is a theory in $\mathcal{L}$ such that all subsets of $T$ of size ${<\kappa}$ have a model. Let $\lambda$ be the cardinality of $T$; we consider $T\subseteq\lambda$. Let $j:V\to M$ with $\mathrm{crit}(j)=\kappa$ and $\mathcal{P}(\lambda)\subseteq M$ and $j\upharpoonright\lambda\in M$. Then $M$ thinks that every sub-theory of $j(T)$ of size $<j(\kappa)$ has a model. But we have $T\in M$ and $T\subseteq\lambda$, and note that $T$ is equivalent to $j``T\in M$, and this has size $\lambda<j(\kappa)$ in $M$. So $T$ has a model $B$ in $M$. But by Lowenheim-Skolem, then it has a model of size $\lambda$ in $M$. Since $\mathcal{P}(\lambda)\subseteq M$, this is truly a model in $V$.

edit. If kappa is inaccessible and we have compactness at kappa with respect to the logic which includes the full first order language of set theory plus the (second order) statement “I am wellfounded”, then there is a measurable less than or equal to kappa. For consider the theory T in the language of set theory plus the constant symbol mu-dot, which includes the full first order theory of $V_{\kappa+1}$ in parameters, the formulas “alpha < mu-dot < kappa”, for each alpha < kappa, and the (2nd order) formula “I am wellfounded”. If that has a model, then it’s truly wellfounded, and it follows there’s a measurable less or equal to kappa. So we just need to see the small subtheories have models, but this easily follows from inaccessibility.

I think that if you have a logic $\mathcal{L}$ which has downward Lowenheim-Skolem (for theories of arbitrary cardinality, i.e. if $T$ has cardinality $\lambda$ and $N$ is a model $A$ of size $\theta\geq\lambda$, and $\lambda\leq\gamma\leq\theta$, then we can find a sub-model of size $\gamma$ which is elementary in $A$ (w.r.t. the relevant formulas of the logic)), then its strong compactness number is $\leq$ the least supercompact $\kappa$.

For suppose $T$ is a theory in $\mathcal{L}$ such that all subsets of $T$ of size ${<\kappa}$ have a model. Let $\lambda$ be the cardinality of $T$; we consider $T\subseteq\lambda$. Let $j:V\to M$ with $\mathrm{crit}(j)=\kappa$ and $\mathcal{P}(\lambda)\subseteq M$ and $j\upharpoonright\lambda\in M$. Then $M$ thinks that every sub-theory of $j(T)$ of size $<j(\kappa)$ has a model. But we have $T\in M$ and $T\subseteq\lambda$, and note that $T$ is equivalent to $j``T\in M$, and this has size $\lambda<j(\kappa)$ in $M$. So $T$ has a model $B$ in $M$. But by Lowenheim-Skolem, then it has a model of size $\lambda$ in $M$. Since $\mathcal{P}(\lambda)\subseteq M$, this is truly a model in $V$.

edit. If kappa is inaccessible and we have compactness at kappa with respect to the logic which includes the full first order language of set theory together with a constant symbol, plus the (second order) statement “I am wellfounded”, then there is a measurable less than or equal to kappa. For consider the theory T in the language of set theory plus the constant symbol mu-dot, which includes the full first order theory of $V_{\kappa+1}$ in parameters, the formulas “alpha < mu-dot < kappa”, for each alpha < kappa, and the (2nd order) formula “I am wellfounded”. If that has a model, then it’s truly wellfounded, and it follows there’s a measurable less or equal to kappa. So we just need to see the small subtheories have models, but this easily follows from inaccessibility.

edit 2. Suppose we have compactness at $\kappa=\gamma^+$ for the language as above, with constant symbol X. Then there is a measurable cardinal $\leq\gamma$. For consider the theory consisting of the first order theory in parameters of $H=\mathcal{H}_{\kappa}$, plus “I am wellfounded”, plus “X is a wellorder of $\gamma$“ plus the statements “$\alpha<$ the ordertype of X”, for each $\alpha<\kappa$. Clearly each size $<\kappa$ subtheory is satisfiable. But if $M$ satisfies the whole theory then $M\neq H$, because of $X^M$, and we have an elementary $\pi:H\to M$, and it has a critical point, which is measurable.

Added remarks on lower bounds
Source Link
Farmer S
  • 9.9k
  • 24
  • 42

I think that if you have a logic $\mathcal{L}$ which has downward Lowenheim-Skolem (for theories of arbitrary cardinality, i.e. if $T$ has cardinality $\lambda$ and $N$ is a model $A$ of size $\theta\geq\lambda$, and $\lambda\leq\gamma\leq\theta$, then we can find a sub-model of size $\gamma$ which is elementary in $A$ (w.r.t. the relevant formulas of the logic)), then its strong compactness number is $\leq$ the least supercompact $\kappa$.

For suppose $T$ is a theory in $\mathcal{L}$ such that all subsets of $T$ of size ${<\kappa}$ have a model. Let $\lambda$ be the cardinality of $T$; we consider $T\subseteq\lambda$. Let $j:V\to M$ with $\mathrm{crit}(j)=\kappa$ and $\mathcal{P}(\lambda)\subseteq M$ and $j\upharpoonright\lambda\in M$. Then $M$ thinks that every sub-theory of $j(T)$ of size $<j(\kappa)$ has a model. But we have $T\in M$ and $T\subseteq\lambda$, and note that $T$ is equivalent to $j``T\in M$, and this has size $\lambda<j(\kappa)$ in $M$. So $T$ has a model $B$ in $M$. But by Lowenheim-Skolem, then it has a model of size $\lambda$ in $M$. Since $\mathcal{P}(\lambda)\subseteq M$, this is truly a model in $V$.

edit. If kappa is inaccessible and we have compactness at kappa with respect to the logic which includes the full first order language of set theory plus the (second order) statement “I am wellfounded”, then there is a measurable less than or equal to kappa. For consider the theory T in the language of set theory plus the constant symbol mu-dot, which includes the full first order theory of $V_{\kappa+1}$ in parameters, the formulas “alpha < mu-dot < kappa”, for each alpha < kappa, and the (2nd order) formula “I am wellfounded”. If that has a model, then it’s truly wellfounded, and it follows there’s a measurable less or equal to kappa. So we just need to see the small subtheories have models, but this easily follows from inaccessibility.

I think that if you have a logic $\mathcal{L}$ which has downward Lowenheim-Skolem (for theories of arbitrary cardinality, i.e. if $T$ has cardinality $\lambda$ and $N$ is a model $A$ of size $\theta\geq\lambda$, and $\lambda\leq\gamma\leq\theta$, then we can find a sub-model of size $\gamma$ which is elementary in $A$ (w.r.t. the relevant formulas of the logic)), then its strong compactness number is $\leq$ the least supercompact $\kappa$.

For suppose $T$ is a theory in $\mathcal{L}$ such that all subsets of $T$ of size ${<\kappa}$ have a model. Let $\lambda$ be the cardinality of $T$; we consider $T\subseteq\lambda$. Let $j:V\to M$ with $\mathrm{crit}(j)=\kappa$ and $\mathcal{P}(\lambda)\subseteq M$ and $j\upharpoonright\lambda\in M$. Then $M$ thinks that every sub-theory of $j(T)$ of size $<j(\kappa)$ has a model. But we have $T\in M$ and $T\subseteq\lambda$, and note that $T$ is equivalent to $j``T\in M$, and this has size $\lambda<j(\kappa)$ in $M$. So $T$ has a model $B$ in $M$. But by Lowenheim-Skolem, then it has a model of size $\lambda$ in $M$. Since $\mathcal{P}(\lambda)\subseteq M$, this is truly a model in $V$.

I think that if you have a logic $\mathcal{L}$ which has downward Lowenheim-Skolem (for theories of arbitrary cardinality, i.e. if $T$ has cardinality $\lambda$ and $N$ is a model $A$ of size $\theta\geq\lambda$, and $\lambda\leq\gamma\leq\theta$, then we can find a sub-model of size $\gamma$ which is elementary in $A$ (w.r.t. the relevant formulas of the logic)), then its strong compactness number is $\leq$ the least supercompact $\kappa$.

For suppose $T$ is a theory in $\mathcal{L}$ such that all subsets of $T$ of size ${<\kappa}$ have a model. Let $\lambda$ be the cardinality of $T$; we consider $T\subseteq\lambda$. Let $j:V\to M$ with $\mathrm{crit}(j)=\kappa$ and $\mathcal{P}(\lambda)\subseteq M$ and $j\upharpoonright\lambda\in M$. Then $M$ thinks that every sub-theory of $j(T)$ of size $<j(\kappa)$ has a model. But we have $T\in M$ and $T\subseteq\lambda$, and note that $T$ is equivalent to $j``T\in M$, and this has size $\lambda<j(\kappa)$ in $M$. So $T$ has a model $B$ in $M$. But by Lowenheim-Skolem, then it has a model of size $\lambda$ in $M$. Since $\mathcal{P}(\lambda)\subseteq M$, this is truly a model in $V$.

edit. If kappa is inaccessible and we have compactness at kappa with respect to the logic which includes the full first order language of set theory plus the (second order) statement “I am wellfounded”, then there is a measurable less than or equal to kappa. For consider the theory T in the language of set theory plus the constant symbol mu-dot, which includes the full first order theory of $V_{\kappa+1}$ in parameters, the formulas “alpha < mu-dot < kappa”, for each alpha < kappa, and the (2nd order) formula “I am wellfounded”. If that has a model, then it’s truly wellfounded, and it follows there’s a measurable less or equal to kappa. So we just need to see the small subtheories have models, but this easily follows from inaccessibility.

Source Link
Farmer S
  • 9.9k
  • 24
  • 42
Loading