All Questions
6,026 questions
32
votes
3
answers
7k
views
Is the statement that every field has an algebraic closure known to be equivalent to the ultrafilter lemma?
The existence and uniqueness of algebraic closures is generally proven using Zorn's lemma. A quick Google search leads to a 1992 paper of Banaschewski, which I don't have access to, asserting that ...
- 118k
32
votes
4
answers
4k
views
Is a random subset of the real numbers non-measurable? Is the set of measurable sets measurable?
One might say, "a random subset of $\mathbb{R}$ is not Lebesgue measurable" without really thinking about it. But if we unpack the standard definitions of all those terms (and work in ZFC), it's not ...
- 2,210
32
votes
11
answers
3k
views
Is there a general setting for self-reference?
This is a question about self-reference: Has anyone established an abstract framework, maybe a certain kind of formal language with some extra structure, which makes it possible to define what is a ...
- 12.3k
32
votes
3
answers
4k
views
What is the reverse mathematical strength of the fundamental theorem of algebra?
Reverse mathematics (RM) is that area that tries to pin down exactly which axioms are necessary to prove theorems, given some weak base theory. Harvey Friedman has pointed out several times (on the ...
- 35.5k
32
votes
2
answers
3k
views
Can we interpret arithmetic in set theory, with exactly PA as the ZFC provable consequences?
There are many interpretations of arithmetic in set theory. The
Zermelo interpretation, for example, begins with the empty set and applies the singleton operator as successor:
$$0=\{\ \}$$
$$1=\{0\}$$
...
- 236k
32
votes
2
answers
3k
views
Do we expect that sufficiently large computable ordinals settle every question of arithmetic?
I came across a post by Ron Maimon on physics.SE that makes what seems to me to be a very interesting conjecture I've never seen before about what it would take to settle every question of arithmetic. ...
- 118k
32
votes
5
answers
4k
views
How many of the true sentences are provable?
Is there a natural measure on the set of statements which are true in the usual model (i.e. $\mathbb{N}$) of Peano arithmetic which enables one to enquire if 'most' true sentences are provable or ...
- 5,339
32
votes
2
answers
4k
views
Similarities between Post's Problem and Cohen's Forcing
Remark: I have since learned that G.H. Moore addresses this question in the third reference listed at the end of this post, beginning on p. 157 in which he cites a letter from Kreisel to Gödel dated 4/...
- 7,831
32
votes
2
answers
2k
views
Applications of Categorical Logic to Logic
This is definitely a very open ended question.
I have been studying Categorical Logic for a while now --- I've read Sheaves in Geometry and Logic, Adámek & Rosický's Presentable Categories, ...
32
votes
2
answers
2k
views
The NP version of Matiyasevich's theorem
By Matiyasevich, for every recursively enumerable set $A$ of natural numbers there exists a polynomial $f(x_1,...,x_n)$ with integer coefficients such that for every $p\ge 0$, $f(x_1,...,x_n)=p$ has ...
user6976
32
votes
5
answers
3k
views
What is the status of the Hilbert 6th problem?
As you know, the Hilbert sixth problem was to axiomatize physics. According to the Wikipedia article, there is some partial succes in this field. For example, Classical mechanics, I believe, can be ...
- 7,426
32
votes
5
answers
9k
views
How many binary operations are associative?
Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each
be ...
- 151k
32
votes
1
answer
2k
views
Can ZFC → NBG be iterated?
von Neumann-Bernays-Gödel set theory (NBG) is a conservative extension of ZFC which contains "classes" (such as the class of all sets) as basic objects. "Conservative" means that anything provable in ...
- 66.8k
32
votes
1
answer
2k
views
Godel on recursion-theoretic hierarchies
At the end of his excellent article, "The Emergence of Descriptive Set Theory" (http://math.bu.edu/people/aki/2.pdf), Kanamori writes:
"Another mathematical eternal return: Toward the end of his ...
- 20.5k
31
votes
6
answers
8k
views
Explanations for mathematicians, about the falsifiability (or not) of string theory [closed]
Like many other mathematicians, I think string theory very attractive. This theory has wonderfully influenced many new topics in mathematics (I myself have worked on one of them), but it's not the ...
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 ...
31
votes
6
answers
4k
views
A Model where Dedekind Reals and Cauchy Reals are Different
Is there a model where Dedekind reals and Cauchy reals are different? I'd appreciate if someone can refer me to any related work in case such a model exists.
- 365
31
votes
4
answers
4k
views
Is "all categorical reasoning formally contradictory"?
In the December 2009 issue of the newsletter of the European Mathematical Society there is a very interesting interview with Pierre Cartier. In page 33, to the question
What was the ontological ...
- 33.3k
31
votes
2
answers
1k
views
Define $\mathbb{N}$ in the ring $\mathbb{Z}$ without Lagrange's theorem
It is well-known that the set of nonnegative integers $\mathbb{N}$ is definable in the ring of integers $\mathbb{Z}$. Indeed, by Lagrange's four squares theorem we have $\mathbb{N} = \{n \in \mathbb{Z}...
user40023
31
votes
3
answers
3k
views
Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?
Question. Given a Turing-machine program $e$, which
is guaranteed to run in polynomial time, can we computably
find such a polynomial?
In other words, is there a
computable function $e\mapsto p_e$, ...
- 236k
31
votes
3
answers
5k
views
Should there be a true model of set theory?
As I understand it, there is a program in set theory to produce an ultimate, canonical model of set theory which, among other things, positively answers the Continuum Hypothesis and various questions ...
- 3,982
31
votes
8
answers
3k
views
Unique existence and the axiom of choice
The axiom of choice states that arbitrary products of nonempty sets are nonempty.
Clearly, we only need the axiom of choice to show the non-emptiness of the product if
there are infinitely many ...
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
2
answers
3k
views
Mathematical Evidence Backing $|\mathbb{R}|=\aleph_2$
The "true" size of the real line, $\mathbb{R}$, has been the subject of Hilbert's first problem. Due to the Goedel and Cohen's work on the inner and outer models of $\text{ZFC}$, it turned ...
31
votes
2
answers
2k
views
The logic of convex sets
Let me start with Helly's theorem: Let $A_1$, $A_2$, ..., $A_{n+2}$ be $n+2$ convex subsets of $\mathbb R^n$. If any $n+1$ of these subsets intersect (this means: have nonempty intersection), the so ...
- 33.8k
30
votes
11
answers
6k
views
Physics and Church–Turing Thesis
Is there constructed some set of physical laws from which we can logically obtain that any function that can be implemented in some device is Turing computable?
EDIT
I believe that if we restrict ...
- 1,318
30
votes
6
answers
6k
views
In set theories where Continuum Hypothesis is false, what are the new sets?
So, say we are working with non-CH mathematics. This means, AFAIK, that there is at least one set $S$ in our non-CH mathematics, whose cardinality is intermediate between $|\mathbb{N}|$ (card. of ...
- 303
30
votes
7
answers
3k
views
What is a logic?
I am not interested in the philosophical part of this question :-)
When I look at mathematics, I see that lots of different logics are used : classical, intuitionistic, linear, modal ones and weirder ...
- 445
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
30
votes
3
answers
3k
views
Can there be an embedding j:V → L, from the set-theoretic universe V to the constructible universe L, when V ≠ L?
Main Question. Can there be an embedding $j:V\to L$ of the
set-theoretic universe $V$ to the constructible universe $L$, if
$V\neq L$?
By embedding here, I mean merely a proper class isomorphism from
$...
- 236k
30
votes
1
answer
2k
views
Do the algebraic integers form a free abelian group?
It is a well-known fact, proved in every introductory textbook on algebraic number theory, that if $K$ is an algebraic number field, i.e. a finite extension of $\mathbb{Q}$, then its ring $\mathcal{O}...
- 1,288
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$ ...
- 66.8k
29
votes
8
answers
4k
views
When is something too big to be a set?
Hello,
recently, I've been reading some algebra and sometimes I stumble up on the concept of something "being too big" to be a set. An example, is given in (http://www.dpmms.cam.ac.uk/~wtg10/tensors3....
- 1,071
29
votes
10
answers
4k
views
Defining the standard model of PA so that a space alien could understand
First, some context. In one of the comments to an answer to the recent question Why not adopt the constructibility axiom V=L? I was directed to some papers of Nik Weaver at this link, on ...
- 18.7k
29
votes
3
answers
3k
views
Is the theory of categories decidable?
There are a lot of theorems in basic homological algebra, such as the five lemma or the snake lemma, that seem like they'd be more easily proven by computer than by hand. This led me to consider the ...
29
votes
6
answers
4k
views
Concrete example of $\infty$-categories
I've seen many different notions of $\infty$-categories: actually I've seen the operadic-globular ones of Batanin and Leinster, and the opetopic, and eventually I'll see the simplicial ones too. ...
- 3,349
29
votes
2
answers
3k
views
Who introduced direct limits?
The general notion of a direct limit of a commuting system of embeddings, indexed by pairs in a directed set, has seen heavy use in set theory. It is the same notion as in category theory. I was ...
- 18.6k
29
votes
3
answers
3k
views
Is there a probability theory developed in intuitionistic logic?
Since Boole it is known that probability theory is closely related to logic.
According to the axioms of Kolmogorov, probability theory is formulated with a (normalized)
probability measure $\mbox{...
- 567
29
votes
6
answers
38k
views
Reading materials for mathematical logic [closed]
Hi everyone, the summer break is coming and I am thinking of reading something about mathematical logic. Could anyone please give me some reading materials on this subject?
29
votes
2
answers
794
views
Does $\mathrm{SO}(3)$ act faithfully on a countable set?
Let $\mathrm{SO}(3)$ be the group of rotations of $\mathbb{R}^3$ and let $S_\infty$ be the group of all permutations of $\mathbb{N}$. Is $\mathrm{SO}(3)$ isomorphic to a subgroup of $S_\infty$?
This ...
- 1,689
29
votes
4
answers
4k
views
How dangerous are set-size assumptions?
Many students' first introduction to the difference between classes and sets is in category theory, where we learn that some categories (such as the category of all sets) are class-sized but not set-...
- 18.7k
29
votes
2
answers
2k
views
What do coherent topoi have to do with completeness?
There is a theorem of Deligne in SGA4 that a "coherent" topos (e.g. one on a site where all objects are quasi-compact and quasi-separated) has enough points (i.e. isomorphisms can be detected via ...
- 25.6k
29
votes
2
answers
2k
views
On the probability of the truth of the continuum hypothesis
First note that there exists a natural measure $\mu$ on $P(\omega \times \omega)$, inherited from the Lebesgue measure on the reals (by identifying the reals with $P(\omega)$ and $\omega$ with $\omega ...
- 32.2k
29
votes
2
answers
5k
views
What is the manner of inconsistency of Girard's paradox in Martin Lof type theory
I am aware that assigning the type of Type to be Type (rather than stratifying to a hierarchy of types) leads to an inconsistency. But does this inconsistency allow the construction of a well-typed ...
- 595
29
votes
2
answers
4k
views
The philosophy behind local rings
This question has been bugging me for a while and I can't seem to make sense of it on a clear conceptual level.
The theory of local rings is given by taking the theory of rings and adding the axioms
\...
- 2,303
29
votes
1
answer
1k
views
Is the Golomb countable connected space topologically rigid?
The Golomb space $\mathbb G$ is the set of positive integers endowed with the topology generated by the base consisting of the arithmetic progressions $a+b\mathbb N_0$ with relatively prime $a,b$ and $...
- 41.9k
29
votes
2
answers
3k
views
Does Taranovsky's system of ordinal notations make sense?
Dmytro Taranovsky has a Web page on which he claims to define a system of ordinal notations strong enough to provide an ordinal analysis of full second-order arithmetic. I think (perhaps unjustly) ...
- 32.5k
29
votes
0
answers
2k
views
Did Grothendieck overestimate topoi?
I was reading the Russian translation of Recoltes et Semailles and in the footnote where Grothendieck lists his 12 contributions (including schemes) we find the following lines:
Из этих тем ...
28
votes
13
answers
4k
views
Are there any good nonconstructive "existential metatheorems"?
Are there any good examples of theorems in reasonably expressive theories (like Peano arithmetic) for which it is substantially easier to prove (in a metatheory) that a proof exists than it is ...
28
votes
5
answers
3k
views
How do we construct the Gödel’s sentence in Martin-Löf type theory?
In Martin-Löf dependent type theory (MLTT), under the proposition-as-types correspondence, we sometimes say that a proposition $A$ is true if the type $A$ is inhabited. However, there is no doubt that ...
- 765