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

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

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

16
votes

### If every definable class admits a group structure, must global choice hold?

ZFC proves that $V$ admits a definable group structure (and actually ZF does too). First note that the Schröder–Bernstein theorem still holds in the context of definable classes (i.e., for any ...

16
votes

### Are there any non-conjugation "extendible automorphisms" in the category of finite groups?

Finite-extensible automorphisms of finite groups are inner. The proof is rather non-trivial. For the classes of finite nilpotent and finite soluble groups, this is proved in a paper of Pettet, "...

15
votes

### Situation with Artemov's paper?

I appreciate your interest in this work. The paper Serial properties, selector proofs and the provability of consistency passed a rigorous refereeing and has been accepted to JLC. I have just approved ...

15
votes

Accepted

### Had this attempt to salvage naïve comprehension been studied before?

Here is a model of your theory. Start with a countably infinite set of objects $X=\bigsqcup_n X_n$, partitioned into infinitely many infinite sections. We inductively define $\in_n$. Consider the ...

13
votes

Accepted

### If every definable class admits a group structure, must global choice hold?

Yes. By the argument in the answer you linked, for any class $A$, either $\text{Ord}$ injects into $A$, or $A$ is well-orderable. If $A$ is well-orderable and a proper class, then $\text{Ord}$ injects ...

12
votes

### Whether an isotone bijection from a power set lattice to another sends singletons to singletons

Yes, such a mapping necessarily sends singletons to singletons.
Let $f\colon\mathcal P(S)\to\mathcal P(T)$ be a monotone bijection (or more generally, a surjective strictly monotone function). By ...

12
votes

Accepted

### Whether an isotone bijection from a power set lattice to another sends singletons to singletons

Here is a more general fact:
Proposition: Any monotone bijection $f: A \to B$ between two Boolean algebras is an isomorphism.
Claim: $f(0) = 0$ and $f(1) = 1$.
Proof of Claim: For all $a \in A$, $0 \...

11
votes

### Uniqueness results that follow from CH

Under CH, we have saturated models of size continuum of any consistent first-order theory in a countable language, and for a complete theory these are unique by the back-and-forth method.
(In my paper,...

Community wiki

11
votes

### Uniqueness results that follow from CH

An example would be the uniqueness of the asymptotic cone for uniform lattices in $SL_m(\mathbb R)$. Under $\neg CH$, these admit $2^{2^{\aleph_0}}$ non-homeomorphic asymptotic cones.
See
Asymptotic ...

Community wiki

11
votes

Accepted

### An infinite hat puzzle variation—if we don't know our place, can we still be almost all correct?

The prisoners cannot win for $\gamma = \omega^2$ even if there are only 2 colours and they know the entire sequence in advance! Assign colour $0$ to anyone whose position is a limit ordinal, and $1$ ...

10
votes

### Are there any non-conjugation "extendible automorphisms" in the category of finite groups?

Not a complete answer. Your definition of an extendible map says that $\beta$ is an endomorphism of the forgetful functor $U$ from the under category $G \downarrow \mathrm{FinGrp}$ to $\mathrm{Set}$ ...

10
votes

### Cardinal arithmetic under determinacy

Starting from $L(\Bbb R)$, we can take a symmetric extension which preserves $\sf DC$ and adds an $\omega_1$-amorphous set, just somewhere far above $\Theta$.
So we cannot prove that (1) or (2) hold ...

9
votes

Accepted

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

By replacement in $L_{\beta_0}$, there is no function from $\omega$ to $L_{\beta_0}$ that is definable over $L_{\beta_0}$ from parameters. Therefore no such function is in $L_{\beta_0+1}$. On the ...

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

9
votes

### Uniqueness results that follow from CH

Here's one about my favorite topological space, the Stone–Čech remainder of the natural numbers, denoted $\mathbb N^*$ or $\omega^*$. The characterization is due to Parovicenko.
Assuming CH, $\mathbb ...

Community wiki

9
votes

### Uniqueness results that follow from CH

Assuming $\textsf{CH}$, a lot of natural fourth-order functionals are computationally equivalent (Kleene's S1-S9) to $\exists^3$. These equivalences do not seem to go through without the former. ([...

Community wiki

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

8
votes

Accepted

### Image-catching families in $\omega$

Original partial answer:
Here is some information:
An easy diagonalization shows that every image-catching family is uncountable. And more generally, MA implies that every image-catching family has ...

8
votes

### An infinite hat puzzle variation—if we don't know our place, can we still be almost all correct?

This solution, for an unknown position in an $\omega$-sequence with an arbitrary palette of colors for the hats, is apparently due to F. Galvin, American Mathematical Monthly Problem 5348, 1965.
...

8
votes

Accepted

### $L(\mathbb{R})$-absoluteness from a proper class of Woodins: source?

You can find this result as theorem 3.1.12 of Larson's The Stationary Tower monograph or theorem 7.22 of Steel's Outline of Inner Model Theory. More generally, Larson's book and Steel's exposition on ...

7
votes

### Situation with Artemov's paper?

I have waited for Noah Schweber to correct his above presentation of my work after we had a meaningful exchange in which Noah seemed to understand (does not mean to accept) my definitions and ...

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

7
votes

### Uniqueness results that follow from CH

In line with Joel’s answer, we have all sorts of uniqueness of ultrapower results that follow form CH and whose negations are known to be consistent with ZFC. Since classical model theory is not my ...

Community wiki

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

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

7
votes

Accepted

### Can a general recursive function be defined by Pr(x)?

You haven't said which theory $T$ you intend to use, but probably you have in mind something like PA. You are proposing to define exponentiation $x^y$ essentially as "the smallest $z$ for which $...

6
votes

Accepted

### Smallest ${\mathbf B}$-function $f:\omega\to( \omega\setminus\{0\})$

The question is really about finite hypergraphs, seeing as an infinite hypergraph (with finite edges) is $2$-colorable (i.e., has property B) iff every finite subhypergraph is $2$-colorable. In effect ...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

lo.logic × 5297set-theory × 2383

model-theory × 887

computability-theory × 553

reference-request × 487

forcing × 434

large-cardinals × 381

ct.category-theory × 288

proof-theory × 281

axiom-of-choice × 273

theories-of-arithmetic × 259

descriptive-set-theory × 229

foundations × 192

mathematical-philosophy × 177

constructive-mathematics × 149

reverse-math × 136

computational-complexity × 124

type-theory × 119

soft-question × 116

nt.number-theory × 115

co.combinatorics × 105

gr.group-theory × 105

gn.general-topology × 105

topos-theory × 105

universal-algebra × 103