**11**

votes

**1**answer

292 views

### Intutionistic Robinson Arithmetic

By Friedman translation $HA$ and $PA$ prove the same $\Pi_2$ formulas.
Is it true for Intutionistic Robinson arithmetic(Robinson axioms with intutionistic logic) and classic Robinson arithmetic?
...

**2**

votes

**1**answer

1k views

### What is the modern consensus on the difficulty of infinitesimals?

At a related thread at MSE an expert in reverse mathematics noted that "As the modern consensus is that only nonstandard models have infinitesimals, it will be quite challenging to give a concrete ...

**12**

votes

**1**answer

803 views

### Reverse-engineer forcing: am I reinventing the wheel?

In the course of a project I’m working on, I’ve started playing around with a sort of “reverse-engineering” forcing. It seems interesting, but
I have a sinking feeling I’m reinventing the wheel; does ...

**7**

votes

**0**answers

165 views

### Can you define a probability measure on the set of countable transitive models of ZFC?

It is well known that the set of hereditarily countable sets $H(\omega_1)$ —or, if you prefer, $H_{\omega_1}$— has cardinality $2^{\aleph_0}$, and I understand that every countable ...

**12**

votes

**0**answers

267 views

### Is the universality of the surreal number line a weak global choice principle?

I'd like to consider the principle asserting that the surreal
number line is universal for all class linear orders, or in other
words, that every linear order (including proper-class-sized)
linear ...

**3**

votes

**1**answer

192 views

### A question regarding the consistency of Nelson's Predicative Arithmetic

Following Dan Willard (from his paper "Self-Verifying Axiom Systems, the Incompleteness Theorem, and Related Reflection Systems", found on his homepage, pdf here):
"Define an axiom system $\alpha$ ...

**6**

votes

**1**answer

254 views

### Finding limit-nondecreasing sets for certain functions

This is a question that arose a while ago in work with Damir Dzhafarov on some pieces of reverse mathematics. As far as I know, it has no deep significance; however, it feels like the sort of thing we ...

**5**

votes

**2**answers

150 views

### first order languages over graphs (and other discrete models)

A lot of research has been devoted to the study of first order language of graphs (FO). Formulas in this language are constructed using variables $x, y,\dots$ ranging over the vertices of a graph, the ...

**8**

votes

**0**answers

132 views

### Are there always large discrete families of normal measures?

Let $\kappa$ be a measurable cardinal. We give the Stone space of all ultrafilters on $\kappa$ the usual topology, where each $x\subseteq\kappa$ determines a basic open $[x]=\{U;x\in U\}$. The ...

**-2**

votes

**1**answer

248 views

### A set theory and a model without the empty set [closed]

Im just asking out of curiosity.
Is there a set theory $\mathcal T$ and a model $\langle M,E\rangle \vDash \mathcal T$ such that no set in M is empty:
$$\left(\forall m\in M \right)\left(\exists n\in ...

**4**

votes

**0**answers

143 views

### Two questions about the behavior of the continuum function

The first question asks about the global behavior of the power function in the case of finite gaps.
Question 1. Fix a natural number $m>1.$ For each limit ordinal $\alpha,$ including $0$, let ...

**1**

vote

**1**answer

146 views

### Why is a cut-free system consistent?

Assume that the cut-elimination theorem holds for a system $T$. Then, for any proof that makes use of the cut-rule in $T$, there is a proof that does not make use of the cut-rule. An immediate ...

**10**

votes

**1**answer

384 views

### What sort of large cardinal can continuum be?

I have stumbled across a related question asking which large cardinal properties can hold for $\aleph_1$. This question is probably also related, asking in what ways $\aleph_0$ is a "large" cardinal.
...

**1**

vote

**0**answers

62 views

### models of $I\exists^+_1$

$\phi$ is a $\exists^+_1$ formula iff it is in language of arithmetic and does not have $\forall$,$\neg$ and $\rightarrow$, therefore $I\exists^+_1$ is theory of $Q$+induction axioms for $\exists^+_1$ ...

**5**

votes

**1**answer

319 views

### Ill-founded models of set theory with well-founded ordinals

Let $(\mathcal{M},E)$ be an internally non-well-founded model of set theory i.e of $ZFC^{\neg f}=ZFC\setminus \mathrm{foundation}+\neg \mathrm{foundation}$, then $\mathcal{M}$ includes an infinite ...

**16**

votes

**1**answer

1k views

### What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?

In this article, Scott Aaronson talks about using Turing Machines for proving the Rosser Theorem.
What is the relationship between the numbering that Gödel used in his proof of incompleteness and ...

**1**

vote

**1**answer

258 views

### Does mathematical induction presuppose the existence of a completed infinity?

Consider the following statement by Edward Nelson--this from the "Outline" of his 'proof' of the inconsistency of $PA$ (which Terry Tao found to contain an error):
"The induction axiom schema of ...

**5**

votes

**0**answers

128 views

### Failure of GCH at a strongly compact cardinal

Does Con(ZFC+ there exists a strongly compact cardinal) imply Con(ZFC+ there exists a strongly compact cardinal $\kappa+ 2^\kappa > \kappa^+$)?

**24**

votes

**1**answer

707 views

### Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?

By "formal analogies" between the metamathematics of $\mathsf{ZFC}$/set theory and $\mathsf{PA}$(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following:
We are considering a ...

**30**

votes

**8**answers

5k views

### What are some important but still unsolved problems in mathematical logic?

In the past, First order logic and its completeness and whether arithmetic is complete was a major unsolved issues in logic . All of these problems were solved by Godel. Later on, independence of ...

**7**

votes

**1**answer

360 views

### Can an ultrapower be undone by forcing?

I am not 100% certain this question is appropriate for MO; I may just be missing something obvious. Also, I vaguely recall a similar question being asked here a while ago, but I can't find it; if it ...

**2**

votes

**1**answer

150 views

### Is there a simpler axiomatization for the quantifiers? [closed]

There is those one Q5 to Q7 in https://en.wikipedia.org/wiki/Hilbert_system#Formal_deductions
But I know the axioms of Boolean algebra were simplified to this ...

**11**

votes

**3**answers

400 views

### Algorithmic complexity of formal proof verification?

In this question, suppose $S$ is some popular real-world automated proof system that is stronger than or equivalent to Peano Arithmetic. I would be happy with a positive answer to the following for ...

**19**

votes

**1**answer

629 views

### Variant of Conceptual Completeness

Let $\mathcal{C}$ and $\mathcal{D}$ be pretopoi, and let $f: \mathcal{C} \rightarrow \mathcal{D}$ be a pretopos functor (that is, a functor which preserves finite coproducts, finite limits, and ...

**8**

votes

**2**answers

479 views

### What is an ordered structure, in general?

This is basically a reference request, but the post is going to be relatively long (and a little bit verbose): I apologize in advance for that.
Premise. There are several examples of "ordered ...

**2**

votes

**1**answer

114 views

### How to show certain theories are not existentially closed

To show that $ZFC$ is not existentially closed, we can use the following forcing argument: Let the ground model can model $V=L$ and the forcing extension model $2^{{\aleph}_{0}}=\aleph_{2}$. (Maybe ...

**4**

votes

**0**answers

81 views

### Does every model of $I\Delta_0$ has an end extension to a model of $I\Delta_0+\Omega_1$?

Does every model of $I\Delta_0$ has an end extension to a model of $I\Delta_0+\Omega_1$?
In End extensions of models of linearly bounded arithmetic paper the author said this problem is open. I ...

**2**

votes

**2**answers

598 views

### What logic can express this sentence?

Trying to figure out the logic in which the following formula is expressible:
$\forall i\in N: (x_i > y_i)$, which is equivalent to the "infinite" conjunction $\bigwedge_{i\in N} (x_i > y_i)$.
...

**22**

votes

**9**answers

3k views

### What is… A Grossone?

Y. Sergeyev developed a positional system for representing infinite numbers using a basic unit called a "grossone", as well as what he calls an "infinity computer". The mathematical value of this ...

**23**

votes

**5**answers

1k views

### What are the advantages of the more abstract approaches to nonstandard analysis?

This question does not concern the comparative merits of standard (SA) and nonstandard (NSA) analysis but rather a comparison of different approaches to NSA. What are the concrete advantages of the ...

**1**

vote

**1**answer

162 views

### A question regarding a fragment of Robinson Arithmetic

In his answer to the following mathoverflow question, The (un)decidability of Robinson Arithmetic without multiplication, Emil Jerabek proved that the following fragment:
$\forall$x(Sx$\neq$0)
...

**37**

votes

**4**answers

3k views

### How undecidable is the spectral gap?

Nature just published a paper by Cubitt, Perez-Garcia and Wolf titled Undecidability of the Spectral Gap, there is an extended version on arxiv which is 146 pages long. Here is from the abstract:"Many ...

**6**

votes

**1**answer

186 views

### Darboux property of non-atomic sigma-additive nonnegative measures equivalent to the AC?

A result commonly, and probably erroneously, attributed to W. Sierpiński is that every non-atomic, countably additive, nonnegative measure $\mu: \Sigma \to \bf R$, where $\Sigma$ is a sigma-algebra on ...

**12**

votes

**1**answer

551 views

### What is the precise relationship between o-minimal theory and Grothendieck's “Esquisse d'un programme”?

I have seen various references in the literature to such a connection but they tend to assume that the reader is familiar with the connection, and limit themselves to providing additional detail. So ...

**3**

votes

**1**answer

150 views

### When can we have “each subtheory is satisfiable iff it is recursively axiomatizable”?

Weak Version:
Is there a 1st order language $L$ (with only countably-many formulas) such that for each recursive coding $C$ of the formulas of $L$, there is a theory $T$ of $L$ where
$T$ is not ...

**5**

votes

**1**answer

305 views

### A proper class of formulas with every set-sized (but no proper-class-sized) subcollection satisfiable

What feature(s) must a (non 1st-order) language with proper-class-many formulas have in order to guarantee that:
There is a proper class P of formulas such that both
(a) every set-sized ...

**0**

votes

**0**answers

97 views

### Distribution of definable integers

Consider the distribution of all formulas of length less then n which define an integer in PA.
So for instance f(7,n)=number of formulas of length less then n which output 7.
Or the number of steps ...

**7**

votes

**0**answers

125 views

### Kripke models of $HA$

Let $K$ be a kripke model and $k$ be one of its node, then $\mathcal{M}_k$ is classical structure of $k$.
What is the strongest theory of arithmetic like $T$ such that for
every kripke model ...

**2**

votes

**1**answer

135 views

### [meta-]decision problem about decidability of finite Hilbert-style axiomatic systems

Consider some arbitrary language $S$ written over a given (propositional) signature with a finite collection of finitary constructors, and consider a procedure that receives as input an arbitrary ...

**3**

votes

**1**answer

223 views

### Can we use this symbol? [closed]

We consider the ring $\mathbb{C}[e^{\lambda x} \mid \lambda \in \mathbb{C}]$ and the language $L=\{+, \cdot , \frac{d}{dx} , 0, 1\}$.
The ring consists of elements of the form $$\sum_{i=0}^N ...

**4**

votes

**3**answers

216 views

### End Extension models of $I\Delta_0$

Recently I'm thinking about question below, but I can not prove or disprove it.
Is it true that for every model $M\models I\Delta_0$ there exists a
model $M'\models PA$ such that $M'$ is end ...

**9**

votes

**2**answers

526 views

### Why is there a need for ordinal analysis?

Consider the Peano axioms. There exists a model for them (namely, the natural numbers with a ordering relation $<$, binary function $+$, and constant term $0$). Therefore, by the model existence ...

**6**

votes

**0**answers

163 views

### “Clubiness” of projective sets of ordinals

I'm sure this is just my google-fu failing me, but: what are sufficient, non-overkill large cardinal axioms which guarantee "Every (boldface) $\Pi^1_n$ set of (real codes for) countable ordinals ...

**2**

votes

**0**answers

110 views

### Some questions regarding an alteration of Grzegorczyk's theory of concatenation, $\operatorname{TC}$

Consider Grzegorczyk's concatenation theory $\operatorname{TC}$, a "weak theory of words over the two letter alphabet $\Sigma=\{a,b\}$" (this from Grzegorczyk and Zdanowski's paper Undecidability and ...

**14**

votes

**1**answer

315 views

### Convergence rate of Fagin's 0-1 law for first-order properties of random graphs

Fagin's 0-1 law for first-order properties of random graphs states that, for every first-order sentence in the logic of graphs, the probability that a uniformly random $n$-vertex graph models the ...

**6**

votes

**0**answers

188 views

### Adding minimal subsets to $\aleph_\omega$

Given a cardinal $\kappa,$ recall that $X \subset \kappa$ is called fresh (over $V$), if $X \notin V,$ but $X \cap \alpha \in V$ for all
$\alpha < \kappa.$
Question. Is it consistent that there ...

**8**

votes

**1**answer

176 views

### Boolean-Valued Models: Why is $\| x=y \| \cdot \| \phi(x) \| \leq \| \phi(y) \|$?

Let $B$ be a complete Boolean algebra. Jech defines a Boolean-valued model $\mathfrak{A}$ of the language of set theory to consist of a Boolean universe $A$ and functions of two variables with values ...

**13**

votes

**1**answer

333 views

### Is this theory decidable?

It is well-known that both Presburger arithmetic (by contrast with Peano arithmetic) and Tarski geometry are decidable. I was in the shower this morning and wondered whether there exists an elegant ...

**3**

votes

**0**answers

301 views

### How close to being well-orderable does this make my powerset?

Let's work in a set theory without assuming AC (for instance, but not necessarily, ZF). Fix a set $k$ satisfying $k\times k \simeq k$, and consider its powerset $X = 2^k$. I have a technical condition ...

**3**

votes

**1**answer

210 views

### When can you canonically extend an ultrafilter after forcing?

Suppose that $V$ is a model of $\sf ZFC$, and fix some regular $\kappa$, say $\omega_1$ for practical purposes.
Let $\cal U$ be an ultrafilter on $\omega_1$ in $V$ which is non-principal and even ...