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)

2
votes
3answers
335 views

Show that Z2 is not conservative over PA

It is well-known that $\mathsf{ACA}_0$ is a conservative extension of PA. I assume this theorem gets a lot of attention because $\mathsf{Z}_2$ is not conservative over PA. Thus there ought to be ...
2
votes
0answers
139 views

Algebras admitting quantifier elimination

I apologize if this question is meaningless or trivial: What are examples of Algebras admitting quantifier elimination? Especially are there Groups admitting quantifier elimination? I need to say ...
5
votes
4answers
633 views

“Introduction to mathematical logic” book from a formalist perspective

I'm looking for books that introduce the reader to mathematical logic assuming the perspective of a formalist. I've found that many books are more or less written for the platonist - like Kunen's ...
4
votes
1answer
98 views

Models of intuitionistic linear logic that reflect the resource interpretation

I am interested in models of intuitionistic linear logic, that is, the logic that you get if you take classical linear logic and restrict the set of operators to $\otimes$, $1$, $\multimap$, $\times$, ...
24
votes
1answer
2k views

A preprint of Sela concerning the work of Kharlampovich-Miyasnikov

Yesterday, Z. Sela published a preprint in arXiv which claims that the solution of Olga Kharlampovich and Alexi Miyasnikov for the Tarski problem on decidablity of the first order theories of free ...
22
votes
4answers
958 views

What is the definition of a large cardinal axiom?

In different books one can find different implicit definitions for a large cardinal axiom. My question is that which one of these definitions are more popular or standard amongst set theorists? Any ...
5
votes
3answers
611 views

PFA: A New Godel's Program & A New Large Cardinal Ladder (Updated)

We know $PFA$ implies $2^{\aleph_0}=\aleph_2$. Q1. What does $PFA$ say about other values of continuum function? Does proper forcing axiom carry any further information about values of continuum ...
7
votes
1answer
239 views

Are superstrong stronger than strongly compact cardinals? (or vice versa)

In the last part of Kanamori's excellent "The Higher Infinite" there is a small diagram about the strength and consistency strength of some major large cardinal axioms. Below supercompact cardinals ...
8
votes
1answer
254 views

What is the proof-theoretic ordinal of PA + Con(PA), PA + Con(PA + Con(PA)) etc., and why?

I seem to remember having read that the proof-theoretic ordinal (sup of ordinals the theory can prove well-ordered) of $\mathsf{PA} + \mathsf{Con}(\mathsf{PA})$ is the same as that of $\mathsf{PA}$, ...
4
votes
1answer
177 views

Why the axiomatic rank of the variety of groups is equal to three?

I am thankful of Anton Klyachko who introduced axiomatic rank to me: the axiomatic rank of a variety is the minimum number of variables which we need to define that variety by identities. It seems ...
8
votes
1answer
230 views

Genericity by names

If $P$ is a notion of forcing in $M$, then $G$ is a $P$-generic filter over $M$ if $G\subseteq P$ is a filter, and for every $D\in M$ which is a dense subset of $P$, $G\cap D\neq\varnothing$. ...
4
votes
1answer
327 views

Fundamental Problems in Mathematics that, without Computer Sciences, would not be resolved? [closed]

Could you please give examples of fundamental questions in mathematics (let us say, pure mathematics) which were resolved fundamentally by the use of computers? More precisely, are there examples that ...
2
votes
1answer
220 views

Elementary proof of bounds on factor polynomials

The question Getting a bound on the coefficients of the factor polynomial got very nice answers on Gelfond's theorem. But for work on proof theory of arithmetic I want a proof in arithmetic. The ...
1
vote
0answers
119 views

Dedekind reals in heyting valued models

Let $V^{H}$ be a Heyting valued model of intuitionistic set theory. What conditions does $H$ have to satisfy in order for the following claim to hold? (where $\| \phi(u) \| \in H$ is the truth value ...
4
votes
1answer
308 views

Why is adopting Russell's Axiom of Reducibility as strong as eliminating the Ramified Hierarchy?

In order to respond to concerns of impredicativity, Bertrand Russell developed a system of ramified second-order logic, which is like regular second-order logic except the comprehension schema is ...
8
votes
0answers
299 views

“Hard” separation results in reverse mathematics (or similar)

This is a fairly broad question. In particular, I specify 5 questions (Q1, Q2.1, Q2.2, Q3, Q4) which for me all fall under one umbrella. Since this is unreasonably broad, I'm really interested in an ...
23
votes
2answers
484 views

When does the choice of the generic matter?

It is a somewhat curious phenomenon that, in forcing arguments, one usually doesn't care about any particular properties of the generic filter being used (this isn't strictly true; there are cases ...
0
votes
3answers
131 views

Negated varieties and their relatively free algebras

During the past days, I asked some questions in order to gain a clear understanding of the notion of "free algebras". I suppose that the question below is the most clear image of the concept I have ...
6
votes
1answer
97 views

Is 0' of PA degree relative to a non-low set?

Definitions: A set $X$ is of PA degree relative to a set $Y$ if every infinite $Y$-computable binary tree has an infinite $X$-computable path. A set $X$ is low if $X'$ is computable from ...
4
votes
3answers
248 views

The existence of an algebra whose set of identities and first order theory are equivalent

Is there an algebra $A$ (for example a group) such that $Th(A)$ is logically equivalent to $id(A)$? In other words, is there an algebra $A$ such that $$ Mod(Th(A))=Var(A)? $$ Clearly finite algebras ...
2
votes
0answers
92 views

What are natural examples of non-relativizable proofs? [duplicate]

As I understand it, a proof that P=NP or P≠NP would need to be non-relativizable (as in recursion theory oracles). Virtually all proofs seem to be relativizable, though. What are good examples of ...
0
votes
1answer
148 views

relatively free groups in $Var(S_3)$

Suppose $S_3$ is the symmetric group of order 6. Which elements of the variety $Var(S_3)$ are relatively free? This question is related to my previous question Relatively free algebras in a variety ...
25
votes
3answers
1k views

Latest stand of core model theory?

What is the "strongest" core model to this day? In particular, how far are we from a core model for supercompact cardinals? There are rumors of some notes from a workshop in 2004: ...
10
votes
1answer
279 views

Harvey Friedman's strict reverse mathematics vs. Cook-Nguyen's V$^0$

Harvey Friedman posted several manuscripts [1] proposing a program for "strict" reverse mathematics, in the sense that the base theory should be mathematically natural and coding-free. In them he ...
3
votes
2answers
109 views

Isomorphism of a chain of structures

Consider an elementary chain of models of some first-order theory $T$: $$ (M_\alpha)_{\alpha < \kappa}, M_\alpha \prec M_\beta \; {\rm for} \; \alpha < \beta .$$ Let also $(N_\alpha)$ be ...
0
votes
0answers
104 views

What references cover finitary systems of Ramified Analysis with transfinite levels?

The ramified theory of types, invented by Bertrand Russell, is a way of dealing with impredicativity by breaking the comprehension schema of second-order logic into levels. The comprehension schema ...
11
votes
2answers
473 views

Can we force the existence of this function?

I want to see if it is possible to force the existence of a function $F:\aleph_2 \times \aleph_2\rightarrow \aleph_1$ such that: a) $F(a,b)=F(b,a)$, for all $a,b\in \aleph_2$ and b) for all ...
3
votes
1answer
68 views

Jump of strongly hyperhyperimmune degrees and DNR relative to 0'

A function f is diagonaly non-recursive (DNR) if for every Turing index $e$, $f(e) \neq \Phi_e(e)$. A set is strongly hyperhyperimmune if there is no r.e. set of disjoint r.e. set intersecting it. ...
3
votes
0answers
187 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 ...
-4
votes
1answer
238 views

Is there a precise definition of “mathematical formula”? [closed]

In the Wikipedia article for Formula (which has no references), it is claimed that: "The informal use of the term formula in science refers to the general construct of a relationship between given ...
2
votes
4answers
178 views

Seemingly ill-founded recursion and the recursion theorem

The following line well-defines a family of subsets $\{S_i\}_{i\in\mathbb N}$ of $\mathbb N$: $n\in S_i$ iff $n=2i$ or $\exists j<i$ such that $n\in S_j$. The following line does not: ...
2
votes
1answer
149 views

why the difference between terms and propositional variables?

Reading some old logic texts (written around 1930) I noticed that these texts make no difference between propositional variables and terms. They do make difference between identity and truthvalue ...
24
votes
10answers
2k views

Can We Decide Whether Small Computer Programs Halt?

The undecidability of the halting problem states that there is no general procedure for deciding whether an arbitrary sufficiently complex computer program will halt or not. Are there some large $n$ ...
2
votes
0answers
95 views

Stability of analytic Zariski structures

Noetherian Zariski structures are introduced by Hrushovski and Zilber.(1996) An analytic Zariski structure is a generalization of Noetherian Zariski structures, introduced by Zilber and Peatfield. ...
10
votes
1answer
225 views

Is “approximate categoricity” absolute?

Let $T$ be a countable first-order theory, and assume that $T$ has exactly one atomic model up to isomorphism in every uncountable cardinality. (By "atomic" I mean a model which omits the ...
5
votes
1answer
289 views

Is this system identical to S4.4?

Consider the normal modal logic system $\mathbf{TAR1}$ given by $\mathbf{T}$ plus the following axiom: $$\mathrm{AR1}: \lozenge \square p \rightarrow (\square p \lor \square (p \rightarrow \square ...
10
votes
1answer
249 views

Reducibility of polynomials maps

Motivated by this question. Let $f \in \mathbb{Q}[x]$ or$f \in \mathbb{Z}[x]$ . Consider the sequence $f(x),f(f(x)), \ldots f^n(x)$. If some $f^k(x)$ is reducible, the rest iterates will be ...
6
votes
0answers
113 views

cut-elimination for infinitary logic

Takeuti (1987, 223) deduces a cut-elimination theorem for infinitary logic from the corresponding soundness-and-completeness theorems. However, is there a way to adapt the basic Gentzen-style ...
3
votes
0answers
105 views

Peano (Dedekind) categoricity

What is the smallest fragment of second order logic such that $Th(\mathbb{N})$ in that logic is categorical (only one model, namely natural numbers, up to isomorphism). For example, can we do this in ...
1
vote
0answers
241 views

What is the role of the (formalized) omega rule in Ramified Analysis?

In the 1960's, Feferman and Schutte did groundbreaking proof-theoretic work to find out the strength of predicative systems of second-order arithmetic. They used the ramified theory of types, a ...
3
votes
2answers
240 views

What is the proof-theoretic ordinal of Hyperarithmetical Comprehension?

As I discuss in my answer here, it seems to me that Solomon Feferman shows, on pages 10-11 of his seminal 1964 paper "Systems of Predicative Analysis", that if you consider predicative second-order ...
6
votes
1answer
239 views

Recursive ordinals and the minimal standard model of ZF

Does the minimal standard model of ZF contain all recursive ordinals or is it limited (probably by the proof theoretic ordinal of ZF as I suspect but cannot prove)? Paul J. Cohen's definition of the ...
0
votes
0answers
73 views

Uncountable models of set theory [duplicate]

Assume we have a countable transitive model of set theory which satisfies some set of first-order axioms $T$. Is it possible to get from this a model $\mathcal{M}$ of set theory which satisfies the ...
4
votes
0answers
223 views

About “natural proof” of Razborov and Rudich

The famous "Natural Proof" paper ,http://www.cs.umd.edu/~gasarch/BLOGPAPERS/natural.pdf , ‎of Razborov and Rudich gives a barrier for any proof that try to separate P and NP. It mainly shows that if ...
3
votes
1answer
97 views

Soundness of modal logics which contain the reflection rule

Let $ML$ be a modal logic which contains the Reflection Rule (from $\vdash\Box F$ infer $\vdash F$). For a modal formula $F$, let $H(F)=\{\ \Box G\rightarrow G~|~\Box G$ is a subformula of $F\}$. A ...
4
votes
1answer
204 views

Bad subforcings of nice forcing notions

Let $\mathbb{P}$ and $\mathbb{Q}$ be two forcing notions. Recall that we say $\mathbb{Q}$ is a subforcing of $\mathbb{P}$ if there exists a regular embedding $\mathbb{Q} \to \text{r.o.}(\mathbb{P}).$ ...
10
votes
1answer
339 views

V=HOD & The Height of the Large Cardinal Tree

As we know the assumption $V=L$ adds a restriction on the height of the large cardinal tree. Also there is a strict border like $0^{\sharp}$ exists such that all large cardinal axioms which are ...
2
votes
1answer
175 views

Variable numerical quantifiers

I posted a similar question on math stack exchange with the same title, but I didn't get a helpful response. I am trying to develop a logical language where one can express variable numerical ...
1
vote
1answer
125 views

Real closed fields in HOD

Let $\mathfrak{M}$ be a model of set theory, and consider HOD (the hereditarily ordinal definable elements) of $\mathfrak{M}$. Let $K$ be any algebraically closed field in HOD of zero characteristic ...
6
votes
1answer
381 views

Is there a suitably generalized Baire property for topological spaces of arbitrary cardinalities?

Is there some suitable generalization to the notion of Baire property for topological spaces of arbitrary cardinalities which satisfies the following condition: The meager sets are sets which are ...