All Questions
1,135 questions
9
votes
1
answer
634
views
Starting Hilbert's Program on the other end
The idea of Hilbert's program was to start with a simple finitary logic and proof the consistency of more complex systems in this system. Of course, this turned out to be problematic. Even when ...
- 1,659
9
votes
1
answer
698
views
Source for NBG+Equipollence conservative over ZFC?
The "conservative" class theory, NBG, proves no new theorems about sets (with respect to ZFC). The choice function used here is set choice, and it's not too hard to prove (if M is a ctm for ZFC, then ...
- 1,979
9
votes
9
answers
2k
views
Existence of unknowable algorithms ?
Here by «algorithm» I mean a (halting) Turing machine with finite alphabet and memory.
Is it possible to obtain by purely existential (i.e. non-constructive) means the existence of an algorithm ...
- 5,428
9
votes
4
answers
3k
views
Incompleteness and nonstandard models of arithmetic
The following are a collection of doubts, some of which shall have concrete answers while others may have not. Any kind of help will be welcome.
Reading Peter Smith's "Gödel Without (Too Many) Tears",...
- 1,465
9
votes
3
answers
1k
views
Structure Theorem for finitely generated commutative cancellative monoids?
Is there a Structure Theorem for finitely generated commutative cancellative monoids?
Of course they can be densely embedded into a finitely generated abelian group, whose structure is known. Also, ...
- 63.1k
9
votes
1
answer
552
views
"Towers" on singular cardinals with countable cofinality
Let $\lambda$ be a singular cardinal of countable cofinality.
Is there necessarily a sequence $\{A_\alpha\mid\alpha<\lambda^+\}$ of countable subsets of $\lambda$, such that $\alpha<\beta$ if ...
- 39.8k
8
votes
1
answer
238
views
Functions over monoids which factor in two different ways
This is a follow-up question to this MO question, which was asked by Richard Stanley in a comment to my answer there.
Let $S$ be a commutative monoid and $f(x_1, \dots, x_n)$ be a function from $S^n$ ...
- 32.1k
8
votes
1
answer
574
views
Iterated Gentzen: or, a Sith objection to the proof of consistency of PA
$\DeclareMathOperator\PRA{PRA}\DeclareMathOperator\WF{WF}\DeclareMathOperator\Con{Con}\DeclareMathOperator\PA{PA}$Preamble: In the year … in a galaxy far far away, a nasty Sith named Darth Dubious (...
- 7,853
8
votes
1
answer
368
views
Are these theories of real and complex number biinterpretable?
Let $T_R$ be the first-order theory of real closed fields. This is precisely the theory over the language $\{0,1,+,\times\}$ such that the theorems are the formulas that hold in $\Bbb R$. It can be ...
- 3,137
8
votes
2
answers
524
views
Analogues of worldly cardinals for (an unusual version of) second-order $\mathsf{ZFC}$
Let $\mathfrak{ZFC}(\mathsf{SOL})$ be the theory in second-order logic (with the standard semantics) gotten from $\mathsf{ZFC}$ by modifying the Separation and Replacement schemes to apply to ...
- 20.5k
7
votes
2
answers
455
views
Ultrafilters preserved by $\mathbb{P}$ but not by products?
Let $U\in V$ be an ultrafilter on $\omega$. We say $U$ is preserved under forcing with $\mathbb{P}$ if $\Vdash \forall x\subset \omega \ \exists Z\in U \ Z\subset x \vee Z\subset x^c$. In other words,...
- 3,038
8
votes
1
answer
540
views
Are representations in computable analysis the equivalent to countably-generated condensed sets?
This is the first in a pair of questions. For the other see here.
Dustin Clausen and Peter Scholze have a theory of condensed sets, which is a slightly different take on topology. For most cases, ...
- 6,287
8
votes
0
answers
285
views
Matrix decompositions as monoid isomorphisms. Ever considered before?
I've noticed some correspondences between some matrix decompositions and monoid isomorphisms (always to some free commutative monoid), in addition to the one I asked about in a previous question:
...
- 4,943
8
votes
1
answer
896
views
Quantifier elimination for abelian groups
In the Wikipedia article (https://en.wikipedia.org/wiki/Quantifier_elimination#cite_note-4) it is said that every abelian group has quantifier elimination property and a long old paper of W. Szmielew ...
- 2,233
8
votes
1
answer
752
views
What is a universal tree?
I came across some slides talking about the Hrushovski construction. One of the examples was the construction of a "universal tree".
I was curious because the collection of finite trees does not ...
- 2,882
8
votes
1
answer
338
views
Modal logic of "mostly-satisfiability"
For $n\in\omega+1$ let $\mathsf{ZFC}_n$ be $\mathsf{ZC}$ + $\{\Sigma_k$-$\mathsf{Rep}: k<n\}$. Let $\widehat{\mathsf{ZFC}}$ be the strongest consistent theory $\mathsf{ZFC}_n$ (so if $\mathsf{ZFC}$ ...
- 20.5k
8
votes
1
answer
357
views
Example of trickiness of finite lattice representation problem?
I'm trying to come up with a good explanation for my students of why the finite lattice representation problem is difficult. I've already shown that the "greedy approach" to representing the ...
- 20.5k
8
votes
2
answers
578
views
Ordinal notations within non-standard models of arithmetic
It is well-known that the order type of any countable non-standard model of arithmetic $\mathfrak{A}$ is $\omega+(\omega^*+\omega)\eta$. My question is what could be said about the order types of ...
- 5,831
8
votes
1
answer
374
views
Order types of models of theories of ordinals
For $C$ a set of ordinals, let $\mathcal{L}(C)$ be the language with identity, a relation symbol for less than, function symbols for successor, addition, multiplication, and exponentiation, and a ...
- 1,155
8
votes
2
answers
313
views
Does fast function forcing really have $\kappa$-Knaster property?
I ran into a claim concerning Woodin's fast function forcing in the following paper of Apter and Cummings which sounds no right to me:
A. Apter, J. Cummings, Blowing up the power set of the least ...
8
votes
1
answer
321
views
Is every total computable function definable by a normalizing lambda term?
$\newcommand{\nat}{\mathbb{N}}$
$\newcommand{\then}{\ \Longrightarrow\ }$
A partial function $f : \mathbb{N} \to \mathbb{N}$ is said to be $\lambda$-definable if there is a term $F \in \Lambda$ such ...
- 333
8
votes
1
answer
222
views
Mostowski's absoluteness theorem and proving that theories extending $0^\#$ have incomparable minimal transitive models
This question says that the theory ZFC + $0^\#$ has incomparable minimal transitive models. It proves this as follows (my emphasis):
[F]or every c.e. $T⊢\text{ZFC\P}+0^\#$ having a model $M$ with $On^...
- 1,097
8
votes
1
answer
770
views
A “formalistic” variant of the Gödel completeness theorem
A week ago I asked this at MathStackExchange, but without success.
I think, the following variant of the Gödel completeness theorem must be true, but I can't find the references. I would be grateful ...
- 7,426
8
votes
1
answer
514
views
How big is the least non-$\Sigma^1_1$-pointwise-definable ordinal?
There's a large countable ordinal which has cropped up (as a lower bound!) in a computable structure theory problem I'm playing with. At present I don't really understand how big it is, and I'm ...
- 20.5k
8
votes
1
answer
250
views
What is the lowest complexity definition of $\mathbb{Z}$ in an infinite extension of $\mathbb{Q}$
In 2009, Jochen Koenigsmann showed that $\mathbb{Z}$ is universally definable in the field $\mathbb{Q}$. And in 2012, Jennifer Park proved a result which implies that $\mathbb{Z}$ is $\exists\forall$-...
- 4,597
8
votes
2
answers
761
views
Syntax/semantics conflation leads to infinitary logic
It is written (cf. Moore 1980, page 100) that mathematical logicians (e.g. Peirce, Schröder, Hilbert) at the turn of the last century did not yet distinguish between syntax and semantics when ...
- 583
8
votes
1
answer
463
views
Reference request: proof-theoretic strength of $\mathsf{KP}$ with recursively large ordinals and $\mathsf{CZF}$ with large set axioms
Large set axioms are notions corresponding to large cardinals on constructive set theories like $\mathsf{IZF}$ or $\mathsf{CZF}$. The notion of inaccessible sets, Mahlo sets, and 2-strong sets ...
- 3,042
8
votes
1
answer
2k
views
decidable fragments of first-order logic without the finite countermodel property
Say a set of sentences in first-order logic has the finite countermodel property if any sentence in the set that is falsifiable is falsifiable on a finite domain. (Two examples: the set of sentences ...
- 1,189
8
votes
2
answers
2k
views
Is $\omega$ absolute in set theory without foundation?
Let $\text{ZF}^-$ be the set theory without powerset, choice, and foundation. Consider the following notions:
Wellfounded sets
$$WF(c) \Leftrightarrow (\forall x \subseteq TC(c)) \left[x \neq \...
- 183
8
votes
3
answers
746
views
Natural statements independent from true $\Pi^0_2$ sentences
I am looking for sentences in the language of first order arithmetic ($0,1,+,\cdot,\leq$) which are independent from $\Pi^0_2$ consequences of true arithmetic $\Pi^0_2\text{-}\mathsf{Th}(\mathbb{N})$. ...
- 5,502
8
votes
1
answer
360
views
Models of ZFA corresponding exactly with a particular class of groups
I recently read [1], in which Blass exhibits a correspondence between:
Permutation models of ZFA in which the axiom of choice (AC) fails but the Boolean prime ideal theorem (BPIT) holds; and
...
- 183
8
votes
2
answers
1k
views
Road to Solovay's Land.
In the first semester of 2012 I took a course in General Topology and Set Theory, at undergraduate level. For topology, I was instructed to use Engelking's General Topology; albeit I had a great ...
- 405
8
votes
1
answer
1k
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 ...
- 2,381
8
votes
0
answers
1k
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 ...
- 16.6k
8
votes
1
answer
3k
views
Foundations: Existence of uncountable ordinals.
This isn't really a research question, but at least it's research-level mathematics. I'm talking with some other people about the first uncountable ordinal, and I want some facts to inform this ...
- 2,754
8
votes
2
answers
560
views
Models of PRA/EFA with induction on $X$ but not $\omega^X$
As I currently understand it, induction on formulas containing $N+1$ first-order quantifiers is required to prove the well-ordering of the ordinal $(\omega \uparrow\uparrow N) < \epsilon_0$, that ...
8
votes
1
answer
535
views
Different approaches to forcing
There are many different approaches to the forcing method, and I am looking for all known such approaches. So my question is:
Question 1. Which different approaches to set theoretic forcing are ...
8
votes
1
answer
643
views
Explicit counter example to Vopěnka's principle in the constructible universe?
Vopěnka's principle is a large cardinal axiom which has many equivalent formulations. One of them, which I find especially appealing, is the following: if the universe is satisfies Vopěnka's principle ...
- 27.5k
8
votes
2
answers
540
views
Vaught's conjecture for partial orders
In
``Steel, John R. On Vaught's conjecture. Cabal Seminar 76–77, pp. 193–208''
the following is proved:
Theorem. Let $\phi\in L_{\omega_1,\omega}.$ If every model of $\phi$ is a tree, then $\phi$ has ...
- 32.2k
8
votes
1
answer
408
views
If there is a non-constructible real, is there an $L$-generic real?
If we assume that $\Bbb R^V\neq\Bbb R^L$, can we deduce that there is some $x\in\Bbb R^V$ which is $L$-generic?
Of course if $V$ is a generic extension of $L$ this is true, but if $V=L[0^\#]$ this is ...
- 39.8k
8
votes
2
answers
578
views
Ultracoproducts and Cartesian products
Let $X$ be a metrizable compact topological space, let $\mathcal U$ be an ultrafilter, and denote by $X^{\mathcal U}$ the ultracopower of $X$ with respect to $\mathcal U$.
As a C$^*$-algebraist, I ...
- 1,786
8
votes
2
answers
474
views
Does forcing with recursively pointed perfect trees add a Turing degree that is minimal over $V$?
A tree $T$ on $\omega$ is recursively pointed if it is recursive in each of its branches. We can consider a variant of Sacks forcing where the conditions are recursively pointed perfect trees ordered ...
- 5,471
8
votes
7
answers
651
views
Strength of Bishop style constructive mathematics vs $\mathsf{RCA}_0$
This question came out of this other MO question of mine. My question is
Is there a formal comparison between $\mathsf{RCA}_0$ and $\mathsf{BISH}$ (Bishop style constructive mathematics as used in ...
- 6,287
8
votes
3
answers
825
views
Does a left basis imply a right basis, without AC?
If $_DV_D$ is a $D$-$D$-bimodule, and we have a $D$-basis for $V_D$, do we still need AC to get a $D$-basis for $_DV$?
(The original question appears below. But this shorter question gets at the ...
- 18.7k
8
votes
5
answers
1k
views
Examples of left reversible semigroups
I am looking for concrete examples of cancellative, left reversible semigroups. Left reversible semigroups are also called "Ore semigroups". See this wikipedia page for the definition of a left ...
- 550
8
votes
3
answers
2k
views
randomness in nature [closed]
What is the explanation of the apparent randomness of high-level phenomena in nature?
For example the distribution of females vs. males in a population (I am referring to randomness in terms of the ...
- 307
8
votes
3
answers
5k
views
Cardinality: Why is there no "ℵ½"?
A wikipedia page/paragraph on ℵ₁ states:
"The definition of ℵ₁ implies (in
ZF, Zermelo-Fraenkel set theory
without the axiom of choice) that no
cardinal number is between ℵ₀ and
ℵ₁."
"If the axiom ...
- 207
7
votes
1
answer
306
views
On the cardinal arithmetic of accessible categories
If $\lambda, \mu$ are regular cardinals, say that $\lambda \trianglelefteq \mu$ if $\lambda \leq \mu$ and
$$\forall X, \, |X| < \mu \implies \mathrm{cf} (P_\lambda(X)) < \mu$$
Here $P_\lambda(X)...
- 64k
7
votes
1
answer
195
views
Bounding and domination numbers for relation $\leq$ modulo $\omega$-nullsets
We say that $A\subseteq \omega$ is a nullset if $$\lim\sup_{n\to \infty} \frac{|A\cap n|}{n+1} = 0.$$
Let $\omega^\omega$ denote the set of functions $f:\omega\to\omega$. We define a pre-ordering ...
- 48.9k
7
votes
1
answer
291
views
Reducing largeness notions, uniformly
This question is a particular take on the following theme. Suppose $A$ and $B$ are two notions of "large subset of $\omega^\omega$;" when is there a uniform method for turning an element of $...
- 20.5k