**12**

votes

**1**answer

559 views

### Complementation of $\omega$-regular languages in reverse mathematics

Does anyone know where Büchi's theorem that $\omega$-regular languages are closed under complementation fits into the reverse-mathematics classification scheme? That is, is it equivalent over ...

**12**

votes

**5**answers

1k views

### Consistency strength needed for applied mathematics

Given that we can never proof the consistency of a theory for the foundations of mathematics in a weaker system, one could seriously doubt whether any of the commonly used foundational frameworks (ZFC ...

**4**

votes

**1**answer

649 views

### Soundness Theorem in reverse mathematics

STPL := soundness theorem for predicate logic
(see this)
When trying to figure out the strength of the STPL in reverse mathematics, I managed to convince myself of the following:
a) ACA0 has a ...

**9**

votes

**4**answers

1k views

### Is finitism an extreme form of constructivism?

I hope this question is not too soft for MO.
The Wikipedia says about finitism that it is an extreme form of constructivism. See http://en.wikipedia.org/wiki/Finitism. I doubt that this is correct.
...

**6**

votes

**1**answer

283 views

### Strength of Transfinite Induction on the Difference Hierarchy

I'm wondering if a particular theory of second order arithmetic has been studied or is known to be equivalent to some other theory.
Consider the formulas generated by $\Pi^1_1$ and $\Sigma^1_1$ ...

**11**

votes

**0**answers

1k views

### Reverse mathematics strength of identically zero polynomials are the zero polynomial

According to wikipedia, the statement "every polynomial over a countable field that is not the zero polynomial has only finitely many roots" is equivalent to RCA0 over RCA0* (which is called ERCA-0 in ...

**2**

votes

**1**answer

219 views

### Proving boundedness of continuous images of [0,1] in WKL0

I've been reading about reverse mathematics (mostly on wikipedia), and I had been thinking that I understood how to prove the equivalences to WKL0 and ACA0 mentioned in the its article. However, I ...

**1**

vote

**4**answers

875 views

### Can transfinite induction be defined as axiom scheme in FOL on bin-tree structures?

Transfinite induction requires a second order induction hypothesis. So, that can not be defined as axiom scheme in FOL.
However, if I look to Goodstein's theorem en the Hydra games, then they have to ...

**6**

votes

**2**answers

565 views

### Weakest subsystems of second order arithmetic for mathematical logic

It is known that to prove completeness of first-order logic for countable languages WKL0 is enough. But, is it the weakest subsystem where one can prove it?
What about the incompleteness theorems? Is ...

**1**

vote

**2**answers

841 views

### Can Goodstein's theorem been proven with first order PA + Constructive Omega Rule?

I am trying to understand transfinite induction and Gentzen's theories.
But I was wondering, if there is any connection with the Constructive Omega Rule (COR).
With COR I mean that if you can proof:
...

**7**

votes

**3**answers

1k views

### What is the reverse mathematics of first-order logic and propositional logic?

Suppose one tries to formalize first-order logic. How much "strength" is required to do this?
Strength can mean in various senses:
The fragment of ZFC needed to codify first-order logic.
Which ...

**10**

votes

**3**answers

741 views

### Reducing ACA₀ proof to First Order PA

According to the Wikipedia ACA0 is a conservative extension of First Order logic + PA.
http://en.wikipedia.org/wiki/Reverse_Mathematics
First of all I have a few questions about the proof:
a - What ...

**20**

votes

**2**answers

1k views

### Reverse mathematics of (co)homology?

Background
Exercise 2.1.16b in Hartshorne (homework!) asks you to prove that if $0 \rightarrow F \rightarrow G \rightarrow H \rightarrow 0$ is an exact sequence of sheaves, and F is flasque, then $0 ...