All Questions
6,026 questions
37
votes
1
answer
2k
views
Is $π$ definable in $(\Bbb R,0,1,+,×,<,\exp)$?
(This question is originally from Math.SE, where it didn't receive any answers.)
Is there a first-order formula $\phi(x) $ with exactly one free variable $ x $ in the language of ordered fields ...
- 3,017
37
votes
1
answer
3k
views
Community experiences writing Lamport's structured proofs
About two years ago, I came across this paper by Lamport
http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-how-to-write.pdf
on writing proofs hierarchically. It changed how I wrote ...
36
votes
3
answers
3k
views
Latest status of core model theory?
What is the "strongest" core model to this day? In particular, how far are we from a core model for supercompact cardinals? There are rumors of some notes from a workshop in 2004:
https://...
- 1,312
36
votes
6
answers
5k
views
Does finite mathematics need the axiom of infinity?
A statement referring to an infinite set can sometimes be logically rephrased using only finite sets/objects. For example, "The set of primes is infinite" <-> "There is no largest prime". ...
- 11.3k
36
votes
3
answers
2k
views
Internal logic of the topos of simplicial sets
I am looking for a closed statement (i.e. not depending on any parameter objects) which is true in the internal logic of the topos of simplicial sets, but is not an intuitionistic tautology. Ideally, ...
- 66.8k
36
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$-...
- 43.2k
36
votes
8
answers
2k
views
Does the truth of any statement of real matrix algebra stabilize in sufficiently high dimensions?
This question is related to this recent but currently
unanswered MO
question
of Ricky Demer, where it arose as a comment.
Consider the structure $R^n$ consisting of $n\times n$
matrices over the ...
- 236k
36
votes
2
answers
3k
views
What can be expressed in and proved with the internal logic of a topos?
The title of this post expresses what I really want, which is to learn how to wield the internal logic of a topos more effectively. However, to bring it down to earth, I'll ask a few basic questions ...
- 8,659
36
votes
3
answers
3k
views
The set-theoretic multiverse as a (bi)category
Joel Hamkin's The set-theoretic multiverse has featured in MO questions before, e.g., here and here. But I was wondering about the best category theoretic angle to take on it.
In the paper Joel ...
- 5,094
35
votes
9
answers
14k
views
What is... a grossone?
Y. Sergeyev developed a positional system for representing infinite numbers using a basic unit called a "grossone", as well as what he calls an "infinity computer". The ...
- 16.6k
35
votes
8
answers
7k
views
Why not adopt the constructibility axiom $V=L$?
Gödelian incompleteness seems to ruin the idea of mathematics offering absolute certainty and objectivity. But Gödel‘s proof gives examples of independent statements that are often remarked as having ...
35
votes
15
answers
2k
views
Objects which can't be defined without making choices but which end up independent of the choice
It happens a lot of times that when one defines a new object (ring, module, space, group, algebra, morphism, whatever) out of given data, one first chooses some additional structure. And sometimes (...
35
votes
7
answers
8k
views
Status of Harvey Friedman's grand conjecture?
Friedman [1] conjectured
Every theorem published in the Annals of Mathematics whose
statement involves only finitary mathematical objects (i.e., what logicians
call an arithmetical statement) ...
- 9,114
35
votes
9
answers
3k
views
Are there examples of statements that have been proven whose consistency proofs came before their proofs?
I'm wondering if there are examples of statements that have been proven whose consistency proofs came before the proofs of the statements themselves.
More informally, I'm wondering how promising in ...
- 505
35
votes
8
answers
4k
views
Is P=NP relevant to finding proofs of everyday mathematical propositions?
Disclaimer: I don't know a whole lot about complexity theory beyond, say, a good undergrad class.
With increasing frequency I seem to be encountering claims by complexity theorists that, in the ...
- 3,267
35
votes
3
answers
5k
views
Using Busy Beavers to prove conjectures
I've been pondering some stuff on Shtetl Optimized where Yedidia and Aaronson construct Turing machines that will only halt if (e.g.) the Riemann Hypothesis is false, or Goldbach's conjecture is false....
- 483
35
votes
7
answers
4k
views
Paradoxical Mathematical Objects Pending for Construction [duplicate]
The possible properties and applications of some mathematical objects have been described far before their rigorous mathematical definition. Some of them even had a seemingly paradoxical description ...
35
votes
8
answers
3k
views
Examples of statements with a high quantifier complexity
What are some natural properties, definitions, and statements that require many alternating quantifiers?
The complexity could be $\Pi^0_k$, $\Pi^1_k$, $\Pi^V_k$, or something else entirely, as long $k$...
- 7,545
35
votes
8
answers
4k
views
Interpretation of the Second Incompleteness Theorem
For simplicity, let me pick a particular instance of Gödel's Second Incompleteness
Theorem:
ZFC (Zermelo-Fraenkel Set Theory plus the Axiom of Choice, the usual foundation of mathematics) does not ...
- 16.2k
35
votes
3
answers
5k
views
Counterintuitive consequences of the Axiom of Determinacy?
I just read Dr Strangechoice's explanation that if all subsets of the real numbers are Lebesgue measurable, then you can partition $2^\omega$ into more than $2^\omega$ many pairwise disjoint nonempty ...
- 7,633
35
votes
3
answers
3k
views
Probably true, but provably unprovable
I'm wondering if anyone has found, or can find, a sequence of statements $P(n)$ ($n \in \mathbb{N}$) such that:
Heuristic arguments using probability theory suggest that all the statements $P(n)$ are ...
- 22.3k
35
votes
2
answers
3k
views
Is Lagrange's Theorem equivalent to AC?
Lagrange's Theorem is most often stated for finite groups, but it has a natural formation for infinite groups too: if $G$ is a group and $H$ a subgroup of $G$, then $|G| = |G:H| \times |H|$.
If we ...
- 643
34
votes
23
answers
29k
views
Textbook recommendations for undergraduate proof-writing class
I am teaching the proof-writing class (for the 3rd time) in the Fall and plan to buck the party line and use a different text than the default Bond and Keane. My parameters are as follows:
Logic, ...
34
votes
3
answers
6k
views
What would remain of current mathematics without axiom of power set? [closed]
The power set of every infinite set is uncountable. An infinite set (as an element of the power set) cannot be defined by writing the infinite sequence of its elements but only by a finite formula. By ...
user34913
34
votes
8
answers
8k
views
Arithmetic fixed point theorem
I want to understand the idea of the proof of the artihmetic fixed point theorem. The theorem is crucial in the proof of Gödel's first Incompletness theorem.
First some notation: We work in $NT$, the ...
- 63.1k
34
votes
3
answers
4k
views
Alternatives to the law of the excluded middle
As a sentential logic, intuitionistic logic plus the law of the excluded middle gives classical logic.
Is there a logical law that is consistent with intuitionistic logic but inconsistent with ...
- 331
34
votes
4
answers
3k
views
In what rigorous sense are Sperner's Lemma and the Brouwer Fixed Point Theorem equivalent?
I understand that one can give a proof of each of these propositions assuming the truth of the other. But this seems a bit squishy to me, since there is a trivial sense in which any two true theorems ...
- 19.7k
34
votes
3
answers
2k
views
How much choice is needed to show that formally real fields can be ordered?
Background: a field is formally real if -1 is not a sum of squares of elements in that field. An ordering on a field is a linear ordering which is (in exactly the sense that you would guess if you ...
- 65.4k
34
votes
2
answers
3k
views
"Transitivity" of the Stone-Cech compactification
Let $\beta \mathbb{N}$ be the Stone-Cech compactification of the natural numbers $\mathbb{N}$, and let $x, y \in \beta \mathbb{N} \setminus \mathbb{N}$ be two non-principal elements of this ...
- 114k
34
votes
4
answers
3k
views
Is it possible to define higher cardinal arithmetics
In number theory there are several operators like addition, multiplication and exponentiation defined from $\omega\times\omega$ to $\omega$. Each of them is defined as an ...
- 32.2k
34
votes
5
answers
2k
views
Forcing as a replacement of induction and diagonal arguments
Let me give some examples motivating the question.
The use of forcing instead of induction: For this consider Cantor's theorem:
Theorem 1. Any two countable dense linear orders $I, J$ without end ...
- 32.2k
34
votes
2
answers
2k
views
What is the logical status of the sentence combining the ideas of Löb and Rosser, "this sentence is provable before any proof of its negation"?
Logicians are familiar with the variety of self-referential sentences expressible in the language of arithmetic:
The Gödel sentence, "this sentence is not provable", which indeed is not ...
- 236k
34
votes
3
answers
3k
views
What is the theory of local rings and local ring homomorphisms?
It is well-known that the category of local rings and ring homomorphisms admits an axiomatisation in coherent logic. Explicitly, it is the coherent theory over the signature $0, 1, -, +, \times$ with ...
- 15.9k
34
votes
1
answer
3k
views
Does "every" first-order theory have a finitely axiomatizable conservative extension?
I originally asked this question on math.stackexchange.com here.
There's a famous theorem (due to Montague) that states that if $\sf ZFC$ is consistent then it cannot be finitely axiomatized. ...
- 3,137
34
votes
2
answers
3k
views
Ur-elemental surprises
For most of my (mathematical) life, I believed that there was really no essential difference between set theory without urelements and set theory with urelements. However, while that may be true in ...
- 20.5k
34
votes
1
answer
3k
views
Is the theory Flow actually consistent?
Recently the paper
Adonai S. Sant'Anna, Otavio Bueno, Marcio P. P. de França, Renato Brodzinski, Flow: the Axiom of Choice is independent from the Partition Principle, arXiv:2010.03664
appeared on ...
- 771
34
votes
5
answers
1k
views
Does the exact pair phenomenon for partial orders occur in your area of mathematics?
Suppose that I have a partial order P and an increasing sequence $a_0< a_1<a_2<\cdots$ of elements of $P$. A pair of elements (b,c) from P is said to be an exact pair for this sequence, if
...
- 236k
33
votes
5
answers
7k
views
Why do people say Gödel's sentence is true when it is true in some models but false in others?
I am a beginner, so this question may be naive.
Suppose we have a (sufficiently strong) consistent first order logic system. Gödel's first incompleteness theorem says there exists a Gödel sentence $g$ ...
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
33
votes
3
answers
7k
views
Category of categories as a foundation of mathematics
In
Lawvere, F. W., 1966, “The Category of
Categories as a Foundation for
Mathematics”, Proceedings of the
Conference on Categorical Algebra, La
Jolla, New York: Springer-Verlag,
1–21.
...
- 2,399
33
votes
3
answers
2k
views
Wiki for consequences of axiom of choice?
I raised the following question as part of another MO question, but I am following the suggestion of Nate Eldredge to make it a question in its own right.
For many years, there has a been a valuable ...
- 82.7k
33
votes
1
answer
3k
views
Is there a position in infinite Go for which the life of a particular stone has transfinite game value?
As follow up to Checkmate in $\omega$ moves?, we can ask the same question about go. Is there a position on a $\mathbb Z \times \mathbb Z$ goban such that either black can kill a white group, but ...
- 6,353
33
votes
2
answers
2k
views
Quantifier complexity of the definition of continuity of functions
This was previously asked at MSE, but I was told to ask it on MO. Consider the structure $(\mathbb{R};+,-,*,0,1,<)$. We adjoin to it a unary function $f$ defined everywhere on the set of real ...
- 2,023
33
votes
1
answer
1k
views
Is this conjecture strictly weaker than P=NP?
My three computability questions are related to the following group theory question (first asked by Bridson in 1996):
For which real $\alpha\ge 2$ the function $n^\alpha$ is equivalent to the Dehn ...
user6976
33
votes
0
answers
2k
views
Is there a (discrete) monoid M injecting into its group completion G for which BM is not homotopy equivalent to BG?
For a (discrete) monoid $M$, the classifying space $BM$ is the
geometric realization of the nerve of the one object category whose
hom-set is $M$. (This definition gives the usual classfiying space
...
- 5,309
33
votes
0
answers
2k
views
Defining $\mathbb{Z}$ in $\mathbb{Q}$
It was proved by Poonen that $\mathbb{Z}$ is definable in the structure $(\mathbb{Q}, +, \cdot, 0, 1)$ using $\forall \exists$ formula. Koenigsmann has shown that $\mathbb{Z}$ is in fact definable by ...
user16974
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 (...
32
votes
9
answers
5k
views
How many groups of size at most n are there? What is the asymptotic growth rate? And what of rings, fields, graphs, partial orders, etc.?
Question. How many (isomorphism types of) finite groups of size at most n are there? What is the asymptotic growth rate? And the same question for rings,
fields, graphs, partial orders, etc.
...
- 236k
32
votes
6
answers
5k
views
How do we recognize an integer inside the rationals?
My question is fairly simple, and may at first glance seem a bit silly, but stick with me. If we are given the rationals, and we pick an element, how do we recognize whether or not what we picked is ...
- 18.7k
32
votes
0
answers
2k
views
Peano Arithmetic and the Field of Rationals
In 1949 Julia Robinson showed the undecidability of the first order theory of the field of rationals by demonstrating that the set of natural numbers $\Bbb{N}$ is first order definable in $(\Bbb{Q}, +,...
- 17.7k