All Questions
1,459 questions with no upvoted or accepted answers
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
2
votes
0
answers
75
views
Sequence of formulae and limit objects
Let $(G_i,x_i)$ be a sequence of rooted graphs that we can assume to have uniformly bounded (finite) maximum degrees, and let $P_i$ be a sequence of first order formulae (in the language of graph ...
- 541
2
votes
0
answers
106
views
Descent of flatness from algebras to monoids II
This is a follow-up question to this one. There, Benjamin Steinberg showed that a morphism of commutative monoids $u$ need not be flat if the induced morphism of $R$-algebras $R[u]$ is flat for some ...
- 6,700
2
votes
0
answers
328
views
The category of sets and "stateful" functions
In some programming languages, there's functions whose output can change on the basis of changing internal state; for example, the second time you compute $f(5)$ you might get a different answer. This ...
- 3,793
2
votes
0
answers
147
views
When do wide initial segments ruin admissibility?
Suppose $\alpha$ is admissible and $\beta<\alpha$. We know that $L_\alpha$ is an admissible set (by definition), but adding subsets of $\beta$ to $L_\alpha$ might break admissibility: while set ...
- 20.5k
2
votes
0
answers
178
views
Monoid prime ideals and prime congruences
I was wondering what the connection is between the notion of "prime congruence" on a monoid, and the notion of "prime ideal" in a monoid. Starting from a prime ideal $P$ in a monoid $M$, one can ...
- 4,547
2
votes
0
answers
409
views
A question on the consistency of a (seemingly) very weak set theory
I have preoccupied myself some with very weak set theories that suffice to interpret Robinson Arithmetic, as in this question Is Extensionality needed for the incompleteness of very weak set theories?....
- 3,574
2
votes
0
answers
179
views
Some questions regarding an alteration of Grzegorczyk's theory of concatenation, $\operatorname{TC}$
Consider Grzegorczyk's concatenation theory $\operatorname{TC}$, a "weak theory of words over the two letter alphabet $\Sigma=\{a,b\}$" (this from Grzegorczyk and Zdanowski's paper Undecidability and ...
- 6,132
2
votes
0
answers
90
views
Fully residually free groups and completion
Let $G$ be a fully residually free group with a finitely generated profinite completion. Is $G$ necessarily finitely generated?
- 11.3k
2
votes
0
answers
122
views
A Question on Provability Logic and Co-Necessitation
The provability logic $GL$ has the characteristic axioms:
$K\hspace{15pt}\Box(\alpha\rightarrow \beta)\rightarrow(\Box\alpha\rightarrow\Box\beta)$
$L\hspace{15pt}\Box(\Box \alpha\rightarrow \alpha)\...
- 3,574
2
votes
0
answers
134
views
A question regarding an analogue of the Kleene $T$-predicate for Koepke's ordinal computability
Does Koepke's notion of ordinal computability admit an analogue of the Kleene $T$-predicate? If so, is the existence of such a $T$-predicate independent of $ZFC$? Also, if one assumes the existence ...
- 6,132
2
votes
0
answers
130
views
Kripke semantics for fuzzy logics
I am interested in Fuzzy logic.
I have a problem about Gödel Logic, I'm studying Kripke semantics for fuzzy logics and have found the necessary and sufficient conditions on Kripke frames for ...
- 137
2
votes
0
answers
81
views
Which self-reference restrictions can be weakened in probabilstic logic?
This work suggests that there is some generalization of Truth in terms of probability, which can be definable within the logic itself.
Is where any other thorems on self-reference restrictions, which ...
- 123
2
votes
0
answers
149
views
RCS iteration such that the RCS limit is semi-proper
For a countable ordinal $\eta$ and an ordinal $\gamma$ let $\langle P_\alpha, \dot{Q}_\alpha \colon \alpha < \gamma \rangle$ be an RCS iteration with RCS limit $P_\gamma$, such that
$\Vdash_\...
- 21
2
votes
0
answers
47
views
Relation between indexed languages (OI-macro or context-free tree) and scattered context languages
I'm not sure about the relation between indexed languages (generated by indexed grammars--Aho) and scattered context languages (generated by
scattered context grammars--J Hopcroft).
I think that ...
- 21
2
votes
0
answers
87
views
Terminology for torsion semigroups where the order of elements is uniformly finite
A (multiplicatively written) semigroup $\mathbb A = (A, \cdot)$ with the property that ${\rm ord}_\mathbb{A}(a) := |\{a^n: n \in \mathbf N^+\}| < \infty$ for every $a \in A$ is called a periodic (...
- 10.5k
2
votes
0
answers
220
views
Type theory: can multiple elimination rules be defined, in principle?
I'd like to ask a question on type theory:
Consider the usual type theoretical definition of the natural numbers. We could give an elimination rule in the form:
or in the form:
I called the ...
- 243
2
votes
0
answers
159
views
BL Algebras that allow for Compactness to hold
Say we have a model $M$ of a theory $T$ of some core fuzzy logic.
When dealing with compactness, we run in to a situation where the new model being built (by the use of compactness over $M$), will ...
- 185
2
votes
0
answers
203
views
Profinite Topology
Let $V$ and $W$ be pseudovarieties of finite groups. For a finite inverse monoid $M$, the $V$-kernel of $M$ is defined to be the intersection of all sets $f^{−1}(1)$, $f$ is a relational morphism ...
- 421
2
votes
0
answers
180
views
Pro-p topology on free group
Let $H$ be a finitely generated subgroup of the free group $F(A)$ and $G_P$ the pseudovariety of all finite $p$-group with $p$ fixed prime number. We endow $F(A)$ with the pro-$G_p$ topology. Suppose ...
- 421
2
votes
0
answers
266
views
Relationship between coherent toposes/coherent logic and coherent sheaves
I've heard it claimed that the adjective "coherent" in logic/topos theory (i.e. coherent logic, coherent toposes, coherent categories) was adopted to fit in with the terminology of coherent sheaves in ...
- 3,058
2
votes
0
answers
139
views
Goldie's Theorem for Semigroups
Goldie's theorem is a theorem in noncommutative ring theory that gives a clear picture of semiprime Noetherian rings (actually a slightly broader class). Let $R$ be a semiprime Noetherian ring. The ...
- 6,870
2
votes
0
answers
237
views
Kripke frames as classes of partitions
Here's something I've been playing with off and on for a bit; I'm curious if anyone has seen it before.
For this question, a Kripke frame $K$ is a finite reflexive directed graph. (Reflexivity isn't ...
- 20.5k
2
votes
0
answers
116
views
May $\Sigma_3$-collection hold below $\Sigma_3$-admissible ordinals for Gödel's L?
Suppose you have a system X=$KP$ + infinity plus $\Sigma_{3}$-collection and $\Delta_{2}$-specification. May $L_{\delta}\vDash X$ for some $\delta$ smaller than all $\Sigma_{3}$ admissible ordinals?
- 3,574
2
votes
0
answers
88
views
A question on recursion and transfinite recursion in extensions of KP
Is the $\Sigma_{n}$-recursion supported by $\Sigma_{n}KP=KP+\Sigma_{n}$-separation + $\Sigma_{n}$-collection equivalent with $\Sigma_{n}$ transfinite recursion? If not, how do these notions differ?
- 3,574
2
votes
0
answers
337
views
Wolfram's axiom completeness
I have been reading Wolfram's A New Kind of Science, and as I was reading the section on systems of logic and axioms, I came across this axiom, for which all of the normal axioms of Boolean logic can ...
- 2,811
2
votes
0
answers
216
views
Standard name for a Monoid/Semigroup with $a+b \leq a, b$?
I have seen suplattice and inflattice being used when dealing with a lattice. What about when you don't have a lattice?
For instance, for reals $a,b > 0$, define $$a \oplus b = \frac{1}{\frac{1}{a}...
- 121
2
votes
0
answers
131
views
characterization of all periodic tiling of a simple set of Wang Tile
Consider a set of Wang Tile such that all the edges are either 1 or 0.... there are 16 elements in such a set.
Now, I wish to characterize all the periodic tilings of this set (better if they are ...
- 867
2
votes
0
answers
163
views
Graph theoretical representation of Wang Tile
We note that for one dimensional tiling problem of Wang Tile could be represented by a graph. Each cycle on the graph represents a periodic solution.
However, is there a well established counter-part ...
- 867
2
votes
0
answers
122
views
First-countable topological monoids without local absorbing elements whose topology is induced by a semimetric
This is a follow up of Question 163246. For the reader's convenience, let me first copy&paste some basic definitions.
We let a semimetric on a set $X$ be a function $d: X \times X \to [0,\infty]$ ...
- 10.5k
2
votes
0
answers
85
views
A question on completeness for quantified temporal logics
Quantified temporal logics have the Barcan formulas and its converses for both G (it will always be the case that) and H (it has always been the case that), so that both $\forall x G \alpha \...
- 3,574
2
votes
0
answers
48
views
Completeness results for quantified tense logics with BF?
Modal tense logics or temporal logics are important in that they correspond with partial orders and their extensions.
Are there completeness results for quantified temporal logics with the Barcan ...
- 3,574
2
votes
0
answers
148
views
Dedekind reals in heyting valued models
Let $V^{H}$ be a Heyting valued model of intuitionistic set theory. What conditions does $H$ have to satisfy in order for the following claim to hold? (where $\| \phi(u) \| \in H$ is the truth value ...
- 631
2
votes
0
answers
107
views
Is there a nice theorem that makes essential use of types in typed first-order logic?
I've read (somewhere) that types in typed first-order logic is just 'syntactic sugar'.
But, surely there is more to than that?
For example: the upper-bound property of the reals can't be expressed ...
- 2,083
2
votes
0
answers
137
views
Extend Lowenheim's decidability result to fragment of second-order logic
Since relational monadic first-order logic has finite model property, its SAT problem is decidable. In H.Behmann's paper, he extended this result to fragment of SOL where all predicates, free and ...
- 63
2
votes
0
answers
124
views
Reasoning about "approximately" associative structures and "almost monoids".
If $(M,+)$ is a monoid then it obeys the laws:
$$m_1 + 0 = 0 + m_1 = m_1$$
$$m_1+(m_2+m_3)=(m_1+m_2)+m_3$$
But what if I have a structure $(A,+)$ that is almost a monoid, but not quite. For example,...
- 21
2
votes
0
answers
300
views
on the Axiom of Choice and the Spectrum of Rings
consider the following theorem, when $R$ is a commutative ring with a non-zero identity:
A ring $R$ is zero-dimensional if and only if $\mbox{Spec(R)}$ is Hausdorff.
The proof uses the Axiom of ...
user30230
2
votes
0
answers
272
views
Continuity of multiplicative character
Let $G$ be a discrete group and $\beta (G)$ denote the Stone-Cech compactification of $G$, a right topological semigroup. By a multiplicative character, I mean a mapping that preserves multiplication ...
- 61
2
votes
0
answers
129
views
Compactness-like property for universal generalization?
Hi all! I have the following problem. Suppose I have a sequence of models $M_1,M_2,...$, all of which have the same countable domain (call it $D$). $x_1,x_2,...$ is a well-ordering of $D$. $\phi(x)$ ...
- 413
2
votes
0
answers
281
views
Axiomatization of the incidence geometry of the Euclidean plane
There are several well-known axiomatizations of Euclidean plane geometry, the language of which is usually considered to include at least the relations of
incidence (point-line, point-segment, or ...
user1448
2
votes
0
answers
369
views
Constructing the Stone space of a distributive lattice
Does anyone have a good reference for the method of giving a topology to a distributive lattice as outlined in M.H. Stone's "Topological representation of distributive lattices and Brouwerian ...
- 10.4k
2
votes
0
answers
169
views
Are there any recommended texts that cover Turing Tilings?
I have read the original paper by Wang, as well as a paper by Boas [1996] entitled 'the Convenience of Tilings', but wanted to know if there were any other texts that people could recommend that ...
- 83
2
votes
0
answers
292
views
About Tarski's axioms A and A' (4): ZFC + Tarski-Grothendieck axiom
4-(suite): axiom A (or equivalently axiom TG) have powerfull consequences.
(i) It is easy to see that A1 and A2 prove the power-set axiom, by separation, because P(x is included inside the set y;
(ii)...
- 2,655
2
votes
0
answers
196
views
About Tarski's axioms A and A' (3): 16 equivalent axioms
3-On the same page (84) he states axioms A and A', Tarski also considers the 16 following axioms variants for A and A' and asserts witout giving a proof that they are all equivalent.
Axiom C: "For ...
- 2,655
2
votes
0
answers
160
views
About Tarski's axioms A and A' (2): transitive sets
2-By A'2, every set y satisfying axiom A' must be a transitive set. But it is not true that every set y satisfying axiom A must be transitive. So, it seems natural to ask the following.
Question 2: (i)...
- 2,655
1
vote
0
answers
58
views
Construction of the smallest nucleus above a prenucleus: what does this proof tell us?
While reading Hyland's paper on the effective topos [retyped version here] in the L. E. J. Brouwer Centenary Symposium, specifically prop. 16.3, I realized that the following proposition is implicit:
...
- 32.5k
1
vote
0
answers
82
views
How strong is separation + reflection without transitivity?
Consider a theory $T$ with a binary relation $\in$ and the following axiom schemas:
$\exists u \forall x (x \in u \leftrightarrow x \in a \land \phi)$ where $u$ is not free in $\phi$. This is the ...
- 2,203
1
vote
0
answers
89
views
About synonymy relationships around these two theories?
The following question is about patterns of synonymy relationships around two theories, $T^+$ and $\sf PA$.
For purposes of self inclusiveness I'll re-iterate $T$ and its extensions.
$\textbf{Logic:}$ ...
- 11.3k
1
vote
0
answers
96
views
Determine equivalences in the generated collection of subgroups and quotients
Let $A$ be an abelian group, and $B_1, B_2, \dots, B_m$ be subgroups of $A$. Define the family of subgroups $\mathcal{D}_0 = \{ \{0\}, A, B_1, B_2, \dots, B_m \}$.
Let $\mathcal{C}_1$ be the ...
- 807
1
vote
0
answers
142
views
A generalization of quasi-identities
In universal algebra, a variety is axiomatized by identities $t \approx s$ between terms $t$ and $s$. More general are quasi-varieties that are axiomatized by quasi-identities of the form $$u_1 \...
- 44.4k