Skip to main content
Noah Schweber's user avatar
Noah Schweber's user avatar
Noah Schweber's user avatar
Noah Schweber
  • Member for 14 years, 4 months
  • Last seen this week
comment
How slow can an uncomputable function from $\mathbb{N}$ to $\mathbb{N}$ grow?
@Vincent Given any noncomputable set $A$, let $B=\{2n: n\in A\}\cup\{2n+1: n\not\in A\}$. Then $B$ is not sparse at all, but is still exactly as complicated as $A$. This question would be more appropriate at MSE.
comment
Reference request: The non-productivity of Lindenbaum numbers
I think I saw the first of these inequalities as an (unattributed) exercise in a set theory class, but I'm not sure. I don't think I've seen the second inequality explicitly. I suspect these are folklore, sadly.
awarded
comment
Can one define second-order equinumerosity in MSO via first-order cardinality quantifiers?
What exactly can $L$ quantify over? You say $L$ is second-order, but then expressing $\vert F\vert=\vert G\vert$ is trivial. Separately, why doesn't the sentence $$C_{=}(F,G)$$ do the job?
comment
Is there a decidable theory of arithmetic with a non-collapsing quantifier hierarchy?
@EmilJeřábek It's not an expansion of Presburger, so no.
comment
Is there a decidable theory of arithmetic with a non-collapsing quantifier hierarchy?
@AlexKruckman Sure, do something stupid with Marker extensions so your model is basically infinitely many definable elements $a_i$ where it takes $i$ quantifier alternations to define $a_i$.
Loading…
comment
Is there a decidable theory of arithmetic with a non-collapsing quantifier hierarchy?
@WillSawin You're quite right, I was having a silly moment (today's not my day for accuracy). Fixed!
Loading…
comment
Is there a decidable theory of arithmetic with a non-collapsing quantifier hierarchy?
@WillSawin Ah, sorry, I should have clarified - I'm looking at unary formulas. Fixed! (I'm used to PA and similar, where there's no essential difference between relations and unary relations, and so I was sloppy.)
Loading…
comment
Completeness vs Compactness in logic
Very belatedly, I don't think the PS is fully correct: the set of ESO validities is not even arithmetically definable, via the sentence "There is an $S$ such that either the axioms of Robinson arithmetic fail to hold, or $S$ defines a proper cut, or $\varphi$ is true" (with $\varphi$ arithmetical).
comment
Are there times when replacement is "more natural" than collection?
@user3840170 It's not my notation, it's from the Gitman/Hamkins/Johnstone paper. (OK, the circle thing is mine.) More significantly, removing powerset is not the same as saying that only first-order objects exist; ZF is a first-order theory, after all. To be honest I find your suggestions significantly worse than what I used.
comment
Czelakowski's claimed proof of the Twin Prime Conjecture
@MonroeEskew Well, it doesn't, so there's that.
awarded
comment
If $\omega_1$ is not inaccessible in $L$, how hard can it be to find a non-measurable $\Sigma^1_3$ set of reals?
I thought you were asking about both upper and lower bounds. My comment was towards the idea that there may be no always-applicable lower bound.
comment
If $\omega_1$ is not inaccessible in $L$, how hard can it be to find a non-measurable $\Sigma^1_3$ set of reals?
Is it clear that $a=\emptyset$ doesn't work (e.g. after Sacks forcing once over $L$)?
revised
Loading…
comment