266 views

As Wojowu already pointed out $\mathsf{RCA}_0$ proves recursion theorem. You could find a proof in Simpson's book , Section II.3. In fact primitive recursion theorem is equivalent to $\Sigma^0_1\... View answer 2 answers votes 636 views 11 votes In the field of ordinal analysis people are typically interested in finding "natural" computable ordinal notation systems corresponding to various theories; those are called proof-theoretic ordinals ... View answer 1 answers votes 200 views Accepted answer 10 votes Yes, indeed this kind of choice in general doesn't imply$\mathsf{AC}$over$\mathsf{ZF}-\mathsf{Reg}$. I will reason in$\mathsf{ZFC}$and construct an interpretation of$\mathsf{ZF}-\mathsf{Reg}$, ... View answer 3 answers votes 543 views Accepted answer 10 votes Let me give an example of a theory that is computably axiomatizable but isn't axiomatizable by finitely many schemas. Fix any finite signature$\Omega$with equality. Further by finite$\Omega$-models ... View answer 3 answers votes 609 views 10 votes I know two constructions of the chains of this sort that aren't based on explicit diagonalization. In a recent work by James Walsh and me https://arxiv.org/abs/1805.02095 we gave an example (Theorem ... View answer 1 answers votes 247 views Accepted answer 9 votes First let me note that one should be careful with formulation of$\mathsf{ZFCfin}$, for it to be bi-interpretable with$\mathsf{PA}$(see the paper "On interpretations of arithmetic and set theory" by ... View answer 2 answers votes 723 views 7 votes The length of the least proof of contradiction in$\mathsf{Graham}+\forall n (n&lt;g_{64})$should be inbetween$(\log_2^*(g_{64}))^{1/N}$and$(\ln^*(g_{64}))^{N}$, where$\ln^*(x)=\min\{n\mid \log_2^...

383 views

I'll provide a description of $(\alpha)^{\mathfrak{A}}$ in the case of countable $\mathfrak{A}$. I base my answer on observations by Emil Jeřábek (see discussion below the initial question), but of ...

260 views

This couldn't be achieved even by $\Sigma_3$ sentences. First note that $L_{\omega_1^{CK}}$ (as any other model of $\mathsf{KP}\omega+L=V$) satisfies the scheme of $\Sigma_3$-reflection: \varphi(\...

383 views

For any given finite signature $\Omega$ there is a second-order sentence $\varphi$ of the signature $\Omega$ such that $\mathsf{ZFC}+V=L$ proves that for any $\mathcal{L}_{\infty,\omega}$-formula $\... View answer 1 answers votes 144 views Accepted answer 5 votes It actually isn't true that the complexity of$\theta$could be meaningfully bounded in the term of complexities of$\varphi$and$\psi$. Let us fix an arbitrary recursive ordinal$\alpha$. Below I ... View answer 1 answers votes 301 views Accepted answer 5 votes$\mathfrak{Q}$is the countable random distributive lattice. Emil Jeřábek has already pointed in his comments that there are only two possibilities for$\mathfrak{Q}$. Either there are no greatest ... View answer 1 answers votes 194 views Accepted answer 5 votes Let me show that for extensions$T\supseteq\mathsf{ACA}_0$the usual proof-theoretic ordinal$|T|_{WO}$coincide with$|T|_{WPO}$that is the suprema of$\mathsf{o}(X)$, for recursive wpo$X$, for ... View answer 3 answers votes 594 views 5 votes In order to prove that any class$\mathrm{No}$satisfying this definition is well-ordered by$\in$it is crucial to use the axiom of foundation. Axiom of foundation tells us that$\in$is a well-... View answer 1 answers votes 360 views Accepted answer 5 votes The ineventable consistency ordinals do not exist for all the computably axiomatizable extensions of$\mathsf{RCA}_0$. Indeed, for any given notation system$\alpha$I'll construct a notation system$\...

219 views

Your system indeed couldn't prove even that $\mathcal{P}(\omega)$ is a set. Let $M$ be a countable transitive of $\mathsf{ZFC}+\mathsf{GCH}+\mbox{there exists an inaccessible}$. Let $\kappa\in M$ be ...

291 views

First, I'll discuss the case of empty $C$. Observe that the structures $(\varepsilon_{\alpha};+,\cdot,\mathsf{exp})$ are definitionally equivalent with the structures $HF(\alpha;&lt;)$ (the structure ...

328 views

Let me denote as $\mathsf{K}(V)$ your system 1.+2.+3.+Super Transitivity. And as $\mathsf{K}^{+}(V)$ your system 1.+2.+3.+Limitation of size. Note that the well-founded part translation gives an ...

203 views
Let me sketch the proof that $\mathsf{ATR}_0+\Pi^1_1\textsf{-Ind}\vdash\mathsf{Con}(\mathsf{ATR}_0)$ (by Gödel's 2-nd incompleteness this implies that $\mathsf{ATR}_0$ doesn't prove $\Pi^1_1\textsf{-... View answer 2 answers votes 230 views 2 votes There is even an example of a cardinal$\kappa$and an r.e. categorical second-order theory$T$such that for no finitely axiomatized second-order theory$U$, the spectrum of$U$has$\kappa$as its ... View answer 1 answers votes 151 views 2 votes In short the answer is yes. Let us consider Schütte-style proof of completeness of$\omega$-logic. This proof works as follows. For any sequent$\Gamma$we define it's canonical (cut-free) pre-proof ... View answer 1 answers votes 145 views Accepted answer 2 votes I don't have a general classification of this kind of models, but it is rather easy to construct quite a lot of models with this property. For example (for first-order variant of your system), ... View answer 1 answers votes 359 views 2 votes I don't have complete answer but I think that my remarks still may be useful. Let me consider theory$\mathsf{NT}$which extends$\mathsf{PRA}$by one unary predicate$X\$ and axiom scheme of ...