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.
60
questions
62
votes
4
answers
6k
views
When size matters in category theory for the working mathematician
I think a related question might be this (Set-Theoretic Issues/Categories).
There are many ways in which you can avoid set theoretical paradoxes in dealing with category theory (see for instance ...
- 2,683
22
votes
1
answer
4k
views
Proof-Theoretic Ordinal of ZFC or Consistent ZFC Extensions?
Let the proof theoretic ordinal $\alpha$ of a theory $T$ be the least recursive ordinal such that $T$ does not prove that $\alpha$ is well-founded. This ordinal is intended to quantify in some sense ...
- 701
32
votes
4
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 \...
- 33.9k
22
votes
6
answers
3k
views
Where in ordinary math do we need unbounded separation and replacement?
[I have updated the question after initial comments in the hope of clarifying it.]
I do quite a bit of reasoning, typically about topology and metric spaces, in "non-standard" foundations, such as ...
152
votes
5
answers
27k
views
What makes dependent type theory more suitable than set theory for proof assistants?
In his talk, The Future of Mathematics, Dr. Kevin Buzzard states that Lean is the only existing proof assistant suitable for formalizing all of math. In the Q&A part of the talk (at 1:00:00) he ...
- 1,617
46
votes
7
answers
6k
views
What is an explicit bijection in combinatorics?
A standard way of demonstrating that two collections of combinatorial objects have the same cardinality is to exhibit a bijection between them. Browsing through some examples (here, there, yonder) ...
- 48k
37
votes
4
answers
6k
views
Could groups be used instead of sets as a foundation of mathematics?
Sets are the only fundamental objects in the theory $\sf ZFC$. But we can use $\sf ZFC$ as a foundation for all of mathematics by encoding the various other objects we care about in terms of sets. The ...
- 3,077
15
votes
2
answers
1k
views
Does foundation/regularity have any categorical/structural consequences, in ZF?
(Prompted by reflection on this old answer, and its suggestion of the “harmlessness” of the axiom of regularity.)
In ZFC, one may justify the axiom of foundation (AF, aka the axiom of regularity) as ...
74
votes
11
answers
11k
views
Why hasn't mereology succeeded as an alternative to set theory?
I have recently run into this Wikipedia article on mereology. I was surprised I had never heard of it before and indeed it seems to be seldom mentioned in the mathematical literature. Unlike set ...
- 5,692
49
votes
4
answers
5k
views
Do set-theorists use informal set theory as their meta-theory when talking about models of ZFC?
Here, Noah Schweber writes the following:
Most mathematics is not done in ZFC. Most mathematics, in fact, isn't done axiomatically at all: rather, we simply use propositions which seem "intuitively ...
- 499
39
votes
4
answers
4k
views
Illustrating Edward Nelson's Worldview with Nonstandard Models of Arithmetic
Mathematician Edward Nelson is known for his extreme views on the foundations of mathematics, variously described as "ultrafintism" or "strict finitism" (Nelson's preferred term), which came into the ...
- 4,529
35
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$-...
- 42.5k
32
votes
11
answers
10k
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 (...
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,095
5
votes
1
answer
687
views
Can the Burgess-Hazen analysis of Predicative Arithmetic be extended to Transfinite Types?
Around page 300 of his book "Mathematical Thought and its Objects", Charles Parsons discusses the work of Edward Nelson, who believes that mathematical induction is impredicative, because it can be ...
- 4,529
72
votes
8
answers
12k
views
Category theory and set theory: just a different language, or different foundation of mathematics?
This is a question to research mathematicians, as well as to those concerned with the history and philosophy of mathematics.
I am asking for a reference. In order to make the reference request as ...
- 6,787
58
votes
8
answers
12k
views
How true are theorems proved by Coq?
Less tongue in cheek, is it known what the relative consistency is for theorems proved with an automatic theorem prover? Of course this depends somewhat on what assumptions one makes with respect to ...
- 33.9k
38
votes
7
answers
6k
views
Is V, the Universe of Sets, a fixed object?
When I first read Set Theory by Jech, I came under the impression that the Universe of Sets, $V$ was a fixed, well defined object like $\pi$ or the Klein four group. However as I have read on, I am ...
- 680
33
votes
3
answers
5k
views
Top-down mathematics, or "Where it all begins"
Sorry if this is off-topic.
It was my attempt to take a top-down approach to mathematics.
Being an inexperienced undergraduate (so please take my writing here lightly), I've been presented with ZFC as ...
- 447
26
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$ ...
- 65.1k
18
votes
10
answers
7k
views
Set theory and alternative foundations
Every foundational system for mathematics I have ever read about has been a set theory, from ETCS to ZFC to NF. Are there any proposals for a foundational system which is not, in any sense, a set ...
- 565
17
votes
2
answers
2k
views
When the definition of a set starts to matter in category theory
In most introductory courses to category theory, the precise definition of a set is more-or-less ignored. The idea being that all basic results in the subject hold for any reasonable definition of a ...
- 131
13
votes
3
answers
2k
views
Consistency of Analysis (second order arithmetic)
Is there a proof of the consistency of Analysis (second order arithmetic), which is similar to Gentzen's proof of the consistency of arithmetic?
Update:
Which (different) methods can be used to ...
12
votes
2
answers
834
views
The inconsistency of Graham Arithmetics plus $ \forall n, n < g_{64}$
As you all know, Ronald Graham just passed away. He is famous for many fabulous contributions to finite combinatorics, and much much more, but perhaps none of them is as popular as the infamous ...
- 7,613
8
votes
3
answers
2k
views
Does the Feferman-Schutte analysis give a precise characterization of Predicative Second-Order Arithmetic?
A definition is called impredicative if it involves quantification over a domain that contains the thing being defined. For instance, if you define hereditary property to be a property which applies ...
- 4,529
6
votes
0
answers
146
views
Does every Tarski plane embed into a 3-dimensional Tarski space?
By a Tarski space I understand a mathematical structure $(X,B,\equiv)$ consisting of set $X$, a betweenness relation $B\subseteq X^3$ and a congruence relation ${\equiv}\subseteq X^2\times X^2$ ...
- 40.9k
5
votes
1
answer
334
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)$ ...
- 9,256
43
votes
4
answers
4k
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 ...
- 61.5k
28
votes
0
answers
2k
views
Is Feferman's unlimited category theory dead?
In 2013 Solomon Feferman in Foundations of unlimited category theory: what remains to be done (The Review of Symbolic Logic, 6 (2013) pp 6-15, link) laid out three desirable axioms for "...
- 1,436
21
votes
4
answers
4k
views
How much of the axiom of choice do you need in mathematics?
Say we have DC-λ where λ is some inaccessible cardinal. Is that enough to develop all of ordinary mathematics? If not, is there a strengthening that is but that nevertheless does not assume full ...
- 347
19
votes
2
answers
2k
views
Which kind of foundation are mathematicians using when proving metatheorems?
Zermelo-Fraenkel set theory (with choice) is commonly accepted as the standard foundation of mathematics. It is a material set theory. For every two objects/sets $a,b$ one can ask whether $a=b$ or not....
user103598
18
votes
4
answers
2k
views
Does the existence of the von Neumann hierarchy in models of Zermelo set theory with foundation imply that every set has ordinal rank?
Let $T$ be the theory consisting of Zermelo's original set theoretic axioms (extensionality, empty set, pairing, union, powerset, infinity, separation, choice) together with foundation. Put more ...
- 2,290
17
votes
1
answer
861
views
Positive set theory and the "co-Russell" set
This is a more focused version of a question which was asked at MSE a couple years ago, but is still unanswered there. That question asks about a broad range of theories, whereas this version focuses ...
- 19k
16
votes
2
answers
797
views
Can a stochastic Turing machine output a consistent extension of PA with positive probability?
Suppose that we interpret the output tape of a Turing machine as an assignment of true or false to all sentences of PA, taking the $n$th output bit as the truth value of the sentence with Goedel ...
- 163
16
votes
3
answers
1k
views
Finite versions of Godel' s incompleteness
Assume you have some notion of proof complexity: for instance, at the basic level, the length of a proof, or the number of symbols used, take your pick (there are more involved measures, but for sake ...
- 7,613
15
votes
1
answer
2k
views
Martin's "Philosophical Issues about the Hierarchy of Sets"
Some months ago (October 2010), in the context of the Workshop on Set Theory and the Philosophy of Mathematics, Professor Donald A. Martin gave a talk entitled "Philosophical issues about the ...
- 1,475
15
votes
2
answers
1k
views
Could Kronecker accept a proof of Goodstein's theorem?
A famous result of Goodstein asserts that the Goodstein sequence of integers terminates.
For a precise statement and a short proof, see https://en.wikipedia.org/wiki/Goodstein%27s_theorem.
A well ...
- 27.3k
15
votes
1
answer
823
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 ...
- 8,186
11
votes
3
answers
2k
views
Kunen's use of Countable Transitive Models
Hi,
I have a doubt concerning Kunen's exposition of forcing in his classical book (arguably $the$ book on forcing). When dealing with Countable Transitive Models to set up the forcing machinery, ...
11
votes
4
answers
2k
views
Why do mathematicians prefer one definition over the other when they both define the same concept?
Here is a basic, though very important, example:
Hilbert takes as primary the notion of “congruence” (or “equal”) between segments. His first axiom of congruence “requires the possibility of ...
- 2,277
10
votes
1
answer
2k
views
Set-theoretical multiverse and foundations
I just had a look to the article The set theoretical multiverse by (mo user) J.D.Hamkins. Not being a logician and not knowing forcing techniques, I couldn't fully appreciate the mathematical ideas, ...
- 22.7k
9
votes
1
answer
596
views
How many closed measure zero sets are needed to cover the real line?
This question assumes familiarity with combinatorial cardinal characteristics of the continuum.
Let $\mathcal{E}$ be the $\sigma$-ideal generated by closed measure zero subsets of the real line. It ...
- 3,104
9
votes
4
answers
1k
views
Direct axiomatization of ordinal and cardinal numbers
Again, this question is related (**) to a previous one:
in standard books on basic set theory, after stating the axioms of ZFC, ordinal numbers are introduced early on. Afterwards cardinals appear: ...
- 7,613
8
votes
1
answer
3k
views
Foundations: Existence of uncountable ordinals.
This isn't really a research question, but at least it's research-level mathematics. I'm talking with some other people about the first uncountable ordinal, and I want some facts to inform this ...
- 2,654
8
votes
1
answer
1k
views
Ill-founded models of set theory with well-founded ordinals
Let $(\mathcal{M},E)$ be an internally non-well-founded model of set theory i.e of $ZFC^{\neg f}=ZFC\setminus \mathrm{foundation}+\neg \mathrm{foundation}$, then $\mathcal{M}$ includes an infinite ...
- 2,341
7
votes
1
answer
522
views
Iterated Gentzen: or, a Sith objection to the proof of consistency of PA
$\DeclareMathOperator\PRA{PRA}\DeclareMathOperator\WF{WF}\DeclareMathOperator\Con{Con}\DeclareMathOperator\PA{PA}$Preamble: In the year … in a galaxy far far away, a nasty Sith named Darth Dubious (...
- 7,613
7
votes
1
answer
425
views
How many closed measure zero sets are needed to cover the real line, really?
This is a refinement of an earlier question.
This question assumes familiarity with combinatorial cardinal characteristics of the continuum.
For the reader's convenience, I reproduce below the ...
- 3,104
6
votes
1
answer
1k
views
Some questions about Ackermann set theory
In a comment on this site Andreas Blass stated:
"To fit this situation into my philosophical point of view, I'd say that what Ackermann's theory
calls proper classes are really certain sets. That ...
- 897
6
votes
1
answer
1k
views
Surreal numbers and large cardinals
This is a question in two parts about the interaction of surreal numbers and large cardinals, in both cases just a request for references on the subject.
Part 1 is about foundations. Much of the ...
- 4,525
6
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 ...
- 7,613