4
votes
0answers
140 views

Examples of unproven but likely true existential sentence (in the sense of incompleteness)

Some examples of universal statements that are unproven but likely true include the Riemann hypothesis (all non-trivial zeros of the zeta function have real part 1/2) and the Goldbach conjecture (all ...
12
votes
1answer
194 views

Nontrivial upper bounds on proof-theoretic ordinals of strong theories: do we have any?

Motivated by Consistency of Analysis (second order arithmetic) and Proof-Theoretic Ordinal of ZFC or Consistent ZFC Extensions?, I have the following question: Are there any examples of strong ...
7
votes
2answers
196 views

Natural $\Pi^1_2$ (or worse) classes of structures?

(To clarify, my interest is mainly lightface, that is, $\Pi^1_2$ instead of $\bf \Pi^1_2$, although it doesn't particularly matter.) This is just an idle curiosity. In logic, I find myself frequently ...
8
votes
4answers
408 views

Order-independent properties arising naturally in mathematics

The motivation for the following question comes from finite model theory, but it is not a technical question about this field, and it is particularly directed at people working in other fields. It ...
14
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 ...
19
votes
3answers
2k views

Clearing misconceptions: Defining “is a model of ZFC” in ZFC

There is often a lot of confusion surrounding the differences between relativizing individual formulas to models and the expression of "is a model of" through coding the satisfaction relation with ...
9
votes
7answers
3k views

Can we have A={A} ?

Does there exist a set $A$ such that $A=\{A\}$ ? Edit(Peter LL): Such sets are called Quine atoms. Naive set theory By Paul Richard Halmos On page three, the same question is asked. Using the ...
33
votes
15answers
6k views

Strong induction without a base case

Strong induction proves a sequence of statements $P(0)$, $P(1)$, $\ldots$ by proving the implication "If $P(m)$ is true for all nonnegative integers $m$ less than $n$, then $P(n)$ is true." for ...
77
votes
42answers
16k 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 ...
117
votes
26answers
14k 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 ...
6
votes
2answers
773 views

Complete theory with exactly n countable models?

For n an integer greater than 2, Can one always get a complete theory over a finite language with exactly n models (up to isomorphism)? There's a theorem that says that 2 is impossible. My ...