The foundations tag has no usage guidance.

**45**

votes

**7**answers

5k 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 ...

**28**

votes

**6**answers

5k 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 ...

**26**

votes

**4**answers

2k 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 ...

**24**

votes

**5**answers

3k views

### Nonstandard analysis in probability theory

I am quite new at nonstandard analysis, and recently I became aware of its use in probability theory mainly through the following two books:
Nelson (1987). Radically Elementary Probability Theory
...

**21**

votes

**1**answer

1k views

### Nontrivial circular arguments?

There is a famous circular argument for the Prime Number Theorem (PNT). It turns
out that there exists an infinite sequence of elementary-to-prove Chebyshev-type estimates
that taken together imply ...

**20**

votes

**3**answers

2k 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 \...

**19**

votes

**6**answers

1k 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 ...

**17**

votes

**2**answers

999 views

### Age of Stochasticity?

One user on MSE made an interesting question, which was unanswered so I suggested him to post it here but he refused for personal reasons and said I could ask it here.
The question is this:
Today ...

**17**

votes

**1**answer

688 views

### On Joyal's completeness theorem for first order logic

In 1978, in a series of unpublished conferences in Montréal, A. Joyal announced a remarkable theorem that unified several completeness theorems for fragments of first order logic, as well as first ...

**17**

votes

**0**answers

436 views

### The cofinality of $(\mathbb{N}^\kappa,\le)$ for uncountable $\kappa$?

For a partially ordered set $P$, a set $A\subseteq P$ is cofinal if for each element of $P$ there is a larger element in $A$. The cofinality of $P$, ${\rm cof}(P)$, is the minimal cardinality of a ...

**17**

votes

**0**answers

397 views

### Are there lightweight foundations for arbitrarily extendable objects?

My experience with foundations is rather scant, but I've run into some types of objects that seem to resist the sort of set-theoretic encoding schemes via Kurowski tuples that are rather common for ...

**16**

votes

**3**answers

853 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 ...

**16**

votes

**1**answer

635 views

### Monte Carlo integration

As probably many other people here, I learned integration, as an undergrad, from Rudin's books. I recently realized, however, that I don't quite use Lebesgue integration in my work, or at least I use ...

**15**

votes

**2**answers

496 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 ...

**15**

votes

**1**answer

1k 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 ...

**14**

votes

**4**answers

718 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 ...

**14**

votes

**3**answers

2k 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 ...

**13**

votes

**1**answer

854 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 ...

**12**

votes

**10**answers

4k 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 (...

**12**

votes

**3**answers

1k views

### Proof correctness problem

I was watching this talk by Vladimir Voevodsky which was given at the Institute of Advanced Study in 2006.
In his talk the first slide he shows has the following written on it:
...

**12**

votes

**5**answers

3k views

### getting rid of existential quantifiers

It seems to me that for most of the twentieth century, axiomatic foundations for mathematical theories were constructed with the (mostly allied) goals of minimizing the number of primitive notions and ...

**12**

votes

**3**answers

865 views

### Where is the end of universe?

In some sense the empty set ($\emptyset$) and the global set of all sets ($G$) are the ends of the universe of mathematical objects. The world which $ZFC$ describes has an end from the bottom and is ...

**11**

votes

**2**answers

599 views

### Are simplicial sets the intended model of HoTT?

While thinking about Jason Rute's question, I wondered if there was an intended model for HoTT. The main candidate for the intended model are simplicial sets, where Vladimir Voevodsky first observed ...

**11**

votes

**3**answers

2k views

### Is there a categorical proof of Gödel's incompleteness theorem?

A significant result in set theory was shown by Cohen when he showed that the continuum hypothesis was independent of ZFC using a new technique called forcing. In Topos theory, this result has a new ...

**11**

votes

**1**answer

846 views

### Elementary Equivalence =? Homotopy Equivalence

One of the most interesting novelties in recent foundational studies is Voevodsky's Homotopical Type Theory project (see here).
Finally homotopy theory ideas have entered in a royal fashion the ...

**10**

votes

**2**answers

893 views

### Equivalent form of the Univalence Axiom

I'm reading the new HoTT book and I'm wondering about a potential equivalent form of the Univalence Axiom: $(A \simeq B) \simeq (A = B)$.
For simplicity, I'm tacitly working in a fixed universe. It ...

**10**

votes

**2**answers

461 views

### Ways to define “definability”

The notion of a definable set is not expressible in the language of set theory: there is no formula $\delta(x)$ that is equivalent with there being a formula $\phi(y)$ such that $x = \lbrace y : \phi(...

**10**

votes

**1**answer

2k views

### Up-to-date version of Principia Mathematica?

Background: I found this interesting translation of Godel's On formally undecidable propositions of Principia Mathematica and related systems I that, along with translating it into English, uses more ...

**10**

votes

**1**answer

1k 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, ...

**10**

votes

**1**answer

458 views

### What is the most transparent, rigorous definition of the Univalence Axiom?

I've been studying homotopy type theory and trying to grasp the Univalence Axiom. I have yet to find a concise, accessible, rigorous definition of Univalence. I have several excellent survey papers ...

**9**

votes

**6**answers

970 views

### (Non?)-linearity of the consistency strength ordering in ZF

Much of the research taking place in set theory, is related to the classification of sentences according to their consistency strength relative to ZF. In order to be more specific, we say that for all ...

**9**

votes

**3**answers

940 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 ...

**9**

votes

**3**answers

919 views

### What set theoretical questions could never be answered by Turing machines of arbitrary cardinality?

Let us assume that there are Turing machines of arbitrary cardinality, by that I mean they can have input tapes of any arbitrarily high cardinality and compute for a number of steps also of ...

**9**

votes

**1**answer

428 views

### Ultimate Maximality Principle

I wonder if it's possible to formulate an "ultimate" maximality principle (UMP) and prove its consistency. I envision UMP to express the idea that no matter how we enlarge the universe of set theory V ...

**9**

votes

**3**answers

747 views

### On a weak choice principle

[PLEASE SEE EDITS AT BOTTOM OF QUESTION]
Consider the following set-theoretic axiom:
For each set $X$ there exists a set-indexed collection $\{C_i \to X\}_{i\in I_X}$ of surjections such that for ...

**9**

votes

**2**answers

636 views

### Consistent hierarchy of axiomatic systems

First of all, I am not an expert in model theory. I just want to get my personal view on the foundations of mathematics straight.
I just learned in Sergey Melikhov's answer to another question ...

**9**

votes

**0**answers

681 views

### Has anyone pursued Frege's idea of numbers as second-order concepts?

Gottlob Frege was a pivotal figure in the history of mathematical logic. He gave an analysis of numbers that proceeded along roughly the following lines, in his books "The Foundations of Arithmetic" (...

**8**

votes

**8**answers

3k 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 ...

**8**

votes

**3**answers

1k 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, ...

**8**

votes

**1**answer

388 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 ...

**8**

votes

**0**answers

221 views

### Is there a notion analogous to separability but requiring definable rather than countable sets?

Among models of $\lambda$-calculus, some like the Bohm tree model have the property that every element is a directed sup of definable elements, whereas others like the $D_\infty$ and $P(\omega)$ ...

**7**

votes

**11**answers

2k views

### A function that is defined everywhere but has unknown values [closed]

For pedagogical purposes I am looking for a function $\mathbb{N}\to\mathbb{N}$ that is defined everywhere but has most of its values unknown. Although such a function cannot be simple by definition, ...

**7**

votes

**3**answers

2k views

### incompleteness in real analysis

Godel's theorem tells us that any sufficiently powerful consistent formal theory of the integers is incomplete; but what about formal theories of the real numbers? More precisely, what about theories ...

**7**

votes

**1**answer

448 views

### Taller models of ZFC

This question is somewhat related to a previous one, where I asked for new forms of infinite beyond the cardinal hierarchy.
Using forcing techniques, at least the ones I know of, one starts from a ...

**7**

votes

**3**answers

463 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 ...

**7**

votes

**1**answer

485 views

### Normality of Chaitin's constant

Can anyone provide an overview of the proof that Chaitin's constant is normal, or better yet, the guiding intuition?
Even if we replace the existential quantifiers in the assertion of non-normality ...

**7**

votes

**1**answer

787 views

### Original proof of Gödel's completeness theorem compared to Henkin's proof

May I have some clarification about original proof of Gödel's Completeness Theorem compared to "standard" Henkin's proof based on Model Existence Lemma ?
My understanding of Gödel's original proof is ...

**7**

votes

**0**answers

975 views

### Is there a finite-dimensional vector space whose dimension cannot be found? [closed]

Is there a finite-dimensional vector space whose dimension cannot be found? Assume, we have somehow constructed a vector space whose dimension is finite, but yet unknown. Is there always an algorithm ...

**6**

votes

**4**answers

534 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: ...

**6**

votes

**1**answer

299 views

### What do we call this quantifier (“binder”)?

There's a quantifier ("binder", whatever), call it $\alpha$, defined as follows: $\alpha x.\tau$ is the (usually infinite) expression obtained by applying the substitution $\{x \mapsto \tau\}$ to the ...