The tag has no usage guidance.

learn more… | top users | synonyms

45
votes
7answers
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
6answers
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
4answers
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
5answers
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
1answer
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
3answers
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
6answers
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
2answers
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
1answer
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
0answers
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
0answers
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
3answers
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
1answer
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
2answers
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
1answer
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
4answers
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
3answers
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
1answer
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
10answers
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
3answers
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
5answers
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
3answers
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
2answers
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
3answers
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
1answer
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
2answers
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
2answers
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
1answer
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
1answer
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
1answer
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
6answers
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
3answers
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
3answers
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
1answer
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
3answers
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
2answers
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
0answers
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
8answers
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
3answers
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
1answer
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
0answers
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
11answers
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
3answers
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
1answer
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
3answers
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
1answer
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
1answer
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
0answers
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
4answers
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
1answer
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 ...