All Questions
6,027 questions
2
votes
1
answer
237
views
term equality in algebraic theories
For algebraic theories how relevant is the underlying logic? Is it possible that two terms $s$ and $t$ can be shown to be equal with respect to one set of logical axioms but not necessarily so with ...
user577
1
vote
0
answers
245
views
Defining filters in closure algebras: reference request
A closure algebra C is a boolean algebra B together with a unary closure operator, and additional axioms, the Kuratowski axioms, that the closure operator must satisfy. (The Wikipedia article prefers ...
- 327
3
votes
0
answers
175
views
Intersecting the algebraic closure of independent elements
$G$ is a group with a simple first order theory $T$ as defined by Shelah, hence equiped with a "nice" notion of independence. $G$ also has generic elements. I write $acl^n(A)$ for the set of elements ...
- 1,555
3
votes
1
answer
205
views
characterization of regular languages among (say) those computable in linear time
For a given language A let A(n) denote the number of words in A of length smaller or equal to n. It is know that if A is a regular language then the function $ f(x) = \sum_{i=0}^\infty A(n)x^n$ is in ...
- 3,897
4
votes
1
answer
358
views
Prime-ness checking for polynomial ideals over ACFs( algebraically closed fields).
Let $f_1,\ldots f_m \in k[X]$ have degrees bounded by $l$. and $I(\bar{f})$ be the ideal generated by $\bar{f}$.
If $I(\bar{f})$ is not a prime ideal then its non-primeness is witnessed by polynomials ...
- 255
-1
votes
1
answer
358
views
Properties of collections (functions) that make them proper classes (uncomputable)
There are collections too big to be a set, e.g. the collection of all sets (in ZFC), and there are collections that cannot be sets for "pure" logical reasons, e.g. the collection of sets that do not ...
- 9,720
5
votes
0
answers
336
views
Defining a topology by means of closed subsets in a topos
In the following we fix a topos. I'll speak of sets instead of objects and of subsets instead of subobjects.
Let $X$ be a set and assume $F$ is a set of subsets of $X$ that contains $\emptyset, X$, ...
- 63.1k
0
votes
0
answers
179
views
semigroup actions of groups on regular rooted trees
If $G$ is a group which has a semigroup action on a regular rooted tree via prefix-preserving, continuous transformations (I give the tree the path metric), what kinds of algebraic restrictions can we ...
- 125
11
votes
0
answers
305
views
What are the logical morphisms from a topos E to Set?
If $E$ is a topos, is there a nice way to characterize the category of logical morphisms $E\to Set$? Is it complete and/or cocomplete?
The topos $Set$ geometrically represents a point; what does it ...
- 8,669
1
vote
1
answer
365
views
Naturally definable sets of natural numbers (3)
[This shall be the last of a series of questions, see Naturally definable sets of natural numbers (2)]
I cannot explain why I have been so stubborn not to see the most straight-forward definition for ...
- 9,720
5
votes
0
answers
350
views
Chain/Hierarchy of Monoids
Let's assume that we have the following collection of structures:
Some space $P$.
Monoids $(M_{i+1},\circ_{i+1})$, and
Actions $\bullet_{i+1}:M_{i+1}\times M_i\to M_i$, for $i\ge 0$
And $\bullet_{0}:...
- 1,882
0
votes
1
answer
172
views
Equivalence of monadic axioms
Call two axioms equivalent if they imply the same set of theorems. I am interested in decidability of so defined equivalence. In this generality the problem is obviously undecidable since it can be ...
- 3
2
votes
1
answer
207
views
Bounded-variable logic: "fewer than $\alpha$ variables" equivalent to "every subformula has fewer than $\alpha$ free variables"?
I believe that "fewer than $\alpha$ variables" is equivalent to "every subformula has fewer than $\alpha$ free variables." The left-to-right implication is straightforward, and from right to left one ...
- 3,267
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
4
votes
0
answers
306
views
To what extent MSO = WS1S, when adding relations?
Let me first clarify my definitions. For a word $w \in \Sigma^*$, with $\Sigma=\{a_1, \ldots, a_n\}$, I define two structures:
$${\mathbb{N}}(w) = \langle {\mathbb{N}}, <, Q_{a_1}, \ldots, Q_{a_n} ...
- 786
3
votes
1
answer
251
views
Image of composite morphisms
I am new to categories and I found in a book that it is possible to construct a category in which the following are true: there exist morphisms $f:A \to B$ and $g:B \to C$, and monomorphisms $\alpha:A'...
- 205
1
vote
0
answers
203
views
Maximizing the number of 'correct' literals in planar monotone 3SAT
I'm trying to find the complexity of this optimization problem:
Given an instance of planar monotone 3SAT, with positive clauses $C_i = v_{i1} V v_{i2} V v_{i3}$ and negative clauses $D_i = not(w_{i1}...
- 1,182
-2
votes
1
answer
271
views
how to weigh the conditions given in a proposition
As we can see,there are some conditions given in a proposition.
If there are 2 propositions having approximate conclusions.Usually，we can name one propositions gives stronger conditions than the ...
- 57
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
0
votes
1
answer
147
views
Small set of acts over a countable monoid?
Given a countable monoid $S$, is the set of all (isomorphic representatives of) $S$-acts a small set?
- 11
0
votes
2
answers
172
views
small extensions of the free semigroup of rank 1
Let N denote the free semigroup of rank 1. Say that a semigroup T is a small extension
of N if N embeds in T and |T - N| is finite. Is there some kind of classification
of small extensions of N? ...
- 91
1
vote
1
answer
154
views
undecidability in the dynamics of functions $f: \Sigma^* \rightarrow \Sigma^*$
Does anyone know any undecidable problems in the dynamics of functions (not necessarily monoid homomorphisms or anything) from \Sigma^* to \Sigma^* where \Sigma is a finite set? In particular, I'm ...
- 549
1
vote
0
answers
260
views
Is this first-order statement true? [closed]
Consider the natural numbers $\mathbb{N}$ as a structure for NBG set theory.
If we interpret the Axiom of Unions in this structure, we get the statement
$(\forall a \in \mathbb{N})$ $(\exists w \in \...
- 21
1
vote
0
answers
264
views
A question about set theory and Frege logic
Does there exist a very weak axiomatic theory of arithmetic-weaker than (but possibly a sub-theory of)
Robinson's theory Q-which can be interpreted in the first order fragment of Frege logic? If so, ...
- 6,215
2
votes
1
answer
184
views
Are these separation logic statements valid?
I have to say whether or not the following two separation logic statements are valid:
$ x \mapsto 3 * y \mapsto 7 \Longrightarrow x \mapsto 3 * true $
$ true * x \mapsto 3 \Longrightarrow x \mapsto 3 ...
- 123
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