All Questions
1,458 questions with no upvoted or accepted answers
4
votes
0
answers
333
views
Can this graph theory serve as a foundational theory of mathematics?
Working in mono-sorted first order logic, add primitives of equality and its axioms, set membership $\in$, a partial ternary relation $\to$ denoting is the direction from to, and at last a total unary ...
- 11.3k
4
votes
0
answers
105
views
Computably saturated Skolem hulls of Morley sequences in $\mathsf{PA}$
Recall that a model $M$ of a first-order theory $T$ (in a computable language $\mathcal{L}$) is computably saturated if for every finite tuple $\bar{a} \in M$ and every computable partial type $\Sigma(...
- 13k
4
votes
0
answers
293
views
How does "spreading-with-determinacy" compare with Cichon's diagram?
For $\mathbb{A},\mathbb{B}\subseteq\mathcal{P}(\omega^\omega)$, say that $\mathbb{A}$ spreads onto $\mathbb{B}$ iff there is some $F:\omega^\omega\rightarrow\omega^\omega$ such that $F[A]\in\mathbb{B}$...
- 20.5k
4
votes
0
answers
300
views
Is the set of approximating sequences for irrationals dominating?
Let $r\in [0,1]\setminus\mathbb{Q}$, let $\mathbb{N}$ denote the set of non-negative integers and let $\mathbb{N}_+=\mathbb{N}\setminus\{0\}$. For $n\in\mathbb{N}_+$ let $$\alpha_r(n)=\min\{|r-\frac{...
- 48.9k
4
votes
0
answers
72
views
When is the submonoid preserving a subspace finitely generated?
Let $T$ be a topological space with at least one open set whose closure is not open.
Let $G$ be a finitely generated group acting by homeomorphisms on $T$. Let $S\subset T$ be a subspace.
Under what ...
- 51
4
votes
0
answers
158
views
Is the group ring of an amenable group, viewed as multiplicative monoid, amenable?
Motivated by this question, it seems natural to ask the following:
Question 1: Is there a [finitely generated discrete] torsion-free virtually Abelian (but not Abelian) group $G$ so that the ...
- 4,432
4
votes
0
answers
197
views
Are there any 1-decidable algebraic extensions of $\mathbb{Q}$ which are not decidable?
A model $M$ is decidable if the set of all first-order formulas which are true in $M$ is a recursive set. And a model is $1$-decidable if the set of all existential formulas which are true in $M$ is ...
- 4,597
4
votes
0
answers
97
views
How hard can it be to extract SOP from an unstable NIP theory?
A very fundamental result of Shelah in neostability theory is the fact that any unstable NIP theory has an instance of the strict order property, a formula $\varphi(x,y)$ (with $x$ and $y$ possibly ...
- 13k
4
votes
0
answers
234
views
Do you know rings without involutions, auto-anti-isomorphics? In that case, what is the minimal example?
Do you know rings without involutions, but auto-anti-isomorphic (isomorphic to their opposite)? In that case, what is the minimal example?
If a ring has an involution f, then f is an anti-automorphism;...
4
votes
0
answers
135
views
Cofinality without choice: can this coarse definition suffer badly?
This is a rephrased version of a question previously asked at MSE without success.
Working in $\mathsf{ZF}$, it is no longer possible in general to give every linear order an ordinal cofinality. For ...
- 20.5k
4
votes
0
answers
225
views
Complexity of $Σ_n$ theory of $H(ω_2)$ under MM$^{++}$
Complexity of $Σ_n$ theory of $H(ω_2)$ under MM$^{++}$
Under Woodin's $\mathbb{P}_\text{max}$ axiom (which is implied by MM$^{++}$), what is the complexity of the $Σ_n$ theory of $H(ω_2)$? Same ...
- 7,545
4
votes
0
answers
174
views
Sequences of sequences of sequences and elementary embeddings
Suppose that $\kappa$ is the critical point of $j\colon V\to M$, and suppose that $\mathcal F=(F_\alpha\mid\alpha\leq\kappa)$ is a sequence such that for every limit ordinal $\alpha$, $F_\alpha$ is a ...
- 39.8k
4
votes
0
answers
222
views
The list reaping number?
My question is inspired by a question of Dominic van der Zypen. Let $[\omega]^\omega$ denote the set of all infinite subsets of $\omega$.
The reaping number, denoted by $\mathfrak r$, is the minimum ...
- 13.4k
4
votes
0
answers
180
views
Ideals with certain properties
I recently isolated the following definition, which I believe it should have appeared somewhere.
Let $\kappa$ be a cardinal, and let $X$ be a set with $\kappa^+\leq |X|$.
Definition: An ideal
$\...
- 2,381
4
votes
0
answers
553
views
Can Robinson arithmetic prove any interesting theorems?
The motivation for my question is I'm curious whether studying Robinson arithmetic can be fruitful in the same sense as studying group theory. Robinson arithmetic is so weak that there are many ...
- 675
4
votes
0
answers
160
views
Finite pre-orders embeddable in the Rudin-Keisler ordering
$\DeclareMathOperator{\NPU}{\operatorname{NPU}}\DeclareMathOperator{\RK}{\,\mathrm{RK}}$A pre-ordered set is a pair $(P, \leq)$ where $P$ is a set and $\leq\subseteq P\times P$ is a reflexive and ...
- 48.9k
4
votes
0
answers
208
views
PFA for cardinal preserving forcing notions and the CH
Let $FA_{\aleph_1}$(cardinal preserving proper forcings) be the forcing axiom: if $\mathbb{P}$ is a cardinal preserving proper forcing notion and $(D_\xi)_{\xi<\omega_1}$ are dense subsets of $\...
- 32.2k
4
votes
0
answers
102
views
Incidence relations of subspaces with infinite descending flags
Let $W = \prod_{k \in \mathbb N} V_k$ be an infinite product of vector spaces, and let $V = \oplus_{k \in \mathbb N} V_k$ be the corresponding sum. Already the case where $V_k$ is 1-dimensional for ...
- 64k
4
votes
0
answers
431
views
How can I prove that primitive recursion “preserves” representability in Peano Arithmetic?
I'm working on my thesis about Gödel's Incompleteness Theorems, and at some point I need to prove that the $\textsf{PA}$ system is able to represent all the recursive functions.
By recursive function ...
- 49
4
votes
0
answers
266
views
Is the collection scheme provable in ZF-Regularity?
By the axiom schema of collection in ZF, I mean: $$\forall A \exists B \forall x \in A (\exists y \phi(x,y) \to \exists y \in B \phi(x,y))$$, for every formula $\phi$ that doesn't use the symbol $B$.
...
- 11.3k
4
votes
0
answers
458
views
Are hyper-Berkeley cardinals equiconsistent with club Berkeley cardinals or with Berkeley cardinals?
Let's define cardinal $\kappa$ as hyper-Berkeley if for any transitive set $M$ such that $\kappa\in M$ there exists an elementary embedding $j: M\prec M$ with
fixed point $\lambda$ and $\text{crit}j\...
- 51
4
votes
0
answers
153
views
Can we pin down the "recursively closed" levels of $L$ by a first-order theory?
I'm broadly interested in problems of the form
Characterize those ordinals $\alpha$ which are not computable from any smaller ordinal
for some meaning of "computable." For example, the ...
- 20.5k
4
votes
0
answers
124
views
Consistency of an intersection property
If $\kappa$ is an infinite cardinal then we denote by $[\kappa]^\kappa$ the collection of subsets of $\kappa$ that have cardinality $\kappa$. We say that $\kappa$ is intersectionally strange if there ...
- 48.9k
4
votes
0
answers
203
views
The Return of Graham Arithmetics: adding induction up to $g_{64}$
In my previous question The inconsistency of Graham Arithmetics plus $ \forall n, n < g_{64}$, I introduced an extension of Robinson Arithmetics with the recursive definition of Tetraction, a small ...
- 7,853
4
votes
0
answers
188
views
An analogue to Robinson's theorem for Kalmar-elementary functions
Julia Robinson proved that the family of all unary computable total functions is the smallest class containing $S$, $\mathrm{Exc}$, and closed under composition, addition and inversion of surjective ...
4
votes
0
answers
177
views
When is validity definable in $L_\alpha$?
Below, $\alpha$ is a countable p.r.-closed ordinal $>\omega$.
Let $\mathcal{L}_\alpha=\mathcal{L}_{\infty,\omega}\cap L_\alpha$ (note that this is not the same as $\mathcal{L}_{\omega_1,\omega}\...
- 20.5k
4
votes
0
answers
198
views
Elementary self-embeddings conservative over ZFC
Question: Is the following theory conservative over ZFC? And if not, what is its strength?
Language: $∈$, $j$ (unary function symbol)
Axioms:
1. ZFC (without separation and replacement for formulas ...
- 7,545
4
votes
0
answers
267
views
Proof theory and subsystems of second-order arithmetic: in particular the reverse mathematics of Godel's system $T$
While doing some research on reverse mathematics, I came across the following document under the address, http://www.andrew.cmu.edu/user/avigad/Talks/survey1.pdf:
Proof theory and Subsystems of ...
- 6,132
4
votes
0
answers
182
views
$\mathcal{C}$-filtering of modules inherited by submodules
I'll state the question about modules, but I'm open to examples in other contexts. I am not an algebraist, so please forgive any non-conventional terminology.
DEFINITION: Let $\mathcal{C}$ be a ...
- 2,231
4
votes
0
answers
127
views
Cyclic relation algebra
A relation algebra $\mathbf{R}$ is a structure $\langle |\mathbf{R}|, \vee, \neg, \circ, I, (-)^{op} \rangle$ such that:
$\langle |\mathbf{R}|, \vee, \neg \rangle$ is a Boolean algebra,
$\langle |\...
- 4,096
4
votes
0
answers
163
views
Apart from Tarski's study, is there any other source that has been looking at the parallelism of concepts and theorems?
Alfred Tarski in his next study (Some Methodological Investigations on the definability of concepts, TARSKI, Logic, Semantics, Metamathematics. Papers from 1923 to 1938. Clarendon Press, Oxford, 1956, ...
- 41
4
votes
0
answers
144
views
Can this reflective class theory interpret ZFC?
Reflective Set Theory $\mathsf{RfST}$ is formulated in first order predicate logic with extra-logical primitives of equality $``="$, membership $``\in"$, and a single primitive constant symbol $V$ ...
- 11.3k
4
votes
0
answers
176
views
Reference request: destroying saturation at an inaccessible?
An ideal $I$ on $P(\kappa)$ is said to be $\kappa^+$-saturated if there is no sequence $\langle S_\alpha \mid \alpha<\kappa^+\rangle$ of $I^+$ sets such that $\alpha<\beta<\kappa^+\implies S_\...
- 123
4
votes
0
answers
368
views
Ordinal analysis and nonrecursive ordinals
Ordinal analysis is typically described as characterizing recursive ordinals in a theory $T$, but there is a sense in which it can characterize all $T$-ordinals, even those that are nonrecursive.
...
- 7,545
4
votes
0
answers
820
views
"Antiforcing" - Is there a method to 'remove' sets from a model of ZF?
Forcing is a method of "adding sets" to a model $M$ of ZF by making a new set $M^{(\mathbb{P})}$ consisting of every set of $M$, but you have the option to add certain sets out of $M^{(\mathbb{P})}$ ...
- 1,252
4
votes
0
answers
204
views
Can there be a segment of regular cardinals with the tree property capped by an almost-strongly-compact?
Recall that a cardinal $\kappa$ is $(\lambda,\infty)$-almost-strongly-compact if every $\kappa$-complete filter can be refined to a $\lambda$-complete ultrafilter. A cardinal $\mu$ has the tree ...
- 64k
4
votes
0
answers
182
views
Generic two-cardinal behavior of first-order sentences
This is a hopefully improved version of a question I asked before and then deleted because it was based on some fundamentally incorrect assumptions.
Some first-order theories are able to control the ...
- 13k
4
votes
0
answers
424
views
What are the requirements of a foundational theory?
There are multiple languages to describe all of mathematics, and there are some equivalences between them, some more successful then others.
My question is can we describe some requirements (in some ...
- 773
4
votes
0
answers
225
views
Short Diophantine definition of the sum-of-divisors function (using less than 100 variables)?
Is there a short Diophantine definition of the sum-of-divisors function? Is there a polynomial $p$ such that
$$c = \sum_{d|n}d \ \leftrightarrow \ \exists x_1, \ldots x_{100}\ p(c,n,x_1, \ldots x_{...
user44143
4
votes
0
answers
245
views
Interesting examples of countable support iteration of ccc forcings
I am looking for examples in the literature of countable support iterations of ccc (particularly $\sigma$-centered) forcings, possibly with some emphasis on iterations that avoid adding Cohen reals.
...
- 3,115
4
votes
0
answers
168
views
A forcing which can build weird models of $\neg$ADS
There is a class of forcing notions I've been playing around with recently. They have a couple nice properties, and all have the same theme, but I've found them difficult to analyze beyond the basics. ...
- 20.5k
4
votes
0
answers
298
views
Finite properties of finite models of first order theories
Let $T$ be a first order theory. Consider the following finiteness property for $T$:
If $M$ is a finite model for $T$, then the number of definable subsets of $M^n$ is bouned by a number $s(n)$ which ...
- 5,039
4
votes
0
answers
270
views
What does $L(A,\mathbb{R})$ mean?
I many papers by Woodin, and on some answers here on MathOverflow (like the first answer of this question), I see the expression "$L(A,\mathbb{R})$" being used, but I have never seen it defined. I ...
- 615
4
votes
0
answers
199
views
On the proof of a normal form theorem for ordinal (primitive) recursion
Consider the following statement (which follows easily from various results found in the literature):
(†) There exists a primitive recursive (“p.r.”) relation $T$ on the ordinals such that, if $(...
- 32.5k
4
votes
1
answer
364
views
Values attained by the coheight of $(H \setminus H^\times)^k$ as a function of $H$ and $k$
Edit (Apr 24, 2017). I'm updating this post in the light of the latest developments of a related thread.
Let $H$ be a multiplicatively written, commutative monoid, and set $M := H \setminus H^\times$,...
- 10.5k
4
votes
0
answers
281
views
Analogues of Silver's theorem for tree property
Recall Silver's theorem which says that "if GCH holds below $\aleph_{\omega_1}$, then $2^{\aleph_{\omega_1}}=\aleph_{\omega_1+1},$ i.e., it also holds at $\aleph_{\omega_1}$".
Recently, Gitik has ...
- 32.2k
4
votes
0
answers
372
views
Set- Theoretic Tree property and Model Theory
There is a tree property in set-theory and a tree property in model theory.
I want the former, not the later.
Definition The tree property holds at some cardinal $\kappa$ if every tree of height $\...
- 2,882
4
votes
0
answers
192
views
Better arguments via worse numberings?
The usual listing $\{\varphi_e: e\in\omega\}$ of partial computable functions has a number of nice properties - the padding lemma, the recursion theorem, etc. Any other numbering which we can "...
- 20.5k
4
votes
0
answers
201
views
Equivalent definitions of Woodin cardinals in $\operatorname{ZFC}_{-}/\operatorname{ZFC}^{-}$
In our background universe $V$ - satisfying $\operatorname{ZFC}$ - we say that an ordinal $\delta$ is a Woodin cardinal iff it satisfies one of the following equivalent properties:
For all $A \...
- 1,080
4
votes
0
answers
120
views
Canonical formal theory corresponding to a given ordinal
There is a notion of "proof theoretic ordinal" for a formal theory https://en.wikipedia.org/wiki/Ordinal_analysis
Can we go backwards?
That is, we are given some recursive ordinal notation (we don't ...
- 1,318