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)

0
votes
0answers
16 views

What is a universal tree?

I came across some slides talking about the Hrushovski construction. One of the examples was the construction of a "universal tree". I was curious because the collection of finite trees does not ...
5
votes
0answers
178 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 ...
-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
130 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 ...
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 ...
6
votes
0answers
192 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. ...
4
votes
0answers
78 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
212 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 ...
7
votes
0answers
101 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
280 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$, ...
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
279 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 ...
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
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
139 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$ ...
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
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
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 ...
5
votes
2answers
357 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 ...
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 ...
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 ...
5
votes
1answer
276 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\...
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 $\...
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)...
5
votes
1answer
186 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,...
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$. ...
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 ...
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 ...
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 $...
5
votes
1answer
251 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
300 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 ...
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 ...
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$ ...
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.) ...
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 ...
2
votes
1answer
176 views

Transfer with minimal choice

Let FUF postulate the existence of a Free UltraFilter on $\mathbb{N}$ and ACC the axiom of countable choice. Consider the superstructure on $\mathbb{R}$ and its inclusion in the bounded ultrapower. ...
10
votes
4answers
471 views

Let's keep adding once undecidable statements

This present thread is inpired by the previous thread the true reason of the incompleteness of formal systems. I have the following intuitive idea: Gödel's second incompleteness theorem states that a ...
10
votes
0answers
187 views

Example of $\aleph_1$-categorical linear order

Is it possible to have an $L_{\omega_1,\omega}$-sentence $\phi$ in a vocabulary that includes $<$ that satisfies the following? $<$ is a linear order on a definable subset; $\phi$ is $\aleph_1$...
7
votes
0answers
131 views

Yoneda embedding and Horn sentences

The following is taken from Borceux and Bourn's Mal'cev, Protomodular, Homological, and Semi-Abelian Categories. Metatheorem 0.1.3. Let $\mathcal P$ be a statement of the form $\varphi\implies \...
7
votes
1answer
147 views

Is there a Fraisse limit whose automorphism group contains dense but not generic automorphisms?

It is well known that $\mathsf{Aut}(\mathbb{Q},<)$ has generic automorphisms (i.e., a comeagre conjugacy class under the diagonal action) but does not admit ample generics. The automorphism group $\...
5
votes
0answers
155 views

Proper full submodels of full models of type theory

Let $N$ be the standard full model of the simply typed lambda calculus with infinite base type $o$ and let $X$ be an infinite and coinfinite subset of $N(o)$. I want to know if there's a full ...
3
votes
1answer
126 views

Rigid structure which is generically homogeneous

Is it possible to have a structure $T$ in some language which is rigid in $V$, but in a cardinal-preserving extension $T$ is homogeneous (in a suitable sense of the word)? If this is not possible, is ...
12
votes
2answers
271 views

Can noncomputable sets be distinguishable in $RCA_0$?

Say that a set $X\subseteq\omega$ is distinguishable if there is some Turing machine $\Phi_e$ which, when given two sets exactly one of which is $X$, can determine which set is $X$. Formally, $X$ is ...
1
vote
0answers
137 views

Full epsilon-induction and bounded epsilon-induction

epsilon-induction is the scheme: $\forall x(\forall y\in x\varphi (y)\rightarrow \varphi (x))\rightarrow \forall x\varphi (x)$. Let "bounded epsilon-induction" be the above scheme, but only for ...
1
vote
0answers
98 views

Can Basic Law $V$ be derived from Leibniz's Law in Second-Order Logic without comprehension principles?

Consider Basic Law $V$: $\hat x$$F$($x$)=$\hat x$$G$($x$)$\equiv$($\forall$$x$)($F$$x$$\equiv$$G$$x$) At first glance, it seems to have the same form as Leibniz's law $x$=$y$$\equiv$($\forall$$F$)($...
10
votes
1answer
317 views

When are generic models not too wild?

This is a question related to ideas raised in http://arxiv.org/abs/1410.1224 and http://arxiv.org/pdf/1405.7456.pdf. Basically, the idea is the following: Suppose I have a first-order theory $T$. ...
31
votes
2answers
4k views

Why is this new result such a big deal?

This popular article reports a recent result in reverse mathematics, showing that a certain theorem in Ramsey theory is provable from RCA$_0$, the base theory in SOSOA. Then there are a bunch of ...
8
votes
2answers
293 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 ...
2
votes
0answers
83 views

Are Braid Groups with Finitely many Generators NIP?

I am curious what braid groups (strings in $\mathbb{R}^3$) are NIP. Consider the following: Let $B_\mathbb{N}$ be braid group with "braids" indexed by the natural numbers (alternatively, the direct ...