first-order and higher-order logic, model theory, set theory, proof theory, computability theory, formal languages, definability, interplay of syntax and semantics, constructive logic, intuitionism, philosophical logic, modal logic, completeness, Gödel incompleteness, decidability, undecidability, ...

learn more… | top users | synonyms (1)

126
votes
0answers
11k views

Ultrafilters and automorphisms of the complex field

It is well-known that it is consistent with $ZF$ that the only automorphisms of the complex field $\mathbb{C}$ are the identity map and complex conjugation. For example, we have that ...
29
votes
0answers
727 views

Bidi: A new cardinal characteristic of the continuum?

This question assumes familiarity with combinatorial cardinal characteristics of the continuum. Identify an infinite set $a\subseteq\mathbb{N}$ with its increasing enumeration. Thus, for each natural ...
28
votes
0answers
1k views

Peano Arithmetic and the Field of Rationals

In 1949 Julia Robinson showed the undecidability of the first order theory of the field of rationals by demonstrating that the set of natural numbers $\Bbb{N}$ is first order definable in $(\Bbb{Q}, ...
27
votes
0answers
1k views

Concerning the various proofs from the axiom of choice that R^3 admits of surprising geometrical decompositions into circles, skew lines and so on: can we prove in any instance that there are no Borel such decompositions? Or that AC is required?

This question follows up on a comment I made on Joseph O'Rourke's recent question, one of several questions here on mathoverflow concerning surprising geometric partitions of space using the axiom of ...
24
votes
0answers
886 views

Godel on recursion-theoretic hierarchies

At the end of his excellent article, "The Emergence of Descriptive Set Theory" (http://math.bu.edu/people/aki/2.pdf), Kanamori writes: "Another mathematical eternal return: Toward the end of his ...
21
votes
0answers
798 views

Supercompact and Reinhardt cardinals without choice

A friend of mine and I ran into the following question while reading about proper forcing, and have been unable to resolve it: Definition. A cardinal $\kappa$ is supercompact if for all ordinals ...
20
votes
0answers
379 views

Decidability of equality of elementary expressions

In the following definition the term expression is to be understood as a finite tree built from formal symbols without any predefined meaning assigned to them. Define the set $\mathcal{E}$ of ...
19
votes
0answers
443 views

Density of first-order definable sets in a directed union of finite groups

This is a generalization of the following question by John Wiltshire-Gordon. Consider an inductive family of finite groups: $$ G_0 \hookrightarrow G_1 \hookrightarrow \ldots \hookrightarrow G_i ...
17
votes
0answers
377 views

Are there lightweight foundations for arbitrarily extendable objects?

My experience with foundations is rather scant, but I've run into some types of objects that seem to resist the sort of set-theoretic encoding schemes via Kurowski tuples that are rather common for ...
16
votes
0answers
437 views

If all reals are generic, is the set of reals generic?

Let $W\subseteq V$ be two models of $\sf ZFC$ with the same ordinals. Is the following situation consistent: For every $x\in\Bbb R^V$ there is some $P_x\in W$ such that for some $G\subseteq P_x$ ...
16
votes
0answers
428 views

Souslin trees on the first inaccessible cardinal

This may be well-known or simply deducible from the existing theorems, but I didn't find an answer in my set theory books: Is there a model of $ZFC$ in which there are no $\kappa$-Souslin trees where ...
16
votes
0answers
794 views

Hrushovski's Construction

Zilber expressed a conjecture for $\aleph_{1}$- categorical theories (In the 80s). Zilber's Conjecture: The geometry of any $\aleph_{1}$- categorical structure is one of the following: (a) Trivial ...
16
votes
0answers
555 views

Antichains of Cardinals in ZF Without Choice…

With the Axiom of Choice, the cardinals form a nice linearly ordered "set". In the absence of the Axiom of Choice, the cardinals form a partially ordered "set". Broadly, I am wondering what ...
16
votes
0answers
478 views

Dual Borel conjecture in Laver's model

A set $X\subseteq 2^\omega$ of reals is of strong measure zero (smz) if $X+M\not=2^\omega$ for every meager set $M$. (This is a theorem of Galvin-Mycielski-Solovay, but for the question I am going to ...
15
votes
0answers
609 views

Souslin trees and weakly compact cardinals

In Souslin trees on the first inaccessible cardinal it is asked if it is consistent that there are no $\kappa-$Souslin trees at the least inaccessible cardinal $\kappa$. In this question I would like ...
14
votes
0answers
444 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 ...
14
votes
0answers
207 views

Can Gentzen-style proofs give omega-consistency and beyond?

In 1936, Gentzen famously showed that Primitive Recursive Arithmetic, plus the assumption that the ordinal $\epsilon_0$ is well-founded, is able to prove Con(PA). But of course, Con(PA) doesn't yet ...
13
votes
0answers
390 views

Ideas behind Gitik's solution of PCF conjecture

Recently Moti Gitik has refuted Shelah's PCF conjecture (see Short extenders forcings II ) by proving the following theorem: Theorem. Assuming the consistency of infinitely many strong cardinals, one ...
13
votes
0answers
592 views

Does every Aronszajn tree has a Suslin or a Special subtree?

Question: Does every $\omega_1$-Aronszajn tree contains a Suslin sub-tree or a special Aronszajn sub-tree? Recall that Suslin trees are $\omega_1$-trees (trees of height $\omega_1$, and countable ...
13
votes
0answers
580 views

Minimal resources for Undecidability of First-Order Logic: the number of variables

It is well-known that First-Order Logic (FO) with a full vocabulary (i.e., a countable numbers of unary predicate symbols, a countable number of binary predicate symbols, etc.) is undecidable. And it ...
13
votes
0answers
421 views

To what extent does (co)homology of groups made discrete depend on set theory?

There's a well-known paper by Milnor, "On the homology of Lie groups made discrete," that discusses the relation between the homology of a Lie group $G$ and the underlying discrete group $G^\delta$. ...
12
votes
0answers
261 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 ...
12
votes
0answers
325 views

Do all linear orders in this class have computable copies?

This is a question which has been bothering me now for quite some time. I've talked to a number of people about it, and we've shown that a few basic ideas can't work, but other than that haven't made ...
12
votes
0answers
665 views

Can a model of $V\neq L$ contain a class giving the $L$-ordering on all its sets?

This question is inspired by the excellent question by Douglas Ulrich When is $L$-Rank definable in inner models of $V=L$? Suppose $M \in L$ is a countable model of $ZFC$, and furthermore suppose $M ...
12
votes
0answers
283 views

How to measure the strength of Zermelo over bounded Zermelo?

Bounded Zermelo is Zermelo set theory with only bounded separation. It has the same strength as simple type theory or MacLane set theory or ETCS. It is a finitely axiomatized fragment of Zermelo, so ...
11
votes
0answers
184 views

Adding a saturated ideal

Is it consistent that there is no $\omega_2$-saturated ideal on $\omega_1$, but one is introduced by an $\omega_2$-closed forcing?
11
votes
0answers
333 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 ...
11
votes
0answers
153 views

Savings property: A transformation which turns nonnegative martingales into uniformly integrable ones

Background I work in a subfield of computability theory called algorithmic randomness. We have been using martingales as long as probability theory (going back to work of von Mises). However, since ...
11
votes
0answers
558 views

Can one exhibit an explicit Kuratowski infinite set without invoking Replacement?

The customary formulation of the Axiom of Infinity within Zermelo-Fraenkel set theory asserts the existence of an inductive set: a set $ I$ with $\varnothing\in I$ such that $x\in I$ implies ...
11
votes
0answers
275 views

What is the simplest known arithmetic definition of exponentiation?

For $n$ a natural number, let $E_n$ denote the set of bounded arithmetic formulas consisting of n alternating blocks of bounded quantifiers starting with an existential quantifier, followed by a ...
11
votes
0answers
477 views

Diagonal lemma from recursion theorem?

Does Gödel's diagonal lemma follow from Kleene's recursion theorem? I believe the converse is true, by an argument like the following. Let e ↦ θe be a bijection between ω and ...
11
votes
0answers
1k views

Reverse mathematics strength of identically zero polynomials are the zero polynomial

According to wikipedia, the statement "every polynomial over a countable field that is not the zero polynomial has only finitely many roots" is equivalent to RCA0 over RCA0* (which is called ERCA-0 in ...
10
votes
0answers
159 views

Generic $\mathbf{\Sigma}_3^1$-absoluteness for class forcings

In the paper "Generic Absoluteness" by Bagaria and Friedman (http://www.logic.univie.ac.at/~sdf/papers/bagfried.pdf) it is shown that in ZFC generic $\mathbf{\Sigma_3^1}$-absoluteness is false for ...
10
votes
0answers
194 views

c.c.c forcing notions and adding minimal generic reals

Is the following statement consistent: ``There is no non-trivial c.c.c forcing notion adding a minimal generic real''? The question is related to Prikry's question: Is it consistent that any ...
10
votes
0answers
286 views

On sentences true in all finite groups (revisited)

Let $w$ be a group word with variables $\bar x, \bar y$, where $\bar x=(x_1,\dots ,x_m)$ and $\bar y=(y_1,\dots ,y_n).$ I am interested in the following questions. (1) Is the sentence $(\forall\bar ...
10
votes
0answers
251 views

Is there a “hereditary” construction for $L$?

Recall that $L$, Godel's constructible universe is constructed by defining the following hierarchy: $L_0=\varnothing$, for a limit ordinal $\delta$, $L_\delta=\bigcup_{\alpha<\delta}L_\alpha$, and ...
10
votes
0answers
189 views

Maximality of linear orders in the Keisler order on theories

Recently Malliaris and Shelah (see their preprint http://math.uchicago.edu/~mem/Malliaris-Shelah-CST.pdf) have shown that theories with $SOP_2$ are maximal in the Keisler order. A preceding result of ...
10
votes
0answers
298 views

Automorphism group of the Turing degrees

It is conjectured that the automorphism group of the Turing degrees, $Aut(\mathcal{D})$, is trivial. However, to the best of my knowledge, the current state-of-the-art is that $Aut(\mathcal{D})$ is ...
10
votes
0answers
499 views

Existence (or non) of “definable” ultrafilters

This is a question which I suspect has an absurdly easy answer, but I'm not seeing it. Let $\langle\cdot,\cdot\rangle:\omega^2\rightarrow\omega$ be your favorite pairing map (for me, this is the ...
10
votes
0answers
231 views

full support iteration of semiproper forcings

Suppose $\langle P_\alpha,\dot{Q}_\alpha:\alpha\leq\omega_1\rangle$ is a full support iteration of (semi)proper forcings. Is the full limit $P_{\omega_1}$ (semi)proper or at least stationary set ...
10
votes
0answers
631 views

Does Fermat hold in non-standard models?

Let $n \geq 3$ be a natural number and $PA$ denote Peano arithmetic. Do we have $PA \models \forall x,y,z \geq 1 : x^n + y^n \neq z^n$? In other words, does Fermat's Last Theorem hold also in ...
9
votes
0answers
176 views

The Chang model after collapsing an inaccessible limit of Woodins

If $\kappa$ is an inaccessible cardinal and $G \subset \operatorname{Col}(\omega,\mathord{<}\kappa)$ is a $V$-generic filter, then in $V[G]$ the Chang model $L(\text{Ord}^\omega)$ satisfies "every ...
9
votes
0answers
157 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 ...
9
votes
0answers
221 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 ...
9
votes
0answers
268 views

Reinhardt cardinals and iterability

Work in $ZF$. Let $j:V\to V$ be a non-trivial elementary embedding which is iterable, so that we can iterate it and form models $M_\alpha, \alpha\in ON,$ with $M_0=V,$ and elementary embeddings ...
9
votes
0answers
176 views

Which forcing types preserve the axiom of determinacy?

Do we have some rudimentary understanding of some properties that a forcing can have in order to guarantee that it doesn't violate the axiom of determinacy? To be more specific, in Which forcings ...
9
votes
0answers
251 views

From Frege to Gödel - German equivalent?

I know this question does not quite fit here, but I felt it could best be answered here. I recently stumbled upon the book From Frege to Gödel, which is a sourcebook containing some of the most ...
9
votes
0answers
227 views

“Fraïssé limits” without amalgamation

All structures are countable with countable signature. Given a structure $\mathcal{A}$, the age of $\mathcal{A}$, $Age(\mathcal{A})$, is the set of structures isomorphic to finitely-generated ...
9
votes
0answers
351 views

“Hard” separation results in reverse mathematics (or similar)

This is a fairly broad question. In particular, I specify 5 questions (Q1, Q2.1, Q2.2, Q3, Q4) which for me all fall under one umbrella. Since this is unreasonably broad, I'm really interested in an ...
9
votes
0answers
221 views

Stability of analytic Zariski structures

Noetherian Zariski structures are introduced by Hrushovski and Zilber(1996). An analytic Zariski structure is a generalization of Noetherian Zariski structures, introduced by Zilber and Peatfield. ...