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)

3
votes
1answer
152 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
270 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
205 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
271 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
151 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
120 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
162 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
188 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
171 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
436 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
155 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
128 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
137 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
154 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
122 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
251 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
136 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
95 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
312 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 ...
7
votes
1answer
217 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
80 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
2answers
194 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
1answer
349 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 ...
2
votes
1answer
168 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 reducibility....
4
votes
0answers
103 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 ...
7
votes
0answers
130 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 $A,B\...
8
votes
0answers
199 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
1answer
197 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
1answer
149 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
0answers
128 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
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 \...
10
votes
1answer
271 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
0answers
183 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
1answer
143 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 A\models\varphi\...
4
votes
1answer
221 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 $2^{\aleph_{\...
10
votes
1answer
363 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
1answer
363 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
1answer
161 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
2answers
369 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
2answers
191 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
0answers
83 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
0answers
389 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
1answer
187 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
2answers
333 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 M\...
6
votes
1answer
262 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 $\...