Questions tagged [foundations]
Mathematical logic, Set theory, Peano arithmetic, Model theory, Proof theory, Recursion theory, Computability theory, Univalent foundations, Reverse mathematics, Frege foundation of arithmetic, Goedel's incompleteness and Mathematics, Structural set theory, Category theory, Type theory.
330 questions
14
votes
5
answers
1k
views
Emergence of the discrete from the continuum
An almost eternal theme in Mathematics is the approximation of the Continuum by the Discrete. This core idea goes back at least to Archimedes, and remains active to these very days (and quite likely ...
- 12.7k
1
vote
0
answers
73
views
How strong is separation + reflection without transitivity?
Consider a theory $T$ with a binary relation $\in$ and the following axiom schemas:
$\exists u \forall x (x \in u \leftrightarrow x \in a \land \phi)$ where $u$ is not free in $\phi$. This is the ...
- 2,203
10
votes
2
answers
513
views
Is there a purely constructive presentation of the HK integral?
Treating the Riemann integral in a constructive setting is easy and straightforward. Treating the closely related but much more powerful Henstock-Kurzweil integral constructively is almost easy, ...
- 1,947
14
votes
0
answers
386
views
Can the axiom of choice be expressed in 4 quantifiers?
This 2007 paper presents a 5-quantifier $(\in, =)$-expression that is ZF-equivalent to the axiom of choice, but leaves open the 4-quantifier case:
Thus the gap is reduced to the undecided case of a 4 ...
- 2,203
12
votes
1
answer
225
views
Is there a $\Pi_2$ sentence $A$ such that $\text{ZFC}^- + A$ proves powerset?
This is a follow-up to this question.
Let $\text{ZFC}^-$ be ZFC without powerset and with collection rather than replacement, as described here.
Is there a $\Pi_2$ (or perhaps $\Sigma_2$) sentence $A$ ...
- 7,525
6
votes
2
answers
319
views
Set theoretical foundations for derived categories
A modern approach to derived functors, that has been shown to be useful in a number of different circunstances is that of a derived category (see the book by Yakutieli, for example, here).
However, it ...
- 15.8k
30
votes
6
answers
3k
views
Mathematics without the principle of unique choice
The principle of unique choice (PUC), also called the principle of function comprehension, says that if $R$ is a relation between two sets $A,B$, and for every $x\in A$ there exists a unique $y\in B$ ...
- 48.8k
36
votes
6
answers
6k
views
Who needs Replacement anyway?
The set theory ETCS famously comes without the Replacement axiom schema (or an equivalent) that is part of ZFC. One (to me, not apparently useful) set that one cannot build in ETCS is $\coprod_{n\in \...
CommunityBot
- 1
60
votes
7
answers
9k
views
In what respect are univalent foundations "better" than set theory?
It was an ambitious project of Vladimir Voevodsky's to provide new foundations for mathematics with univalent foundations (UF) to eventually replace set theory (ST).
Part of what makes ST so appealing ...
- 48.8k
16
votes
2
answers
1k
views
CH in non-set theoretic foundations
I asked this question on stack exchange and got little attention, barring a nice example I intend to look into. The original post can be found here: https://math.stackexchange.com/q/4941233/1053681
I ...
- 35.4k
27
votes
4
answers
4k
views
Who introduced the terms "equivalence relation" and "equivalence class"?
Consider that the question does not concern the origin of the ideas of equivalence relation and equivalence class. It exactly concerns the origin of the terms "equivalence relation" and "equivalence ...
- 61
13
votes
1
answer
932
views
Consistency strength of HoTT
What is the consistency strength of Homotopy type theory (HoTT) relative to various set theories (e.g., are there any known set theories that it can interpret)? Does this question even make sense?
- 6,353
8
votes
0
answers
157
views
How to define Dedekind reals and Eudoxus reals such that they are equivalent to unmodulated Cauchy reals
In constructive mathematics without choice, we have three different versions of the real numbers (each embedding into the next).
Regular Cauchy reals (functions $f : \mathbb N \to \mathbb Q$ such ...
- 6,353
3
votes
1
answer
256
views
Can these short set-building expressions of the finite set world extend to the infinite set world?
A formula of the form $\forall \vec{p}\, \exists x \, \forall y\, (y \in x \leftrightarrow \phi(y,\vec{p}))$
is to be named a "set-building" formula.
Now, when $\vec{p}$ includes a predicate ...
- 11.3k
24
votes
2
answers
2k
views
Foundations and contradictions of Scholze's work: the category of presentable infinity categories contains itself
Preface: I am not an expert in the work of Scholze, or anything for that matter.
Question
Has Scholze stated what axioms he is using to develop his theory of motives and analytic geometry. In the ...
- 63.9k
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
14
votes
2
answers
1k
views
Type vs. Set Theory: Expressive Ability
In the modern mathematical arena, the two primary contenders for the ‘correct’ foundation of mathematics are set and type theory.
Set theory, very roughly, captures the intuition that we frequently ...
- 12.4k
6
votes
1
answer
1k
views
An axiomatic approach to the multiverse of sets
Work in a theory where the primitives are classes $X,Y,Z,\dots$, and class membership $X\in Y$, and add an individual constant $\mathcal{M}$ called 'the multiverse'. Classes $V$ which are members of ...
- 10.1k
9
votes
2
answers
380
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
5
votes
3
answers
664
views
Negating fundamental axioms
It is commonplace to consider standard axiomatic systems (e.g. $ZF$) with one of the 'less essential' axioms negated, like infinity, 'less essential' here having some ambiguous definition related to ...
- 4,359
11
votes
1
answer
1k
views
Are categories special, foundationally?
Some folks over at nLab want to use categories as a foundation for all of mathematics, I'm guessing as an alternative to sets. Sets work fine, and so do categories, so I have started wondering what ...
- 63.9k
15
votes
2
answers
959
views
Can the opposite of an elementary topos be an elementary topos?
This question is not really about elementary topoi, it is much more about a category $(\mathcal{E}, \Omega)$ admitting a subobject classifier, or about a category with power objects, you can choose ...
- 4,165
29
votes
3
answers
3k
views
Are there substantive differences between the different approaches to "size issues" in category theory?
In category theory, there are different ways to approach the "size issues" that crop up when we try to formalise the subject in axiomatic set theory. As far as I can tell, there are two main ...
- 109
20
votes
5
answers
2k
views
Does formalizing math require search and creativity, or is it near-mechanical?
I remember reading somewhere that it takes about a week to convert a page of math into something a proof-assistant like Isabelle or HOL Light would accept.
Is this type of conversion something that ...
- 1,667
4
votes
0
answers
177
views
Recording of 2009 lecture on Harvey Friedman's work
On December 13--20 2009 at Bristol, there was a meeting devoted to thorough dissection of Harvey Friedman's work on the foundations of mathematics and his statements claimed to be equivalent to ...
- 865
2
votes
0
answers
220
views
Which is richer Set or Graph Theory?
This theory about structures, defined as abstractions over isomorphic graphs, can interpret Set Theory in a rather creepy manner. Though the theory is largely technical, yet it is not far from being ...
- 11.3k
11
votes
3
answers
2k
views
What governs our "perception?" about the platonic realm of sets?
Here, I want to delve into what do we exactly feel about what constitutes a platonic existence of a set? Or what makes us think or actually a kind of feel or sense the existence of a set in the ...
- 571
7
votes
9
answers
7k
views
Ultrainfinitism, or a step beyond the transfinite
Cantor has, in the immortal words of D. Hilbert, given all of us a paradise (or perhaps, I would rather say, a great vacation spot), the TRANSFINITE.
$\aleph_0, \aleph_1,\aleph_2\dots$
the lists ...
- 2,031
3
votes
0
answers
164
views
Suitability of formal type theory for mathematical thinking (vs. traditional set theory)
Type theory has advantages over set theory for the (computer) formalisation of mathematics, but has anybody who does mathematics with pen and paper found proof assistants or automated theorem provers, ...
5
votes
1
answer
596
views
The "first-order theory of the second-order theory of $\mathrm{ZFC}$"
$\newcommand\ZFC{\mathrm{ZFC}}\DeclareMathOperator\Con{Con}$It is often interesting to look at the theory of all first-order statements that are true in some second-order theory, giving us things like ...
- 236k
3
votes
1
answer
510
views
Harvey Friedman: The expanding mind
In reference 1, Friedman writes:
I discuss my efforts concerning 3 crucial issues in the foundations of mathematics that are deeply connected with the great work of Kurt Gödel.
[...]
B. Are there ...
- 2,031
4
votes
1
answer
600
views
Why not $\sf ZFC+[V=HOD]$?
Why not $\sf ZFC+[V=HOD]$ as the standard set theory?
It implies the existence of a definable global choice and well-order, and it is compatible with all large cardinal axioms extending $\sf ZFC$, so ...
- 11.3k
1
vote
2
answers
832
views
Intension vs. Extension: Coextensive relations in model and set theory
(originally posted at MSE as Same same but different: Coextensive relations in model and set theory, slightly modified)
The official definition of a structure in model theory in its presumably most ...
- 1,446
4
votes
2
answers
2k
views
Dedekind's theorem
In "Was sind und was sollen die Zahlen?" Dedekind gives a noncircular
proof of the statement that a set is finite if and only if it cannot be
put in bijective correspondence with a proper subset. By "...
- 1,446
7
votes
2
answers
2k
views
What is a good definition of a mathematical structure?
At the moment I am writing a textbook in Foundations of Mathematics for students and trying to give a precise definition of a mathematical structure, which is the principal notion of structuralist ...
- 41.8k
-4
votes
1
answer
198
views
Is Bounding Reflection consistent?
Working in the first order language of set theory.
Let $\varphi^{*B}$ be the formula obtained from $\varphi$ by merely bounding all open quantifiers in $\varphi$ by the symbol "$B$".
Here a ...
- 2,031
-3
votes
1
answer
296
views
Can this form of reflection be consistent?
Is this form of reflection consistent?
First I'll begin by clarifying the notation I'm using here:
By a quantifier being relativized or bounded it means that the first occurrence of the quantified ...
- 2,031
5
votes
1
answer
344
views
What is the proof of consistency of anterior reflection?
Let Anterior Reflection be the following principle: $$\forall \vec{v}~ \exists X: \operatorname {transitive} (X) \land \, (\varphi \to \varphi^{X"}) $$
where $\varphi$ is a formula in $\sf FOL(=,\in)$ ...
- 11.3k
2
votes
1
answer
200
views
Does inductive definitions must be supported by the set theoretical definition of natural numbers?
In page 4 of Gödel's book The Consistency Of The Axiom Of Choice and Of The Generalized Continuum Hypothesis With The Axioms Of Set Theory, Gödel defined the $n$-tuple as
$\langle x \rangle = x$;
$\...
- 4,265
3
votes
1
answer
96
views
Is this form of replacement suitable for ZF - Powerset + well-ordering principle?
The following scheme can be understood as a form of replacement. Axiomatizing $\sf ZF$ with it instead of the usual replacement schema renders it immune to removal of extensionality; see here.
In an ...
- 236k
18
votes
3
answers
3k
views
What's the earliest result (outside of logic) that cannot be proven constructively?
Although mathematicians usually do not work in constructive mathematics per se, their results often are constructively valid (even if the original proof isn't).
An obvious counter-example is the law ...
- 82.6k
6
votes
1
answer
315
views
In HoTT with LEM, are sets and pointed sets the same thing?
The operations of adding and removing a point (where removing is a consideration of a subset of elements x such that $(x = *) \to 0$) implements the equivalence of these 1-types, as far as I can see. ...
- 989
6
votes
1
answer
317
views
Is univalence equivalent to every type function being a functor over equivalence?
Introduce a rule in type theory that if $\Gamma \vdash f : \text{Type} \to \text{Type}$ and $\Gamma \vdash e : A \simeq B$ then $\Gamma \vdash f[e] : f(A) \simeq f(B)$.
It may seem like such a rule is ...
- 48.8k
12
votes
0
answers
209
views
Are there times when replacement is "more natural" than collection?
There are a couple examples I'm aware of where choosing to axiomatize $\mathsf{ZF(C)}$ using collection instead of replacement results in a much nicer (or at least less surprising) picture:
Let $\...
- 21.1k
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 (...
- 2,031
6
votes
1
answer
935
views
Smallest ordinal modelling $\aleph_1$?
Let $X_1$ be the class of all ordinals $\alpha$ such that there exists a transitive model $M$ of ZF(C) such that $M$ thinks that $\alpha$ is $\aleph_1$.
Every class of ordinals has a minimum element (...
- 2,031
7
votes
2
answers
1k
views
Explaining the consistency of PRA and ZF from predicative foundations
Recently I got interested in predicative foundations, mostly because of Laura Crosilla's work and because Agda employs a predicative type theory.
From the point of view of a predicative foundation to ...
- 3,302
4
votes
1
answer
368
views
Bounded alternatives to powerset that interpret ZFC
In set theory, many properties/relations of interest can be expressed as $\Delta_0$ formulas (formulas with only bounded quantifiers):
\begin{align}
\text{empty}(a) &\equiv \forall x \in a . \...
- 2,203
5
votes
3
answers
897
views
Did Gödel prove that the Ramified Theory of Types collapses at $\omega_1$?
Second-Order Arithmetic is considered impredicative, because the comprehension scheme allows formulas with bound second-order variables that range over all sets of natural numbers, including the set ...
- 32.4k
7
votes
3
answers
459
views
How much Dependent Choice is provable in $Z_2$? And what about Projective Determinacy?
So, second order arithmetic, $Z_2$, is capable of proving quite a few things. One thing which would be of use is dependent choice for $\mathbb{R}$.
Basically, dependent choice on $\mathbb{R}$ says ...
- 17.7k