**2**

votes

**1**answer

514 views

### Can Turing machines clarify mathematical, philosophical, and physical existence?

From Harvey Friedman's manuscript on "Order Invariant Relations and Incompleteness":
DEFINITION 4.4. A $\Pi_1^0$ sentence is a sentence asserting that some given Turing machine never halts at the ...

**10**

votes

**1**answer

325 views

### Uniform elimination of imaginaries

Does the following principle follow from uniform elimination of imaginaries?
For every formula $\varphi(x;y)$ there is a formula $\vartheta(x;z)$ such that
$$\forall y\;\exists^{=1}z\;\forall x\;\...

**3**

votes

**1**answer

163 views

### Theories of arithmetic from recursively inseparable sets

Edit: all sets / theories considered below are supposed to be recursively enumerable, although I'd also be interested in any possible generalizations to non-enumerable theories.
In the comments on ...

**2**

votes

**6**answers

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

**7**

votes

**1**answer

304 views

### Relationship between first and second incompleteness theorems

By my understanding, Gödel's first incompleteness theorem says that any theory with sufficient1 interpretability strength is essentially incomplete, that is, any consistent recursively enumerable ...

**1**

vote

**1**answer

176 views

### In what sense is the “descending chain principle” for ordinals less than $\epsilon_0$ 'infinitary?

In the introduction to his paper "Assignment of Ordinals to Terms for Primitive Recursive Functionals of Finite Type", W.A. Howard writes:
Gentzen...showed that the consistency of first order (...

**3**

votes

**2**answers

331 views

### Determinacy of (infinite, possibly loopy) combinatorial games

I am looking for references and hopefully enlightening proofs of the following statement(s) concerning the determinacy of not-necessarily-well-founded (i.e., possibly infinite, possibly loopy) ...

**5**

votes

**1**answer

169 views

### Deciding isomorphism between structures which interpret in the pure set

I am interested in the following decision problem:
Given descriptions of two relational structures $A,B$ which interpret in the pure set $\mathbb N=(\{0,1,2,\ldots\},=)$, decide whether $A$ and $B$...

**8**

votes

**0**answers

191 views

### ω-categorical, ω-stable structure with trivial geometry not definable in the pure set

Briefly, my question is the following.
does every countable ω-categorical, ω-stable structure with
disintegrated strongly minimal sets interpret in the countable pure set?
By countable pure set I ...

**6**

votes

**1**answer

278 views

### $\omega$-colorings of $\kappa^2$

Let $\kappa\le 2^{\aleph_0}$ be an infinite cardinal. We have a collection of functions $\{f_i|i<\kappa\}$ such that $f_i:i\rightarrow \omega$ and the collection is "triangle-free", i.e. there are ...

**3**

votes

**0**answers

445 views

### What's Reeb's take on naive integers?

Georges Reeb's "claim Q" is the statement that "naive integers don't fill up $\mathbb{N}$". To anyone familiar with model theory this could easily be interpreted as the existence of nonstandard models ...

**7**

votes

**3**answers

483 views

### Is there research on Machine Learning techniques to discover conjectures (theorems) in a wide range of mathematics beyond mathematical logic?

Although there already exists active research area, so-called, automated theorem proving, mostly work on logic and elementary geometry.
Rather than only logic and elementary geometry, are there ...

**6**

votes

**1**answer

170 views

### Heyting algebras originating from directed graphs

The category RefGph of reflexive directed graphs is the functor
category $\hat{∆}_1=\mbox{Fun}(∆^◦_1,$Set), where $∆_1$ is
the simplex category truncated at level 1.
Hence the poset Sub(X) of ...

**0**

votes

**0**answers

34 views

### How to convert an expression to conjunctive normal form for Maximum-2-satisfiability?

I have a simplified Boolean expression almost ripe for maximum-2-satisfiability:
$(A\lor \neg B)\land(A\land C)\land(D\lor \neg A)$
In other words, I want to find the assignment of variables so that ...

**3**

votes

**1**answer

264 views

### Simplest PA theorem whose proof requires encoding of sequences even though the statement itself doesn't

What is the simplest number-theoretic theorem whose proof requires exponentiation or finite sequences/sets (so any proof in Peano Arithmetic would need to use encodings of such things using e.g. Gödel'...

**4**

votes

**0**answers

305 views

### About the “semi-classical” view of Prof. Weaver and Prof. Feferman [closed]

In the thread "Is platonism regarding arithmetic consistent with the multiverse view in set theory?", Prof. Hamkins writes:
The view you are suggesting is something close to what is held by ...

**12**

votes

**2**answers

596 views

### Is there a consistent arithmetically definable extension of PA that proves its own consistency?

I asked this on stackexchange with no answer.
The negation would be the obvious generalization of Gödel's second incompleteness from r.e. extensions of PA to any arithmetically definable extension of ...

**10**

votes

**1**answer

406 views

### “Set theory” founded on lists rather than sets

On a computer, sets are often represented rather "indirectly / implicitly", e.g. in terms of some properties that they or their members satisfy. But some sets can be represented more "directly / ...

**0**

votes

**1**answer

198 views

### Does every ultrafilter contain sets of sup-measure $0$?

Let $\mathbb{N}$ be the set of positive integers and for $A\subseteq {\mathbb{N}}$ set $$m(A) = \text{lim sup}_{n\to\infty}\frac{|A\cap\{1,\ldots,n\}|}{n}.$$
Does every ultrafilter ${\cal U}$ on $\...

**6**

votes

**4**answers

529 views

### Direct axiomatization of ordinal and cardinal numbers

Again, this question is related (**) to a previous one:
in standard books on basic set theory, after stating the axioms of ZFC, ordinal numbers are introduced early on. Afterwards cardinals appear: ...

**2**

votes

**1**answer

129 views

### Can tests for the convergence and divergence of series be used to create undecidable sentences?

Let f(k) be a recursive function which maps the set of positive integers into itself. Let T be a formalized theory which is axiomatizable and contains Peano's Arithmetic as a sub-theory. For example, ...

**2**

votes

**1**answer

167 views

### Some very weak statements on choice

This is a follow-up question to Does $|(X\times\{0\}) \cup (X\times\{1\})| \leq |X|$ for $X$ infinite imply ${\sf AC}$?
Consider the statements
$(\text{S}1)$ For any infinite set $X$ there ...

**2**

votes

**1**answer

162 views

### Does $|(X\times\{0\}) \cup (X\times\{1\})| \leq |X|$ for $X$ infinite imply ${\sf AC}$?

Consider the statement
For any infinite set $X$ there is an injection $\varphi$ from $(X\times\{0\}) \cup (X\times\{1\})$ into $X$.
Does this imply the ${\sf AC}$?

**4**

votes

**0**answers

94 views

### Ref request: modelling regular theories as an injectivity condition

The background to the following observation is standard material in categorical logic, and I thought this was was too — I don’t remember learning it, but I don’t think it is original — but I can’t now ...

**2**

votes

**1**answer

286 views

### A derivation in Tait calculus

I have seen in at least two different places (here, p. 183; and here, last slide) the Tait calculus defined the following way.
Here $\Gamma$ denotes a set of formulas $\{A_1, \ldots, A_k\}$, which is ...

**1**

vote

**0**answers

173 views

### Reference request: Models of isomorphic languages result into isomorphic categories

This is basically a reference request by someone who has not been educated as a logician and would like to be rigorous about certain preliminary aspects of model theory.
Fix an uncountable universe $\...

**7**

votes

**1**answer

443 views

### Taller models of ZFC

This question is somewhat related to a previous one, where I asked for new forms of infinite beyond the cardinal hierarchy.
Using forcing techniques, at least the ones I know of, one starts from a ...

**7**

votes

**2**answers

299 views

### How can any theory prove well-foundedness of ordinals above $\omega_1^{\text{CK}}$?

$\newcommand{\omegaoneck}{\omega_1^{\text{CK}}}$
Pardon the extremely basic question - this isn't quite my area - but I'm confused about the definition of proof theoretic ordinals.
The proof ...

**3**

votes

**1**answer

186 views

### Reference request: eliminating function symbols in predicate logic

Here is a basic technique in logic which seems well-known in folklore, but which I haven’t managed to find written down anywhere. $\newcommand{\T}{\mathbf{T}}$
Fact. Let $\Sigma$ be a signature (in ...

**6**

votes

**1**answer

195 views

### Adding a truth-like predicate to PA

It is well known that adding a truth predicate to arithmetic in the most natural way leads to a contradiction.
Suppose as usual that we add a one place relation T to the language of arithmetic, and ...

**10**

votes

**1**answer

350 views

### Every measure on a set $X$ extends to the power set of $X$: Consistent or not with ZF?

Question. Is it consistent with ZF that every (countably additive, non-negative) measure $\mu: \Sigma \to \bf R$, where $\Sigma$ is a sigma-algebra on a given set $X$, extends to a (countably additive,...

**5**

votes

**0**answers

166 views

### Set theory and forcing from the point of view of a formal system $G^+$ of Gentzen type

There are four papers by Vladimir Alfeevich Kuznetsov, which discuss the above titled topic:
(1) Some problems in set theory from the standpoint of a formal system G+ of Gentzen type. (Russian) Akad. ...

**4**

votes

**1**answer

228 views

### When does an infinite model have a proper class-sized elementary extension?

Suppose that a set of sentences of a 1st order language has an infinite model $M$.
Under what conditions is there is a proper class-sized elementary extension of $M$?
How does the answer change if ...

**6**

votes

**2**answers

157 views

### a variant of the Kleene tree

The (a?) Kleene tree is a computable (a.k.a. decidable) sub-tree of the full binary tree with no computable path. It is well-known.
I need a variant. (For those in the know, I need a c-bar which is ...

**9**

votes

**0**answers

361 views

### Riemann hypothesis in Zilber's field

Question. What is known about the situation (truth or falsity) of Riemann hypothesis in the Zilber's field?

**3**

votes

**0**answers

155 views

### Reducing Consistency of $PA$ [closed]

By godel translation consistency of $PA$ is equivalent to consistency of $HA$.
I want to know any similar theorems for $PA$.
1.What is the minimal theory $T\subsetneq PA$ such that the proof of $...

**5**

votes

**1**answer

300 views

### Constructive compactness for countable models?

The compactness theorem for countable (Tarski?) models is equivalent to the weak König's lemma by a result of H. Friedman and others as noted here, in the context of classical logic. The weak König's ...

**2**

votes

**2**answers

304 views

### Non-Formal Applications: Higman and Kruskal

After looking through many papers, I noticed that most of the discussions and proofs for Higman's Lemma and Kruskal's Tree Theorem only have formal applications in set theory, logic, and type theory. ...

**14**

votes

**1**answer

251 views

### Is the Martin's axiom number $\mathfrak m$ regular

The Martin's axiom number $\mathfrak m$ is the least cardinal $\kappa$ for which $\text{MA}_\kappa(\text{ccc})$ is false, i.e. the least cardinal such that there exists a ccc poset $P$ and a family $\...

**2**

votes

**2**answers

188 views

### Compactness for countable models?

How and where is it proved that WKL$_0$ proves the compactness theorem for countable models? (This is a follow-up to a comment of F. Dorais.)

**1**

vote

**1**answer

159 views

### What restriction(s) of Goedel's primitive recursive functionals is (are) necessary and sufficient to prove the consistency of $PRA$

It is well known that one can use Goedel's primitive recursive functionals of finite type to prove the consistency of $PA$ (Peano Arithmetic). As such, one can certainly use them to prove the ...

**6**

votes

**1**answer

214 views

### Does “$|{\cal P}_2(X)| = |X|$ for $X$ infinite” imply ${\sf (AC)}$?

This comes from a comment made by user bof in this thread.
Let $X$ be a set, define ${\cal P}_2(X) = \big\{\{a, b\}: a\neq b\in X\big\}$.
Consider the statement
${\sf (S)}$ If $X$ is an ...

**5**

votes

**3**answers

698 views

### What does the axiom of replacement mean and why should I believe it?

Here Professor Blass describes the following cumulative hierarchy of sets:
Begin with some non-set entities called atoms ("some" could be "none" if you want a world consisting exclusively of sets),...

**4**

votes

**1**answer

131 views

### Weak Bounded Arithmetics

Let $\Sigma^b_i$ and $\Pi^b_i$ formulas be bounded formulas defined by Buss in language of $L_b$. $PIND(\phi(x))$ is the formula:
$$\phi(0)\land \forall x(\phi(\left \lfloor \frac{x}{2} \right \...

**5**

votes

**3**answers

399 views

### Can the omega-rule rescue Hilbert's program?

As known the second incompleteness theorem derailed Hilbert's program.
However, Hilbert himself tried to rescue it with the $\omega \text{-rule}$, according to the following paper:
http://repository....

**5**

votes

**1**answer

283 views

### How much choice does a linear or well-order on cardinals imply?

It is well-known that if the natural (partial) order on the class of cardinal numbers is a linear order, then it is in fact a well-order and the axiom of choice holds. I was, however, interested in ...

**11**

votes

**1**answer

302 views

### Intutionistic Robinson Arithmetic

By Friedman translation $HA$ and $PA$ prove the same $\Pi_2$ formulas.
Is it true for Intutionistic Robinson arithmetic(Robinson axioms with intutionistic logic) and classic Robinson arithmetic?
...

**2**

votes

**1**answer

1k views

### What is the modern consensus on the difficulty of infinitesimals?

At a related thread at MSE an expert in reverse mathematics noted that "As the modern consensus is that only nonstandard models have infinitesimals, it will be quite challenging to give a concrete ...

**12**

votes

**1**answer

830 views

### Reverse-engineer forcing: am I reinventing the wheel?

In the course of a project I’m working on, I’ve started playing around with a sort of “reverse-engineering” forcing. It seems interesting, but
I have a sinking feeling I’m reinventing the wheel; does ...

**7**

votes

**0**answers

173 views

### Can you define a probability measure on the set of countable transitive models of ZFC?

It is well known that the set of hereditarily countable sets $H(\omega_1)$ —or, if you prefer, $H_{\omega_1}$— has cardinality $2^{\aleph_0}$, and I understand that every countable ...