All Questions
47 questions
-1
votes
0
answers
94
views
Relation between properties of functions/sets and Grzegorczyk's hierarchy
I know for example that the first level of the Grzegorczyk hierarchy contains the functions which enumerate the c.e sets and that it has an interesting relation to the provably total functions in ...
- 893
298
votes
34
answers
53k
views
What are some reasonable-sounding statements that are independent of ZFC?
Every now and then, somebody will tell me about a question. When I start thinking about it, they say, "actually, it's undecidable in ZFC."
For example, suppose $A$ is an abelian group such ...
- 328
107
votes
36
answers
21k
views
Interesting examples of vacuous / void entities
I included this footnote in a paper in which I mentioned that the number of partitions of the empty set is 1 (every member of any partition is a non-empty set, and of course every member of the empty ...
- 12.9k
73
votes
9
answers
29k
views
What are some important but still unsolved problems in mathematical logic?
In the past, first-order logic and its completeness and whether arithmetic is complete was a major unsolved issues in logic . All of these problems were solved by Godel. Later on, independence of ...
- 47.3k
7
votes
0
answers
166
views
Examples of finitary problems/theorems of high logical complexity? [duplicate]
Generally, number theoretic conjectures which are well-known and easy to explain are either obviously $\Pi^0_1$ or $\Pi^0_2$, which is to say, their truth can be decided by a single membership query ...
- 1,452
9
votes
2
answers
473
views
Completing half of Hilbert's program: Foundations that are conservative over Peano Arithmetic
The goal of the Hilbert program was to find a complete and consistent formalization of mathematics. Gödel's first incompleteness theorem establishes that completeness is impossible with first-order ...
- 6,353
64
votes
15
answers
7k
views
Unnecessary uses of the axiom of choice
What examples are there of habitual but unnecessary uses of the axiom of
choice, in any area of mathematics except topology?
I'm interested in standard proofs that use the axiom of choice, but where
...
- 328
20
votes
5
answers
1k
views
Uniqueness results that follow from CH
Recently, Joel David Hamkins presented a historical thought experiment that shows that CH could have been adopted as an axiom if we had been using the hyperreal field $\mathbb{R}^*$ instead of $\...
CommunityBot
- 1
10
votes
0
answers
274
views
Open problems in complete theories
It is well-known that every complete recursively enumerable first-order theory is decidable. Does that mean that such theories are "trivial", or are there still interesting open problems ...
- 6,353
19
votes
6
answers
2k
views
Book recommendation introduction to model theory
Next semester I will be teaching model theory to master students. The course is designed to be "soft", with no ambition of getting to the very hardcore stuff. Currently, this is the syllabus....
- 5,031
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
20
votes
6
answers
3k
views
What are some nice uses of ultraproducts/ultrapowers?
Motivated by a recent post (Non-definability of graph 3-colorability in first-order logic), I was wondering: what are some nice arguments based on ultraproducts? I don't mind definability results, but ...
- 236k
150
votes
45
answers
30k
views
Nontrivial theorems with trivial proofs
A while back I saw posted on someone's office door a statement attributed to some famous person, saying that it is an instance of the callousness of youth to think that a theorem is trivial because ...
96
votes
16
answers
34k
views
Most 'unintuitive' application of the Axiom of Choice?
It is well-known that the axiom of choice is equivalent to many other assumptions, such as the well-ordering principle, Tychonoff's theorem, and the fact that every vector space has a basis. Even ...
- 4,713
18
votes
2
answers
1k
views
What notable theorems cannot be automatically proven without choice using Shoenfield absoluteness?
There have been a couple of recent questions, here and here, regarding the role of the axiom of choice in real-analytic results with applicability to general relativity. This lead me to look at some ...
- 4,316
51
votes
30
answers
8k
views
Taking a theorem as a definition and proving the original definition as a theorem
Gian-Carlo Rota's famous 1991 essay, "The pernicious influence of mathematics upon philosophy" contains the following passage:
Perform the following thought experiment. Suppose that you are ...
- 1,422
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 ...
- 2,031
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 ...
- 1
135
votes
43
answers
38k
views
What are the most attractive Turing undecidable problems in mathematics?
What are the most attractive Turing undecidable problems in mathematics?
There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on ...
- 349
23
votes
2
answers
1k
views
Statements in differential geometry independent from ZFC
It is well known that some problems in functional analysis and in general topology are independent from ZFC: to name a few, Kaplansky's conjecture, the existence of outer automorphisms of the Calkin ...
- 1,263
18
votes
5
answers
2k
views
What are some interesting applications/corollaries of Kleene's Recursion theorem?
Lately I became very interested in the theory of computability and a fundamental early result you learn is the Recursion Theorem also known as the Fixed point theorem. At first sight you can see it's ...
- 236k
143
votes
12
answers
30k
views
Solutions to the Continuum Hypothesis
Related MO questions: What is the general opinion on the Generalized Continuum Hypothesis? ; Completion of ZFC ; Complete resolutions of GCH How far wrong could the Continuum Hypothesis be? When was ...
- 82.7k
60
votes
15
answers
11k
views
Abstract thought vs calculation
Jeremy Avigad and Erich Reck claim that one factor leading to abstract mathematics in the late 19th century (as opposed to concrete mathematics or hard analysis) was the use of more abstract notions ...
- 4,713
69
votes
19
answers
9k
views
What are some results in mathematics that have snappy proofs using model theory?
I am preparing to teach a short course on "applied model theory" at UGA this summer. To draw people in, I am looking to create a BIG LIST of results in mathematics that have nice proofs ...
- 12.9k
16
votes
2
answers
1k
views
Major applications of the internal language of toposes
What are the major applications of the internal language of toposes?
Here are a few applications I know:
Mulvey's proof of the Serre–Swan theorem in which he interprets the intuitionistically valid ...
- 8,481
12
votes
3
answers
2k
views
What are some other uses for Ehrenfeucht-Fraïssé games?
Let $\mathfrak{A} = \langle A, \dots \rangle$ and $\mathfrak{B} = \langle B, \dots \rangle$ be structures for a signature $\mathscr{L}$. For each ordinal $\gamma$ we define a game of perfect ...
- 11
6
votes
5
answers
684
views
Stronger theorem not resulting from proof analysis
Suppose that we proved $\varphi$ from a theory $T$. Often we ask whether or not we could have proved $\varphi$ with a weaker theory, to find out we usually analyze the proof and try to figure out ...
- 20.5k
9
votes
5
answers
830
views
Positive results coming from paradoxes
Many examples comes to mind, the most famous being the Gödel's theorems viewed as formalisations of the Liar's paradox. I just realised that the proof of non-calculability of Kolmogorov complexity is ...
- 19.6k
8
votes
8
answers
5k
views
probability and math puzzle books/references [closed]
Hi All,
I'd like to solve some math puzzles, especially in the context of probability theory, but I'm open to other areas too. The kind of problems that does not require much knowledge of mathematics, ...
- 39.9k
20
votes
8
answers
5k
views
Decent texts on categorical logic
Recently I read the chapter "Doctrines in Categorical Logic" by Kock, and Reyes in the Handbook of Mathematical Logic. And I was quite impressed with the entire chapter. However it is very short, and ...
- 63.9k
10
votes
5
answers
5k
views
Examples of inductive proofs that can be generalized by transfinite induction
Hello. I am currently searching for some nice examples of proofs by induction in the finite case, that can be generalized to the infinite case using transfinite induction (and dont become trivial ...
CommunityBot
- 1
12
votes
6
answers
750
views
Conditions equivalent to finiteness
We've all probably come across some conditions that naturally imply finiteness, or are equivalent to it. For ZFC examples:
A set $X$ can be ordered in such a way that the ordering is well-founded and ...
- 63.9k
6
votes
1
answer
532
views
The connections between Kolmogorov complexity and mathematical logic
We know that Kolmogorov Cmplexity (KC) has connections to mathematical logic since it can be used to prove the Gödel incompleteness results (Chaitin's Theorem and Kritchman-Raz). Are there any other ...
- 188k
13
votes
2
answers
1k
views
Contrasting theorems in classical logic and constructivism
Is it possible there are examples of where classical logic proves a theorem that provably is false within constructivism? Is so what are some examples?
What are some examples of most contrasting ...
- 1,616
15
votes
7
answers
1k
views
Examples of proofs by making reduction to a finite set [closed]
This is a very abstract question, I hope this is appropriate.
Suppose $T$ is some claim over some infinite set $A$, for example, let $A$ be the set of all loopless planar graphs, and $T$ be the claim "...
- 4,786
19
votes
14
answers
4k
views
Excellent uses of induction and recursion
Can you make an example of a great proof by induction or construction by recursion?
Given that you already have your own idea of what "great" means, here it can also be taken to mean that the chosen ...
- 1
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 (...
- 3,249
45
votes
8
answers
10k
views
What is Realistic Mathematics?
This post is partially about opinions and partially about more precise mathematical questions. Most of this post is not as formal as a precise mathematical question. However, I hope that most readers ...
- 505
17
votes
7
answers
2k
views
Non-constructive proofs of decidability?
Are there examples of sets of natural numbers that are proven to be decidable but by non-constructive proofs only?
- 53
20
votes
12
answers
10k
views
The best text to study both incompleteness theorems
Hi!
What text on both incompleteness theorems you would recommend for beginner?
Specifically, I'm looking for the text with the following properties:
1) The proofs should be finitistic, in Godel's ...
- 39.9k
18
votes
15
answers
14k
views
undergraduate logic textbook
I am going to teach the standard undergraduate Logic course for math and engineering majors. What are good (bad) text-books and why. I have not taught that course for a while and wonder if there are ...
2
votes
1
answer
267
views
Maximality statements that cannot be proved using $\mathsf{ZL}$ [closed]
What are examples for maximality statements that cannot be proved using Zorn's Lemma?
- 48.9k
4
votes
1
answer
1k
views
Transfinite induction vs induction in mathematics
What are the nontrivial theorems one can prove about natural numbers which need transfinite induction? By "need transfinite induction" I mean one can show that the statement is not provable in ...
CommunityBot
- 1
7
votes
4
answers
2k
views
Interactions of number theoretic conjectures and other fields of mathematics
There are many interesting open conjectures in number theory. My question is not about partial results or possible ways to prove them. It is about their interactions with the other fields of ...
- 11.2k
1
vote
2
answers
1k
views
An undergraduate's guide to the foundational theorems of logic [closed]
How would you explain one of these theorems in the foundations of mathematics to a fellow colleague outside the field of logic (or rather to an undergraduate mathematics student) handwaving over the ...
- 1,545
39
votes
10
answers
4k
views
Believing the Conjectures
In Believing the axioms (I and II), Penelope Maddy proposes five "rules of thumb" that she then uses to justify large cardinal axioms in set theory. These extrinsic rules are modeled after the ...
CommunityBot
- 1
26
votes
9
answers
8k
views
Why are proofs so valuable, although we do not know that our axiom system is consistent? [closed]
As a person who has been spending significant time to learn mathematics, I have to admit that I sometimes find the fact uncovered by Godel very upsetting: we never can know that our axiom system is ...
- 1