All Questions
1,459 questions with no upvoted or accepted answers
2
votes
0
answers
235
views
The supremum of ordinals eventually writable by Ordinal Turing Machines with an oracle for the class of stabilization ordinals
This question is based on the assumption that all computations start with no ordinal parameters (i.e. the input is empty).
The term “stabilization time of a machine” for this question implies the ...
- 959
2
votes
0
answers
189
views
Can Set theory be interpreted in Relational Mereology?
In a posting to MathStackExchange, I've presented a theory of rudimentary relations having a rudimentary kind of membership together with a primitive ordered pairing with the aim for it to capture the ...
- 11.3k
2
votes
0
answers
93
views
Can this predicative kind of type-set theory reach the consistency of ${\sf Z}_2$?
Add a primitive total one place fuction symbol $\tau$, and a primitive binary relation $<$, to the language of set theory. Add the following axioms:
Extensionality: $\forall z \, (z \in x \iff z\in ...
- 11.3k
2
votes
0
answers
243
views
Pairs vs. two pieces: is the usual proof model-theoretically-optimal?
(For clarity, I'll use $R,S$ for binary relation symbols and $A,B$ for actual binary relations.)
There is an equality between the numbers (up to isomorphism in the appropriate sense) of partitions of ...
- 20.5k
2
votes
0
answers
58
views
Weaker uniformisation theorems
An interesting topic in Reverse Mathematics is uniformisation theorems (see VI.2 and VII.6 in Simpson's SOSOA). Now, these theorems all express the following: for a suitable formula $\varphi$, there ...
- 4,359
2
votes
0
answers
255
views
A formal definition of a useful theorem?
Sorry if this feels a bit squishy, but I'm wondering if there is any published work trying to give a fully formal definition of the notion of a useful theorem. I mean, in mathematics we all know that ...
- 3,029
2
votes
0
answers
125
views
Consistency strength of Muller's modification of Ackermann set theory
In his 2001 paper Sets, Classes and Categories, F. A. Muller lays out a modification of Ackermann class theory that he claims is not conservative over Ackermann's original theory in the sense that it ...
- 10.1k
2
votes
0
answers
309
views
Set theory for category theory
Let $SC$ (sets and classes) denote the modification of Ackermann set theory laid out in F. A. Muller's Sets, Classes and Categories (denoted there by ARC -- a brief summary of the theory is given ...
- 10.1k
2
votes
0
answers
97
views
How restrained are we in terms of metatheories when working with higher order logics with full semantics?
When working in the realm of first order logic one can use very basic mathematical backgrounds(in reverse mathematical sense) to prove interesting things about more "structures".
In what ...
- 893
2
votes
0
answers
160
views
What is the consistency strength of the following pattern of failure of the continuum hypothesis?
What is the least theory in which the following sentence is proved?
$ \exists M: M\text { is CTM(ZFC+ GCH)} \land \forall \kappa \in Card^M (\kappa > 1 \implies \\\exists N: N \text { is CTM(ZFC) }...
- 11.3k
2
votes
0
answers
67
views
Type of numerical semigroups is not bounded when embedding dimension is $\geq 4$
I am currently studying numerical semigroups. I know that there is no upper bound for the type of a numerical semigroup with embedding dimension greater or equal than $4$. There is a famous example by ...
- 121
2
votes
0
answers
185
views
Generalized models of set theory
The forcing method can be viewed as building a Boolean-valued model of set theory. Some generalizations include Heyting algebra/sheaf/lattice-valued model. However, it seems these generalizations are ...
- 237
2
votes
0
answers
118
views
Details on partial oracle computability in Ganov
I'm currently glancing at a couple papers by V. A. Ganov (Recursion on generalized computable ordinals and A generalized constructable continuum), and I'm running into some basic issues. Ganov ...
- 20.5k
2
votes
0
answers
123
views
Can the well founded world of NFU be itself the hereditarily Cantorian world and also satisfy ZFC?
Is it possible to squeeze the hereditarily Cantorian world "$\sf H_{Cant}$" of $\sf NFU$ be the well founded world $\sf WF$ of
$\sf NFU$. Moreover, can we have $\sf WF$ of $\sf NFU$ to ...
- 11.3k
2
votes
0
answers
202
views
Are there re-formulations of ZFC that more closely parallel large-cardinal extensions?
The following is a reformulation of $\sf ZFC$, it is a version of a well known approach going back to Dana Scott (I suppose), it axiomatizes $\sf ZFC$ simply by "Specification, Reflection, and ...
- 11.3k
2
votes
0
answers
115
views
Does NBG set theory minus power set minus extensionality interpret NBG set theory minus power set?
In On the Axiom of Extensionality, Part II, JSL, Vol. 24, No. 4, 1959, 287-300, R. O. Gandy shows that NBG set theory minus extensionality interprets NBG set theory. His systems make use of set ...
- 3,574
2
votes
0
answers
108
views
Left-elements of a numerical semigroup generated by two elements
A numerical semigroup $S$ is a semigroup in $\mathbb{N}$ such that $\mathbb{N}\backslash S$ is finite. It is known that there exists always a set $M$ such that an element in $S$ can be expressed as a ...
- 31
2
votes
0
answers
117
views
Does $ZFC^-$ plus $\mathcal{P}^\gamma$ have a countable $L_\alpha$ model if it has a countable model?
Suppose $ZFC^-$ is $ZFC$ minus the power set axiom, and that, for $\gamma$ a countable ordinal, $\mathcal{P}^\gamma$ is an axiom that allows less than $\gamma$ applications of the power set operation....
- 3,574
2
votes
0
answers
76
views
Maps defined on the set of Turing degrees
Let $\mathcal{D}$ be the collection of Turing degrees. Are there nontrivial maps $\phi:\mathcal{D}\to \mathcal{D}$ which is natural to consider? For instance, I wonder whether maps which are ...
- 4,459
2
votes
0
answers
114
views
Is set theory bi-interpretable with a first order theory about higher order predication?
Language: Mono-sorted first order logic with equality and additional primitives of $\xi$ signifying is the order of, and the binary relation $ [ \ ] $ signifying predication that is $P[x]$ to be read ...
- 11.3k
2
votes
0
answers
174
views
A question about Shoenfield's absoluteness theorem and $0^{\sharp}$
Shoenfield's theorem states that any $\Pi_{3}^{1}$ sentence that holds in $V$ holds in $L$, but I know that it is consistent with ZFC that there exists a set $A\subset \mathbb{N}$ where $A\not\in L$ ...
- 143
2
votes
0
answers
126
views
What choice we can get from stipulating an extending well order on the Scott cardinals?
The following question is similar to that one, but it adds some features not included in that question.
Working in $\sf ZF+ Classes$, if we axiomatize the existence of a well order on the class of all ...
- 11.3k
2
votes
0
answers
171
views
Is Definable Partition Principle not equivalent to AC over ZF?
Definable Partition Principle: If $\phi;\psi$ are formulas in which only the symbol $x$ occur free, then: $$A = \{x \mid \phi\} \land B=\{x \mid \psi\} \land B \, ||| \, A \to B \leq A$$ where $|||$ ...
- 11.3k
2
votes
0
answers
83
views
Is restricting class parameters to be arguments of set functions in reflection consistent?
Working in mono-sorted first order logic with equality and membership:
Define: $\operatorname{set}(x) \equiv_\text{df} \exists y \, (x \in y)$
Axiomatize:
Extensionality: $(\forall x \, (x \in a \...
- 11.3k
2
votes
0
answers
73
views
Nonzero idempotents in compact semitopological semigroups with zero
Let $S$ be a compact semitopological semigroup. Then, $S$ contains minimal idempotents by Ellis' theorem.
Ellis' Theorem: In a compact left-topological (resp. right-topological) semigroup, every ...
- 2,605
2
votes
0
answers
391
views
Which commutative diagrams are reflected by adjunctions?
Functors $F\colon C\to D$ preserve commutative diagrams: if a diagram $A$ commutes in $C$, then $FA$ commutes in $D$ (where $FA$ is the diagram in $D$ that can be obtained from $A$ by applying to ...
- 551
2
votes
0
answers
145
views
Semigroup ideals of a ring or an algebra
Let $R$ be a ring or an algebra. Suppose $B\subseteq R$ satisfies the property $BR \subseteq B$ and $RB\subseteq B$. Is there a general theory of subsets with this property in a ring (resp. algebra) ...
- 2,605
2
votes
0
answers
119
views
The "matrix direct sum" monoid modulo unitary equivalence
Given a commutative $*$-ring $(R,*)$, let $M(R,*)$ be the monoid whose elements are matrices over $R$ of all possible shapes and entries, including those that have $0$ columns or $0$ rows. Let the ...
- 4,943
2
votes
0
answers
125
views
Is this principle of internalization of external injections inconsistent?
Working in bi-sorted FOL, where lower cases stand for sets and upper cases for classes; add all axioms of ZF written completely in lower case, and add an axiom of Extensionality over all classes, and ...
- 11.3k
2
votes
0
answers
171
views
Is there an example Hamiltonian that is uncomputable?
In a paper from 2015 Toby S. Cubitt et al showed that the problem of determining the existence of a band gap in the excitation spectrum of a quantum many-body system, was undecidable. This result ...
- 123
2
votes
0
answers
203
views
Can the relation between count of commuting pairs and conjugacy classes for finite groups be generalized to semigroups?
It is well-known that number of pairs of commuting elements in finite group G is equal to number of conjugacy classes multiplied by cardinality of G.
More generally here (MO275769) Qiaochu Yuan ...
- 24.9k
2
votes
0
answers
127
views
Quantifierisation of maps
I will rewrite my question using Matt F. suggestion.
Consider the logical structure $L = (\mathbb{R}, +, *, 1, 0, =)$ and a function $f:\mathbb{R}\to\mathbb{R}$.
Consider the map $Q:2^\mathbb{R}→2^\...
- 329
2
votes
0
answers
186
views
Are there some algorithms which have high consistency strength?
Are there some algorithms, their time complexity is relatively good, for example polynomial time.
And the correctness of them has high consistency strength.
And these algorithms shouldn't able to ...
- 1,490
2
votes
0
answers
193
views
What is the strength of the single Replacement sentence?
What's the consistency strength of adding the following single sentence replacement like statement to $\sf Z + \forall x \exists \alpha: x \in V_\alpha$ ?
$$\forall \varphi \forall A \ [\forall x \in ...
- 11.3k
2
votes
0
answers
183
views
A question on entailments in sequents
Suppose $\Gamma\vdash A\vee \Delta$, where as usual $\Gamma$ and $\Delta$ are thought of as sets of propositions and the turnstyle is for logical consequence, or entailment.
Given the assumption, may ...
- 3,574
2
votes
0
answers
326
views
Can we have $\sf V=HTD$? How it relates to $\sf V=HOD$?
In my search for some type-set motivated line of thought that might prove axiom of choice, I was thinking of a concept that looks like $\sf V=HOD$, but in terms of types instead of ordinals, that is ...
- 11.3k
2
votes
0
answers
74
views
Terminology and notation for generated subgroups
I would like to think about formation of the smallest subgroup (or monoid, or whatever) $H$ of $G$ containing two given subgroups $A$ and $B$ as an operation on subgroups, and I wonder if there is a ...
- 12.5k
2
votes
0
answers
71
views
Empty preimage under homomorphism of finitely presented groups with decidable word problems
Let $G, H$ be finitely presented groups with decidable word problems.
Can there be a homomorphism $f:G\to H$ such that there is no algorithm deciding given $w\in H$ whether $f^{-1}(w)$ is empty or not?...
user178109
2
votes
0
answers
258
views
Can we have a "very strong" cone phenomenon in the Turing degrees (and a related question)?
By Borel determinacy + Martin's cone theorem, for every countable fragment $\mathcal{A}$ of $\mathcal{L}_{\omega_1,\omega}$ there is a turing degree ${\bf c}$ such that for all ${\bf d}\ge_T{\bf c}$ ...
- 20.5k
2
votes
0
answers
177
views
Can NBG be interpreted in this system that use new notation for class-abstractions?
We introduce a new symbol $\lambda$ to denote class-abstractions, and we add the following rule:
if $\phi$ is a formula that use $``\mu"$, and in which the symbol $\sf y$ doesn't occur; then: $\lambda ...
- 11.3k
2
votes
0
answers
128
views
Can we have such a sequence of external automorphisms?
Working in some suitable extension of ZF, can we have a sequence of external [not appear in instances of separation and replacement] automorphisms $(j_n)_{n \in \omega}$ over the universe that move ...
- 11.3k
2
votes
0
answers
146
views
Are partial elements necessary in boolean-valued models?
It seems to me that there is a difference in the treatment of "partial" elements in boolean-valued models in set theory vs topos theory: in set theory, one usually only considers "...
- 15.9k
2
votes
0
answers
177
views
Definability of the ground model in its class-forcing extension
It is known that Laver's ground model definability theorem doesn’t hold for all class forcing notions. That is, if $M$ satisfies ZFC then $M$ is not necessarily definable in $M[G]$, a class forcing ...
- 533
2
votes
0
answers
145
views
Reference for Gödel-Bernays Axioms
I am currently working through Hungerford's Algebra, which in the first few pages claims to rely on the (or perhaps a) Gödel-Bernays axiomatization of set theory. I am looking for a citable reference ...
- 21
2
votes
0
answers
305
views
Is there a clear inconsistency with this system that would interpret NF?
This is a first order set theory, with the purpose of interpreting $\sf NF$ set theory:
Extensionality: $\forall X \forall Y: \forall z (z \in X \leftrightarrow z \in Y) \implies X=Y$
Pairing: $\...
- 11.3k
2
votes
0
answers
306
views
Can this external injection into a set from its power set, be not isomorphic on membership?
Add a primitive partial unary function symbol $F$ to the first order language of set theory.
Working in Zermelo (Separation restricted to the language of set theory), add the following axioms:
$F$ ...
- 11.3k
2
votes
0
answers
222
views
Countable Fodor's Lemma?
Does Fodor's lemma fail for countable ordinals?
For the usual statement of Fodor's lemma to make sense, one needs well-behaved notions of club and stationary sets, which fail for countable ordinals, ...
- 64k
2
votes
0
answers
157
views
Can we add $NF$ to Ackermann's set theory?
Can we simply add stratified comprehension $SF$ to axioms of Ackermann's set theory $Ack$?
Is there a clear argument of inconsistency involved with such addition? supposing that $NF$ and $Ack$ are ...
- 11.3k
2
votes
0
answers
89
views
Semigroups associated to binary necklaces and their semigroup algebra
I came across the following semi-group and the associated finite dimensional semi-group algebras over a field $K$ (which are Nakayama algebras) as they have very nice homological properties. My ...
- 26.5k
2
votes
0
answers
237
views
Representing iteration of a function in PA
Let $\mathscr{L}$ be a (recursive) FOL language, with numeral symbols $\underline{0},\underline{1},\ldots$. Let $T$ be a recursive, consistent theory, containing PA (or even just Robinson arithmetic)....
- 18.7k