**5**

votes

**1**answer

168 views

### Uncountably categorical theories which are interpretable in a strongly minimal

Definition: Let $\lambda$ be a cardinal. An $\mathcal{L}$-theory $T$ is called $\lambda$-categorical whenever every two models of $T$ of cardinality $\lambda$ are isomorphic.
Definition: An ...

**6**

votes

**1**answer

435 views

### Adding sets not containing arithmetic progressions of length three by forcing

Consider the following forcing notion: conditions in $\mathbb{P}$ are pairs $(s, N),$ where:
1) $s\in 2^{<\omega}$,
2) $N\in \mathbb{N}$,
3) (by identifying $s$ with a subset of $lh(s)$) $s$ ...

**6**

votes

**0**answers

184 views

### Tree property and singular strong limit cardinals

I heard that the following theorem is proved recently by Foreman-Magidor, which answers a famous old open question:
Theorem. It is consistent, relative to the existence of large cardinals, that ...

**9**

votes

**2**answers

461 views

### Non-Forcing and Independence

I asked this question about two weeks ago on MSE and haven't gotten an answer, so I thought I would post the question here.
Do there exists sentences which are independent of ZFC, cannot be shown to ...

**0**

votes

**1**answer

96 views

### Completeness of a set of propositional formulas [closed]

A set $\sum$ of formulas in propositional logic is complete if for each propositional formula $\phi$ either $\sum \vdash \phi$ or $\sum \vdash \neg \phi$. Clearly every inconsistent set of formulas ...

**11**

votes

**1**answer

316 views

### Is factorial definable using a $\Delta_0$ formula?

The factorial function is primitive recursive, and therefore definable by a $\Sigma_1$ formula.
Is it also definable by a $\Delta_0$ formula (i.e. bounded quantifiers)?
If not, why?

**1**

vote

**1**answer

234 views

### Confusion with proof about a fact $\mathbb{P}$-name [closed]

Let $\mathbb{P}$ be poset.
Let $B$ be a set. We say that a $\mathbb{P}$-name $\dot{b}$ is a nice name for member of $B$ if there is a maximal antichain $A\subseteq\mathbb{P}$ and a function ...

**6**

votes

**1**answer

118 views

### Chains of forking extension in stable theories

Let $T$ be an stable theory.
Further we work in the monster model of $T^{eq}$.
We say that a chain of types of the form
$$tp(a_1/A_1)\subset tp(a_2/A_2) ... \subset tp(a_n/A_n)$$
is a forking chain ...

**3**

votes

**1**answer

142 views

### A question on many-one reducibility

Let $\phi_0,\phi_1,\phi_2,\ldots$ be an acceptable programming system. For each $x\in\mathbb{N}$, let $W_x$ the domain of $\phi_x$, and let $K=\{x\in\mathbb{N}:W_x\neq\emptyset\}$. Is there a ...

**6**

votes

**1**answer

378 views

### Alternate proof of Morley's theorem?

I'm trying to understand the result given in the first box at slide 45 of this talk. Specifically:
1) What is the source cited? I have not been able to find any article by Keisler, Chudnovsky and/or ...

**5**

votes

**2**answers

355 views

### Primitive Recursive Arithmetic via Universal Algebra

From the wikipedia article on Primitive Recursive Arithmetic (see http://en.wikipedia.org/wiki/Primitive_recursive_arithmetic):
"Primitive recursive arithmetic, or PRA, is a quantifier-free ...

**7**

votes

**1**answer

223 views

### Is $ACA_0$ + `True Arithmetic exists' interpretable in $ACA$?

Maybe someone here can help me with a question concerning second-order arithmetic. Consider the system $ACA_T := ACA_0 + \exists X \forall x (x \in X \leftrightarrow T(x))$, where $T(x)$ is a ...

**6**

votes

**1**answer

280 views

### Axiom of choice and the equality between second-order constructible universe and HOD

I try to prove $L_{SO}=\mathrm{HOD}$, where $L_{SO}$ is second-order constructible universe which has similar definition with $L$ but it uses second-order definability rather than the first-order ...

**4**

votes

**1**answer

191 views

### Explicit bounds for transfer results in algebraic geometry

Assume you have an ideal $I\subseteq\mathbb{Z}[X_1,\ldots,X_n]$ of the polynomial ring in $n$ variables over the integers. For any field $\Bbbk$, I can consider the ideal ...

**3**

votes

**1**answer

219 views

### Was $\Sigma x$ used as quantifier?

Kurt Gödel in 1931 used $x\Pi a$ where we in contemporary notation would use $(\forall x) A$ or $(x)A$, and $Ex a$ where we would use $(\exists x) A$. I believe that I remember that $\Sigma xA$ has ...

**0**

votes

**0**answers

117 views

### Reference Request: Category of explicit maps between primitive recursive sets?

[Edited]
Let $\mathsf{PR}$ be the category defined as follows:
Choose a specific presentation of Primitive Recursive Arithmetic, that is, with a specific set of terms for primitive recursive ...

**4**

votes

**1**answer

133 views

### presaturated ideals

In this paper, Gitik and Shelah make the following claim (part of Proposition 1.5):
Claim (Gitik-Shelah): Suppose $\kappa < \lambda$ are regular, $2^\lambda = \lambda^+$, and $D$ is a normal ...

**1**

vote

**0**answers

156 views

### Property theories

Property theory is, as I have understood it, first of all characterized by an attempt to approach naive comprehension type-freely and without committing to extensionality.
There is e.g. the work of ...

**5**

votes

**2**answers

520 views

### A specific Model of ZFC

In his paper "Some Second Order Set Theory", Joel Hamkins asked whether there is a model of set theory $V$ that is elementary equivalent to $V[G]$, Whenever $G$ is $V$-generic for the collapse of a ...

**10**

votes

**4**answers

476 views

### The groupoid of algebraic expressions and proofs

Fix a set of variables $V$, and suppose we're given a presentation of a monosorted algebraic theory, with variable symbols taken from $V$. For the sake of example, suppose the presentation consists of ...

**5**

votes

**1**answer

199 views

### $\text{Cont}(X,X)$ and $\neg\mathsf{GCH}$

For a topological space $(X,\tau)$ let $\text{Cont}(X,X)$ denote the set of continuous functions $f:X\to X$. Is it consistent that there a space $(X,\tau)$ such that $$|X| < |\text{Cont}(X,X)| < ...

**2**

votes

**2**answers

158 views

### Computable Categories in the most direct sense?

While there is a lot of work in category related to notions of realizability and computability, etc... I've failed to find work on categories that are computable in the sense of having object and ...

**4**

votes

**1**answer

262 views

### stationary tower forcing

It is known that if $\delta$ is a Woodin cardinal and $\kappa < \delta$, then the stationary tower forcing $\mathbb Q^\kappa_{<\delta}$ preserves cardinals up to $\kappa$ and forces $\delta = ...

**6**

votes

**1**answer

203 views

### What is known about the boundary between Richardson's theorem and the Tarski-Seidenberg theorem?

Tarski proved that equalities and inequalities in can be decided over $\mathbb{R}[x].$ Richardson proved that adding composition with the sine and exponential functions caused the problem to become ...

**3**

votes

**1**answer

121 views

### Is $PA+ \neg R_{PA}$ $\Pi_1$- conservative over $PA$?

I think it is well-known that $PA+\neg con(PA)$ is $\Pi_1$-conservative over $PA$ (for proof see Smorynski's article, 'the incompleteness theorems', in handbook of mathematical logic).
What can we ...

**3**

votes

**0**answers

84 views

### Logical framework for type theories like ML and CIC

I'm looking for a logical framework in which it is possible to easily present both intensional and extensional theories of dependent types with a partially ordered set of universes à la Russell ...

**6**

votes

**0**answers

164 views

### Singular Jonsson cardinals

Is the consistency of the following well-known:
$(*)$: There exists a singular cardinal $\kappa$ such that :
(1) $\kappa$ is a Jonsson cardinal,
(2) $\kappa$ is not a fixed point of the ...

**7**

votes

**1**answer

153 views

### $2$-uniformization versus $\omega$-uniformization of ladder systems

Let $S \subseteq \omega_1$ be a stationary set of limit ordinals and let $L = \langle L_\alpha \;|\; \alpha\in S\rangle$ be a ladder system. We say that $L$ has $\kappa$-uniformization if for every ...

**19**

votes

**2**answers

832 views

### What do you do if you believe a problem is undecidable?

While the title of this question is subjective, I hope to make what I'm looking for quite concrete. The first, and main question is this: If you believe that a problem you are working on is formally ...

**12**

votes

**1**answer

528 views

### Ordinary mathematics in Chang's model

This question is prompted by a paper by Andre Kornell that just appeared on the arXiv. A large portion of the paper is devoted to showing that a surprising amount of ordinary mathematics can be ...

**12**

votes

**0**answers

239 views

### The topos for forcing in computability theory

My understanding is that forcing (such as Cohen forcing) can be described via a topos. For example this nlab article on forcing describes forcing as a "the topos of sheaves on a suitable site."
My ...

**2**

votes

**1**answer

138 views

### Two questions on substitutability

(1) The condition that a term $a$ be substitutable for another term in an expression can be given a recursive definition. Who first developed such a definition?
(2) One sometimes see the phrase "$a$ ...

**9**

votes

**0**answers

213 views

### Proving regularity properties from forcing axioms

It's well known that PFA implies projective determinacy. It's also well known that PD implies that all projective sets are Lebesgue measurable, have the Baire property, etc.
Is there a direct proof ...

**0**

votes

**1**answer

185 views

### Is there a nontrivial maximally recursive function? [closed]

Say that a (recursive) function $f:\Bbb N\rightarrow\Bbb N$ is maximally recursive if, for all $n\in\Bbb N$, the value $f(n+1)$ can be calculated only by first knowing $f(n)$. A rather trivial example ...

**8**

votes

**0**answers

318 views

### What is known about the reverse mathematics of algebraic number fields?

I know work on the reverse mathematics of countable algebraic field extensions including Galois theory, notably including Dorais, Hirst, and Shafer http://arxiv.org/pdf/1209.4944v2.pdf. But algebraic ...

**2**

votes

**0**answers

97 views

### May $\Sigma_3$-collection hold below $\Sigma_3$-admissible ordinals for Gödel's L?

Suppose you have a system X=$KP$ + infinity plus $\Sigma_{3}$-collection and $\Delta_{2}$-specification. May $L_{\delta}\vDash X$ for some $\delta$ smaller than all $\Sigma_{3}$ admissible ordinals?

**1**

vote

**1**answer

164 views

### Propositional logic: Minimal set of formulas, which is consistent and complete

Hello together,
I have a rather basic issue on propositional logic: first, consider an arbitrary set of formulas $T$ that is consistent and complete, i.e., for every propositional formula $\varphi$, ...

**9**

votes

**1**answer

313 views

### singularize the least inaccessible?

Is it consistent that there is some partial order $\mathbb P$ and some inaccessible cardinal $\kappa$, which is the least inaccessible, such that $\mathbb P$ forces $\kappa$ to be singular while ...

**8**

votes

**1**answer

387 views

### Adding a real with infinite conditions

Consider the forcing $\Bbb P$ whose conditions are partial functions $p\colon\omega\to2$ with $\operatorname{dom}(p)$ a co-infinite subset of $\omega$, ordered by reverse inclusion.
Does $\Bbb P$ ...

**1**

vote

**1**answer

83 views

### On whether a formula of KP is $\Pi_3$

In the context of KP, is the formula $\forall w(w\in x \leftrightarrow\forall y\exists z F(w,y,z))$ $\Pi_3$ when $F(w,y,x)$ is $\Delta_0$?

**5**

votes

**2**answers

549 views

### Consequences of ZF+“all subsets of reals are Lebesgue measurable”

(I'm not sure if this is entirely suitable here so feel free to close it if it's not.) The statement "there is a Lebesgue measure on $\mathbb{R}$($2^\omega$)" means: there is a total $\sigma$-additive ...

**7**

votes

**2**answers

241 views

### Decidability of diophantine equation in a theory

Given a theory $T \subseteq \operatorname{Th}(\mathbb{N})$, define the decision problem $D_T$ as follows:
Given a polynomial $p$ with integer coefficients and variables $\bar{x}$, decide whether
...

**10**

votes

**2**answers

343 views

### Is there a compendium of the consistency strength between the most important formal theories?

Preliminar Notions:
A formal system is a tuple $(\Sigma,G,A,R)$ where $\Sigma$ is an alphabet (set of symbols), $G$ is a formal grammar on $\Sigma$ that generates a formal language $L$ (set of well ...

**11**

votes

**1**answer

485 views

### Analogues of Primitive Recursive Functions

Let $\mathbf{A}$ be an admissible set (possibly with urelements). I am wondering if there is some good notion of "primitive recursive arithmetic" relative to $\mathbf{A}$. More precisely, I would like ...

**2**

votes

**1**answer

113 views

### Total formulae in a theory equivalent to $\Delta_0$ formulae in the theory?

Let a formula $\phi$ of the language of first-order Peano arithmetic be total in a theory Th that extends PA iff, for any $k_1, \dots, k_n \in \omega$, Th $\vdash \phi(\bar k_1, \dots, \bar k_n)$ or ...

**4**

votes

**2**answers

269 views

### Limits of determinacy on reals

For $X\subseteq\mathbb{R}^\omega$, say that $X$ is determined if the associated game on $\mathbb{R}$ of length $\omega$ (players I and II alternate playing reals, player I wins iff the sequence built ...

**0**

votes

**0**answers

41 views

### representing quasicrystal as tilings and appearing frequencies of each tile

Quasicrystal can be fully represented either using projection method or tilings with constraints. For the latter, is there some sort of study on the "appearing frequency" of each tile or even ...

**6**

votes

**1**answer

219 views

### Are two forms of the Dual Schroeder-Bernstein property equivalent?

We know the Shroeder-Bernstein (SB) theorem can be proved in ZF, while the Dual Schroeder-Bernstein (DSB) can be proved in ZF+AC but not in ZF. Define as ISB the property that whenever there are both ...

**4**

votes

**1**answer

423 views

### Did Brouwer evade uncountability?

I have the distinct memory of having often heard and read that intuitionism was inter alia geared to avoid Cantor's uncountable sets, and it may be that this was Brouwer's plan. But are there accounts ...

**-2**

votes

**1**answer

146 views

### Does PA prove a sentence asserting that all of I-sigma(n) theories are consistent? [closed]

We know that PA proves consistency of $I\Sigma_{n}$ for any $n$. But does PA prove the sentence:
$\forall n (con(I\Sigma_{n}))$?