All Questions
1,458 questions with no upvoted or accepted answers
2
votes
0
answers
75
views
Deduction theorem for the modal mu-calculus
Does the modal mu-calculus have a deduction theorem?
If yes, how is it stated? Does it have the 'classical' form (i.e. as in classical propositional logic) or is it more involved?
- 21
2
votes
0
answers
236
views
About functions primitive recursively definable using a $ \Sigma _ 1 $ oracle
In a discussion with one of my friends about degrees of computability, I was informed about something that was somehow new to me. As I'm not that much familiar with computability theory, I've ...
- 346
2
votes
0
answers
129
views
Logical axioms used in the construction of counterexamples to ISP
In many cases, some problems are either solved in an affirmative way, or in a negative way. However, in some cases it turns out that some logical axioms lead to a proof of a certain statement, while ...
- 1,175
2
votes
0
answers
185
views
Is the existence of undecidable propositions decidable?
In proving his first incompleteness theorem Godel constructed a proposition that is undecidable, i.e. neither provable nor disprovable within a consistent formal system $F$ that contains elementary ...
- 4,862
2
votes
0
answers
96
views
Non-commutative version of the order dimension of a poset
I view the order dimension of a poset $P$ as an inherently commutative notion. On the one hand, it can be defined via realizers, which I find fairly intuitive from an order-theoretic viewpoint. On the ...
- 51
2
votes
0
answers
116
views
Bijection between monoid of nilpotent decreasing self-maps and local subsemigroup
Let $\mathcal{C}_X\cong\mathcal{C}_n$ be the monoid of self-maps $\alpha$ of $X=\{1\dots,n\}$ that are order-preserving ($\forall x,y$, $x\le y$ $\Rightarrow$ $\alpha(x)\le\alpha(y)$) and decreasing ($...
- 355
2
votes
0
answers
33
views
On the number of connected functional digraphs recoverable from the preimage set size structure
I am studying the list of inverse images (preimage sets) of some function $f$ at a given inverse depth $j$ -- for each element $x_i$ of a finite domain $X$.
For example,
$P_j=\left[f^{-j}(...
- 23
2
votes
0
answers
247
views
Can we have the well founded world of NF obeying ZF?
The following question is about the possibility of having a world of sets obeying new foundations "NF" with their well founded sets obeying rules of ZF. It uses the revised version of Quines ...
- 11.3k
2
votes
0
answers
404
views
A decision problem from sheaf set theory?
Let $V^{X}$ be a sheaf model of ZF set theory, where $X$ is a topological space as it is defined in [1].
Let $T(y_1,\ldots,y_n)$ be an $B(T)$-free algebra as it is defined in [2], where $B(T)$ is the ...
- 121
2
votes
0
answers
91
views
Is the natural action of the monoid of endomorphisms is a complete invariant for group?
Let $\alpha$ and $\beta$ be actions of semigroups $A$ and $B$ on sets $X$ and $Y$ respectively. Recall that $\alpha$ and $\beta$ are called isomorphic if there exists an isomorphism $\phi$ between ...
- 6,962
2
votes
0
answers
48
views
Compute irreducibles of monoid
Given $n > 0$ and $w \in \mathbb{Z}^n$. Is there an efficient algorithm to compute the set of irreducible elements of the monoid $M_w = \{x \in \mathbb{N}^n \mid \langle x,w\rangle = 0 \}$?
Here, ...
2
votes
0
answers
267
views
Continuum hypothesis in nonstandard universe
In Vladimir Kanovei's book "Nonstandard Analysis, Axiomatically", some nonstandard set theory is introduced. It seems that, one of them, DNST, is useful.
When we are talking about higher order ...
- 475
2
votes
0
answers
219
views
Categorical semantics of the identity type
In Appendix B of the article Simplicial Model of Univ. Foundations, Definition B.1.3 specifies the structure for identity types in a contextual category $\mathcal{C}$ (which in particular is equipped ...
- 317
2
votes
0
answers
60
views
Are there finitely-presented astral monoids?
We say a semigroup $S$ is $k$-astral if there exists a finite set $F \subset S$ such that
whenever $s_1, s_2, ..., s_k \in S$ there exists $s \in S$ such that $\forall i: s_i \in sF$. Say $S$ is ...
- 6,652
2
votes
0
answers
149
views
Primitive recursive functions
Suppose $f_1, f_2, ... ,f_n$ is a finite list of primitive recursive functions.
Consider the set of terms $T$ that can be constructed from $f_1, .... , f_n$ and the constant $0$.
Consider the ...
- 358
2
votes
0
answers
183
views
Cut elimination proofs of the consistency of arithmetic
It is well known that one can use cut elimination to establish the consistency of arithmetic (though this involves assuming transfinite induction up to $\varepsilon_0$.) Most proofs, however, work ...
- 358
2
votes
0
answers
159
views
Why not replace reflection by bounded reflection in Muller's approach?
Bounded Reflection: If $\phi$ is a formula in the language of set theory [i.e.; $\small \sf FOL(=,\in)$], in which all and only symbols $``x,x_1,..,x_n"$ occur free, and $\phi^V$ is the formula ...
- 11.3k
2
votes
0
answers
90
views
'Algebraic Skolemization' of (neo-)stable theories
A slightly obtuse way to say that a first-order theory $T$ has Skolem functions is to say that for any $M\models T$ and $A\subseteq M$, $\mathrm{dcl}(A)\preceq M$.
This suggests a similar condition ...
- 13k
2
votes
0
answers
65
views
Length of Gaps in Clockable Values
As I understand, there can't be any (total) OTM computable function (in traditional input/output sense) $f:Ord \rightarrow Ord$ such that $f(x)$ gives an upper-bound on the length of the $x$-th gap.
...
- 881
2
votes
0
answers
305
views
Does this axiomatic system satisfy requirements for founding mathematics?
In this article, the author, F.A.Muller, suggests criteria for a founding theory of mathematics (pp:14-16). The author proposes $ARC$ Class Theory to embody these requirements. The motivation is ...
- 11.3k
2
votes
0
answers
73
views
How to decide if a recursive addition of subsets after certain formula would terminate?
Lets call a definable property $\phi(y,z_1,..,z_n)$ as terminating over a set $A$ if and only if recursive successive additions of every set $\{y \in A| \phi(y,z_1,..,z_n)\}$ from parameters $z_1,..,...
- 11.3k
2
votes
0
answers
170
views
Proof of the Specker-Blatter theorem
The theorem in the title states the following: If $\mathcal{C}$ is a class of structures definable in monadic second order logic with unary and binary relation symbols only, then the function $f_\...
- 265
2
votes
0
answers
161
views
What is the consistency limit of accumulative typing below $\omega_1^{CK}$?
Let $Th_\zeta$ be a Mono-sorted first order theory with $\zeta$ representing some recursive ordinal notation system.
Primitives: =, $\in$, $T_0, T_1, ..,T_i,..$ where i is an $\zeta$ ordinal, and ...
- 11.3k
2
votes
0
answers
173
views
How to construct "inaccessible hypernatural"?
Consider that, take a sufficient large natural number $a_1$, then take a natural number $a_2$ sufficient large to $a_1$, then take $a_3$,...
Now we have a function $n \mapsto a_n$ which grows very ...
- 475
2
votes
0
answers
110
views
What conditions make this embedding become algebraically closed?
This question is just out of curiosity.
Let $\mathcal{L}$ be the first-order language of theory of rings. Let K and F are two fields such that $K \subseteq F$. If K is existentially closed in F, ...
- 151
2
votes
0
answers
142
views
The premises of Aczel's inductive definitions
This is a follow-up to
https://stackoverflow.com/questions/49650053/are-inductive-definitions-finitely-generated-in-isabelle
As I said there, Aczel writes in his paper An Introduction to Inductive ...
- 289
2
votes
0
answers
77
views
Substructural shuffling: can we avoid a modal collapse in a certain Intuitionistic modal logic via making the logic linear?
Consider Propositional Lax Logic ($PLL$)
https://www.uni-bamberg.de/fileadmin/uni/fakultaeten/wiai_professuren/grundlagen_informatik/papersMM/pll.pdf
The Hilbert system of $PLL$ takes as axiom ...
- 639
2
votes
0
answers
183
views
Notation in 'The lambda calculus, its syntax and semantics' by H.P. Barendregt
I'm reading the book 'The lambda calculus its syntax and semantics'. In part 5, chapter 19: Local structure of Models, more specifically 19.2 Local structure of $D_\infty$, the notation $D_\infty \...
- 21
2
votes
0
answers
80
views
Are the roots of an infinitely divisible probability infinitely divisible themselves?
Let $\mu$ be an infinitely divisible probability on a topological group $G$. If $\nu ^{* n} = \mu$ for some $n$, is $\nu$ an infinitely divisible probability too?
A sufficient criterion would be to ...
- 5,407
2
votes
0
answers
93
views
Universal abstract elementary classes and closure operators
In this article Hyttinen and Kangas claim that universal abstract elementary classes which are categorical are essentially classes of vector spaces as soon as the model reaches a critical cardinality.
...
- 9,111
2
votes
0
answers
105
views
Why can a least fixed point operator only be expanded finitely many times?
If we expand modal logic with least and greatest fix point operators $\mu$ and $\nu$, respectively, we obtain the logic $L_\mu$.
An alternating automaton on infinite trees has a state space that is ...
- 21
2
votes
0
answers
89
views
Is the equational theory of the variety of ternary self-distributive algebras decidable?
A ternary self-distributive algebra is an algebra $(X,t)$ that satisfies the identity $$t(u,v,t(x,y,z))=t(t(u,v,x),t(u,v,y),t(u,v,z)).$$
Is the equational theory of the variety of ternary self-...
2
votes
0
answers
325
views
The universe and multiverse views of set theory from the perspective of $ZFC^2$
(Note: the 'Second-order $ZFC$' ($ZFC^2$) I am talking about is the theory [in the second order language of set theory consisting of a single non-logical symbol $\in$ ] consisting of the axioms ...
- 6,132
2
votes
0
answers
81
views
A semigroup property related to von Neumann regularity
A very common and useful notion in rings is that of von Neumann regular elements: those elements $a\in R$ such that there exists $b\in R$ satisfying $aba=a$. As this is a property defined solely ...
- 18.7k
2
votes
0
answers
50
views
Nonautonomous wave equation of memory type
I want to apply the semigroup approach of nonautonomous evolution equation for the following wave equation
$$u'' - \Delta u + \int\limits_0^t {g(s)} \Delta u(s)ds = 0$$
This problem can be written ...
- 617
2
votes
0
answers
169
views
What is the difference between a monosemiring and a semigroup?
What is the difference between a monosemiring and a semigroup?
The following definitions are for clarity of my question.
A semigroup $S$ is a non empty set that satisfies closure and associativity ...
- 203
2
votes
0
answers
63
views
QF-3 monoid algebras
A finite dimensional algebra $A$ is called QF-3 in case the injective envelope of the regular module is projective. For example all Frobenius algebras are QF-3.
Given a monoid algebra $kG$ of a finite ...
- 26.5k
2
votes
0
answers
91
views
Semigroups of nondecreasing functions
Consider some partially ordered set $(E,\leq)$. Assume either that it is countable with the discrete topology, or that it has some topology compatible with the order, preferably one that makes it into ...
2
votes
0
answers
98
views
If $H$ is an atomic, unit-cancellative monoid such that the set of atoms of $H$ is finite up to associates, then $H$ is BF
In a previous version of this post, $H$ was an atomic commutative monoid such that the quotient $H/H^\times$ is finitely generated, and I was asking if such conditions were enough for $H$ to be BF. ...
- 10.5k
2
votes
0
answers
139
views
Getting a copy of Stanley H. Stahl's dissertation on "Classes of primitive recursive ordinal functions"
Stanley Hershel Stahl did his PhD thesis at the University of Michigan, under the direction of Peter Hinman, and wrote a dissertation in 1974 with title "Classes of Primitive Recursive Ordinal ...
- 32.5k
2
votes
0
answers
392
views
Geometric Theories have models in any Grothendieck Topos?
This question is linked to this one.
My question is:
Is it true any consistent geometric (here I mean coherent theory, different books have different standards) theory $T$ has a model in a ...
- 9,111
2
votes
0
answers
118
views
About existential graphs
I would like to read articles about Peirce's existential graphs. I already have the works of Brady and Trimble on it, and I would like to know if there exists a geometric approach to them, or a ...
2
votes
0
answers
62
views
Extensions of an ideal-theoretic criterion for a monoid to be BF
Let $H$ be a multiplicatively written, commutative monoid. We denote by $H^\times$ the set of units (or invertible elements) of $H$, and by $\mathcal A(H)$ the set of atoms (or irreducible elements) ...
- 10.5k
2
votes
0
answers
90
views
Recursion theoretical Characterization of time complexity classes
Is there any known Recursion theoretical Characterization of time complexity classes like $\mathsf{DTIME(n^k)}$ or $\mathsf{NTIME(n^k)}$ for some fixed $k$?
Thanks.
- 1,689
2
votes
0
answers
51
views
Existence of a canonical embedding from a quotient of $\mathscr{F}^\ast(\mathcal A(H))$ to another
Let $H$ be a multiplicative, commutative monoid, and denote by $H^\times$ the group of units of $H$, by $\mathcal A(H)$ the set of atoms (or irreducible elements) of $H$, by $\mathscr{F}^\ast(\mathcal ...
- 10.5k
2
votes
0
answers
192
views
$P=NP$ and provability of family of propositional formulas
Let $\mathcal{L}'=\{+,\cdot,0,S,=,<,||,\#,R\}$ be the lanugage of bounded arithmetic with a $k$-ary relation $R$.
For every bounded sentence $\phi({\bf\bar{n}})$ in $\mathcal{L}'$ define ...
- 1,689
2
votes
0
answers
113
views
Description of all total recursive functions where operator is effective?
What is a description of all total recursive functions $g(x)$ for which the operator$$\Phi_g: \mathcal{F}_2 \to \mathcal{F}_1$$defined by the formula$$\Phi_g(f)(x) := g(\mu y(f(x, y) = 0))$$is ...
- 45
2
votes
0
answers
111
views
Internal characterization of topos validity
I'm using Goldblatt's "Topoi: A categorical analysis of logic" as an introduction to topos logic. At the end of chapter 6, he defines the validity of propositional formulas (I'm not concerned with ...
- 171
2
votes
0
answers
194
views
Locally consistent theories
Is there a notion in the literature of a theory which is locally consistent, in some sense wherein choosing a "vantage" yields a theory which is consistent, but the entire theory may not be consistent?...
- 713
2
votes
0
answers
149
views
Strong determinacy principles for "small" sets
In the course of a (fun but silly) project I'm working on, I've run into the following class of determinacy notions:
Suppose I have a "reasonably definable" class $\mathcal{C}$ of games (in the usual ...
- 20.5k