## New answers tagged lo.logic

5
votes

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

6
votes

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

5
votes

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
votes

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

4
votes

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

7
votes

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

5
votes

### How big can function spaces get without extensionality?

Expanding on my comment: The methods from Richard Garner’s 2008 paper On the strength of dependent products in the type theory of Martin-Löf (arXiv:0803.4466) show that your axiom $\newcommand{\big}{\...

5
votes

### Nonexistence of short integer program sequence which generates squares

If you can do this efficiently, you can factor integers efficiently.
Set $X-Y=N$.
If $X=u^2,Y=v^2$ then $(u^2-v^2)=(u-v)(u+v)=N$ will give the factorization of $N$.
To avoid the trivial solution, add ...

6
votes

### How big can function spaces get without extensionality?

$\newcommand{Pot}{\mathsf{Pot}}
\newcommand{Act}{\mathsf{Act}}
\newcommand{Id}{\mathsf{Id}}
\newcommand{refl}{\mathsf{refl}}$
I'm happy to defer to someone more knowledgeable on the topic. However, I'...

15
votes

Accepted

### Finite verification for theorems due to Busy Beaver numbers

I would like to elaborate on an idea at the end of one of Z. A. K.'s comments above. The following quote is from Scott Aaronson's "The Busy Beaver Frontier" (2020):
As we’ll see in Section ...

48
votes

### Finite verification for theorems due to Busy Beaver numbers

Many years ago I was at a party in Berkeley and found myself standing in a group of fellow graduate students listening to Hendrik Lenstra, the famous number theorist, holding court.
Someone asked ...

27
votes

### Finite verification for theorems due to Busy Beaver numbers

Yes, this can be proven directly.
Suppose all even numbers greater than two are a sum of two primes. Then $N=2$ works, so the statement is true.
Suppose not all even numbers greater than two are a sum ...

3
votes

### Negating fundamental axioms

At the very bottom of logical strength, there is the following example.
Julian Hook's PhD thesis with title A Many-Sorted Approach to Predicative Mathematics, written under the supervision of Ed ...

0
votes

### Completing half of Hilbert's program: Foundations that are conservative over Peano Arithmetic

One possible such theory is described by Solomon Feferman in chapter 13 (“Weyl vindicated: Das Kontinuuum seventy years later”) of his book In the Light of Logic (Oxford University Press 1998); ...

3
votes

### Completing half of Hilbert's program: Foundations that are conservative over Peano Arithmetic

The foundation in this answer is probably a bit weird to work in, but I think it is interesting meta-mathematically and would at least be interesting to compare other foundations too. Perhaps it is bi-...

4
votes

### Mostowski's absoluteness theorem and proving that theories extending $0^\#$ have incomparable minimal transitive models

This answer by Farmer S to another question, which Farmer S linked in a comment to this question, proves that if $\alpha$ is the least ordinal that is the height of a transitive model of $\text{ZFC}+0^...

Community wiki

5
votes

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

4
votes

Accepted

### Two equivalent statements about formulas projected onto an Ultrafilter

First, since I found your notation confusing, I hope you don't mind if I rewrite your Question 1 in more standard notation.
Fix a language $L$. Let $I$ be a non-empty set, and let $(\varphi_i)_{i\in I}...

8
votes

Accepted

### Negating fundamental axioms

In my limited experience (which may soon be changed! :P), merely negating "fundamental" axioms does not yield strong in-system consequences. The word "merely" is doing some work ...

5
votes

### Equivalence of omniscience principles for natural numbers and analytic omniscience principles for Cauchy real numbers

Let me try to tackle the LPO case. I will even try to show that it doesn't matter whether we assume our Cauchy sequences to have a modulus or not. (Please check me carefully because I know I've made ...

5
votes

Accepted

### About having one axiom schema for ZFC motivated after the iterative conception of sets?

I won't engage with the level terminology, but I believe your question is answered by the following observation.
Theorem. ZFC is equiconsistent with the theory ZFC + there is a closed unbounded class $...

4
votes

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

5
votes

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

17
votes

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

6
votes

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

5
votes

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

11
votes

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

16
votes

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

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

8
votes

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

4
votes

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

3
votes

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

Community wiki

2
votes

### Axiomatic strength of the cumulative hierarchy

Now, I think the bare idea of a Hierarchy is this:
if $F$ is a total unary function, then we can build a function $V$, such that:
$V^F_\emptyset = \emptyset \\ V^F_{\alpha+1} = F(V^F_\alpha) \\ V^F_\...

5
votes

### How strong is the Schröder–Bernstein theorem where one set is the natural numbers?

I have a slight strengthening of OP’s result. Assume the Schröder–Bernstein Theorem for $\mathbb{N}$.
Lemma (Creating Subject): for all propositions $P$, there exists a function $f : \mathbb{N} \to \{...

0
votes

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

13
votes

### Is it consistent with ZFC that the real line is approachable by sets with no accumulation points?

Here's a ZF proof that if $S$ is a chain of sets with $\bigcup S = \mathbb{R},$ then there is $X \in S$ which contains a countable set dense in some nonempty open set.
If there is $X \in S$ such that $...

23
votes

Accepted

### Is it consistent with ZFC that the real line is approachable by sets with no accumulation points?

It is a very nice question, but unfortunately, this is impossible.
Each member $s\in S$ must be countable, since uncountable sets have accumulation points. And since the hierarchy is accumulating as ...

3
votes

Accepted

### A question on the size of an admissible ordinal

Some references to literature: In "Reflection and Partition Properties of Admissible Ordinals" (Annals of Math. Logic vol. 22, iss. 3, 1982), Kranakis defines a $\Sigma_n$-admissible ordinal ...

0
votes

### Computability-theoretic results relevant to realizability

This wasn't exactly what I had in mind when I first asked this question, but I don't think it's unrelated either: combining realizability (in a very naive way) with classical computability-theoretic ...

16
votes

Accepted

### What gets to be called a "proper class?"

The term "class" is not a technical term with a universally definite meaning, but there are various established meanings in various contexts.
In ZFC the established usage as Wojowu mentions ...

19
votes

Accepted

### Proof/Reference to a claim about AC and definable real numbers

The argument, given to me by Hugh Woodin over a drink in Barcelona in September 2016, is a nice retort to "AC is obviously false since there cannot be a well-ordering of the real numbers". ...

14
votes

### Proof/Reference to a claim about AC and definable real numbers

Unfortunately, the claim you have stated is not true. Regardless of the axiom of choice, every real is definable from a countable sequence of ordinal parameters, since the real is definable from the ...

2
votes

### What is a "general" relation algebra?

I understand where general elements of it "come from."
Well, you do and you don't. You do because you know the elements of a representable relation algebra are relations on some set. You ...

2
votes

### What is a "general" relation algebra?

As relation algebras are Boolean algebras with extra bits of structure (sometimes `with operations'), they occur importantly in the algebraic semantics of modal logics (see for instance the paper R. ...

4
votes

### What is a "general" relation algebra?

I don't know anything about the history and context of this idea of a relation algebra but the definition doesn't smell like "the right one" to me, and for a simple reason: why restrict ...

7
votes

### What is a "general" relation algebra?

There is one natural candidate that leaps to mind, namely the construal of $2^G$ as a relation algebra for each group $G$ $\ldots$
This construction will not answer your question, since each relation ...

2
votes

### Variable-centric logical foundation of calculus

As mentioned in one comment, you might be interested in Calculus – A modern approach (1955) by Karl Menger:
What Is A Variable?
The conceptual and semantic clarification of calculus is centered on
...

2
votes

### Which ordinals can be proof-theoretic ordinals of a reasonable theory?

Pakhomov and Walsh proved the following result:
Theorem. Let $\alpha$ be an ordinal notation. Then $|\mathbf{R}^\alpha_{\Pi^1_1}(\mathsf{ACA}_0)|_{\Pi^1_1}=\varepsilon_\alpha$.
Here $\mathbf{R}^\...

9
votes

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

8
votes

### Which are the hereditarily computably enumerable sets?

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

Top 50 recent answers are included

#### Related Tags

lo.logic × 5275set-theory × 2371

model-theory × 882

computability-theory × 551

reference-request × 485

forcing × 433

large-cardinals × 380

ct.category-theory × 287

proof-theory × 279

axiom-of-choice × 273

theories-of-arithmetic × 258

descriptive-set-theory × 227

foundations × 191

mathematical-philosophy × 175

constructive-mathematics × 149

reverse-math × 136

computational-complexity × 124

type-theory × 119

soft-question × 116

nt.number-theory × 115

gn.general-topology × 105

topos-theory × 105

co.combinatorics × 103

gr.group-theory × 103

ho.history-overview × 102