# Tagged Questions

**11**

votes

**3**answers

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

**16**

votes

**0**answers

432 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

443 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

113 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

77 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

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

**21**

votes

**9**answers

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

**21**

votes

**4**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

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

**36**

votes

**4**answers

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

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

**6**

votes

**0**answers

219 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

142 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

298 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

93 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

118 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

128 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

217 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

206 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

477 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

161 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

104 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

292 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

182 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

172 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

321 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

289 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

192 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

**1**answer

284 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

143 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

256 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

68 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

49 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

550 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

287 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

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

**-5**

votes

**1**answer

128 views

### New hilbert system and theorem [closed]

Let we have following axioms and modus ponens :
$$(A1):(B ⇒ (C ⇒B ))$$
$$(A2):((B ⇒ (C ⇒D )) ⇒ ((B ⇒C ) ⇒ (B ⇒D )))$$
$$(A3):( ( B ⇒C) ⇒(¬C ) ⇒ (¬B ))$$
now can we prove following theorem ?
$\vdash ...

**4**

votes

**1**answer

289 views

### Show that the positive existential theory is undecidable

To show that the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0 , 1, t\}$ is undecidable we have to prove the following: ...

**6**

votes

**0**answers

91 views

### Finitely presented algebras with isomorphic semilattices of congruences

Let $\mathbb{T}$ be a finitary algebraic theory. For each $\mathbb{T}$-algebra $A$, let $Q (A)$ be the join semilattice of finitely generated congruences on $A$. There is an evident pushforward ...

**3**

votes

**1**answer

226 views

### How can the critical point of an elementary embedding be omega_1?

I've seen an example of an elementary embedding such that $\omega_1$ is the critical point.
I was wondering what's wrong with the following proof that this cannot be:
Let $\phi(x_1,x_2)$ be the ...

**2**

votes

**0**answers

106 views

### Is a finitely generated residually free group “almost LERF”?

Let $G$ be a finitely generated residually free group.
(i.e. for each $1 \neq g \in G$ there exists a homomorphism $\tau \colon G \to F$ such that $F$ is a free group, and $\tau(g) \neq 1$.)
...

**19**

votes

**3**answers

606 views

### Is being rational decidable?

Given a real number uniquely defined by a finite system of equations and inequalities with rational coefficients involving the standard elementary functions only. Is it decidable whether this number ...

**14**

votes

**1**answer

289 views

### Joyal's construction of the spectrum of a commutative ring

I am trying to understand bits and pieces of Lawvere's article Continuously Variable Sets; Algebraic Geometry = Geometric Logic. I'm not doing very well.
I know this is a lot to ask, but basically, I ...

**2**

votes

**0**answers

62 views

### A Question on Provability Logic and Co-Necessitation

The provability logic $GL$ has the characteristic axioms:
$K\hspace{15pt}\Box(\alpha\rightarrow \beta)\rightarrow(\Box\alpha\rightarrow\Box\beta)$
$L\hspace{15pt}\Box(\Box \alpha\rightarrow ...

**3**

votes

**3**answers

229 views

### Semantic reflection

Let $\ulcorner \cdot \urcorner$ be a fixed encoding of formulas by numbers, e.g.
let $\ulcorner \varphi \urcorner$ denote the Godel number of $\varphi$.
Let $T$ be a first-order arithmetic theory, ...

**7**

votes

**0**answers

204 views

### Proving Richardson's theorem for constants

(I asked this a little over 3 months ago on math.SE, and when I initially re-asked here, no one had responded there. $\:$ After I re-asked here, Eric Towers responded there, since I had forgotten to ...

**4**

votes

**1**answer

184 views

### What is the right notion of generalized element of a category?

I've been working out how the internal language of a category C extends to taking the category itself as a type.
The most obvious way to interpret $X : \mathbf{C}$ is, of course, that $X$ is an ...

**18**

votes

**2**answers

533 views

### Removing large cardinals from an uncountable transitive model

The usual way of removing large cardinals from a given model of set theory is to cut off the model below the least large cardinal of interest. But this method may have dramatic effects on the external ...

**6**

votes

**2**answers

245 views

### The role of the index set in the product of uncountably many topological spaces

Let $\langle X_i,\mathcal{T}_i \rangle_{i\in I}$ be a family of topological spaces. Consider $X=\prod_{i\in I} X_i$ with product topology.
Question. Is there a topological property that holds in ...

**3**

votes

**2**answers

230 views

### Do limit groups satisfy Howson's theorem?

Let $G$ be a limit group, and let $A,B \leq G$ be finitely generated
subgroups generating $G$ (i.e. $\langle A \cup B \rangle = G$). Must
$A \cap B$ be finitely generated?
Recall that a limit ...