All Questions
Tagged with formal-languages model-theory
14 questions
1
vote
0
answers
94
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
7
votes
1
answer
494
views
Normal form for terms in language with two ring structures
Suppose I have two different ring structures on the same domain $\langle R,+,\cdot,0,1\rangle$, $\langle R,\oplus,\otimes,\bar 0,\bar 1\rangle$ and I throw the structures together into a single common ...
- 236k
2
votes
0
answers
100
views
Name for the theory of words with equal length, prefix, successors
I've worked with this theory for a while, but I've never been quite sure what to call it:
$$(\Sigma^*, =_{el}, \preceq, (S_a)_{a \in \Sigma})$$
Where
$\Sigma^*$ is the set of finite words on finite ...
- 429
4
votes
0
answers
179
views
A lemma from Jarden's and Lubotzky's paper 'Elementary equivalence of profinite groups'
I have a question about a reduction argument from
Jarden's and Lubotzky's paper 'Elementary equivalence of
profinite groups' in Lemma 1.1 on page 3:
Lemma 1.1: For each positive integer $n$ and each ...
- 5,998
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
6
votes
1
answer
485
views
Show that the positive existential theory is undecidable
To show that the positive existential theory of $\mathbb{C}[t, e^{\lambda t} \mid \lambda \in \mathbb{C}]$ in the language $\{+, \cdot , ' , 0 , 1, t\}$ is undecidable we have to prove the following: $...
- 309
9
votes
0
answers
221
views
Is there a ``Ladner's Theorem" for the PH-vs-PSPACE scenario?
Like a statement of the kind, ``If the Polynomial Hierarchy (PH) $\neq$ PSPACE then there exists $L \in PSPACE \backslash PH$ which is not PSPACE-complete"?
Or is there something else that states ...
- 1,893
5
votes
2
answers
266
views
Formal languages with non-unique interpretations of terms
In mathematical logic and model theory, one considers interpretations of syntactic expressions: terms without free variables are interpreted as elements of some structure, formulas without free ...
- 1,481
2
votes
2
answers
745
views
All properties of a mathematical object
This is primarily a question about related literature. I am looking for specific references, or terminology that I can use to search for references.
Let A a well defined mathematical structure of ...
- 313
1
vote
2
answers
480
views
Satisfiability problem for FOL[<,R]
Let FOL[<,R] be the fragment of first-order logic enriched with two relational symbols < and R and the first-order axioms that say:
< is a strict partial order and R is an irreflexive and ...
- 105
12
votes
5
answers
1k
views
Predicates of infinite arity
Infinitary logic considers languages being infinite by infinite conjunctions and disjunctions.
I wonder why it not considers languages being infinite by relations and functions of infinite arity.
...
- 9,720
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
2
answers
989
views
Theory interpreted in non-set domain of discourse may be consistent?
Following the blow. I will try to ask question in order to check if I well understand what was pointed. I decide to ask another question, because mathoverflow is not projected to be good environment ...
- 1,626
8
votes
3
answers
739
views
What assumptions and methodology do metaproofs of logic theorems use and employ?
In logic modules, theorems like Soundness and completeness of first order logic are proved. Later, Godel's incompleteness theorem is proved. May I ask what are assumed at the metalevel to prove such ...
user2529