Skip to main content

New answers tagged

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....
Noah Schweber's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Fedor Pakhomov's user avatar
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 ...
Joel David Hamkins's user avatar
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 ...
Maaz's user avatar
  • 41
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 ...
Andreas Blass's user avatar
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}{\...
Peter LeFanu Lumsdaine's user avatar
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 ...
joro's user avatar
  • 24.7k
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'...
Dan Doel's user avatar
  • 414
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 ...
C7X's user avatar
  • 1,696
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 ...
Joel David Hamkins's user avatar
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 ...
Will Sawin's user avatar
  • 141k
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 ...
Sam Sanders's user avatar
  • 4,087
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); ...
Gro-Tsen's user avatar
  • 30.8k
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-...
Christopher King's user avatar
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^...
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 ...
Joe Lamond's user avatar
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}...
Alex Kruckman's user avatar
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 ...
Noah Schweber's user avatar
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 ...
Gro-Tsen's user avatar
  • 30.8k
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 $...
Joel David Hamkins's user avatar
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 ...
Joel David Hamkins's user avatar
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 ...
Andreas Blass's user avatar
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 ...
GuestPoster5678's user avatar
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. ...
Tim Button's user avatar
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 ...
Emil Jeřábek's user avatar
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 ...
Joel David Hamkins's user avatar
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....
Dave Marker's user avatar
  • 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 ...
user76284's user avatar
  • 1,823
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 ...
Will Sawin's user avatar
  • 141k
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 ...
Noah Schweber's user avatar
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, ...
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_\...
Zuhair Al-Johar's user avatar
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 \{...
Mark Saving's user avatar
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 \...
François G. Dorais's user avatar
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 $...
Elliot Glazer's user avatar
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 ...
Joel David Hamkins's user avatar
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 ...
C7X's user avatar
  • 1,696
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 ...
Noah Schweber's user avatar
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 ...
Joel David Hamkins's user avatar
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". ...
Asaf Karagila's user avatar
  • 38.5k
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 ...
Joel David Hamkins's user avatar
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 ...
Adam Přenosil's user avatar
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. ...
Tim Porter's user avatar
  • 9,367
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 ...
Qiaochu Yuan's user avatar
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 ...
Keith Kearnes's user avatar
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 ...
Alexey Muranov's user avatar
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}^\...
Hanul Jeon's user avatar
  • 2,910
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$ ...
Dmytro Taranovsky's user avatar
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 ...
Farmer S's user avatar
  • 9,167

Top 50 recent answers are included