**11**

votes

**1**answer

403 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

96 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

263 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

40 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

210 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

413 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

138 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

577 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?

**11**

votes

**5**answers

771 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

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

**23**

votes

**2**answers

698 views

### Forcing as a replacement of induction and diagonal arguments

Let me give some examples motivating the question.
The use of forcing instead of induction: For this consider Cantor's theorem:
Theorem 1. Any two countable dense linear orders $I, J$ without end ...

**6**

votes

**0**answers

225 views

### A new cardinality living in every forcing extension?

This question is motivated by the papers http://arxiv.org/abs/1405.7456 and http://arxiv.org/abs/1410.1224.
Say that a set $X$ is "generically presentable" over $V\models ZF$ if there is some ...

**14**

votes

**0**answers

403 views

### Has anyone read/debunked Yessenin-Volpin–Hennix “Beware of the Gödel-Wette paradox”?

A student recently asked me about the status of a 2001 arXiv post, Beware of the Gödel-Wette paradox!, by Alexander Yessenin-Volpin (aka Esenin-Volpin and several other transliterations) and Catherine ...

**2**

votes

**1**answer

233 views

### Axiomatic ZFC Set Theory [closed]

Can the Axiom Schema of Comprehension be omitted from ZFC since it is implied by the Axiom Schema of Replacement?

**-1**

votes

**1**answer

95 views

### types and elementary extensions [closed]

Let $\mathcal{M}$ and $\mathcal{N}$ be two $\mathcal{L}$-structures and suppose that for n-tupls $\bar{a}\in M^n$ and $\bar{b}\in N^n$,
$tp^\mathcal{M}(\bar{a})=tp^\mathcal{N}(\bar{b})$ where ...

**6**

votes

**1**answer

465 views

### A question on rank-to-rank embeddings

Consider a non-trivial elementary embedding $j:V_\lambda\to V_\lambda$ and, for each $A\subset V_\lambda$, set $j(A)=\bigcup_{\delta<\lambda}j(A\cap V_\delta)$.
In Implications between strong ...

**3**

votes

**3**answers

311 views

### The Set-Theoretic Multiverse and Joint Embeddings

I am curious whether or not the following axiom is independent of Hamkins's axioms for the Set-Theoretic Multiverse. Hamkins's axioms can be found here on pages 1-2 and here on pages 24-26.
Consider ...

**5**

votes

**0**answers

237 views

### Cardinal characteristics without choice

(I'm taking my definition of a cardinal characteristic from Blass' excellent article http://www.math.lsa.umich.edu/~ablass/need.pdf, which cites Vojtas/Fremlin/Miller; theirs is more general, but I'm ...

**8**

votes

**0**answers

197 views

### Is there a notion analogous to separability but requiring definable rather than countable sets?

Among models of $\lambda$-calculus, some like the Bohm tree model have the property that every element is a directed sup of definable elements, whereas others like the $D_\infty$ and $P(\omega)$ ...

**11**

votes

**2**answers

660 views

### Where is the Erdős–Rado theorem stated in Erdős and Rado's Bull AMS paper?

This may be inappropriate for MO, but here goes: if I have understood the statement of the Erdős–Rado theorem correctly, then it contains as a special case the following result:
if $\mu$ is ...

**4**

votes

**2**answers

235 views

### Is it consistent that $\frak{d} < 2^{\aleph_0}$?

Let $\omega^\omega$ denote the set of all functions $f:\omega\to\omega$. We write $f <^* g$ if there is $N\in\omega$ such that $f(n) < g(n)$ for all $n>N$. A set $D\subseteq \omega^\omega$ is ...

**12**

votes

**4**answers

911 views

### Sierpinski's construction of a non-measurable set

In the early 20th century there was a lot of fuss over the axiom of choice implying that there are Lebesgue non-measurable sets of reals. In his book about The Axiom of Choice, Gregory Moore points to ...

**7**

votes

**1**answer

555 views

### Application of the Riemann hypothesis and the ABC conjecture to independence results

In Old Home Page of Andreas Weiermann Andreas Weiermann has stated the following:
Quite recently I submitted a preprint about an application of the Riemann hypothesis and the ABC conjecture to ...

**6**

votes

**2**answers

243 views

### When does Skolemization require the axiom of choice?

Skolemization is often used for eliminating existential quantifiers, which is often useful for proving theorems, especially in automated resolution theorem proving. Skolemization in first order ...

**6**

votes

**1**answer

284 views

### Existence of internal toposes/inner models in a topos

It has been known for some time that one can define a topos as a model of a (finitary) essentially algebraic theory (or in other words, can be defined internal to any category with finite limits). In ...

**28**

votes

**1**answer

719 views

### Producing finite objects by forcing!

It is a trivial fact that forcing can not produce finite sets of ground model objects. However there are situations,
where we can use forcing to prove the existence of finite objects with some ...

**11**

votes

**2**answers

1k views

### Existential statement without witness

Are there existential theorems of ZFC, or PA say, with no witnesses?
Ie does there exist a formula $\phi$ such that ZFC $\vdash\exists x \phi(x)$, but for all numerals $\underline{n}$, ZFC $\nvdash ...

**2**

votes

**0**answers

65 views

### A question on recursion and transfinite recursion in extensions of KP

Is the $\Sigma_{n}$-recursion supported by $\Sigma_{n}KP=KP+\Sigma_{n}$-separation + $\Sigma_{n}$-collection equivalent with $\Sigma_{n}$ transfinite recursion? If not, how do these notions differ?

**5**

votes

**0**answers

63 views

### TCAs (total combinatory algebras) with oracles

Is there a natural, non-trivial example of a TCA (total combinatory algebra, cf. pca) with a natural notion of an oracle?

**8**

votes

**3**answers

623 views

### Does a left basis imply a right basis, without AC?

If $_DV_D$ is a $D$-$D$-bimodule, and we have a $D$-basis for $V_D$, do we still need AC to get a $D$-basis for $_DV$?
(The original question appears below. But this shorter question gets at the ...

**4**

votes

**1**answer

217 views

### Decidability of Frankl's union-closed sets conjecture

Is it conceivable that Frankl's union closed sets conjecture is undecidable in $\mathsf{ZFC}$, or is this quite implausible, perhaps due to the "finitistic" nature of the statement, or for some other ...

**6**

votes

**2**answers

175 views

### Formal languages with non-unique interpretations of terms

In mathematical logic and model theory, one considers interpretations of syntactic expressions: terms without free variables are interpreted as elements of some structure, formulas without free ...

**0**

votes

**0**answers

159 views

### Wolfram's axiom completeness

I have been reading Wolfram's A New Kind of Science, and as I was reading the section on systems of logic and axioms, I came across this axiom, for which all of the normal axioms of Boolean logic can ...

**4**

votes

**1**answer

71 views

### Is below every cohesive set a 1-generic?

A set $X$ is called cohesive for $(R_i)_{i\in \mathbb{N}}$ if it is infinite and for each $i$ we have $X\subseteq^* R_i$ or $X\subseteq^* \overline{R_i}$. (Where $X\subseteq^*Y$ means that $X$ is ...

**8**

votes

**1**answer

177 views

### Base change in homotopy type theory

Recall that with the internal language of 1-toposes, we have the nice, basic, and useful result that geometric sequents are stable under base change along geometric morphisms: If $\varphi$ and $\psi$ ...

**7**

votes

**2**answers

338 views

### When can we reach a real by forcing?

I'm sure this is well-known, but: suppose I have a non-constructible real $r\in V-L$. Under what conditions is there a poset $\mathbb{P}\in L$ and a $G$ which is $\mathbb{P}$-generic over $L$, such ...

**3**

votes

**1**answer

122 views

### A question on recursion in Kripke-Platek set theory with infinity and $\Sigma_{3}$-separation and $\Sigma_3$-collection

$\Sigma_{3}KP\omega$ be Kripke-Platek set theory with infinity and $\Sigma_{3}$-separation and $\Sigma_3$-collection. What strengthening of Barwise's Definition by $\Sigma$ Recursion (Theorem 6.4 on ...

**9**

votes

**1**answer

267 views

### Busy beaver function vs low Turing degrees

Let $BB(n)$ denote busy beaver function. It's well known that $BB(n)$ dominates all computable functions (I'm quite certain it includes partial computable functions too). However, I was wondering if ...

**14**

votes

**1**answer

626 views

### Is it possible to define higher cardinal arithmetics

In number theory there are several operators like addition, multiplication and exponentiation defined from $\omega\times\omega$ to $\omega$. Each of them is defined as an ...

**4**

votes

**2**answers

187 views

### Relation between Turing degrees and functions computable with them

Suppose $A<_T B$ ($A$ is a set computable from $B$ but not vice versa). Is it always the case that there exists a $B$-computable function which eventually outgrows all $A$-computable functions?
Of ...

**12**

votes

**1**answer

748 views

### Von Neumann's consistency proof

In the paper Zur Hilbertschen Beweistheorie, John Von Neumann has proposed a consistency proof for
a fragment of first-order arithmetic (the fragment without induction and with
the successor axioms ...

**10**

votes

**2**answers

439 views

### Can a parent and child node have the same type in a well-founded digraph tree?

$\newcommand\toward{\rightharpoonup}$It would help me to
understand something in a current research project if someone
could provide an example of directed graph $\langle
G,\toward\rangle$ with the ...

**-1**

votes

**2**answers

418 views

### Can an algorithm decide whether a program computes all strings? [closed]

I am interested in the type of program, which is given as input to a Universal Turing Machine (UTM) with language $L$, and for which it holds that every possible finite string $s$ of symbols in $L$ ...

**1**

vote

**0**answers

42 views

### Non overlapping boxes with constraint modelling [closed]

I'm stucked with this problem for 2 days and i've finished the ideas. Any hint is appreciated.
Given a set of squares (2x2, 3x3, 4x4, 5x5), and a rectangular grid (9x7) place the squares on the grid ...

**4**

votes

**0**answers

186 views

### A question on the size of an admissible ordinal

Let $\mathbf{L}_{\varsigma}$ be the level of ordinal $\varsigma$ of Gödel's constructible universe $\mathbf{L}$. Let $\Sigma_{3}$-KP be Kripke-Platek set theory with infinity and ...

**-5**

votes

**1**answer

177 views

### An axiomatic system with a set of constants that form a complete ordered field [closed]

I am developing a ZFC axiomatic system where together with the empty set, there is a singular (and huge) set of constants that are themselves sets and form a complete ordered field (cof) these ...

**7**

votes

**2**answers

279 views

### Peano arithmetic vs. fast-growing hierarchy with pathological fundamental sequences

Fundamental sequence for a countable limit ordinal $\alpha$ is an increasing sequence $\{\alpha[i]\}$ of ordinals of length $\omega$ such that $\lim_{i\rightarrow\omega}\alpha[i]=\alpha$. There are ...

**12**

votes

**1**answer

462 views

### Is there a nonstandard model of arithmetic having precisely one inductive truth predicate?

$\newcommand\Tr{\text{Tr}}$My question is whether there can be a nonstandard model of PA having a unique inductive truth predicate.
Background. If $\mathcal{N}=\langle N,+,\cdot,0,1,<\rangle$ is ...

**0**

votes

**1**answer

231 views

### How to formalize “Is there a proof for every instance of the halting problem?”? [closed]

In a previous question that I asked here it turned out that for every instance of the halting problem, being the matter whether a certain computer program halts or runs forever, there exists a ...

**0**

votes

**1**answer

202 views

### Is there a consistent theory for each instance of the halting problem?

I got a bit confused by a discussion about the provability of the Goldbach conjecture and the seemingly different opinions about this subject. Since I understand computer science better, I will ask my ...