**-3**

votes

**0**answers

48 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

**1**answer

128 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

**0**answers

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

**0**answers

188 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

**0**answers

73 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

**1**answer

206 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

**0**answers

97 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

**2**answers

276 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

**4**answers

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

**0**answers

275 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

**1**answer

319 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

**1**answer

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

**0**answers

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

**1**answer

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

**1**

vote

**1**answer

265 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

**1**answer

149 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

**0**answers

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

**2**answers

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

**4**

votes

**1**answer

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

**0**answers

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

**1**answer

272 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

**1**answer

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

**1**answer

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

**1**answer

183 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

**1**answer

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**3**

votes

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

175 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

**4**answers

470 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

**0**answers

182 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

**0**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**2**answers

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

**0**answers

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

**0**answers

97 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

**1**answer

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

**2**answers

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

**2**answers

277 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

**0**answers

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

**2**

votes

**2**answers

196 views

### Interpreting peano arithmetic without parameters

I will accept an answer in the form of references to the literature about my question as well as any other information. I am quite ignorant of the area and that will be clear from my question.
I ...

**13**

votes

**1**answer

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