**0**

votes

**0**answers

2 views

### Bounding and dominating numbers ${\frak b}, {\frak d}$ via ultrafilters

Let $\omega^\omega$ denote the set of all functions $f:\omega\to\omega$ and suppose that ${\cal U}$ is a free ultrafilter on $\omega$. We write $f \leq_{\cal U} g$ if $$\{n\in\omega: f(n) \leq ...

**1**

vote

**1**answer

142 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

435 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

115 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

127 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

119 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

88 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

133 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

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

**6**

votes

**1**answer

372 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

220 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

173 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

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

**9**

votes

**1**answer

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

**4**

votes

**0**answers

137 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

201 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

141 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

315 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

141 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

265 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

284 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

230 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

168 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

143 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

188 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

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

**3**

votes

**1**answer

88 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

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

**5**

votes

**1**answer

254 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

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

**1**

vote

**1**answer

840 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

767 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

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

**10**

votes

**0**answers

247 views

### Is the universality of the surreal number line a weak global choice principle?

I'd like to consider the principle asserting that the surreal
number line is universal for all class linear orders, or in other
words, that every linear order (including proper-class-sized)
linear ...

**3**

votes

**1**answer

182 views

### A question regarding the consistency of Nelson's Predicative Arithmetic

Following Dan Willard (from his paper "Self-Verifying Axiom Systems, the Incompleteness Theorem, and Related Reflection Systems", found on his homepage, pdf here):
"Define an axiom system $\alpha$ ...

**4**

votes

**0**answers

159 views

### Finding limit-nondecreasing sets for certain functions

This is a question that arose a while ago in work with Damir Dzhafarov on some pieces of reverse mathematics. As far as I know, it has no deep significance; however, it feels like the sort of thing we ...

**4**

votes

**2**answers

139 views

### first order languages over graphs (and other discrete models)

A lot of research has been devoted to the study of first order language of graphs (FO). Formulas in this language are constructed using variables $x, y,\dots$ ranging over the vertices of a graph, the ...

**8**

votes

**0**answers

128 views

### Are there always large discrete families of normal measures?

Let $\kappa$ be a measurable cardinal. We give the Stone space of all ultrafilters on $\kappa$ the usual topology, where each $x\subseteq\kappa$ determines a basic open $[x]=\{U;x\in U\}$. The ...

**-2**

votes

**1**answer

222 views

### A set theory and a model without the empty set [closed]

Im just asking out of curiosity.
Is there a set theory $\mathcal T$ and a model $\langle M,E\rangle \vDash \mathcal T$ such that no set in M is empty:
$$\left(\forall m\in M \right)\left(\exists n\in ...

**4**

votes

**0**answers

133 views

### Two questions about the behavior of the continuum function

The first question asks about the global behavior of the power function in the case of finite gaps.
Question 1. Fix a natural number $m>1.$ For each limit ordinal $\alpha,$ including $0$, let ...

**1**

vote

**1**answer

133 views

### Why is a cut-free system consistent?

Assume that the cut-elimination theorem holds for a system $T$. Then, for any proof that makes use of the cut-rule in $T$, there is a proof that does not make use of the cut-rule. An immediate ...

**10**

votes

**1**answer

337 views

### What sort of large cardinal can continuum be?

I have stumbled across a related question asking which large cardinal properties can hold for $\aleph_1$. This question is probably also related, asking in what ways $\aleph_0$ is a "large" cardinal.
...

**1**

vote

**0**answers

60 views

### models of $I\exists^+_1$

$\phi$ is a $\exists^+_1$ formula iff it is in language of arithmetic and does not have $\forall$,$\neg$ and $\rightarrow$, therefore $I\exists^+_1$ is theory of $Q$+induction axioms for $\exists^+_1$ ...

**5**

votes

**1**answer

290 views

### Ill-founded models of set theory with well-founded ordinals

Let $(\mathcal{M},E)$ be an internally non-well-founded model of set theory i.e of $ZFC^{\neg f}=ZFC\setminus \mathrm{foundation}+\neg \mathrm{foundation}$, then $\mathcal{M}$ includes an infinite ...

**16**

votes

**1**answer

1k views

### What is the relationship between Turing Machines and Gödel's Incompleteness Theorem?

In this article, Scott Aaronson talks about using Turing Machines for proving the Rosser Theorem.
What is the relationship between the numbering that Gödel used in his proof of incompleteness and ...

**1**

vote

**1**answer

231 views

### Does mathematical induction presuppose the existence of a completed infinity?

Consider the following statement by Edward Nelson--this from the "Outline" of his 'proof' of the inconsistency of $PA$ (which Terry Tao found to contain an error):
"The induction axiom schema of ...

**5**

votes

**0**answers

126 views

### Failure of GCH at a strongly compact cardinal

Does Con(ZFC+ there exists a strongly compact cardinal) imply Con(ZFC+ there exists a strongly compact cardinal $\kappa+ 2^\kappa > \kappa^+$)?

**23**

votes

**1**answer

642 views

### Do the analogies between metamathematics of set theory and arithmetic have some deeper meaning?

By "formal analogies" between the metamathematics of $\mathsf{ZFC}$/set theory and $\mathsf{PA}$(=Peano Arithmetic)/first order arithmetic, I mean facts such as the following:
We are considering a ...

**29**

votes

**8**answers

5k views

### What are some important but still unsolved problems in mathematical logic?

In the past, First order logic and its completeness and whether arithmetic is complete was a major unsolved issues in logic . All of these problems were solved by Godel. Later on, independence of ...

**6**

votes

**1**answer

348 views

### Can an ultrapower be undone by forcing?

I am not 100% certain this question is appropriate for MO; I may just be missing something obvious. Also, I vaguely recall a similar question being asked here a while ago, but I can't find it; if it ...