# Tagged Questions

first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, ...

322 views

### Coherence and rewriting

In category theory there are numerous coherence theorems (https://ncatlab.org/nlab/show/coherence+theorem). One example is the Mac Lane's coherence theorem for monoidal categories. This and probably ...
103 views

### How to get $\omega$-regular expression from buchi automaton

Is there an algorithm or a trick on how to get $\omega$-regular expressions from Buchi automatons? If yes, is there also some way to do create minimal such regular expressions? It is extremely ...
221 views

### Is the two variable fragment of arithmetic, i.e., theory of ($\mathbb{N}, + ,\times$), decidable?

Any references would be appreciated. Most places only address different vocabularies (e.g. a survey of arithmetical definability by Bes).
224 views

### A button for individual reals

Hamkins introduced the notion of a "button" in forcing. This is a set-theoretic statement that can be forced, and can never be made false by further forcing. An example is $V \not= L$. Another ...
268 views

### Is there a modern account of Veblen functions of *several* variables?

Veblen $\phi$ functions extend the $\xi \mapsto \phi(\xi) := \omega^\xi$ and the $\xi \mapsto \phi(1,\xi) := \varepsilon_\xi$ functions on the ordinals by repeatedly taking fixed points (I won't ...
173 views

166 views

### Theories of arithmetic from recursively inseparable sets

Edit: all sets / theories considered below are supposed to be recursively enumerable, although I'd also be interested in any possible generalizations to non-enumerable theories. In the comments on ...
2k views

### Looking for a source for Intended Interpretation

Hao Wang writes: "The originally intended, or standard, interpretation takes the ordinary nonnegative integers $\{0, 1, 2, \ldots \}$ as the domain, the symbols $0$ and $1$ as denoting zero and one, ...
305 views

### Relationship between first and second incompleteness theorems

By my understanding, Gödel's first incompleteness theorem says that any theory with sufficient1 interpretability strength is essentially incomplete, that is, any consistent recursively enumerable ...
178 views

### In what sense is the “descending chain principle” for ordinals less than $\epsilon_0$ 'infinitary?

In the introduction to his paper "Assignment of Ordinals to Terms for Primitive Recursive Functionals of Finite Type", W.A. Howard writes: Gentzen...showed that the consistency of first order (...
348 views

### Determinacy of (infinite, possibly loopy) combinatorial games

I am looking for references and hopefully enlightening proofs of the following statement(s) concerning the determinacy of not-necessarily-well-founded (i.e., possibly infinite, possibly loopy) ...
169 views

### Deciding isomorphism between structures which interpret in the pure set

I am interested in the following decision problem: Given descriptions of two relational structures $A,B$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $A$ and $B$...
191 views

### ω-categorical, ω-stable structure with trivial geometry not definable in the pure set

Briefly, my question is the following. does every countable ω-categorical, ω-stable structure with disintegrated strongly minimal sets interpret in the countable pure set? By countable pure set I ...
280 views

### $\omega$-colorings of $\kappa^2$

Let $\kappa\le 2^{\aleph_0}$ be an infinite cardinal. We have a collection of functions $\{f_i|i<\kappa\}$ such that $f_i:i\rightarrow \omega$ and the collection is "triangle-free", i.e. there are ...
451 views

### What's Reeb's take on naive integers?

Georges Reeb's "claim Q" is the statement that "naive integers don't fill up $\mathbb{N}$". To anyone familiar with model theory this could easily be interpreted as the existence of nonstandard models ...
498 views

### Is there research on Machine Learning techniques to discover conjectures (theorems) in a wide range of mathematics beyond mathematical logic?

Although there already exists active research area, so-called, automated theorem proving, mostly work on logic and elementary geometry. Rather than only logic and elementary geometry, are there ...
170 views

### Heyting algebras originating from directed graphs

The category RefGph of reflexive directed graphs is the functor category $\hat{∆}_1=\mbox{Fun}(∆^◦_1,$Set), where $∆_1$ is the simplex category truncated at level 1. Hence the poset Sub(X) of ...
35 views

### How to convert an expression to conjunctive normal form for Maximum-2-satisfiability?

I have a simplified Boolean expression almost ripe for maximum-2-satisfiability: $(A\lor \neg B)\land(A\land C)\land(D\lor \neg A)$ In other words, I want to find the assignment of variables so that ...
264 views

### Simplest PA theorem whose proof requires encoding of sequences even though the statement itself doesn't

What is the simplest number-theoretic theorem whose proof requires exponentiation or finite sequences/sets (so any proof in Peano Arithmetic would need to use encodings of such things using e.g. Gödel'...
307 views

### About the “semi-classical” view of Prof. Weaver and Prof. Feferman [closed]

In the thread "Is platonism regarding arithmetic consistent with the multiverse view in set theory?", Prof. Hamkins writes: The view you are suggesting is something close to what is held by ...
607 views

### Is there a consistent arithmetically definable extension of PA that proves its own consistency?

I asked this on stackexchange with no answer. The negation would be the obvious generalization of Gödel's second incompleteness from r.e. extensions of PA to any arithmetically definable extension of ...
408 views

### “Set theory” founded on lists rather than sets

On a computer, sets are often represented rather "indirectly / implicitly", e.g. in terms of some properties that they or their members satisfy. But some sets can be represented more "directly / ...
198 views

### How can any theory prove well-foundedness of ordinals above $\omega_1^{\text{CK}}$?
$\newcommand{\omegaoneck}{\omega_1^{\text{CK}}}$ Pardon the extremely basic question - this isn't quite my area - but I'm confused about the definition of proof theoretic ordinals. The proof ...