**6**

votes

**3**answers

477 views

### Category of Gödel Codings? [Reference Request]

Consider computation with the integers $\mathbb{Q}$. The traditional theory of recursive functions on $\mathbb{N}$ applies to $\mathbb{Q}$ by the identification of $\frac{a}{b} \in \mathbb{Q}$ with ...

**5**

votes

**0**answers

231 views

### Quasi-disjoint subsets of an infinite set and $\neg \mathsf{AC}$

Is it consistent with $\mathsf{ZF}$ (without $\mathsf{AC}$) that there is an infinite set $X$ and a subset $S\subseteq\mathcal P(X)$ of the same cardinality as $\mathcal P(X)$ with the property that ...

**12**

votes

**2**answers

1k views

### Do the real numbers “know” that they are countable in a larger model?

(This was first posted to math.stackexchange but had no answers there after several days):
Let ${\mathbb R}$ be the set of real numbers in whatever is your favorite model of $ZFC$. Then (by Levy ...

**2**

votes

**0**answers

64 views

### Potentiality classes and Borel reductions

In a 1998 paper by Hjorth, Kechris, and Louveau, there was a definition given of a "potentiality class." That is, given an invariant equivalence relation $E$ on a standard Borel space $X$, we say $E$ ...

**6**

votes

**1**answer

172 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

436 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

185 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

463 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

318 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

235 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

119 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

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

**6**

votes

**2**answers

364 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

281 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

194 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

134 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

524 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

263 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

205 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

123 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

531 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

240 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

214 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

186 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

319 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

165 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

314 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

389 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

550 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

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

**13**

votes

**1**answer

567 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

115 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

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