**14**

votes

**1**answer

278 views

### Whatever happened to $L(j)$?

So this question probably shows my inner model theoretic ignorance, but:
In "Two remarks on elementary embeddings of the universe" (http://projecteuclid.org/download/pdf_1/euclid.pjm/1102969567), ...

**-4**

votes

**1**answer

284 views

### the real Generalized Continuum Hypothesis, reflecting the finite powers [on hold]

The real Generalized Continuum Hypothesis is a model of ZFC, from any universe of ZFC, via Easton forcing, where the following hold:
$$ 2^{\omega} = \omega_1 $$
$$ 2^{\omega_1} = \omega_2 $$
$$ ...

**-1**

votes

**0**answers

198 views

### Comparing the Kolmogorov complexity of theories - Part 2

Chaitin's incompleteness theorem says no sufficiently strong theory of arithmetic can prove $K(x) > L$ where $K(x)$ is the Kolmogorov complexity of natural number $x$ and $L$ is a sufficiently ...

**0**

votes

**0**answers

68 views

### Turing Machine Halting [closed]

I have come across this halting problem question during my exam preparation and can't come up with a solid proof for the following question.
Question:
Let L be { Ti does not halt on input i}
Show ...

**2**

votes

**0**answers

108 views

### What can be said about a Boolean-valued structure from what the Boolean-valued forcing extension thinks about it?

Suppose that $\phi$ is a formula in the language of set theory such that
there are some $n_{1},...,n_{k}$ such that if $V\models\phi(x)$, then $x=(X,R_{1},...,R_{k})$ and ...

**11**

votes

**0**answers

303 views

### Decidability of $x^3+y^3+z^3 = c$

I wondering if it is known whether the following problem is algorithmically decidable or undecidable by Turing machines: given an integer c, determine if there are integers $(x,y,z)$ such that ...

**0**

votes

**0**answers

33 views

### How can nontrivial elementary embeddings of the universe to some inner model be surjective? [migrated]

Consider $\kappa$ to the least measurable cardinal, or equivalently $\kappa$ is the critical point for an elementary embedding $j:V \rightarrow M$ from the universe $V$ to an inner model $M$ (critical ...

**6**

votes

**0**answers

241 views

### Reference for “if the set $A$ is Suslin, then every $\Sigma^1_1(A)$ set is Suslin”

Does anyone know of a reference for one or both of the following facts (in $\mathsf{ZF}$)?
If the set of reals $A$ is Suslin, then every $\Sigma^1_1(A)$ set of reals is Suslin.
If $T$ is a tree on ...

**12**

votes

**2**answers

854 views

### When does Vopěnka's principle hold?

Vopěnka's principle (VP) is the statement that, given any proper class $\{\mathcal{A}_\eta: \eta\in ON\}$ of first-order structures in the same language, there are some $\alpha\not=\beta$ with ...

**7**

votes

**1**answer

341 views

### Explicit counter example to Vopěnka's principle in the constructible universe?

Vopěnka's principle is a large cardinal axiom which has many equivalent formulations. One of them, which I find especially appealing, is the following: if the universe is satisfies Vopěnka's principle ...

**5**

votes

**1**answer

76 views

### When is a formula preserved under taking factors in a reduced product or the stalk in a Boolean product?

I want to know if there is a nice characterization of when a formula is preserved under taking reduced factors.
We say that a formula $\phi$ is closed under taking reduced factors if whenever $I$ is ...

**0**

votes

**0**answers

97 views

### A question on complexity notation

I am considering writing ''$\Pi^{n}_{i_{0},...,i_{n-1}}$-comprehension'' as abbreviation for ''$\Pi^{0}_{i_{0}}$-comprehension plus ... plus $\Pi^{n-1}_{i_{n-1}}$-comprehension'' in the context of an ...

**3**

votes

**1**answer

139 views

### Maximality statements that cannot be proved using $\mathsf{ZL}$ [closed]

What are examples for maximality statements that cannot be proved using Zorn's Lemma?

**5**

votes

**1**answer

76 views

### Strongly minimal set with DMP

Recall that a strongly minimal theory $T$ has the Definable Multiplicity Property (DMP) if for all natural $k$, $m$ and $\varphi(\bar{x},\bar{b})$ of rank $k$, multiplicity $m$, there exists a formula ...

**5**

votes

**0**answers

159 views

### Universal anti-Horn classes?

Is there published work about universal anti-Horn classes?
Anti-Horn formulas are also sometimes known as dual Horn.
See also related question Is there any research of universal algebras ...

**1**

vote

**0**answers

82 views

### saturated model [closed]

Suppose you have a saturated model N of a complete theory T without finite models. How is it possibile to construct a proper saturated elementary substructure of N of the same cardinality of N ?
I ...

**6**

votes

**2**answers

561 views

### How do I apply the Boolean Prime Ideal Theorem?

I have become aware of an amazing phenomenon from a myriad of questions and answers here on MathOverflow: many of the results that I would typically prove using the Axiom of Choice can actually be ...

**1**

vote

**0**answers

175 views

### Seeking reference to result in this talk by Voevodsky [duplicate]

In this presentation by Vladimir Voevodsky [1], he mentions a result that there is a formula over the natural numbers with a single free variable such that one can prove that there is no algorithmic ...

**3**

votes

**0**answers

77 views

### Fixed Points of the Friedman Stanley Jump

Consider the situation of a pair $(X,E)$, where $X$ is a standard Borel space and $E$ is an invariant equivalence relation on $X$*. The Friedman-Stanley jump of this pair is an equivalence relation ...

**5**

votes

**1**answer

244 views

### Logical strength of “choice functions exist for well-ordered families”?

A colleague of mine suggested the following weakening of the axiom of choice:
If $\mathscr{F} := \{F_\alpha\}$ is a well-ordered family of non-empty sets (i.e., there is a bijection between ...

**6**

votes

**1**answer

149 views

### Degree of unsolvability of finding a open approximation to a Borel set, given its Borel code

It is well known that every Borel set has the property of Baire. That is, for every Borel set $B$, there is an open set $U$ and a sequence of dense open sets $D_n$ such that for every $x\in \cap_n ...

**1**

vote

**0**answers

172 views

### Existence of $\lambda$-transitive linear orders for $\lambda \geq \aleph_0$

A linear order $(L, <)$ is $\lambda$-transitive iff any order-preserving bijection between sets of size $\lambda$ can be extended to an order automorphism of $L$.
For $\lambda < \aleph_0$, ...

**4**

votes

**1**answer

138 views

### Embedding of classical into intuitionistic linear logic

Following on from this recent question, there is another construction that is well-known, but I don’t know a good primary source for: the Kolmogorov-style double-negation embedding of classical into ...

**9**

votes

**0**answers

143 views

### Consistency strength of $\aleph_2$-Souslin hypothesis

Question 1. What is known about the consistency strength of $\aleph_2$-Souslin hypothesis?
Question 2. What is known about the consistency strength of having both $\aleph_2$-Souslin hypotheis and ...

**5**

votes

**1**answer

173 views

### Conservativity of multiplicative linear logic over intuitionistic multiplicative linear logic

It is well known that multiplicative linear logic (MLL) is conservative over intuitionistic multiplicative linear logic (IMLL). In other words, if an IMLL formula is provable in MLL then it is already ...

**7**

votes

**0**answers

217 views

### What is the Turing degree of $\mathbb{C}_{exp}$?

Let $\mathbb{C}_{exp}$ be the theory of the complex numbers in the language of exponential rings. I am interested in the Turing degree of $\mathbb{C}_{exp}$. As the natural numbers are definable in ...

**5**

votes

**0**answers

164 views

### Can the first ordinal in which $V\neq HOD$ be $\aleph_\omega$?

Assume that $V\neq HOD$ and let $\kappa = \min \{\alpha\in On \mid \mathcal{P}(\alpha) \not\subseteq HOD\}$.
Clearly, $\kappa$ is a cardinal.
Question: Is it consistent that $\kappa = ...

**37**

votes

**1**answer

3k views

### Mathematicians wearing hats on arbitrary total orders

I've been pondering the following generalisation of a famous problem (the special case where $T = \mathbb{N})$:
Question: We have some totally-ordered set $T$ of mathematicians, each wearing a hat ...

**7**

votes

**1**answer

224 views

### Notions of infinity in $\mathsf{ZF}$ without choice

Consider the following statements about a given set $X$ in in $\mathsf{ZF}$:
(1) There is $x_0\in X$ such that there is a surjective map $\varphi: X\setminus\{x_0\}\to X$.
(2) There is an injective ...

**13**

votes

**3**answers

1k views

### Applications of set theory in physics

In the introduction of the paper "Links between physics and set theory", the following quote of Eris Chric is stated:
"Set theory perhaps is too important to be left just to ...

**3**

votes

**0**answers

143 views

### A property of the Frechet filter and every ultrafilter

(Joint question with Piotr Szewczak.)
Definitions and notation. By filter we mean a filter on $\omega$ containing the cofinite sets at least.
For a filter $\mathcal{F}$, let ...

**1**

vote

**1**answer

63 views

### Injecting premises into two implicational premises connected by a tensor (multiplicative conjunction) in linear logic

I have another question regarding linear logic: I want to get to the proof E, using the premises in (1-4). Is this at all possible?
1: $A$
2: $C$
3: $(A\multimap B)\otimes(C\multimap D)$
4: ...

**2**

votes

**0**answers

129 views

### Relationship between coherent toposes/coherent logic and coherent sheaves

I've heard it claimed that the adjective "coherent" in logic/topos theory (i.e. coherent logic, coherent toposes, coherent categories) was adopted to fit in with the terminology of coherent sheaves in ...

**2**

votes

**1**answer

192 views

### Mal'cev “rational equivalence” and model theory

In Universal Algebra, it is possible to say that two presentations denote the "same" kind of algebraic structures, if the two corresponding varieties are "rationally equivalent" (Mal'cev 1958).
In ...

**4**

votes

**1**answer

297 views

### Does PA+Con(PA) entail the existence of non-standard models of PA?

Does $\textsf{PA}$+Con($\textsf{PA}$) entail the existence of non-standard models of $\textsf{PA}$?
Is there a reasonable way in which to code, inside $\textsf{PA}$, the statement that $\textsf{PA}$ ...

**4**

votes

**1**answer

157 views

### Generalizing a result of Kreisel on $\omega$-consistency

In (reference)The following result is attributed to Kreisel:
Lemma1(Kreisel) If $T$ is an $\omega$-consistent theory in the language of arithmetic and $\pi$ is a true $\Pi_1$ sentence, then $T+\pi$ ...

**13**

votes

**4**answers

2k views

### Is there a natural bijection from $\mathbb{N}$ to $\mathbb{Q}$?

In a conversation where it came up that the Pythagoreans probably found an enumeration of the rational numbers I erroneously remarked that Georg Cantor found a natural bijection from $\mathbb{N}$ to ...

**2**

votes

**2**answers

129 views

### Is there a good list of nomenclature for modal axioms?

I would like to see what names that has been suggested for useful modal axioms. By name here I mean some abbreviation such as $T$, $K$, $4$, $.2$, $E$ and so on. In particular I am interested in ...

**8**

votes

**2**answers

310 views

### For a partition of $\mathbb{R}$ into countably infinite sets, must there be an almost-disjoint family of $2^{\frak c}$ many selectors?

My question arises from a construction I gave in my recent
answer to a question of Alexander Pruss concerning large families of independent non-measurable sets of reals. In that argument, using
the ...

**1**

vote

**0**answers

117 views

### This modal logic semantics is not S5, but is it something else well-known?

The short form of the question is this:
Is there a model of modal propositional calculus that gives the modal operators the meanings
...

**2**

votes

**1**answer

88 views

### Representable cylindric algebras and correspondence with first-order models

The class $\textsf{Cs}_{\omega}^{reg}\cap \textsf{Lf}_{\omega}$ of locally finite and regular cylindric set algebras (of dimension $\omega$) can be seen as the algebraic counterpart of first-order ...

**7**

votes

**0**answers

133 views

### Decidabilty of the Hilbert lattice and quantum logic

What is known about the decidability of (first-order formulas in) the structure $(\mathcal{L}(H),\leq)$, where $\mathcal{L}(H)$ is the collection of all closed linear subspaces of a (separable) ...

**8**

votes

**1**answer

334 views

### If $\kappa$ is weakly inaccessible and $A\subset\kappa$, can $L[A]$ violate $\kappa^{\lt\kappa}=\kappa$?

In some current work, my co-authors and I had wanted in a certain
argument to appeal to $\kappa^{\lt\kappa}=\kappa$ in $L[A]$, in a
situation where $A\subset\kappa$ and $\kappa$ was weakly
...

**4**

votes

**1**answer

315 views

### Inaccessible cardinal and $\Sigma_1$ reflection

A theorem of A. Levy says that, if $\kappa$ is an inaccessible cardinal, then $V_\kappa\prec_{\Sigma_1}V$ namely $V_\kappa$ is an elementary submodel when considering only $\Sigma_1$ formulas.
Where ...

**3**

votes

**1**answer

207 views

### Hamkins infinite time Turing machines: dovetailing ordinal time

It is claimed in the Hamkins and Lewis founding article "Infinite time Turing machines" (proof of the gap existence theorem 3.4) that for $\omega$ steps of a computation of a machine performing a ...

**2**

votes

**0**answers

279 views

### A query on how to climb inaccessibles in £

I am investigating to what extent extensions of the librationist property or set theory £ may support relative inaccessible sets; see Librationist Closures of the Paradoxes and Elements of ...

**1**

vote

**0**answers

126 views

### Kripke frames as classes of partitions

Here's something I've been playing with off and on for a bit; I'm curious if anyone has seen it before.
For this question, a Kripke frame $K$ is a finite reflexive directed graph. (Reflexivity isn't ...

**14**

votes

**2**answers

519 views

### Scott-Solovay unpublished paper on ``Boolean valued models of set theory''

I have read some papers from 1970$^{th}$, and in some of them, the paper of Scott and Solovay on ``Boolean valued models of set theory'' is given as a main reference, with many references to the ...

**3**

votes

**3**answers

840 views

### Reverse Skolem's paradox

By using the Löwenheim–Skolem theorem & Mostowski collapse, in every model $V$ of $ZF+Con(ZF)$ there is a countable transitive set $M$ such that $(M,\in_M) \models ZF$. Is the following "converse" ...

**7**

votes

**3**answers

348 views

### Decision problem on triviality of intersection of two subgroups

What is known about the following decision problem?
Given two finite sets in a finitely generated group G,
decide whether the subgroups generated by them have trivial intersection.
Is this problem ...