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)

4
votes
0answers
96 views

Cohen's model yet again

It has been discussed already whether a countable OD set necessarily contains an OD element. See e.g. A question about ordinal definable real numbers . A negative answer was obtained in Archive for ...
8
votes
2answers
278 views

Normal subgroups of Aut(M)

Let $S$ be the set of all finite permutations of $\mathbb{N}$, i.e. they fix all but a finite set, and $A\subset S$ the set of all even permutations. Theorem The normal subgroups of $S_\infty$ are ...
-3
votes
0answers
49 views

Is ∃x.px=>q equal to ∃x.(px=>q)? [on hold]

I wondered if the sentences ∃x.px=>q equal to ∃x.(px=>q). I think they are equal because of the following example: The instance of the first sentence: If there exist a cow, then it ...
3
votes
1answer
129 views

Number of distinct variables used in axiomatizating (Classical) Propositional Logic

The first part of the present question is concerned with Classical Propositional Logic (CPL). The second part involves its fragments or alternative logical systems. There are in the literature many ...
6
votes
0answers
189 views

Tree property using side conditions

The following problems were asked during the high and low forcing workshop: Question 1. Can one force tree property at $\kappa^{++}$ for $\kappa$ singular using side conditions? Question 2. ...
0
votes
0answers
67 views

(∀x.(p(x)⇒∀x.p(x)) )= ((∃x.p(x))⇒(∀y.p(y)))? [closed]

In dealing with my homeowrk, someone has told me ∀x.(p(x)⇒∀x.p(x)) could be transformed to (∃x.p(x))⇒(∀y.p(y)) However, intuitively, this doesn't make sense to me, could anyone give me a ...
4
votes
0answers
77 views

Semi-algebraicness of cells involved in integrals of semi-algebraic functions

Background: In "Stability under integration of sums of products of real globally subanalytic functions and their logarithms", by R. Cluckers and D.J. Miller, it is shown that the integral of a ...
7
votes
1answer
208 views

Uncountable models of Kelley-Morse set theory with only a countable number of sets

The Kelley-Morse set theory can be thought as the "full-secondorderification of $\sf ZFC$", where we switch from sets to classes and allow the comprehension schema to include quantifiers on class ...
4
votes
0answers
222 views

Unbounded towers and combinatorial cardinal characteristics of the continuum

Update: Perhaps the question is too difficult. I would appreciate, thus, even just comments or related observations. This question assumes familiarity with combinatorial cardinal characteristics of ...
10
votes
1answer
320 views

Forcing PFA with ccc forcing

Is it consistent (from suitable large cardinals) that there is a ccc poset which forces PFA? This seems quite implausible to me. If we could force PFA via ccc forcing, the ground model would have to ...
5
votes
2answers
278 views

Why do we need a transitive model in forcing arguments?

One major approach to the theory of forcing is to assume that ZFC has a countable transitive model $M \in V$ (where $V$ is the "real" universe). In this approach, one takes a poset $\mathbb{P} \in M$, ...
7
votes
0answers
98 views

Choice and the Baire property in non-separable complete metric spaces

It's known to be consistent with ZF+DC that every subset of $\mathbb{R}$ has the Baire property (BP). (E.g. Shelah's model). If so, then every subset of every complete separable metric space has ...
5
votes
2answers
356 views

Consistent sentences with no arithmetically definable models

I've seen a construction of a sentence of first order logic that is consistent, but has no models with underlying set $\mathbb{N}$ and recursive functions and relations. Do there also exist consistent ...
5
votes
1answer
275 views

Comparing the sizes of uncountable sets of reals under AD

Working in ZF+AD, let $$\theta_0(X)=\min\{\alpha\in ON: \not\exists f: X\rightarrow \alpha\mbox{ surjective and OD}\}$$ be the least ordinal onto which $X$ does not surject in an OD way, for $X\...
19
votes
4answers
1k views

Nuances Regarding Naturality

It's frequently said, informally, that a natural isomorphism is one that doesn't depend on arbitrary choices. But the phrase "arbitrary choices" lends itself to different interpretations. Consider ...
9
votes
0answers
278 views

What ccc forcings add a Suslin tree?

In a comment to Miha's question in Forcing PFA with ccc forcing, I suggested that if such situation is even possible, it might be achieved by screwing with PFA by some ccc forcing (e.g. adding a Cohen ...
5
votes
1answer
150 views

Spreading sets - especially without choice

For what follows, I work in ZF+AD+DC. However, the questions below are not obviously trivial in ZFC, so I'm also interested in results in that system. Suppose I have a set $X\subseteq \mathbb{R}$. ...
5
votes
1answer
118 views

Dropping “generic” from the definition of forcing

Back when I was first learning about forcing and trying to understand the need to consider generic filters, I came up with the following question. Suppose we have a countable transitive model $M$. ...
3
votes
0answers
123 views

Compactness beyond extendibility

By a result of Magidor, $\kappa$ is extendible if and only if the infinitary $n$th-order logic over the language $L_{\kappa,\kappa}$ is compact for every $n < \omega$, where by compact, we mean ...
2
votes
1answer
138 views

How can two theories $T$ and $T+\phi$ be mutually interpretable?

Following Koellner in http://plato.stanford.edu/entries/independence-large-cardinals/, "a theory $T_1$ is interpretable in $T_2$ ($T_1 \leq T_2$) when, roughly speaking, there is a translation $\tau$ ...
7
votes
1answer
267 views

Proof-theoretic ordinals after liberalizing induction to $RCA_0$

This is kind of a follow-up to this question. For a class $\Gamma$ of second-order formulas (here either $\Sigma_n^0$ or $\Sigma_n^1$), let $X\Gamma$ be a formal theory consisting of $RCA_0$ together ...
1
vote
1answer
266 views

Further research on $\mathrm L_{\infty}$

In the mathoverflow question , "Godel's Constructible Universe in Infinitary Logics (A Possible Solution to $HOD$ Problem), Prof Hamkins answered user46667's question 2 What is $\mathrm L_{\infty}$...
5
votes
1answer
905 views

Surreals and NSA: some foundational issues

Surreals and NSA: some foundational issues. A. Leaving aside the whole internal machinery of surreals (with funny questions like is $\omega$ an entire number and if yes is it odd or even, simple, a ...
5
votes
0answers
144 views

Radin forcing and large cardinals

Assume $\kappa$ is a $(\kappa+2)$-strong cardinal and let $j: V \to M \simeq Ult(V, E) \supseteq V_{\kappa+2}$ witness this where $E$ is a $(\kappa, \kappa^{++})$-extender. Also let $u$ be the measure ...
14
votes
1answer
936 views

Can Vopenka's principle be violated definably?

One form of Vopenka's principle (a large cardinal axiom) states that no locally presentable category contains a full subcategory which is large (= a proper class) and discrete (= contains no ...
6
votes
2answers
534 views

An Extender is a Generalization of an Ultrafilter?

I'm not sure whether this belongs here or on math stackexchange, but I'll give a try here. I've heard that an extender is a generalization of an ultrafilter. This is not to say that an ultrafilter ...
4
votes
1answer
175 views

What countable ordinals are called $\kappa_\alpha$?

Jervell has a notation for countable ordinals up to the small Veblen ordinal using trees: • Herman Ruge Jervell, How to wellorder finite trees and get good ordinal notations, Berkeley Logic ...
9
votes
1answer
238 views

Cofinal monotone maps from $\omega^\omega$ to $\kappa^\kappa$

Given a cardinal $\kappa$ consider the set $\kappa^\kappa$ of all functions from $\kappa$ to $\kappa$, endowed with the partial order $f\le g$ iff $f(\alpha)\le g(\alpha)$ for all $\alpha\in\kappa$. ...
6
votes
0answers
100 views

On the use of Weisfeiler-Leman refinement in Babai's GI proof

This question is for those familiar with the methods behind Babai's recent proof that graph isomorphism can be decided in quasipolynomial time. I am a newcomer to the GI problem, so I apologize if my ...
7
votes
1answer
172 views

On the cardinal arithmetic of accessible categories

If $\lambda, \mu$ are regular cardinals, say that $\lambda \trianglelefteq \mu$ if $\lambda \leq \mu$ and $$\forall X, \, |X| < \mu \implies \mathrm{cf} (P_\lambda(X)) < \mu$$ Here $P_\lambda(X)...
6
votes
1answer
154 views

$\mathfrak b_a$: a new cardinal characteristic of the continuum?

By a partial function from $\omega$ to $\omega$ we understand a function $f:dom(f)\to\omega$ defined on an infinite subset of $\omega$. A family $\mathfrak F$ of partial functions from $\omega$ to $\...
5
votes
1answer
185 views

Ordinal-definable witnesses to the perfect set property?

This possibly a very basic descriptive set-theory question; if it is too basic for MO, feel free to migrate. Throughout we work in ZF+AD. My question is: If $A$ is an uncountable OD set of reals,...
5
votes
0answers
94 views

Preservation of Baumgartner's I-ultrafilters under various forcings

For $I\subset \mathcal{P}(2^\omega)$, an ultrafilter $U$ on $\omega$ is said to be an I-ultrafilter if for all $f:\omega \to 2^\omega$, there exists $A\in U$ such that $f''[A]\in I$ [Baumgartner]. In ...
57
votes
2answers
5k views

How would you solve this tantalizing Halmos problem?

$1-ab$ invertible $\implies$ $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? ...
17
votes
2answers
1k 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
1answer
320 views

History of the notation for substitution

One of the very common notations for syntactic substitution is $[\ /\ ]$. However, there seems to be an inconsistency in the literature about its usage. Many write $[t/x]$ for "substitute $t$ for $...
3
votes
1answer
218 views

A kind of saturation property related to forcing notions

Forcing is typically done over well-founded models. There are lots of good reasons for this, but it can feel confining at times. Fortunately, we can equally well force over non-well-founded models! It ...
8
votes
2answers
597 views

Difference between Laver's and Mathias's forcing

Mathias forcing consists of conditions of the form $(s,A)$ where $s$ is a finite subset of $\omega$, $A$ is an infinite subset of $\omega$ such that $\max(s) < \min(A)$ and $(s,A)\leq (t,B)$ iff $s\...
13
votes
1answer
367 views

Turing degree of finding independent formulas

In this Paper of D. Isaacson, it is proved that the true arithmetic($Th(\mathbb{N}$)) is the only $\omega$-consistent and complete extension of $Q$ (Robinson's arithmetic). This, together with the ...
5
votes
1answer
250 views

Why relative consistency results by forcing arguments are provable in finitistic metatheory

It is claimed in many textbooks that relative consistency results, such as $\text{Con}(\text{ZFC})\rightarrow\text{Con}(\text{ZFC}+2^{\aleph_0}\geq\aleph_2)$, are provable in the finitistic metatheory....
6
votes
1answer
299 views

What do we call this quantifier (“binder”)?

There's a quantifier ("binder", whatever), call it $\alpha$, defined as follows: $\alpha x.\tau$ is the (usually infinite) expression obtained by applying the substitution $\{x \mapsto \tau\}$ to the ...
42
votes
5answers
4k views

Is the Riemann Hypothesis equivalent to a $\Pi_1$ sentence?

1) Can the Riemann Hypothesis (RH) be expressed as a $\Pi_1$ sentence? More formally, 2) Is there a $\Pi_1$ sentence which is provably equivalent to RH in PA? Update (July 2010): So we have ...
3
votes
0answers
164 views

Construction of model of arithmetic from an arbitrary model

Let $M$ be a non-standard model of $PA$, $a\in |M|$ be an arbitrary non-standard number and $T$ be a theory of arithmetic. We want to choose a subset $M'\subsetneq M$ such that: $M'\models PA^-$ (or ...
6
votes
1answer
178 views

O-minimal spectrum is a spectral space

I'm trying to understand a proof on "Sheaves of Continuous Definable Functions" (Pillay, Anand. "Sheaves of continuous definable functions." The Journal of symbolic logic 53.04 (1988): 1165-1169.) ...
2
votes
1answer
130 views

Model existence and consistency conditions for $\Pi_1^0$ oracles

Let a $\Pi_1^0$ sentence be a sentence asserting that some given Turing machine never halts at the empty input tape. Let Q1 be a (potentially consistently lying) oracle for deciding $\Pi_1^0$ ...
4
votes
1answer
205 views

Spectrum Problem for Higher-Order Logic

Definitions. Given a sentence $\varphi$ of $n$th-order logic, we define the spectrum of $\varphi$ to be the set of cardinalities of finite structures that satisfy $\varphi$. A set $X\subseteq\mathbb ...
15
votes
12answers
5k views

The best text to study both incompleteness theorems

Hi! What text on both incompleteness theorems you would recommend for beginner? Specifically, I'm looking for the text with the following properties: 1) The proofs should be finitistic, in Godel's ...
5
votes
1answer
97 views

Complexity of integer programming with added predicates

A classical theorem in Integer Programming by Lenstra says that any integer system $$A x \le b$$ can be solved in polynomial time, where $A \in \mathbb{Z}^{m \times n}, x \in \mathbb{Z}^n, b \in \...
7
votes
1answer
194 views

Definability using rudimentary function

Denote by RUD the set of all rudimentary functions, together with the function that takes any set to its transitive closure. Assume that I know that a binary relation $R$ is definable by some ...
20
votes
4answers
943 views

Is there a non-Hopfian lacunary hyperbolic group?

The question's in the title and is easily stated, but let me try to give some details and explain why I'm interested. First, a disclaimer: if the answer's not already somewhere in the literature then ...