# Tagged Questions

**8**

votes

**0**answers

239 views

### From Frege to Gödel - German equivalent?

I know this question does not quite fit here, but I felt it could best be answered here. I recently stumbled upon the book From Frege to Gödel, which is a sourcebook containing some of the most ...

**4**

votes

**2**answers

370 views

### Reverse Math of High Sets?

Is there a standard principle in reverse math that is known to be equivalent (over $RCA_0$) to the existence of a set of high (Turing) degree? I'm interested in the general case, but would be happy to ...

**2**

votes

**0**answers

90 views

### Comparing two non-deterministic Turing equivalents as basis for Logic, request for references

I am designing a logic, that is simpler than FOL + PA. And I like to know if there already exists something in this direction.
First of all a non-deterministic Turing equivalent is defined by ...

**6**

votes

**0**answers

166 views

### “Fraïssé limits” without amalgamation

All structures are countable with countable signature.
Given a structure $\mathcal{A}$, the age of $\mathcal{A}$, $Age(\mathcal{A})$, is the set of structures isomorphic to finitely-generated ...

**1**

vote

**1**answer

114 views

### A question about consistent fragments of formalized mathematical theories with Natural Deduction

Ref to : Sara Negri & Jan von Plato, Structural Proof Theory (2001).
In Ch.6 : Structural Proof Analysis of Axiomatic Theories [page 126-on], they
give a method of adding axioms to sequent ...

**16**

votes

**3**answers

735 views

### Function extensionality: does it make a difference? why would one keep it out of the axioms?

Yesterday I was shocked to discover that function extensionality (the statement that if two functions $f$ and $g$ on the same domain satisfy $f\left(x\right) = g\left(x\right)$ for all $x$ in the ...

**7**

votes

**1**answer

238 views

### Fields of characteristic zero via ultraproducts

Is every noncountable field of characteristic zero the ultraproduct (using a non principal ultrafilter over the set of prime numbers) of fields of positive characteristic?

**1**

vote

**2**answers

128 views

### Quantifying simplicity, in the case of trigonometric and exponential functions

The pair of identities the sine and cosine of a sum of two terms as functions of the sines and cosines of the terms separately is not as simple as the identity that expresses the exponential of a sum ...

**4**

votes

**0**answers

135 views

### The theory of two finite linear orders

My colleague Matthias Baaz is looking for a reference for the following question (or possibly theorem):
Let T be the "theory of pairs of finite linear orders". That is, consider all finite ...

**8**

votes

**3**answers

297 views

### Who proved “sets in every generic are already in the ground model?”

Suppose $\mathbb{P}$ is a notion of forcing in the ground model $V$, and $X$ is a set which is in $V[G]$ for every $\mathbb{P}$-generic filter $G$. Then $X\in V$ already, by a fairly simple (if ...

**6**

votes

**1**answer

224 views

### Robinson Arithmetic and Composite Numbers

Define a number $n$ to be composite if it can be written as $a\cdot b$ for some $a,b$ where $a,b\neq 1$.
Define $p$ to be prime if $p=a\cdot b$ implies $a=1$ or $b=1$.
The theorem that every ...

**4**

votes

**0**answers

85 views

### Stabilization of recursive approximation in $PA^-+I\Sigma_1^0$

Over any model M of $PA^-+I\Sigma_1^0$. Suppose $A\in [T]$ where $T$ is a $\Delta_2^0$-tree and $A$ is one isolated path. Further, $A$ is regular, i.e. $\forall n A\upharpoonright n$ has a code in ...

**1**

vote

**2**answers

329 views

### Bishop's paradox of the countability of sequences

In 'Foundations of Constructive Analysis', in the notes at the end of the first chapter, Bishop poses an apparent paradox as an exercise for the reader:
Since every sequence of rational numbers ...

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

140 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

647 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

99 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

964 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

615 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

240 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

258 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

179 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

232 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

329 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

222 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

313 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

300 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

488 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

132 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

476 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

189 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

226 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

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