All Questions
1,142 questions
8
votes
2
answers
567
views
Darboux property of non-atomic sigma-additive nonnegative measures equivalent to the AC?
A result commonly, and probably erroneously, attributed to W. Sierpiński is that every non-atomic, countably additive, nonnegative measure $\mu: \Sigma \to \bf R$, where $\Sigma$ is a sigma-algebra on ...
- 10.5k
8
votes
2
answers
774
views
Does PA prove (Artemov-style) the consistency of a stronger system?
There was a recent question on Artemov's paper here on MO Situation with Artemov's paper?
In one of the answers there it was asserted (apparently incorrectly - see Noah Schweber's comments and ...
- 1,974
8
votes
2
answers
1k
views
Is there one binary operation foundational for set theory?
The membership relationship "$\in$" is foundational for set theory, in the sense that the axioms of any set theory are formulated in the language of "$\in$". Naturally, the ...
- 889
7
votes
1
answer
799
views
Is equality of terms for "real" numbers with roots, logarithm, exponential, sin, cos, and other trigonometric operations decidable with a Turing-machine?
If yes, how? Also, I know you can't do it for arbitrary statements about real numbers, but that's not what I'm asking, and by "real" numbers, I mean the numbers constructible from 1, -, /, and the ...
- 125
7
votes
1
answer
536
views
Is $\in$-induction provable in first order Zermelo set theory?
Are there models of first order Zermelo set theory (axiomatized by: Extensionaity, Foundation, empty set, pairing, set union, power, Separation, infinity) in which $\in$-induction fail?
I asked this ...
- 11.3k
6
votes
3
answers
444
views
Is $0^{(\omega)}$ a minimal cover in the arithmetic degrees
Is it known if $0^{(\omega)}$ a minimal cover in the arithmetic degrees? In the Turing degrees to show that $0'$ (indeed $0^{(n)}$) isn't a minimal cover one uses the density of r.e. degrees. ...
- 3,029
5
votes
2
answers
1k
views
How to define compatible topology for first-order structures?
Background Because a bounded distributive lattice can be represented by the clopen sets of a Priestley space, I tried to learn some basics about Priestley spaces. After reading (on Wikipedia)
A ...
- 2,464
5
votes
5
answers
2k
views
Defining 'free monoid' without Nat?
Is there a definition of what is a 'free monoid' which does not pre-suppose that the natural numbers has already been defined? The definitions that I have been able to track down all use the natural ...
- 11.8k
5
votes
1
answer
597
views
Can every cancellative invertible-free monoid be embedded in a group?
A monoid is invertible-free if $xy=1$ implies $x=y=1$ for all $x,y$.
Question: Can every cancellative invertible-free monoid be embedded in a group?
I'm fairly sure that a quotient of the free product ...
5
votes
1
answer
406
views
Computational approach deciding whether a set of Wang Tile could tile the space up to some size
As an applied person, I'm facing one practical problem deciding whether a set of Wang tile could tile the plane periodically or aperiodically. Although both problems seem undecidable, but I'm on a ...
- 867
5
votes
0
answers
218
views
Improving a Lindstrom-y fact about $\mathcal{L}_{\omega_1,\omega}$?
See e.g. the last section of Ebbinghaus/Flum/Thomas for the relevant background on abstract model theory. Below, all languages are finite for simplicity. "$HC$" is the set of hereditarily ...
- 20.5k
5
votes
2
answers
790
views
What is lost in General Relativity without Hahn-Banach axiom in the ZF+HB set theory?
In the same spirit of this question:
How much of mathematical General Relativity depends on the Axiom of Choice?
I want to go radically further ahead and ask for what remains of mathematical general ...
- 612
5
votes
1
answer
720
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,597
4
votes
2
answers
2k
views
Independence of PA implies independence of PA union all true $\Pi_1$ statements
Prove that if a statement is independent of Peano Arithmetic (PA), then it's also independent of PA$_1$, where PA$_1$ is the union of the set of axioms in PA and the set of all true $\Pi_1$ statements....
- 551
4
votes
0
answers
368
views
Ordinal analysis and nonrecursive ordinals
Ordinal analysis is typically described as characterizing recursive ordinals in a theory $T$, but there is a sense in which it can characterize all $T$-ordinals, even those that are nonrecursive.
...
- 7,545
3
votes
2
answers
709
views
Extendibility vs supercompactness
The following quotes comes from "Cantor's Attic"'s page on supercompacts:
If κ is $|V_{κ+η}|$-supercompact with $η<κ$ then it is preceeded by a stationary set of $η$-extendible cardinals. If $κ$ ...
- 615
2
votes
1
answer
203
views
Does $|(X\times\{0\}) \cup (X\times\{1\})| \leq |X|$ for $X$ infinite imply ${\sf AC}$?
Consider the statement
For any infinite set $X$ there is an injection $\varphi$ from $(X\times\{0\}) \cup (X\times\{1\})$ into $X$.
Does this imply the ${\sf AC}$?
- 48.9k
2
votes
1
answer
973
views
Compactness and completeness in Gödel logic
The standard proof of the completeness theorem in first-order Gödel logic is based
on a first-order countable language. I want to know that is there any proof of the completeness theorem in first-...
- 49
2
votes
1
answer
143
views
Does adding definability axiom expressed in infinitary language to ZF, let all models be pointwise definable?
This posting is generally related to a prior posting titled "Are all constructible from below sets parameter free definable?"
If we work in infinitary language $\mathcal L_{\omega_1, \omega}$...
- 11.3k
114
votes
2
answers
12k
views
How would you solve this tantalizing Halmos problem?
$1-ab$ invertible $\implies$ $1-ba$ invertible has a slick power series "proof" as below, where Halmos asks for an explanation of why this tantalizing derivation succeeds. Do you know one?
Geometric ...
- 4,736
74
votes
8
answers
14k
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,937
72
votes
13
answers
19k
views
Logic in mathematics and philosophy
What are the relations between logic as an area of (modern) philosophy and mathematical logic.
The world "modern" refers to 20th century and later, and I am curious mainly about the second ...
- 24.7k
60
votes
7
answers
9k
views
Does anyone still seriously doubt the consistency of $ZFC$?
As someone self-taught in set theory beginning with Donald Monk’s excellent book on MK set theory, $ZFC$ has always seemed like a weak set theory.
Despite this, the majority of professional ...
60
votes
8
answers
6k
views
Is the ultraproduct concept fundamentally category-theoretic?
Once again, I would like to take advantage of the large number of knowledgable category theorists on this site for a question I have about category-theoretic aspects of a fundamental logic concept.
My ...
- 236k
59
votes
8
answers
8k
views
Cauchy reals and Dedekind reals satisfy "the same mathematical theorems"
The succinct question
The conjecture of Birch and Swinnerton-Dyer (to take a random example) mentions L-functions and hence the complex numbers and hence the real numbers (because the complexes are ...
- 41.4k
49
votes
1
answer
2k
views
Producing finite objects by forcing!
It is a trivial fact that forcing can not produce finite sets of ground model objects. However there are situations,
where we can use forcing to prove the existence of finite objects with some ...
- 32.2k
47
votes
5
answers
10k
views
Set theory and Model Theory
This question probably doesn't make any sense, but I don't see why, so I ask it here hoping someone will illuminate the matter:
There is this whole area of study in Set Theory about the consistency, ...
- 1,219
46
votes
2
answers
2k
views
Applications of Zorn’s lemma that aren’t chain-complete/directed-complete?
Zorn’s Lemma applies to posets in which every chain has an upper bound. However, in all applications I know, the poset is also evidently chain-complete — chains have least upper bounds. A few ...
- 21.3k
44
votes
2
answers
4k
views
Is multiplication implicitly definable from successor?
A relation $R$ is implicitly definable in a structure $M$ if there is a formula $\varphi(\dot R)$ in the first-order language of $M$ expanded to include relation $R$, such that $M\models\varphi(\dot R)...
- 236k
43
votes
1
answer
2k
views
Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?
By "formal analogies" between the metamathematics of $\mathsf{ZFC}$/set theory and $\mathsf{PA}$(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following:
We are considering a ...
- 32.5k
43
votes
9
answers
5k
views
The sets in mathematical logic
It is well known that intuitive set theory (or naive set theory) is characterized by having paradoxes, e.g. Russell's paradox, Cantor's paradox, etc. To avoid these and any other discovered or ...
- 764
40
votes
3
answers
5k
views
How much of mathematical General Relativity depends on the Axiom of Choice?
One of the cornerstones of the mathematical formulation of General Relativity (GR) is the result (due to Choquet-Bruhat and others) that the initial value problem for the Einstein field equations is ...
- 655
39
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 ...
- 750
39
votes
3
answers
5k
views
For which Millennium Problems does undecidable -> true?
Three good answers were received — by Alex Gavrilov, Bjørn Kjos-Hanssen, and Terry Tao — and the bounty has been awarded (somewhat arbitrarily) to Alex Gavrilov.
The answers ...
39
votes
5
answers
4k
views
A “mother of all groups”? What kind of structures have "mother of all"s?
For ordered fields, we have a “mother of all ordered fields”, the surreal numbers $\mathbf{No}$, a proper-class “field” which includes (an isomorphic copy of) every other ordered field as a subfield. ...
- 1,687
38
votes
1
answer
3k
views
Is the area of the Mandelbrot provably computable?
Recall the Mandelbrot set $M$ is the set of points $c$ in the complex plane such that the sequence $z_0 = 0, z_{n+1} = z_n^2 + c$ is bounded. It is well-known that $M$ is a compact set of positive ...
- 6,287
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 ...
37
votes
4
answers
2k
views
Is the field of constructible numbers known to be decidable?
By the field of constructible numbers I mean the union of all finite towers of real quadratic extensions beginning with $\mathbb{Q}$. By decidable I mean the set of first order truths in this field, ...
- 11.1k
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
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
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
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
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
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
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
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
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
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
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
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