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)

13
votes
1answer
334 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
161 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
252 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 ...
41
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
141 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
156 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
116 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
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 ...
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
184 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
927 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 ...
10
votes
4answers
429 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 ...
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. ...
7
votes
1answer
136 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 $\...
13
votes
1answer
803 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 ...
12
votes
2answers
247 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 ...
6
votes
1answer
291 views

Discrete orderings on $\mathbb{Z}[x,y]$ that violate the universal theory of the integers

Working in the language of ordered rings, which we take to have type $(+ - \times < 0\, 1)$, can anyone give an example of a discrete ordering on the polynomial ring in two variables $\mathbb{Z}[x,...
5
votes
0answers
153 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 ...
10
votes
0answers
146 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 \...
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 ...
7
votes
1answer
253 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 ...
12
votes
15answers
8k views

undergraduate logic textbook

I am going to teach the standard undergraduate Logic course for math and engineering majors. What are good (bad) text-books and why. I have not taught that course for a while and wonder if there are ...
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 ...
6
votes
1answer
374 views

Essential incompleteness via diophantine formulas?

Work in the first order language of number theory, consisting of the symbols $\mathbf{0}$, $\mathbf{S}$, $\boldsymbol{+}$, and $\boldsymbol{\cdot}$, and let $Q$ denote Robinson's arithmetic. By a ...
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 ...
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$)($...
9
votes
1answer
316 views

Coherence and rewriting

In category theory there are numerous coherence theorems (https://ncatlab.org/nlab/show/coherence+theorem). One example is the Mac Lane's coherence theorem for monoidal categories. This and probably ...
10
votes
1answer
311 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$. ...
2
votes
2answers
367 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 "&...
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 ...
61
votes
39answers
12k views

nontrivial theorems with trivial proofs

A while back I saw posted on someone's office door a statement attributed to some famous person, saying that it is an instance of the callousness of youth to think that a theorem is trivial because ...
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 ...
7
votes
1answer
215 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 ...
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 ...
5
votes
1answer
368 views

Infinite blue eyed islanders puzzle

Can the well known blue eyed islanders puzzle be extended to an infinite number of islanders? In that puzzle, a set of $k$ islanders, each with either blue eyes or non-blue eyes, each knows the color ...
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 ...
1
vote
1answer
217 views

Sets of Vitali's type in models of $\mathsf{ZF}+\mathsf{GCH}$ where $V \neq L$

Consider sets of Vitali's type in models of $\mathsf{ZF}+\mathsf{GCH}$ where $V \neq L$. Are there sets of Vitali's type in both $L$ and $V \backslash L$? If so, is there any way one can distinguish ...
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....
3
votes
1answer
242 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 $...
31
votes
2answers
3k views

“Transitivity” of the Stone-Cech compactification

Let $\beta \mathbb{N}$ be the Stone-Cech compactification of the natural numbers $\mathbb{N}$, and let $x, y \in \beta \mathbb{N} \setminus \mathbb{N}$ be two non-principal elements of this ...
9
votes
5answers
311 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 ...
2
votes
6answers
2k views

Looking for a source for Intended Interpretation

Hao Wang writes: "The originally intended, or standard, interpretation takes the ordinary nonnegative integers $\{0, 1, 2, \ldots \}$ as the domain, the symbols $0$ and $1$ as denoting zero and one, ...
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 ...
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 ...
20
votes
2answers
2k views

Euler's mathematics in terms of modern theories?

Some aspects of Euler's work were formalized in terms of modern infinitesimal theories by Laugwitz, McKinzie, Tuckey, and others. Referring to the latter, G. Ferraro claims that "one can see in ...
7
votes
0answers
129 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\...