# Tagged Questions

**4**

votes

**0**answers

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

**1**answer

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

**2**answers

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

**4**answers

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

**12**answers

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

**3**answers

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

**7**answers

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

**15**answers

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

**42**answers

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

**26**answers

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

**2**answers

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 ...