Questions about mathematical logic, including model theory, proof theory, computability theory (a.k.a. recursion theory), and non-standard logics. Consider using one of the following tags: (model-theory), (set-theory), (computability), (proof-theory) if they fit the question.

learn more… | top users | synonyms (1)

9
votes
1answer
116 views
+150

Every non-increasing sequence of polynomial towers stabilizes — Finitary proof

In this question we are concerned only with positive integers $\mathbb N$ and other finitary objects that can be encoded using integers. A term function means a total computable function $\mathbb ...
2
votes
0answers
51 views
+50

Reference request: fixed point and first-order logics

I'm looking for materials on the relationship between first-order and fixed-point logics, specifically on the condition for a formula in a fixed-point logic to have an equivalent first-order formula. ...