All Questions
1,142 questions
36
votes
3
answers
2k
views
Defining $SU(n)$ in HoTT
From a recent answer by Mike Shulman, I read:
"HoTT is (among other things) a foundational theory, on roughly the same ontological level as ZFC, whose basic objects can be regarded as $\infty$-...
- 43.2k
35
votes
8
answers
7k
views
Why not adopt the constructibility axiom $V=L$?
Gödelian incompleteness seems to ruin the idea of mathematics offering absolute certainty and objectivity. But Gödel‘s proof gives examples of independent statements that are often remarked as having ...
34
votes
3
answers
3k
views
What is the theory of local rings and local ring homomorphisms?
It is well-known that the category of local rings and ring homomorphisms admits an axiomatisation in coherent logic. Explicitly, it is the coherent theory over the signature $0, 1, -, +, \times$ with ...
- 15.9k
34
votes
3
answers
2k
views
How much choice is needed to show that formally real fields can be ordered?
Background: a field is formally real if -1 is not a sum of squares of elements in that field. An ordering on a field is a linear ordering which is (in exactly the sense that you would guess if you ...
- 65.4k
32
votes
11
answers
11k
views
Is PA consistent? do we know it?
1) (By Goedel's) One can not prove, in PA, a formula that can be interpreted to express the consistency of PA. (Hopefully I said it right. Specialists correct me, please).
2) There are proofs (...
32
votes
9
answers
5k
views
How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?
Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings,
fields, graphs, partial orders, etc.
...
- 236k
31
votes
2
answers
4k
views
Hahn's Embedding Theorem and the oldest open question in set theory
Hans Hahn is often credited with creating the modern theory of ordered algebraic systems with the publication of his paper Über die nichtarchimedischen Grössensysteme (Sitzungsberichte der ...
- 6,453
31
votes
8
answers
3k
views
On independence and large cardinal strength of physical statements
The present post is intended to tackle the possible interactions of two bizarre realms of extremely large and extremely small creatures, namely large cardinals and quantum physics.
Maybe after all ...
30
votes
3
answers
3k
views
Is it decidable whether or not a collection of integer matrices generates a free group?
Suppose we have integer matrices $A_1,\ldots,A_n\in\operatorname{GL}(n,\mathbb Z)$. Define $\varphi:F_n\to\operatorname{GL}(n,\mathbb Z)$ by $x_i\mapsto A_i$. Is there an algorithm to decide whether ...
- 18.7k
27
votes
5
answers
3k
views
Formalizations of the idea that something is a function of something else?
I'll state my questions upfront and attempt to motivate/explain them afterwards.
Q1: Is there a direct way of expressing the relation "$y$ is a function of $x$" inside set theory?
More ...
- 5,343
26
votes
4
answers
3k
views
What is the definition of a large cardinal axiom?
In different books one can find different implicit definitions for a large cardinal axiom.
My question is that which one of these definitions are more popular or standard amongst set theorists?
Any ...
user45939
25
votes
2
answers
1k
views
The number of polynomials on a finite group
A function $f:X\to X$ on a group $X$ is called a polynomial if there exist $n\in\mathbb N=\{1,2,3,\dots\}$ and elements $a_0,a_1,\dots,a_n\in X$ such that $f(x)=a_0xa_1x\cdots xa_n$ for all $x\in X$. ...
- 41.9k
25
votes
1
answer
3k
views
Surreal exponentiation -- are the varying definitions equivalent? If not, is there agreement on which ones are better?
The surreal numbers are sometimes introduced as a place where crazy expressions like $(\omega^2+5\omega-13)^{1/3-2/\omega}+\pi$ (to use the nLab's example) make sense. The problem is, there seem to ...
- 2,585
24
votes
6
answers
5k
views
Interesting meta-meta-mathematical theorems?
The Goedel incompleteness theorems can be considered meta-mathematical theorems, as they are "written" in a meta-theory and "talk" about properties of a class of formal theories.
The following may be ...
- 23.3k
23
votes
2
answers
2k
views
Prospects for reverse mathematics in Homotopy Type Theory
Reverse mathematics, as I mean here, is the study of which theorems/axioms can be used to prove other theorems/axioms over a weak base theory. Examples include
Subsystems of Second Order Arithmetic (...
- 6,287
23
votes
5
answers
6k
views
Hahn-Banach without Choice
The standard proof of the Hahn-Banach theorem makes use of Zorn's lemma. I hear that, however, Hahn-Banach is strictly weaker than Choice. A quick search leads to many sources stating that Hahn-Banach ...
- 1,202
22
votes
2
answers
2k
views
If ZFC has a transitive model, does it have one of arbitrary size?
It is known that the consistency strength of $\sf ZFC+\rm Con(\sf ZFC)$ is greater than that of $\sf ZFC$ itself, but still weaker than asserting that $\sf ZFC$ has a transitive model. Let us denote ...
- 39.8k
22
votes
5
answers
1k
views
What is the spectrum of possible cofinality types for cuts in an ordered field? Or in a model of the hyperreals? Or in a nonstandard model of arithmetic?
I am interested to know the full range of possibilities for the cofinality type of cuts in an ordered field and in other structures, such as nonstandard models of arithmetic.
Definitions. ...
- 236k
22
votes
2
answers
2k
views
What is the largest Laver table which has been computed?
Richard Laver proved that there is a unique binary operation $*$ on $\{1,\ldots,2^n\}$ which satisfies $$a*1 \equiv a+1 \mod 2^n$$
$$a* (b* c) = (a* b) * (a * c).$$
This is the $n$th Laver table $(A_n,...
- 3,547
20
votes
2
answers
3k
views
What is a Choice Principle, really?
This question is quite soft, and I apologize in advance if it borderline off-topic.
When working in theories between ZF and ZFC the term "choice principle" is heard quite often. For example:
$\quad$ ...
- 39.8k
20
votes
3
answers
4k
views
Categories of recursive functions
I have a couple of conjectures on recursive functions, that I feel must have been proved or refuted by someone else, but I don't know where to look. In short:
1. The primitive recursive functions ...
- 1,289
20
votes
3
answers
4k
views
Cohen reals and strong measure zero sets
A set of reals $X$ is $\textit{strong measure zero}$ if for any sequence of real numbers $ ( \epsilon_n ) _{n \in \omega }$ there is a sequence of open intervals $ ( a_n ) _{n \in \omega }$ which ...
- 540
19
votes
3
answers
1k
views
Large categories vs. $\mathrm{U}$-categories: why is the loss of category-theoretic information inessential?
I've asked a related question about nine months ago here, however, apparently, I lacked expertise to ask the precise question I want to ask here, as I wish to revisit the matter of universes. I hope ...
- 1,115
19
votes
2
answers
2k
views
Can we take a supremum over all Hilbert spaces?
In my paper On the optimal error bound for the first step in the method of cyclic alternating projections, I defined functions $f_n:[0,1]\to\mathbb{R}$,
$n\geqslant 2$, by
$$
f_n(c)=\sup\{\|P_n\dotsm ...
- 935
18
votes
1
answer
1k
views
Lebesgue Measurability and Weak CH
Let $LM$ denote "all subsets of $\Bbb{R}$ are Lebesgue measurable", and
$WCH$ (weak continuum hypothesis) denote "every uncountable subset of $\Bbb{R}$ can be be put into 1-1 correspondence with $\...
- 17.7k
18
votes
4
answers
4k
views
Proof strength of Calculus of (Inductive) Constructions
This is a follow-on from this question, where I pondered the consistency strength of Coq. This was too broad a question, so here is one more focussed. Rather, two more focussed questions:
I've read ...
- 35.5k
17
votes
1
answer
1k
views
Is there an $L$ like inner model for $\sf Z$?
Godel proved the consistency of the axiom of choice with the axioms of $\sf ZF$ by showing that given any model of $\sf ZF$, there is a definable class which satisfies $\sf ZFC$.
The proof uses a lot ...
- 39.8k
16
votes
1
answer
2k
views
A contradiction in the Set Theory of von Neumann–Bernays–Gödel?
Thinking on the theory NBG (of von Neumann–Bernays–Gödel) I arrived at the conclusion that it is contradictory using an argument resembling Russell's Paradox. I am sure that I made a mistake in my ...
- 41.9k
15
votes
5
answers
2k
views
In what sense does the sentence $\operatorname{con}(\mathsf{PA})$ "say" that $\mathsf{PA}$ is consistent?
It seems common amongst logicians to think of "truth" as being relative to a particular structure. Consider, for instance, the first-order theory of groups. The sentence $\forall x\forall y(...
- 961
15
votes
1
answer
2k
views
Can one exhibit an explicit Kuratowski infinite set without invoking Replacement?
The customary formulation of the Axiom of Infinity within Zermelo-Fraenkel set theory asserts the existence of an inductive set: a set $ I$ with $\varnothing\in I$ such that $x\in I$ implies $x\...
- 2,550
14
votes
2
answers
2k
views
What are Moschovakis cardinals?
The question is exactly that of the title: what are Moschovakis cardinals?
Background. In a recent answer to the question, "Are there examples of statements that have been proven whose consistency ...
- 20.5k
14
votes
2
answers
1k
views
"Fraïssé limits" without amalgamation
All structures are countable with countable signature.
Given a structure $\mathcal{A}$, the age of $\mathcal{A}$, $Age(\mathcal{A})$, is the set of structures isomorphic to finitely-generated ...
- 20.5k
13
votes
1
answer
649
views
Kleene realizability in Peano arithmetic
For completeness of MathOverflow and for clarity of the question, I will first recall a few things, including the the definition of Kleene realizability: experts can jump directly to the question ...
- 32.5k
13
votes
3
answers
1k
views
Reducing ACA₀ proof to First Order PA
According to the Wikipedia ACA0 is a conservative extension of First Order logic + PA.
http://en.wikipedia.org/wiki/Reverse_Mathematics
First of all I have a few questions about the proof:
a - What ...
- 1,659
13
votes
2
answers
1k
views
Failure of diamond at large cardinals
What is known about the failure of $\Diamond_{\kappa}$ (diamond at $\kappa$) for $\kappa$ (the least) inaccessible, (the least) Mahlo and (the least) weakly compact.
Remark. The problem of forcing ...
- 32.2k
13
votes
1
answer
1k
views
For what sets $X$ do there exist a pair of functions from $X$ to $X$ with the identity being the only function that commutes with both?
It is not too difficult to show that if $X$ is an infinite set, then there exists a two-element subset of the group $\operatorname{Sym}(X)$ with trivial centralizer iff $\lvert X\rvert \leq \lvert\...
- 328
13
votes
2
answers
730
views
What can the degrees of constructibility be?
If $r, s\in\mathbb{R}$, we say $r$ is constructible relative to $s$ - and write $r\le_cs$ - if $r\in L[s]$. Modding out by the induced equivalence relation $\equiv_c$, we get a partial order, the ...
- 20.5k
12
votes
1
answer
971
views
What metatheory proves $\mathsf{ACA}_0$ conservative over PA?
Simpson's book shows $\mathsf{ACA}_0$ is conservative over $\mathsf{PA}$ in the natural way by model theory using definable subsets. Of course, $\mathsf{ACA}_0$ being conservative over PA is ...
- 11.1k
11
votes
1
answer
540
views
Is AC equivalent over ZF to 'every fibration can be equipped with a cleavage'?
It is well known that (working over ZF) AC implies that every fibration $p:\mathcal{E}\to\mathcal{B}$ can be equipped with a cleavage by choosing, for each arrow $u:I\to p(X)$ in the base category ...
- 10.1k
11
votes
2
answers
1k
views
Henkin-style completeness proofs for intuitionistic logic
Henkin-style completeness proofs are founded on a few basic presuppositions, such as the assumptions that the language of a logical theory must be enumerable (or at least that the axiom of choice ...
- 215
11
votes
1
answer
769
views
Is there a suitably generalized Baire property for topological spaces of arbitrary cardinalities?
Is there some suitable generalization to the notion of Baire property for topological spaces of arbitrary cardinalities which satisfies the following condition:
The meager sets are sets which are ...
- 1,416
10
votes
2
answers
1k
views
A question about open induction
An old theorem of A. J. Wilkie (Some results and problems on weak systems of arithmetic, Logic Colloquium '77) asserts that a discretely ordered ring $R$ can be extended to a model of open induction ...
- 6,199
10
votes
2
answers
812
views
Category theory from MK class theory perspective?
I'm looking for a text that treats category theory from the perspective of MK class theory.
MK is already very well-designed and equipped for the type of abstraction that occurs in category theory, ...
- 10.1k
9
votes
1
answer
616
views
Essential incompleteness via diophantine formulas?
Work in the first order language of number theory, consisting of the symbols $\mathbf{0}$, $\mathbf{S}$, $\boldsymbol{+}$, and $\boldsymbol{\cdot}$, and let $Q$ denote Robinson's arithmetic.
By a ...
- 103
9
votes
2
answers
870
views
Decidability of diophantine equation in a theory
Given a theory $T \subseteq \operatorname{Th}(\mathbb{N})$, define the decision problem $D_T$ as follows:
Given a polynomial $p$ with integer coefficients and variables $\bar{x}$, decide whether
$...
- 193
9
votes
2
answers
892
views
Can formal logic give a precise notion of "canonical"?
Coming off of this discussion, I'm wondering what the term "canonical" really means. In that thread, many suggested category theory as a way to formalize the concept of what "canonical" means, using ...
- 15.4k
9
votes
2
answers
2k
views
Sperner's lemma and Tucker's lemma
In their article "A Borsuk-Ulam Equivalent that Directly Implies Sperner's Lemma" (American Mathematical Monthly, April 2013), Nyman and Su write "[W]e are unaware of a direct proof that Tucker's ...
- 19.7k
9
votes
4
answers
1k
views
When $X \times Y \cong X \times Z$ implies $Y \cong Z$ (in the category of finite topological spaces)
The title has it all. I'm looking for a reference to the following:
Q. Let $X, Y, Z$ be finite, non-empty (topological) spaces. When does $X \times Y \cong X \times Z$ imply $Y \cong Z$ (in the ...
- 10.5k
9
votes
7
answers
8k
views
Uncountable family of infinite subsets with pairwise finite intersections
I am searching for a constructive proof of the following fact: If $X$ is an infinite set, there exists an uncountable family $(X_\alpha)_{\alpha \in A}$ of infinite subsets of $X$ such that $X_\alpha \...
- 8,559
9
votes
1
answer
982
views
Complexity of $L[\mathrm{cf}]$
Assuming large cardinal axioms, which real numbers are in $L[\mathrm{cf}]$, where $\mathrm{cf}$ is the cofinality function on ordinals?
$L[\mathrm{cf}]$ is the minimal inner model that 'knows' the ...
- 7,545