All Questions
6,027 questions
6
votes
0
answers
263
views
Decidably clarifying ordinals
For a computable$^*$ ordinal $\alpha$ (viewed as an $\{<\}$-structure), say that a first-order sentence $\sigma$ in a relational language $\Sigma\supseteq \{<\}$ decidably clarifies $\alpha$ iff ...
- 20.5k
9
votes
0
answers
276
views
Has a computer search for inconsistency of large cardinals been carried out before?
In discussion about the consistency of large cardinals, a justification which occasionally appears is that despite years of work, no inconsistency has currently been discovered. For example, here are ...
- 2,031
4
votes
0
answers
103
views
Unstable structures with unstable $\aleph_0$-categorical reducts
Suppose $M$ is a first-order structure which is unstable. If necessary, assume it is $\aleph_0$-saturated (or more, but I don't think it matters beyond that).
Are there any interesting criteria for ...
- 1,338
7
votes
0
answers
196
views
Infinite cardinals and learnability of probability distributions
Two players play as follows. Player one chooses a secret finitely supported probability distribution $P$ on $ω_k$ (or another known set with $\aleph_k$ elements), and randomly takes $n+1$ samples ...
- 7,545
1
vote
0
answers
75
views
How many constant symbols can a set of intuitionistic formulas have for completeness to hold?
Fitting proves a version of the completeness theorem for intuitionistic FOL in his book on intuitionistic model theory and forcing.
Let $U$ be any set of formulas without parameters (i.e. constant ...
- 149
16
votes
1
answer
1k
views
Proving that ZF is Artemov-consistent
As discussed in another MO question, Sergei Artemov has proposed that the standard formalization Con(PA) of "PA is consistent" is flawed, and has proposed a different way to formalize "...
- 82.7k
23
votes
8
answers
3k
views
Simpler proofs using the axiom of choice
I am looking for examples of results which may be proven without resorting to the axiom of choice/Zorn lemma/transfinite induction but whose proof is quite simplified by the use of the axiom.
For ...
1
vote
1
answer
310
views
Is reflection on Grothendieck universes equivalent to TG set theory?
Let take the first order set theory whose axioms are Extensionality, Separation and Universal reflection.
By $\operatorname {unv}(x)$, denoting "$x$ is a universe", we'll take it to mean ...
- 11.3k
15
votes
2
answers
919
views
Which are the hereditarily computably enumerable sets?
My question is about sets that are computably enumerable with respect to their hereditary membership structure. Specifically, let me define that a hereditarily computably enumerable (h.c.e.) set is ...
- 236k
2
votes
1
answer
150
views
Weakly compact characterization
In Theorem 9.26 of Jech, it is shown that if $\kappa$ is inaccessible and has the tree property, then $\kappa \rightarrow (\kappa)^2_\lambda$ for every $\lambda<\kappa$. Jech remarks after the ...
- 41
4
votes
1
answer
395
views
How many variations can be derived from Gödel's fixed-point lemma?
Recently, I attempted to generalize the fixed-point lemma and proved the following:
Let $ F_n $ be the set of all formulas with $ n $ free variables in $L_{PA}$.
Let us define the unary function $ f $ ...
- 127
16
votes
0
answers
218
views
If a map between unital rings preserves multiplication and successor, does it preserve addition?
Welcome to my first MathOverflow posting!
This is a question about rings, all of them assumed to be both unital and associative.
Let $f\colon R\to S$ be a map between rings such that $f(xy)=f(x)f(y)$ ...
- 161
35
votes
3
answers
5k
views
Using Busy Beavers to prove conjectures
I've been pondering some stuff on Shtetl Optimized where Yedidia and Aaronson construct Turing machines that will only halt if (e.g.) the Riemann Hypothesis is false, or Goldbach's conjecture is false....
- 483
10
votes
1
answer
1k
views
What gets to be called a "proper class?"
ZFC has no formal notion of "proper class," but informally, everyone uses the term anyway. $V$, $Ord$, etc are said to be proper classes. Similarly, although in ZFC, one can only take the &...
- 4,907
9
votes
2
answers
381
views
How big can function spaces get without extensionality?
In what follows we work in the usual formulation of Martin-Löf Type Theory including Axiom K [1]. Boldface numbers $\mathbf{n}$ denote the usual finite type with $n$ elements.
Motivation
Postulating ...
- 756
27
votes
1
answer
932
views
A cardinal inequality for finiteness
Nearly ten years ago, I explained in a blog post that, assuming only ZF, a cardinal number $\mathfrak{n}$ is finite if and only if it satisfies this monstrous inequality:
$$2^{2^{2^{2^{\mathfrak{n}}}}}...
- 44.4k
3
votes
0
answers
76
views
Why does the following test for protoalgebraicity work?
Remark. Crossposted from Math SE due to lack of responses.
The following text appears in Janusz Czelakowski's "Protoalgebraic Logics":
Suppose there exists a class $\mathbf{K}$ of matrices ...
- 31
6
votes
1
answer
199
views
$L(\mathbb{R})$-absoluteness from a proper class of Woodins: source?
For a paper I'm writing I need to use (as a blackbox) the following theorem: if there is a proper class of Woodin cardinals and $G$ is set-generic, then $L(\mathbb{R})$ and $L(\mathbb{R})^{V[G]}$ are ...
- 20.5k
12
votes
2
answers
1k
views
Am I doing a forcing argument here?
I have an argument of the following form:
Executive Summary:
We have a $\mathbb R$-valued function $L$ which we want to show is $\mathbb Z$-valued. We approximate it by $\mathbb Q$-valued functions $\...
- 64k
3
votes
0
answers
130
views
Is Quine's Mathematical Logic "ML" consistent with Azcel's Extensionality?
Now that Holmes had proven the consistency of adding Extensionality to Stratified Comprehension (i.e. $\sf NF$), a question along the same vein presents itself:
Is Aczel's Extensionality axiom ...
- 11.3k
6
votes
1
answer
197
views
Is there a 1-generic degree g such that Th(D(< g)) is more complicated than true arithmetic?
I am currently reading an article titled "Embedding and Coding Below a 1-Generic Degree" by Greenberg and Montalbán(link to a free source:https://pi.math.cornell.edu/~erlkonig/Papers/...
- 893
5
votes
1
answer
167
views
Cardinality of separating families on an infinite cardinal $\kappa$
Let $\kappa$ be an infinite cardinal. We say ${\cal S}\subseteq {\cal P}(\kappa)$ is separating if whenever $a\neq b\in \kappa$ there is $T\in {\cal S}$ such that $|T\cap\{a,b\}| = 1$. Let $\...
- 48.9k
23
votes
4
answers
3k
views
Is Bauer–Hanson’s result “there is a topos where the Dedekind reals are countable” novel?
Last year, Andrej Bauer gave a talk showing that there is a topos in which the set of Dedekind reals is (sub)countable, and thus, you cannot prove that $\mathbb{R}$ is uncountable without LEM. He ...
- 317
4
votes
0
answers
261
views
Läuchli's "intermediate thing"
On page 230 of An abstract notion of realizability ..., Läuchli writes the following:
If we drop the restrictions put on $\Theta$, then we get classical logic in one case and an intermediate thing in ...
- 20.5k
14
votes
3
answers
1k
views
Examples of concrete games to apply Borel determinacy to
I'm teaching a course on various mathematical aspects of games, and I'd like to find some examples to illustrate Borel determinacy. Open or closed determinacy is easy to motivate because it proves ...
- 32.5k
11
votes
6
answers
1k
views
When can a function defined on $[a, b] \cup [b, c]$ be constructively extended to a function defined on $[a, c]$?
Let $a, b, c \in \mathbb R$ such that $a \le b \le c$. Let $S$ be some set and $f : [a, b] \cup [b, c] \to S$ be a function. When can we find a function $g : [a, c] \to S$ that meets the following ...
- 6,353
1
vote
0
answers
122
views
How could I formally express: System F cannot express universal quantification over things that are not types? [closed]
I'm trying to understand exactly why it is that https://ncatlab.org/nlab/show/computational+trilogy states that quantification requires dependent types, and why this wouldn't be possible to achieve ...
- 113
6
votes
0
answers
120
views
Is there a syntactic proof that first-order positive inductive definitions are conservative?
Every first-order positive inductive definition has a fixed point. It follows that, if the biconditional is thought of as an axiom in the language obtained from the background language by adding a new ...
- 61
150
votes
45
answers
30k
views
Nontrivial theorems with trivial proofs
A while back I saw posted on someone's office door a statement attributed to some famous person, saying that it is an instance of the callousness of youth to think that a theorem is trivial because ...
5
votes
1
answer
212
views
Image-catching families in $\omega$
Let $[\omega]^\omega$ be the collection of infinite subsets of the set of nonnegative integers $\omega$, and let $\newcommand{\I}{\cal{I}}\I=$ $\{S\in[\omega]^\omega: (\omega\setminus S)\in[\omega]^\...
- 48.9k
6
votes
0
answers
252
views
Whence compactness of automorphism quantifiers?
The following question arose while trying to read Shelah's papers Models with second-order properties I-V. For simplicity, I'm assuming a much stronger theory here than Shelah: throughout, we work in $...
- 20.5k
6
votes
1
answer
743
views
Which part(s) of this proof of Goodstein's Theorem are not expressible in Peano arithmetic?
EDIT: Noah Schweber helpfully points out that $\mathsf{ACA}_0$ is a conservative extension of Peano arithmetic in which certain aspects of my proof not expressible in Peano arithmetic are expressible. ...
- 708
5
votes
1
answer
168
views
Countably compact Boolean algebras versus distributivity
Let us say that a complete Boolean algebra $B$ is:
countably distributive when for any sequence $(I_n)_{n\in\mathbb{N}}$ of sets and any elements $(u_{n,i})_{n\in\mathbb{N},i\in I_n}$ of $B$ we have
$...
- 32.5k
3
votes
1
answer
253
views
Can a general recursive function be defined by Pr(x)?
In the book Metamathematics of First-Order Arithmetic, I learned that a general recursive function can be defined by a $\Delta_1$-formula. I am curious about another matter: Since we have $Pr_T^\...
- 127
10
votes
1
answer
645
views
Infinitary logics and the axiom of choice
Suppose we want to enhance ZF by allowing for infinitary formulas instead of just first-order ones in our axiom schema of separation and/or replacement. It seems that we don't need much power in our ...
- 4,907
1
vote
1
answer
246
views
Minimal Turing machines associated to math statements
It is known that some famous Number Theoretic problems are equivalent to halting of specific Turing machines:
Goldbach conjecture holds iff a 47 state TM halts
Lagarias' formulation of Riemann ...
- 593
60
votes
7
answers
9k
views
Does anyone still seriously doubt the consistency of $ZFC$?
As someone self-taught in set theory beginning with Donald Monk’s excellent book on MK set theory, $ZFC$ has always seemed like a weak set theory.
Despite this, the majority of professional ...
32
votes
2
answers
2k
views
Applications of Categorical Logic to Logic
This is definitely a very open ended question.
I have been studying Categorical Logic for a while now --- I've read Sheaves in Geometry and Logic, Adámek & Rosický's Presentable Categories, ...
14
votes
2
answers
2k
views
Are Berkeley cardinals easier to refute in ZFC than Reinhardt cardinals?
Kunen showed that Reinhardt cardinals are inconsistent in ZFC. But his proof is a bit technical for a non-set-theorist to follow. Berkeley cardinals are stronger than Reinhardt cardinals. You can ...
- 64k
15
votes
0
answers
244
views
Natural examples of Borel surjections without right inverse
As discussed in this question, in general a Borel surjection $f:\mathbb{R}\rightarrow\mathbb{R}$ may not have a Borel right inverse, namely a $g$ such that $f\circ g=id$, although there is always a ...
- 623
3
votes
0
answers
211
views
Intuitionistic set-theoretic geology
Work in ZF, if there are proper class many supercompact cardinals, then all grounds are uniformly definable. Hence under reasonable assumption, we can have choiceless set-theoretic geology.
But can we ...
- 695
1
vote
2
answers
339
views
Heuristic interpretations of the PA-unprovability of Goodstein's Theorem
I've relatively recently learned about Goodstein's Theorem and its unprovability in Peano arithmetic (the Kirby-Paris Theorem). I do not have any real knowledge of formal logic; but I think I've seen ...
- 708
9
votes
2
answers
473
views
Completing half of Hilbert's program: Foundations that are conservative over Peano Arithmetic
The goal of the Hilbert program was to find a complete and consistent formalization of mathematics. Gödel's first incompleteness theorem establishes that completeness is impossible with first-order ...
- 6,353
1
vote
0
answers
71
views
Can we have partitions on powersets of infinite cardinals that preserve natural arithmetical operators?
There exists an infinite cardinal $\zeta$ such that there exists a set $P$ such that $P$ is a partition on $\mathcal P(\zeta) \setminus \{\varnothing\}$ such that each element $h$ of $P$ is an ...
- 11.3k
-2
votes
1
answer
181
views
What is the computational complexity to verify a P solution with a deterministic Turing machine? [closed]
As we know, NP (nondeterministic polynomial time) is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is &...
- 3,104
3
votes
0
answers
90
views
Ordering the elements of a semigroup by $a \le b$ iff $a=b$ or $b=ab=ba$
Let $S$ be a semigroup, written multiplicatively. The binary relation $\le$ on (the underlying set of) $S$, whose graph consists of all pairs $(a,b) \in S \times S$ such that $a = b$ or $b = ab = ba$, ...
- 10.5k
43
votes
4
answers
5k
views
Lists as a foundation of mathematics
I am wondering if there is a foundation of mathematics where not sets or "set-like objects" (such as objects of a suitable topos as in ETCS) are the primitive notion, but rather lists. These ...
- 63.1k
20
votes
6
answers
3k
views
What are some nice uses of ultraproducts/ultrapowers?
Motivated by a recent post (Non-definability of graph 3-colorability in first-order logic), I was wondering: what are some nice arguments based on ultraproducts? I don't mind definability results, but ...
2
votes
0
answers
196
views
On "necessary connectives" in a structure
Given a clone $\mathcal{C}$ over $\{\top,\perp\}$, let $\mathsf{FOL}^\mathcal{C}$ be the version of first-order logic with connectives from $\mathcal{C}$ in place of the usual Booleans. Given a clone $...
- 20.5k
3
votes
1
answer
329
views
Nonexistence of short integer program sequence which generates squares
Is there a way to show within an integer program with constant number of variables and constraints of length $poly(\log B)$ (say length $\leq10^{1000000}\log B$), it is not possible for a variable to ...
- 13.9k