# Tag Info

### At what ordinal $\chi$ does $\mathrm{L}_\chi$ contain a surjection from $\omega$ to $\mathrm{L}_{\beta_0}$?

As a precoda to Gabe's answer, it's worth noting that $\beta_0$ is in fact the first ordinal $\alpha$ which "starts a gap," i.e. such that $L_{\alpha+1}\models$ "$\alpha$ is uncountable....
• 20.7k
Accepted

### Natural functions outside $\sf PA$?

Sure, but this is really a fact about structures rather than theories. For example, $\mathsf{ZFC}$ can define the function sending $n$ to the least natural number not definable in the language of ...
• 20.7k
Accepted

### Can we see quantifier elimination by comparing semirings?

No, for example consider $T=\mathsf{Th}(\mathbb{N};=,0,1,+)$, i.e. Presburger arithmetic in non-extended signature. Quantifier elimination does not hold for this $T$: this would require to extend the ...
• 5,546
Accepted

### Can PA define functions related to higher theories?

Yes, this function is obviously definable in PA and PA proves it is total. You are defining the tower of theories by recursion, which PA can do, and taking the Rosser sentence of each theory, which PA ...

### Example of applying real quantifier elimination algorithm for polynomials

Although this question is nearly 5 years old, I'd like to write a proper answer to this in case it helps anyone. First, I'd suggest not to study Tarski's construction if you are interested in ...
• 41
Accepted

### Large almost disjoint family on $\mathbb{N}$ with property $\mathbf{B}$

One of the standard examples of an almost disjoint family of cardinality $\mathfrak c$ is the set of paths through the complete binary tree $2^{<\omega}$ (identified with $\omega$ via your favorite ...
• 72.4k

### Negating fundamental axioms

I just wanted to point out as a comment that there is some ambiguity, already mentioned by Joel David Hamkins, about what it means to "negate fundamental axioms" (there is some further ...
• 951
Accepted

### Heuristic interpretations of the PA-unprovability of Goodstein's Theorem

To my way of thinking, the arguments you mention seem not to distinguish sufficiently between the content of Goodstein's theorem as a universal claim $\forall p$ and Goodstein's theorem as a ...
Accepted

### Heuristic interpretations of the PA-unprovability of Goodstein's Theorem

You've shown how to prove, in PA, the statement "the Goodstein sequence starting with $p$ terminates" for any given $p$. But once $p$ is given, that statement has a proof in PA that just ...
• 72.4k
Accepted

### Is the field of constructible numbers known to be decidable?

See Barry Mazur, Karl Rubin, Alexandra Shlapentokh, Defining $\mathbb{Z}$ using unit groups, Acta Arithmetica (Published online: 27 June 2024) DOI: 10.4064/aa230505-6-6 One of the corollaries of our ...
Accepted

### Axiomatic strength of the cumulative hierarchy

This is an edited and improved answer; see edit details at the end. We can obtain the whole of ZF using a single, natural, scheme. I will keep the definition of level from Button 2021, as cited above. ...
• 136
Accepted

### What determines non-finite axiomatizability of a class extension of a set theory?

As explained with more details in https://mathoverflow.net/a/87249, every sequential theory that proves the induction schema for all formulas in its languages is reflexive (even uniformly essentially ...
• 45.7k
Accepted

### Which part(s) of this proof of Goodstein's Theorem are not expressible in Peano arithmetic?

Because your argument involves arithmetical classes at several points, as you noticed, it is not directly expressible in the first-order language of $\newcommand\PA{\text{PA}}\PA$, although as Noah ...
Accepted

### Rigid non-archimedean real closed fields

Charles Steinhorn and I have answered this question positively by constructing a rigid non-archimedean real closed field of transcendence degree 2. Our preprint is now posted on arxiv. https://arxiv....
• 3,460
1 vote

### Variable-centric logical foundation of calculus

The following papers present a "relational" rather than "functional" approach to differential calculus: Extending the algebraic manipulability of differentials Simplifying and ...
• 1,823
Accepted

### Am I doing a forcing argument here?

This is not quite an answer to the question you asked, but: The argument, and any similar argument, can't work because the theorem to be proven is false. Let me quote the result: Let $\mathcal C$ be ...
• 141k
Accepted

### How can we define non-finitely axiomatizable extensions of set theories?

For any "reasonable" theory $T$, we can find a computable sequence of sentences $(\sigma_i^T)_{i\in\omega}$ such that $T\cup\{\sigma_i^T: i\not=n\}\not\vdash\sigma_n^T$ for each $n$ (so the ...
• 20.7k

### Am I doing a forcing argument here?

It looks like the "logic aspects" of the argument boil down to using compactness. [However, this appears to be moot since the argument may have flaws pointed out by Will Sawin.] First, ...

• 263

### When can a function defined on $[a, b] \cup [b, c]$ be constructively extended to a function defined on $[a, c]$?

This is mostly a long comment, not really an answer. If one slightly modifies the closed interval notation as follows: $$[a,b\Vert = \{ x : a \leq x \not\gt b \}$$ \Vert b,c] = \{ x : b \not\gt x \...
• 43.8k

• 2,910
Accepted

### Which are the hereditarily computably enumerable sets?

The complexity of h.c.e. sets is quite subtle as the structure of the target set affects our ability to offload complexity to the limiting process. The property of being an h.c.e. code is $Π^1_1$ ...
• 6,365
Re question 3: Not every arithmetic real is h.c.e.. In fact, every h.c.e. real is $\Sigma_2^\mathbb{N}$. For fix a program $e$ such that $x_e\subseteq\omega$. Let $n\in\omega$. Then $n\in x_e$ iff ...