**9**

votes

**2**answers

479 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

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

**12**

votes

**1**answer

402 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

245 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

131 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

147 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

398 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

545 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

238 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

296 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

202 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

225 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

121 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

147 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

161 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

545 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

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

**7**

votes

**1**answer

204 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

162 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

299 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

211 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

134 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

99 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

174 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

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

**20**

votes

**2**answers

866 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

559 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

272 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

145 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

223 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

198 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

348 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

100 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

180 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

328 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

397 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

84 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

564 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

272 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

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

**14**

votes

**1**answer

752 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

133 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

285 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

248 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

441 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

161 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}))$?

**1**

vote

**3**answers

597 views

### Brouwer vs. Cantor

Brouwer criticises Cantor e.g. in Intuitionistiche Mengenlehre. Is there a link or reference to some streamlined modern account of Brouwer's ideas?

**12**

votes

**5**answers

827 views

### Does k(X) have a k-basis for every set X, without AC?

This question is inspired by Pace Nielsen's recent question Does a left basis imply a right basis, without AC?.
For any field $k$, the field $k(x)$ of rational functions in one variable has an ...

**11**

votes

**1**answer

235 views

### counterexample regarding quotient algebras in forcing

Suppose $A$ and $B$ are complete subalgebras of a complete boolean algebra $C$. Let $G \subseteq A$ be generic. In the extension $V[G]$, we can define the quotient algebras $B/G$ and $C/G$ in the ...