# Tagged Questions

**9**

votes

**4**answers

1k views

### Are there non-diagonal proofs for Cantor's continuum and Godel's incompletness theorems?

There is a formal definition for the notion of a formal proof.
Question 1. Is there any formal definition for the notion of a diagonal formal proof?
Consider the following theorems both proved by ...

**8**

votes

**0**answers

302 views

### “Hard” separation results in reverse mathematics (or similar)

This is a fairly broad question. In particular, I specify 5 questions (Q1, Q2.1, Q2.2, Q3, Q4) which for me all fall under one umbrella. Since this is unreasonably broad, I'm really interested in an ...

**1**

vote

**0**answers

156 views

### Has the Ramified Theory of Types been applied to Predicative Set Theories?

Questions of predicativity are well-studied in the context of arithmetic. We have a base theory, first-order Peano arithmetic. Some people, like Edward Nelson (in chapter 1 of his book) and Charles ...

**0**

votes

**1**answer

656 views

### Is there any danger far from home? (Edited & Revised Version) [closed]

The notion of formal proof is defined by finite sequences ($<\omega$ - sequences) of sentences. In some sense if a sentence $\sigma$ is (finitely) provable from the theory $T$ it is very "near" to ...

**5**

votes

**1**answer

219 views

### the choice of representing formulas and Gödel's second incompleteness theorem

In Rautenberg's book (A Concise Introduction to Mathematical Logic, Universitext, Springer 2006), GĂ¶del's second incompleteness theorem is stated:
Theorem 3.2 (Second incompleteness theorem). PA ...

**10**

votes

**1**answer

380 views

### Proof-Theoretic Ordinal of ZFC or Consistent ZFC Extensions?

Let the proof theoretic ordinal $\alpha$ of a theory $T$ be the least recursive ordinal such that $T$ does not prove that $\alpha$ is well-founded. This ordinal is intended to quantify in some sense ...

**8**

votes

**2**answers

823 views

### When does $ZFC \vdash\ ' ZFC \vdash \varphi\ '$ imply $ZFC \vdash \varphi$?

Being a new member, I am not yet sure whether my question will be taken as a research level question (and thus, appropriate for MO). However, I have seen similar questions on MO, couple of which led ...

**4**

votes

**1**answer

173 views

### Notation for upperbound power sets.

There is a standard notation $\mathrm{ZF}[n]$ for Zermelo Fraenkel set theory with the power set axiom restricted to saying the set of natural numbers has $n$ successive power sets ...

**11**

votes

**0**answers

263 views

### How to measure the strength of Zermelo over bounded Zermelo?

Bounded Zermelo is Zermelo set theory with only bounded separation. It has the same strength as simple type theory or MacLane set theory or ETCS. It is a finitely axiomatized fragment of Zermelo, so ...

**8**

votes

**4**answers

814 views

### How many well orderings of $\aleph_0$ are there?

What is known about the set of well orderings of $\aleph_0$ in set theory without choice? I do not mean the set of countable well-order types, but the set of all subsets of $\aleph_0$ which (relative ...

**7**

votes

**0**answers

310 views

### Can second order arithmetic make $\aleph_1^L$ countable?

Simpson's book Subsystems of Second Order Arithmetic shows $Z_2$ can interpret some fragments of ZF strong enough to give good theories of constructible sets and formalize statements like "there is a ...

**23**

votes

**15**answers

4k views

### What's a magical theorem in logic?

Some theorems are magical: their hypotheses are easy to meet, and when invoked (as lemmas) in the midst of an otherwise routine proof, they deliver the desired conclusion more or less ...

**9**

votes

**2**answers

741 views

### Asymptotic density of provable statements in ZFC

This question is in response to one of the questions asked here. The OP wanted to know if the percentage of statements provable from ZFC tended to some value, and if so, what it was. In particular, ...

**4**

votes

**2**answers

354 views

### What is the depth of the “provability heirarchy”?

I am not a logician or set theorist, so hopefully this makes sense. Let $T$ be a theory which is expressive enough to make statements like "Statement $A$ has a proof in $T$"; for example, $T$ might ...

**4**

votes

**1**answer

842 views

### Can one really construct an “ordinal table”?

Many books describe how one can construct "by hand" a table of ordinals $1,\ 2,\ \ldots,\ \omega,\ \omega +1,\ \omega +2,\ \ldots,\ \omega\cdot 2,\ \omega\cdot 2 +1,\ \ldots,\ \omega^{2},\ \ldots,\ ...