**2**

votes

**3**answers

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

**0**answers

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

**4**answers

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

**1**answer

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

**1**answer

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

**4**answers

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

**3**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**1**answer

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

**0**answers

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

**2**answers

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

**3**answers

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

**1**answer

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

**3**answers

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

**0**answers

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

**1**answer

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

**3**answers

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

**1**answer

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

**2**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**1**answer

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

**4**answers

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

**1**answer

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

**10**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**0**answers

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

**0**answers

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

**0**answers

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

**2**answers

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

**1**answer

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

**0**answers

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

**0**answers

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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

**1**answer

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