**9**

votes

**1**answer

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

**3**

votes

**1**answer

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

**4**

votes

**0**answers

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

**5**

votes

**1**answer

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

**8**

votes

**1**answer

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

**3**

votes

**0**answers

173 views

### Borel equivalence relations in models of determinacy

The following appears as fact 3.1 in the slides from Hjorth's 2010 Tarski Lectures. Assume ${L(\mathbb R)} \models \mathrm{AD}$.
Fact 3.1 For E and F Borel equivalence relations one has
$$E \...

**14**

votes

**1**answer

492 views

### Is there a class of mathematical structures with non-isomorphic natural representations as a standard Borel space?

Background. The field of Borel equivalence relation theory
provides a robust, unifying theory that organizes most of the
classification problems of classical mathematics into a hierarchy,
allowing us ...

**10**

votes

**0**answers

295 views

### A question concerning model theory of groups

Several days ago, Professor Martin Bridson gave a very nice talk in my department. Some questions concerning his talk came into my brain Since I am neither a model theorist nor a algebraist, I am not ...

**2**

votes

**1**answer

155 views

### Non-completeness of the Borel-Lebesgue measure and countable choice

Is it possible to prove the non-completeness of the Borel-Lebesgue measure on $\mathbb{R}$ (restricted to the Borel $\sigma$-algebra) without the full axiom of choice, but still with Countable Choice ?...

**10**

votes

**0**answers

229 views

### A variant of strong ideals, is it consistent?

Is it consistent relative to large cardinals that there is a precipitous ideal on $\omega_1$ forcing a generic elementary embedding $j : V \to M \subseteq V[G]$, such that $j(\omega_1) = \omega_n^V$ ...

**4**

votes

**1**answer

218 views

### Reference request, proof about well-ordering of ordinals

I am looking for a second order proof that ordinals are well-ordered up to $\epsilon_0$.
So, starting with encoding those ordinals in numbers, defining the < relation on those encoded ordinals and ...

**3**

votes

**0**answers

333 views

### A question about the Chaitin constant of a theory

Chaitin's famous incompleteness theorem states that for every r.e. theory $T\supseteq Q$ in the language of arithmetic, there is a constant $d_T$ such that for any $m\geq d_T$ and any $x$, $T$ can ...

**12**

votes

**1**answer

408 views

### Changing cofinalities above supercompact cardinals

Question. Suppose $\kappa$ is a supercompact cardinal and $\lambda > \kappa$
is measurable (or even larger large cardinal if necessary).
Is there a set generic extension of the universe in ...

**1**

vote

**1**answer

154 views

### A question on the provability predicate of Q

I am not familiar with Robinson's construction as I do not have access to his text or to precise accounts of this, but I have come to understand that the proof predicate of Robinson arithmetic is non-...

**4**

votes

**2**answers

179 views

### Which Heyting algbras arise out of some elementary topos which satisfies the ultrafilter principle?

It is known that AC implies LEM constructively, and also that AC implies the ultrafilter principle. Is there a similar relationship between the ultrafilter principle and classical logic? In other ...

**11**

votes

**1**answer

339 views

### Singular in $V$ regular in $HOD$

Prikry forcing can be used to produce a model $V$ of $ZFC$ such that fo rsome cardinal $\kappa$ we have:
(1) $\kappa$ is singular in $V$ of cofinality $\omega,$
(2) $\kappa$ is regular (and in fact ...

**1**

vote

**0**answers

167 views

### “Kolmogorov complexity” of models of computation

This question was partly inspired by my learning about John Tromp's binary lambda calculus and similar minimal languages such as Jot. A more detailed discussion of some of these ideas is in Michael ...

**2**

votes

**0**answers

340 views

### A question on the consistency of a (seemingly) very weak set theory

I have preoccupied myself some with very weak set theories that suffice to interpret Robinson Arithmetic, as in this question Is Extensionality needed for the incompleteness of very weak set theories?....

**6**

votes

**1**answer

442 views

### Are there 'finitistic' nonrecursive functions (assuming Church's Thesis is false)?

[Note: In what follows, I will be using the same type of argument Laszlo Kalmar did in his paper "An Argument Against the Plausibility of Church's Thesis" found in Constructivity in Mathematics, (...

**9**

votes

**2**answers

277 views

### Bounded Arithmetic vs Complexity Theory

In this post, when I talk about bounded arithmetic theories,
I mean the theories of arithmetic according to "Logical Foundations of Proof Complexity", which capture the complexity classes between $AC^...

**5**

votes

**1**answer

236 views

### Is the set of subsequences of branches through a tree Borel?

Let $T$ be pruned subtree of $\omega^{<\omega}$. For my cases of interest, we may assume that $T$ is infinitely branching at every node, and consists of increasing sequences.
Let $A=\{x\in\omega^{\...

**6**

votes

**1**answer

479 views

### Godel's proof of Completeness

Where could I find a detailed exposition in English of Godel's proof (not Henkin's) of Completeness Theorem for first order logic? The wikipedia article omits certain details that I am not clear about,...

**2**

votes

**1**answer

519 views

### Can Turing machines clarify mathematical, philosophical, and physical existence?

From Harvey Friedman's manuscript on "Order Invariant Relations and Incompleteness":
DEFINITION 4.4. A $\Pi_1^0$ sentence is a sentence asserting that some given Turing machine never halts at the ...

**10**

votes

**1**answer

334 views

### Uniform elimination of imaginaries

Does the following principle follow from uniform elimination of imaginaries?
For every formula $\varphi(x;y)$ there is a formula $\vartheta(x;z)$ such that
$$\forall y\;\exists^{=1}z\;\forall x\;\...

**3**

votes

**1**answer

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

**2**

votes

**6**answers

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

**7**

votes

**1**answer

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

**1**

vote

**1**answer

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

**3**

votes

**2**answers

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

**5**

votes

**1**answer

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

**8**

votes

**0**answers

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

**6**

votes

**1**answer

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

**3**

votes

**0**answers

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

**7**

votes

**3**answers

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

**6**

votes

**1**answer

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

**0**

votes

**0**answers

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

**3**

votes

**1**answer

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

**4**

votes

**0**answers

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

**12**

votes

**2**answers

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

**10**

votes

**1**answer

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

**0**

votes

**1**answer

198 views

### Does every ultrafilter contain sets of sup-measure $0$?

Let $\mathbb{N}$ be the set of positive integers and for $A\subseteq {\mathbb{N}}$ set $$m(A) = \text{lim sup}_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n}.$$
Does every ultrafilter ${\cal U}$ on $\...

**6**

votes

**4**answers

534 views

### Direct axiomatization of ordinal and cardinal numbers

Again, this question is related (**) to a previous one:
in standard books on basic set theory, after stating the axioms of ZFC, ordinal numbers are introduced early on. Afterwards cardinals appear: ...

**2**

votes

**1**answer

129 views

### Can tests for the convergence and divergence of series be used to create undecidable sentences?

Let f(k) be a recursive function which maps the set of positive integers into itself. Let T be a formalized theory which is axiomatizable and contains Peano's Arithmetic as a sub-theory. For example, ...

**2**

votes

**1**answer

170 views

### Some very weak statements on choice

This is a follow-up question to Does $|(X\times\{0\}) \cup (X\times\{1\})| \leq |X|$ for $X$ infinite imply ${\sf AC}$?
Consider the statements
$(\text{S}1)$ For any infinite set $X$ there ...

**2**

votes

**1**answer

163 views

### Does $|(X\times\{0\}) \cup (X\times\{1\})| \leq |X|$ for $X$ infinite imply ${\sf AC}$?

Consider the statement
For any infinite set $X$ there is an injection $\varphi$ from $(X\times\{0\}) \cup (X\times\{1\})$ into $X$.
Does this imply the ${\sf AC}$?

**4**

votes

**0**answers

95 views

### Ref request: modelling regular theories as an injectivity condition

The background to the following observation is standard material in categorical logic, and I thought this was was too — I don’t remember learning it, but I don’t think it is original — but I can’t now ...

**2**

votes

**1**answer

286 views

### A derivation in Tait calculus

I have seen in at least two different places (here, p. 183; and here, last slide) the Tait calculus defined the following way.
Here $\Gamma$ denotes a set of formulas $\{A_1, \ldots, A_k\}$, which is ...

**1**

vote

**0**answers

174 views

### Reference request: Models of isomorphic languages result into isomorphic categories

This is basically a reference request by someone who has not been educated as a logician and would like to be rigorous about certain preliminary aspects of model theory.
Fix an uncountable universe $\...

**7**

votes

**1**answer

448 views

### Taller models of ZFC

This question is somewhat related to a previous one, where I asked for new forms of infinite beyond the cardinal hierarchy.
Using forcing techniques, at least the ones I know of, one starts from a ...

**7**

votes

**2**answers

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