**8**

votes

**0**answers

133 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

262 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

145 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

156 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

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

**2**

votes

**0**answers

67 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

328 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

271 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

131 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

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

**31**

votes

**8**answers

6k 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

371 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

159 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 https://en.wikipedia.org/wiki/...

**11**

votes

**3**answers

412 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

697 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

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

**5**

votes

**0**answers

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

**2**

votes

**2**answers

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

**23**

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

**24**

votes

**5**answers

2k 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

166 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

192 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

585 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

151 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

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

**0**

votes

**0**answers

103 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

127 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 $K\...

**2**

votes

**1**answer

136 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

226 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

223 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

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

**8**

votes

**2**answers

301 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

113 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

325 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

190 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

180 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

342 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

308 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

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

**1**

vote

**2**answers

366 views

### Was “arithmetical translation” (coding in the Goedel sense) ever a part of Hilbert's Program?

Was "arithmetical translation" (that is, coding in the Goedel sense) ever a part of Hilbert's Program? I ask this question for several reasons:
i) it gives the numerals |, ||, |||,.... an ersatz '...

**0**

votes

**0**answers

150 views

### Is the positive existential theory undecidable?

Could you tell if the positive existential theory of $\mathbb{C}[e^{\mu x} \mid \mu \in \mathbb{C}]$ is undecidable in the language $\{+, \cdot , \frac{d}{dx} , 0, 1, e^x\}$ ?
How can we prove the (...

**2**

votes

**2**answers

272 views

### Time Hierarchy Theorem and P vs NP

One obvious strategy for proving P not equal to NP would be to show that there is some problem in NP which is hard for a time class strictly containing P (the origin of this question is the recent ...

**4**

votes

**1**answer

82 views

### Proving moduli of uniform continuity in RCA_0

Simpson's Subsystems of Second Order Arithmetic (pp. 134ff.) uses RCA$_0$ to prove various theorems of analysis for all continuous functions with a suitable modulus of uniform continuity. And he ...

**1**

vote

**0**answers

54 views

### Fully residually free groups and completion

Let $G$ be a fully residually free group with a finitely generated profinite completion. Is $G$ necessarily finitely generated?

**8**

votes

**2**answers

574 views

### Did Bishop, Heyting or Brouwer take partial functions seriously?

The partial μ-recursive functions which may or may not be provably total seem to have some direct relation to the initial motivations for intuitionistic mathematics. (Following Kronecker, one ...

**4**

votes

**2**answers

296 views

### A property of uncountable almost disjoint families

Let $\mathcal{A}$ be an uncountable almost disjoint family (not necessarily maximal) of infinite subsets of $\mathbb{N}$. Denote by $\mathcal{A}_{\subseteq}=\{ B\subseteq\mathbb{N}:|B|=\omega \wedge \...

**4**

votes

**0**answers

176 views

### Theories introduced by a class of forcing notions

The following notion is introduced by Mohammad Golshani. Let $V$ be a model of set theory and let $\mathcal{P}$ be a class consisting of non-trivial forcing notions in $V$. Let
$$Th(V, \mathcal{P})...