**11**

votes

**0**answers

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

**6**

votes

**0**answers

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

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

**5**

votes

**1**answer

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

**5**

votes

**0**answers

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

**24**

votes

**4**answers

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

**11**

votes

**2**answers

807 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

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

**13**

votes

**1**answer

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

**5**

votes

**1**answer

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

**0**

votes

**0**answers

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

**-4**

votes

**0**answers

40 views

### Two easy questions of propositional logic [closed]

if M1VM2 is unsatisfiable can we say M1|=¬M2;
if M|=ψ then does ¬ψ|=¬Μ;
Please help

**2**

votes

**1**answer

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

**11**

votes

**2**answers

815 views

### Which recursively-defined predicates can be expressed in Presburger Arithmetic?

In Presburger Arithmetic there is no predicate that can express divisibility, else Presburger Arithmetic would be as expressive as Peano Arithmetic. Divisibility can be defined recursively, for ...

**5**

votes

**2**answers

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

**6**

votes

**2**answers

544 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

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

**108**

votes

**15**answers

19k views

### Why worry about the axiom of choice?

As I understand it, it has been proven that the axiom of choice is independent of the other axioms of set theory. Yet I still see people fuss about whether or not theorem X depends on it, and I don't ...

**1**

vote

**0**answers

174 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

74 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

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

**1**

vote

**0**answers

168 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$, ...

**46**

votes

**2**answers

4k views

### How would you solve this tantalizing Halmos problem?

1-ab invertible => 1-ba invertible has a slick power series "proof" as below, where Halmos asks for an explanation of why this tantalizing derivation succeeds. Do you know one?
Geometric series. In ...

**13**

votes

**6**answers

1k views

### The origins of forcing in mathematical logic and other branches of mathematics

As everyone knows, forcing was created by Cohen to answer questions in set theory.
Question 1. What are the first applications of set theoretic forcing in other branches of mathematical logic, like ...

**13**

votes

**6**answers

813 views

### Application of Fraïssé construction in set theory

As you know Fraïssé limit construction and its generalization, Hrushovski's construction, have many applications in model theory to build models with interesting property.
Now I would like to know ...

**6**

votes

**1**answer

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

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

**7**

votes

**0**answers

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

**3**

votes

**2**answers

279 views

### Impact of the axiom of replacement on finite sets

The axiom of replacement is usually used to prove the existence of large sets, to provide a reflection principle, for transfinite recursion… However, I am wondering how it affects finite sets. Let me ...

**1**

vote

**2**answers

247 views

### Can the Multiplicative Fragment of Linear Logic be shown to be non-truth-functional?

The short form of my question is: Can we find two formulae (in the multiplicative fragment of linear logic (MLL), that is, without additives or exponentials) A and B such that (1st) A is provable and ...

**4**

votes

**1**answer

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

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

**9**

votes

**0**answers

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

**95**

votes

**12**answers

19k views

### Knuth's intuition that Goldbach might be unprovable

Knuth's intuition that Goldbach's conjecture (every even number greater than 2 can be written as a sum of two primes) might be one of the statements that can neither be proved nor disproved really ...

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

**6**

votes

**1**answer

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

**5**

votes

**0**answers

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

**7**

votes

**1**answer

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

**8**

votes

**4**answers

718 views

### Why is alpha-equivalence in untyped $\lambda$-calculus substitutive?

This is something all introductory texts seem to avoid proving, and many even avoid stating.
We consider untyped $\lambda$-terms on some countably infinite alphabet. If $x$ is a variable and $p$ is ...

**1**

vote

**0**answers

25 views

### embdedding standard models of PA into nonstandard models [migrated]

Maybe it's well known to experts, but is there always an embedding $f$ of the standard model of Peano arithmetic into a nonstandard model? By Peano arithmetic I mean its first-order version, with the ...

**3**

votes

**0**answers

137 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

62 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

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

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

**15**

votes

**8**answers

2k views

### What is a logic ?

I am not interested in the philosophical part of this question :-)
When I look at mathematics, I see that lots of different logics are used : classical, intuitionistic, linear, modal ones and weirder ...

**19**

votes

**2**answers

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

**5**

votes

**4**answers

4k views

### About the proof of the proposition “there exists irrational numbers a, b such that a^b is rational”

What does the classical proof of the proposition "there exists irrational numbers a, b such that $a^b$ is rational" want to reveal? I know it has something to do with the difference between classical ...

**6**

votes

**2**answers

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

**2**

votes

**1**answer

191 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

155 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$ ...