All Questions
1,460 questions with no upvoted or accepted answers
0
votes
0
answers
41
views
Characterizing centralizer of nilpotent self-maps
Let $\mathcal{C}_n$ be the monoid of self-maps $\alpha$ of $\{1\dots,n\}$ that are order-preserving ($\forall x,y$, $x\le y$ $\Rightarrow$ $\alpha(x)\le\alpha(y)$ and decreasing ($\forall x$, $\alpha(...
- 109
0
votes
0
answers
199
views
Is there a formula with one free variable in NBG that defines a class that does not exist?
This question concerns Godel's Theorem on existence of classes in Set Theory of von Neumann–Bernays–Gödel.
This theorem implies that for any formula $\varphi(x)$ with one free variable $x$ whose ...
- 41.9k
0
votes
0
answers
93
views
A semifield of characteristic zero may have a finite number of elements
A commutative semiring $(S, +, \cdot, 0, 1)$ with unity is said to be a semifield if for all $a, b\in S$, $a+b=0$ implies that $a=0$ and $b=0$, and $a.b=0$ implies that either $a=0$ or, $b=0$.
I ...
- 203
0
votes
0
answers
117
views
Can inaccessibility be captured in relational flat set theory?
Working in a first order theory of flat sets (axioms given below) , which is a theory with a single non-trivial tier of membership, that is all sets are nonempty sets of Quine atoms, plus having some ...
- 11.3k
0
votes
0
answers
92
views
Lindenbaum lemma and non-monotonic logics
Is it possible to apply Lindenbaum's lemma to non-monotonic propositional logics to prove completeness theorem? To be more specific, for a given non-monotonic deductive system is it always possible to ...
user57432
0
votes
0
answers
142
views
Why not this reflective-size set theory be the foundational theory of sets?
Language: first order logic with equality + primitives of membership $\in$ and a constant $W$ signifying the world of all sets.
Axioms:
Extensionality: $\forall z (z \in x \leftrightarrow z \in y) \...
- 11.3k
0
votes
0
answers
66
views
A countable expression expressible in $\mathrm{FO}_3$ with only one binary predicate?
Transitivity on a set is defined as follows
$$\forall x \forall y\forall z( T(x,y) \land T(y,z) \rightarrow T(x,z))$$
Now if we wanted to count total number transitive relations which are defined on ...
- 131
0
votes
0
answers
61
views
Can consistent proxi-finite extensions of ZFC be additive?
The definition of "strongly coming from $HF$" is given in this posting.
Question: if $\varphi, \psi$ each is strongly coming from $HF$, then can the following be true?
$Con (ZFC + \varphi) \land Con ...
- 11.3k
0
votes
0
answers
136
views
What's the consistency strength of resemblance + global failure of the continuum hypothesis?
Let $T$ be a theory formalized in first order logic with equality and membership and the additional primitive constant symbol $W$, with the following axioms:
Extensionality: $\forall z (z \in x \...
- 11.3k
0
votes
0
answers
110
views
Expressing a model transformation by using monads in the simply-typed lambda calculus
In https://link.springer.com/content/pdf/10.1007/s10670-019-00128-z.pdf , page 16, the following clause is given for a modal operator $\langle R_k \rangle$ (see definition 4.2 for the definition of a ...
- 639
0
votes
0
answers
115
views
What's the exact consistency strength of this proper fragment of Muller's class theory?
This question is largely connected to the question presented here.
Let $T$ be the theory extending first order logic with equality, with primitives of a binary symbol $\in$, an unary symbol $S$; and ...
- 11.3k
0
votes
0
answers
75
views
Can extensionality and separative-reflection interpret all rules of set theory?
Language: first order logic with equality, with additional primitives of membership $\in$ and a constant symbol $V$ standing for the class of all sets.
Extensionality: $\forall z (z \in x \...
- 11.3k
0
votes
0
answers
219
views
Is there a foundational approach that takes "structure" as primitive?
As per the title, I'd be curious to know if there have been attempts at constructing a foundation of mathematics taking, somehow, purely the notion of "structure" as primitive, maybe via a system of ...
- 23.3k
0
votes
0
answers
119
views
Is there a standard way to relativize algorithmic complexity constructively?
Given an index set $A$ of indices that compute some (class of) structures such that $A$ is complete in the class $ \Pi^0_n$ in the arithmetical hierarchy, let’s say we want to determine the ...
0
votes
0
answers
192
views
Is this anti-foundation axiom consistent?
Starting with ZFC:
Replace axiom of Extensionality by weak Extensionality (nonempty sets having the same members, are identical)
Remove axiom of Foundation.
Add the anti-foundation axiom which ...
- 11.3k
0
votes
0
answers
444
views
Artificial intelligence simulating mathematicians (what a distopia!)
This is kind of soft and naive question, so feel free to shame on me :)
I start from the fact that, in my opinion, what humans are interested in about mathematics are things that we find deep and ...
- 2,152
0
votes
0
answers
133
views
Can we have a countable universe if we weaken limitation of size to parameter free replacement in MK set theory?
Starting from $MK$, if we
replace the axiom of limitation of size by an axiom schema of parameter free Replacement, that is: any parameter free definable class bijection from a set domain, has a set ...
- 11.3k
0
votes
0
answers
104
views
How much high iterative partitioning of the first inaccessible stage can be?
Working in $ZF$ + existence of an inaccessible ordinal.
Let $\kappa$ be the first inaccessible ordinal (i.e. the first regular ordinal that is a limit of regular ordinals).
Let subpartition of $X$ ...
- 11.3k
0
votes
0
answers
118
views
What's the consistency strength of this theory of Stretchable Hierarchies?
Working in Morse-Kelley set theory:
A hierarchy is defined as a class that is the union of sets uniquely indexed by ordinals, called as stages, such that each stage is the power set of the ...
- 11.3k
0
votes
0
answers
194
views
What known paradoxes are associated with having a type-level tuple indexed by all ordinal numbers?
By a type-level tuple $t(f)$ that captures a function $f$, it is meant a relation that is definable by a stratified formula that assigns to $t(f)$ the same type it assigns to each element of the ...
- 11.3k
0
votes
0
answers
62
views
Can we have relations of the same type of their composing ordered pairs?
Is it possible to define a binary function $P$ in the language of set theory that obeys the characteristic property of ordered pairs and such that for any two sets $A,B$, for any definable relation $R$...
- 11.3k
0
votes
0
answers
184
views
Can second order ordinal arithmetic be extended to the same extent as ZFC?
In a prior posting, I've posed the idea of reducing set theory to an extended kind of second order ordinal arithmetic $\small \sf`` 2 oO A"$. The idea was to have a domain of ordinals and sets of ...
- 11.3k
0
votes
0
answers
97
views
Is there a criterion for reducibility of equi-interpretable theories?
I want to coin a notion for reducibility of theories. Generally this goes like that: if we have two equi-interpretable theories $T;Q$ and it is harder to interpret $T$ in $Q$ than to interpret $Q$ in $...
- 11.3k
0
votes
0
answers
172
views
Is this fragment of NF known to be consistent?
The following theory is a fragment of $\small \sf NF$. My question is about if it is known to be consistent without assuming the consistency of $\small\sf NF$.
The language is of first order logic ...
- 11.3k
0
votes
0
answers
160
views
Strength of $Δ^1_{2n}$ determinacy
According to Lightface mice with finitely many Woodin cardinals from optimal determinacy hypotheses by Yizheng Zhu, theorem 1.1, over $\mathbf{Σ^1_{2n+1}}$ determinacy, $Δ^1_{2n+2}$ determinacy is ...
- 7,545
0
votes
0
answers
147
views
Groups implementable by finite field
I'm interested in finding all groups for which the group operation (and inverse map) may be implemented using finite field arithmetic.
I've done some searching and have come across "algebraic groups",...
0
votes
0
answers
162
views
Are the HBL derivability conditions necessary for Gödel's incompleteness theorems? (For Löb's theorem?)
I've been working through a textbook, often encountering difficulties with the exercises.
On mathstackexchange, with most of them I haven't arrived yet at a satisfactory solution.
As I understand, ...
- 121
0
votes
0
answers
96
views
Shepherdson's conditions - a shortcut to the second incompleteness theorem?
I've been working through a textbook, often encountering difficulties with the exercises. On mathstackexchange, with most of them I haven't arrived yet at a satisfactory solution.
As I understand, ...
- 121
0
votes
0
answers
179
views
Can reflection in $V$ and reflection out of $V$ principles be used in the same theory?
I've noticed that most of the work in Ackermann set theory is primarily concerned with constructing sets in $V$, the rest of the classes are just excess material, carrying no comprehension over them. ...
- 11.3k
0
votes
0
answers
150
views
Is "ZF+ V=L" an upper limit theory for cardinal decidability (per its strength)?
{EDIT: this posting has been edited, the additional text is in italics}
If $\varphi, \psi$ are two parameter free formulas in the language of set theory $T$ such that there is a theorem of $T$ that ...
- 11.3k
0
votes
0
answers
387
views
Is there a known shorter axiomatization of NF than this?
Is there an already known axiomtization of $NF$ that is shorter than the following axiomatic system in first order logic with equality $``="$ and membership $``\in"$? And what is exactly meant by ...
- 11.3k
0
votes
0
answers
92
views
Functoriality of indiscernible sequences
Let $T$ be a first order theory of, say, some type of combinatorial geometries which contain indiscernible sequences of points. Let $(\Gamma,\mathcal{O})$ be a model of $T$, where $\Gamma$ is the ...
- 4,547
0
votes
0
answers
213
views
make me idempotent
$T_n$ be the full transformation semigroup on $X_n= \{1, 2, \cdots , n\}$.
$D_r =\{\alpha \in T_n: |im(\alpha)|=r\}$.
$E(D_r)$ is the set of all idempotents of semigroup $T_n$.
$support(\alpha)=\{...
- 109
0
votes
0
answers
92
views
Example of a zero-knowledge protocol for a strictly Pi_n sentence?
I'm looking for an example of a zero-knowledge protocol such that (1) the prover Peggy can demonstrate to the verifier Victor that she has a proof of $P$ (to the usual standards of a zero-knowledge ...
- 1,155
0
votes
0
answers
128
views
Is this schema equivalent to Replacement under removal of Extensionality?
If $\phi(x)$ is a formula in which only symbol $``x"$ occurs free, and it only occurs free, and in which symbol $``y"$ never occurs; and if $\phi(y)$ is the formula obtained from $\phi(x)$ by merely ...
- 11.3k
0
votes
0
answers
187
views
How are incompleteness and independence proofs related?
(1) Some typical inclompleteness proofs use a kind of fixed point argument - for certain $\Phi$ you find a $\varphi$ with $\Phi(\mathrm{code}(\varphi))\leftrightarrow\varphi$.
(2) Some independence ...
- 18.4k
0
votes
0
answers
136
views
Amalgamated free-product of semigroups (definition)
I am self-studying some concepts including the title one. I reached the definition of an amalgamated free-product ${S_1}{*_U}S_2$ where $[S_1, S_2; U, w_1,w_2]$ is an amalgam of semigroups. Let $S_1=\...
- 233
0
votes
0
answers
53
views
a generalization of group (monoid with order-by-order invertible elements)
Fix a filtered monoid, $H=H_0\supsetneq H_1\supsetneq H_2\supsetneq\cdots$. Suppose for any $h\in H$ and any $n\in \Bbb{N}$ exists $h_n\in H$ such that $h\cdot h_n\in H_n$ and $h_n\cdot h\in H_n$. If ...
- 2,232
0
votes
0
answers
148
views
Converting complicated general propositional formula to CNF
I have a propositional formula of the form
$$\bigvee_{i=1}^n \neg \left( x_i \Leftrightarrow \left(\bigvee_{j=1}^{f(i)} y_{ij} \right) \right)$$
where the $x_i$'s are propositional variables and ...
- 283
0
votes
0
answers
226
views
Does Bounded Arithmetic, $I\Delta_0$, prove the Recursion Theorem?
Compare my question Does Robinson Arithmetic already entail the Recursion Theorem. I would find it desirable and interesting if $I\Delta_0$ could be extended with a comprehension principle CP stating ...
- 3,574
0
votes
0
answers
127
views
Totally computable least real upper bounds for bounded recursive sets of totally computable real numbers?
A recursive set $Y$ is a set with a characteristic total computable function $\chi_Y$ so that $\chi_Y(n)=0$ iff $n\in Y$ and $\chi_Y(n)=1$ iff $n\notin Y$. Let a $recursive \ condition$ be one which ...
- 3,574
0
votes
0
answers
101
views
Spherical Rings
My question is concerned with filtered rings. It is a classical result that if $R$ is a finitely generated commutative ring graded by a semigroup $S$ then $S$ is also finitely generated.
The reverse ...
- 501
0
votes
0
answers
75
views
Homomorphic image of $B_{\lambda}^o(S)$ is the Brandt $\lambda^o$-extension of some monoid with zero
Let $S$ be a monoid with zero and $I_{\lambda}$ be an indexed set, then $B_{\lambda}(S) = \{ (\alpha, s , \beta ) : \alpha , \beta \in I_{\lambda}, s\in S \} \cup \{0\}$ is a semigroup and $J = \{ (\...
- 143
0
votes
0
answers
125
views
Embedding a cancellative monoid into another in such a way that $|X-x|=|X|$, where $X$ is a fixed finite set and $x\in X$
Preliminaries.
Let $\mathbb A = (A, +)$ be a possibly non-commutative semigroup. For $X, Y \subseteq A$ we set
$$
X - Y := \{a \in A: a + y \in X\text{ for some }y \in Y\},
$$
which is just the usual ...
- 10.5k
0
votes
0
answers
197
views
Is the positive existential theory undecidable?
Could you tell if the positive existential theory of $\mathbb{C}[e^{\mu x} \mid \mu \in \mathbb{C}]$ is undecidable in the language $\{+, \cdot , \frac{d}{dx} , 0, 1, e^x\}$ ?
How can we prove the (...
- 309
0
votes
0
answers
173
views
Minimum regular open set containing a given set in a T0 Alexandrov topological space
What is known about the minimum regular open set containing a given set in a T$_0$ Alexandrov topological space? I'm particularly interested in the condition for the minimum set happening to be first-...
- 1
0
votes
0
answers
410
views
Set as a (strict) infinite-category?
First, let me say that I have no idea if such a post has its place here. However, I believe that the ideas I'm going to present are important. The goal of this thread is three fold:
1) trying to ...
- 438
0
votes
0
answers
46
views
representing quasicrystal as tilings and appearing frequencies of each tile
Quasicrystal can be fully represented either using projection method or tilings with constraints. For the latter, is there some sort of study on the "appearing frequency" of each tile or even ...
- 867
0
votes
0
answers
136
views
Monoid action on an uncountably infinite set
The action of a monoid on a finite set is equivalent to a finite state machine, however I would like a categorical way to think about an uncountably infinite state machine (a state transition system?)....
- 101
0
votes
0
answers
72
views
Decomposition results for locally commutative semigroups
Every finite abelian group is the direct product of its cyclic groups of prime order, and every commutative monoid divides a product of its cyclic submonoids. Could these results generalized to ...
- 798