**30**

votes

**2**answers

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

**7**

votes

**1**answer

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

**-1**

votes

**0**answers

51 views

### Ddifference between deduct and deduce [closed]

In the context of logic, the term "deduction" was used as a way of thinking. I think, apparently, the verb of "deduction" should be "deduct", hence it is natural and reasonable to use the term ...

**2**

votes

**0**answers

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

**1**

vote

**1**answer

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

**8**

votes

**0**answers

153 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 the fact ...

**2**

votes

**1**answer

165 views

### What is the extension of the truth-table degrees to Baire Space called?

Recall that for sets $A, B \in 2^\omega$ that we say $A \leq_{tt} B$ if there is a total Turing functional $F \colon 2^\omega \to 2^\omega$ such that $F(B)=A$. This is called truth-table ...

**4**

votes

**0**answers

92 views

### Automorphism group of a structure without the SAP

A few years ago, a number of examples were given of Fraisse structures without the SAP in answer to the question raised in A Fraïssé class without the strong amalgamation property.
It is ...

**6**

votes

**0**answers

119 views

### Examples of analytic $\mathcal{I}$-mad families

If $\mathcal{I}$ is an ideal (proper and containing the finite sets) on $\omega$, call a family of subsets $\mathcal{A}\subseteq[\omega]^\omega$ $\mathcal{I}$-almost disjoint if for all distinct ...

**8**

votes

**0**answers

184 views

### Inner models and strongly compact cardinals

The following question is motivated by a result of Magidor that it is consistent that the least strongly compact cardinal is the least measurable cardinal.
Question. Assume $\kappa$ is a strongly ...

**4**

votes

**0**answers

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

**4**

votes

**1**answer

142 views

### Expressive power of $\omega$-order logic

According to the article Second-order and Higher-order Logic
from the Stanford Encyclopedia of Philosophy,
there is no need to stop at second-order logic; one can keep going. [...] we can allow ...

**0**

votes

**0**answers

118 views

### local analyticity of volumes of slices of semi-algebraic sets

I would like a reference and/or a simple proof using well-known results of the following, which I think is true. (If it's false, I'd like to know that as well of course -- and ideally a way to modify ...

**5**

votes

**1**answer

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

**10**

votes

**1**answer

260 views

### Precipitous ideals and GCH

It is well known that ZFC + "There is a measurable cardinal" is equiconsistent with ZFC + "There is a precipitous ideal on $\omega_1$." Is ZFC + "There is a measurable $\kappa$ such that $2^\kappa ...

**4**

votes

**0**answers

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

**1**

vote

**1**answer

131 views

### $\mathcal A\equiv\mathcal B\implies \mathcal A\cong\mathcal B$ for finite $\mathcal L$-structures where $\mathcal L$ is an infinite signature

Let $\mathcal L$ be an infinite signature and $\mathcal A$, $\mathcal B$ two finite $\mathcal L$-structures such that
for each first-order $\mathcal L$-sentence $\varphi$, $$\mathcal ...

**4**

votes

**1**answer

214 views

### Is it consistent that the gaps between cardinals $\kappa$ and $2^\kappa$ “get larger and larger”?

Is the following statement consistent in $\mathsf{ZFC}$?
For every ordinal $\beta$ there is an ordinal $\lambda_0$ such that for all ordinals $\lambda\geq\lambda_0$ we have ...

**10**

votes

**1**answer

351 views

### What Turing degree is this function?

Over at http://www.scottaaronson.com/blog/?p=2725#comment-1089004 we had a discussion of intermediate Turing degrees.
The following function came up:
Take Chaitin’s constant, and rearrange its ...

**-8**

votes

**1**answer

349 views

### Missing Axiom: There are no other axioms. Leads to a proof of CH within ZFC [closed]

I have come to the conclusion that there is often an implied axiom: There are no other axioms. Failure to explicitly state this axiom and to consider its consequences can result in the misleading ...

**0**

votes

**1**answer

154 views

### Can epsilon-induction be derived from the transitive closure operator?

I was wondering (and could not seem to prove or disprove) if epsilon-induction could be derived from the transitive closure operator for binary relations, if we do not have the Foundation Axiom.
The ...

**2**

votes

**2**answers

350 views

### What are the sense and reference of the propositions $R \notin R$, $R \in R$, where $R=\{x \mid x \notin x\}$ in Frege's Grundgesetze?

In the paper,
Aldo Antonelli and Robert May, Frege's new science, Notre Dame J. Form. Log. 41 (2000), no. 3, 242–-270, MR 1943495.
the authors give the following quote of Frege, from his paper ...

**2**

votes

**2**answers

178 views

### Henkin semantics for Second-order Logic

I know that the natural numbers can be categorically characterized in second-order logic with the standard semantics. However, I could not find an example of a non-standard Henkin structure (one that ...

**0**

votes

**0**answers

81 views

### What is the known weakest axiom system has Löb's derivability conditions?

We know that Peano Arithmetic satisfies Löb's derivability conditions, which is required in the proof of Gödel's 2nd incompleteness theorem. Is this the best result? If not, is there any known weaker ...

**14**

votes

**0**answers

345 views

### The axiom $I_0$ in the absence of $AC$

It is well-known that if $AC$ holds and if $j: L(V_{\lambda+1}) \to L(V_{\lambda+1})$ is a non-trivial elementary embedding with $crit(j) < \lambda,$
then $\lambda$ has countable cofinality (and in ...

**1**

vote

**1**answer

182 views

### Non-regular languages fulfilling the Pumping Lemma

Some non-regular languages don't yield to the Pumping Lemma ($L_1=a^nb^mc^m$ should work). But now consider the set of non-regular languages L only over the alphabet {a}. (Like $L_2=a^{n^2}$ or ...

**4**

votes

**2**answers

321 views

### Embedding property of weakly compact cardinals

One of the characterizations of $\kappa$ being a weakly compact cardinal is being inaccessible, and for every $\kappa$-model $M$, there is a [$\kappa$-model] $N$ and an elementary embedding $j\colon ...

**6**

votes

**1**answer

258 views

### moving up a consequence of PFA

The Proper Forcing Axiom (PFA) implies that every forcing which adds a subset of $\omega_1$ either adds a real or collapses $\omega_2$. Is it consistent that every forcing which adds a subset of ...

**6**

votes

**0**answers

188 views

### Nonexistence of generic objects over $L(\mathbb{R})$

A well known result (stated and credited to Todorcevic in "Semiselective Coideals", by Farah, Mathematika, 1997, but with antecedents going back to Mathias) says that, under the appropriate large ...

**9**

votes

**5**answers

307 views

### Probability theory without deductive closure

Human knowledge is not deductively closed. Uncertainty can arise from that just as much as from lack of brute facts. (When a Harvard graduate was reported to have thought that the earth is farther ...

**14**

votes

**1**answer

464 views

### Does Con(ZF + Reinhardt) really imply Con(ZFC + I0)?

The question is: if I assert in ZF that there exists a Reinhardt cardinal, do I really get a theory of higher consistency strength than when I assert in ZFC that there exists an I0 cardinal (the ...

**4**

votes

**1**answer

263 views

### Large cardinals without choice?

For any given extension $T$ of ZFC (or perhaps NBGC or something), we can ask whether there is an extension $T'$ of ZF which does not prove AC such that
$Con(T) \leftrightarrow Con(T')$
$Con(T) \to ...

**15**

votes

**4**answers

2k views

### Languages beyond enumerable

A language is a set of finite-length strings from some finite alphabet $\Sigma$.
It is no loss of generality (for my purposes) to take $\Sigma=\{0,1\}$; so a language is a set of bit-strings.
...

**4**

votes

**2**answers

234 views

### Is injectivity of $2^{(\ldots)}$ weaker than $\mathsf{GCH}$? [duplicate]

The following statement cannot be proven in $\mathsf{ZFC}$:
(S) : If $A, B$ are sets with $|A| < |B|$, then $2^{|A|} = |{\cal P}(A)| < |{\cal P}(B)| = 2^{|B|}$.
Obviously, ...

**4**

votes

**1**answer

209 views

### Does “Every infinite set is splittable” imply $\mathsf{AC}$? [duplicate]

We say an infinite set $X$ is splittable if there are $X_1, X_2\subseteq X$ with $X_1\cap X_2 = \emptyset$, $X_1\cup X_2 = X$ and there are bijections $\varphi:X_1\to X_2$ and $\psi:X_1\to X$.
Does ...

**7**

votes

**2**answers

379 views

### Difference between constructive Dedekind and Cauchy reals in computation

If the Axiom of Countable Choice (ACC)
$$ \forall n\in \mathbb{N} . \exists x \in X . \varphi [n, x] \implies \exists f: \mathbb{N} \longrightarrow X . \forall n \in \mathbb{N} . \varphi [n, f(n)] $$
...

**6**

votes

**1**answer

352 views

### Does the consistency strength hierarchy coincide with the “arithmetic consequence” hierarchy at ZF + Reinhardt?

In these slides (see especially slide 26), Steel emphasizes the phenomenon that for all known "natural" extensions of ZFC, the ordering by consistency strength agrees with the ordering by containment ...

**3**

votes

**1**answer

233 views

### Representation of meager sets in Cohen extensions

Let $M$ be a transitive model of ZFC and $c\in {}^\omega2$ a Cohen real over $M$. Let $A$ be a meager Borel subset of $^\omega2$ in $M[c]$. I would like to prove that there exists a meager Borel set ...

**6**

votes

**1**answer

199 views

### Theorem of Bukovsky characterizing ground models

It was mentioned in a talk that Bukovsky proved the following are equivalent for inner models $M \subseteq V$:
(1) There is a partial order $\mathbb P \in M$ and a $\mathbb P$-generic filter $G \in ...

**9**

votes

**0**answers

451 views

### Algebraic proofs of algebraic theorems about algebraically closed fields

It is well-known that the first order theory of algebraically closed fields admits quantifier elimination, whence the theory $ACF_p$ of algebraically closed fields of given characteristic $p$ is ...

**3**

votes

**1**answer

193 views

### “Lexicographic” ordering on ${\cal P}(\omega)$

For $A\neq B\in {\cal P}(\omega)$ we set $$\mu(A,B) = \min\big((A\setminus B)\cup (B\setminus A)\big).$$ We define $A < B$ if and only if $A \neq B$, and
$A = B\cap \mu(A,B)$ (that is $A$ is an ...

**1**

vote

**0**answers

39 views

### Quantifier elimination of pp-subgroups of modules

This is a model-theoretic questions. Let $M$ be a $R$-module. Our language will be the standard language of modules, i.e. the language of abelian groups together with an unary function symbol for ...

**8**

votes

**1**answer

223 views

### Must $L_\alpha$ be correct about well-foundedness?

If $R \in L_\alpha$ is a binary relation so that $L_\alpha$ thinks $R$ is well-founded, must $R$ truly be well-founded? (Edit) That is, if $L_\alpha$ thinks that every nonempty subset of the domain of ...

**5**

votes

**1**answer

189 views

### Easier Girard's paradox in a circular pure type system (PTS)

System U is an inconsistent PTS in that one has a term of type $\bot = \forall p\colon \ast \ldotp p$, and such a term is explicitly constructed in Hurkens' A Simplification of Girard's Paradox.
...

**22**

votes

**0**answers

454 views

### Can one divide by the cardinal of an amorphous set?

This question arose in a discussion with Peter Doyle.
It is provable in ZF that one can divide by any positive finite cardinal $k$: if $X \times \{1,\ldots,k\} \simeq Y \times \{1,\ldots,k\}$ then $X ...

**9**

votes

**1**answer

295 views

### Two questions about higher Souslin trees

Assume $V=L$ and let $\kappa$ be a Mahlo cardinal. Let $L[G]$ be the generic extension obatined by Mitchell forcing to make $2^{\aleph_0}=\aleph_2=\kappa.$
It is known that in the extension there ...

**6**

votes

**1**answer

199 views

### Fat stationary sets

Recall a stationary subset $S$ of a regular cardinal $\kappa$ is fat when for every $\alpha < \kappa$, and every club $C$, there is a closed set of order type $\alpha$ contained in $S \cap C$. It ...

**2**

votes

**1**answer

149 views

### Posets (partially ordered sets) in equational logic

I know about equational logic, cf. https://en.wikipedia.org/wiki/Lattice_(order)#Lattices_as_algebraic_structures, and understood that lattices are expressed equationally, i.e., in terms of equational ...

**2**

votes

**0**answers

120 views

### When do wide initial segments ruin admissibility?

Suppose $\alpha$ is admissible and $\beta<\alpha$. We know that $L_\alpha$ is an admissible set (by definition), but adding subsets of $\beta$ to $L_\alpha$ might break admissibility: while set ...

**15**

votes

**2**answers

628 views

### $\mathfrak{ufo}$: An unidentified combinatorial cardinal characteristic of the continuum?

An ultrafilter ornament is a chain of free filters on $\mathbb{N}$ that are not ultrafilters, whose union is an ultrafilter.
Let $\mathfrak{ufo}$ be the minimal cardinality of
an ultrafilter ...