1
vote
1answer
315 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 ...
6
votes
4answers
1k 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 ...
30
votes
10answers
3k 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 ...
13
votes
12answers
2k 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
vote
2answers
969 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 ...
9
votes
2answers
1k 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 ...
43
votes
26answers
6k views

Sexy vacuity …

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 ...
16
votes
7answers
4k 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 ...
18
votes
9answers
4k 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 ...
13
votes
6answers
966 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?
66
votes
41answers
15k 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 ...
40
votes
18answers
4k 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 using model ...
111
votes
26answers
12k 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 that every ...