Fedor Pakhomov
  • Member for 8 years, 5 months
  • Last seen this week
1 answers
votes
266 views
What subsystem of second-order arithmetic is needed for the recursion theorem?
Accepted answer
11 votes

As Wojowu already pointed out $\mathsf{RCA}_0$ proves recursion theorem. You could find a proof in Simpson's book [1], Section II.3. In fact primitive recursion theorem is equivalent to $\Sigma^0_1\...

View answer
2 answers
votes
636 views
Ordinal analysis and proofs of consistency
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
Is choice over definable sets equivalent to AC over axioms of ZF-Reg.?
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
Is there a theory in a finite language that is computably axiomatizable but not by a finite number of axiom schemas?
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
Infinite descending consistency chains
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
Is restricting Replacement and Separation enough to make $Q+I\Sigma_n$ bi-interpretable with Set Theory?
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
The inconsistency of Graham Arithmetics plus $ \forall n, n < g_{64}$
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^...

View answer
2 answers
votes
383 views
Ordinal notations within non-standard models of arithmetic
Accepted answer
6 votes

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 ...

View answer
1 answers
votes
260 views
Capturing the $\omega_1^{\mathrm{CK}}$-th stage of Gödel's constructible hierarchy
Accepted answer
6 votes

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(\...

View answer
1 answers
votes
383 views
Is there an infinitary sentence which is absolutely not second-order expressible?
Accepted answer
5 votes

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
Sharp Craig interpolation theorem for $L_{\omega_1 \omega}$
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
The lattice of analogues of Robinson's $Q$
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
Is there a relation between type (maximum linearization) of a computable WQO and the ordinal strength of a theory needed to prove it?
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
Compact definition of ordinals
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
Proof-theoretic ordinals: inevitable consistency?
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 $\...

View answer
1 answers
votes
219 views
Can power set axiom be proved in a class theory of well ordered hereditarily accessible sets?
Accepted answer
5 votes

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 ...

View answer
1 answers
votes
291 views
Order types of models of theories of ordinals
4 votes

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 ...

View answer
1 answers
votes
328 views
What is the strength of adding limitation of size and a simple version of reflection to Ackermann set theory?
Accepted answer
4 votes

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 ...

View answer
1 answers
votes
203 views
Independence of $\Pi^1_1$-induction from ATR$_0$
Accepted answer
3 votes

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
Are there structures in a finite signature that are recursively categorically axiomatizable in SOL but not finitely categorically axiomatizable?
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
Strengthening of Shoenfield's result on the recursive omega-rule
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
Models of arithmetical theory R + induction in which successor is not injective
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
Proof-theoretic ordinals after liberalizing induction to $RCA_0$
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 ...

View answer
1 answers
vote
202 views
Interpreting PA2 in second-order logic + existence of infinitely many objects
Accepted answer
1 votes

First note that monadic second-order logic (i.e. the variant of second-order logic with second-order quantifiers only over unary predicates) isn't sufficient. This is implied by the fact that the ...

View answer