**5**

votes

**1**answer

228 views

### Iteration of random reals

Consider two random reals $x, y$ over a transitive model $V$ of ZFC. More specifically, if $\mathcal C^V={}^\omega2$ is the Cantor space, composing the canonical homeomorphism with the projections ...

**3**

votes

**1**answer

89 views

### Levels of L resembling each other, take 2

(Everything below is assuming $V=L$.)
Fix an uncountable regular cardinal $\kappa$, and let $$E_\kappa=\{\mu<\kappa: \mbox{there is an elementary substructure of $L_\kappa$ isomorphic to ...

**3**

votes

**1**answer

89 views

### Generic sections of non-null sets are non-null

Consider the Cantor space $\mathcal C={}^\omega2$ with the usual product measure, and let $r$ be a random real (over a transitive model $V$ of ZFC). Let $B\subset \mathcal C^V\times\mathcal C^V$ a ...

**6**

votes

**1**answer

204 views

### Fine structure question: when do levels of $L$ look “a lot” like each other?

(Everything is assuming $V=L$.)
Fix an uncountable regular cardinal $\kappa$, and let $$E_\kappa=\{\mu<\kappa: \mbox{there is an elementary substructure of $L_\kappa$ isomorphic to $L_\mu$}\},$$ ...

**6**

votes

**0**answers

234 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

89 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

211 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

220 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

190 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

164 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

474 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

280 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

150 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

227 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

213 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

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

**11**

votes

**1**answer

396 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

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

**4**

votes

**2**answers

176 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

331 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

161 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

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

**6**

votes

**1**answer

430 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

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

**5**

votes

**1**answer

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

**6**

votes

**1**answer

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

**2**

votes

**1**answer

500 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

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

**3**

votes

**1**answer

148 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

302 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

171 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

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

**8**

votes

**0**answers

190 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

277 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

439 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

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

**5**

votes

**1**answer

168 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

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

**4**

votes

**0**answers

301 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

584 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

404 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

520 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

164 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

161 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

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