The tag has no wiki summary.

learn more… | top users | synonyms

19
votes
0answers
328 views

Decidability of equality of elementary expressions

In the following definition the term expression is to be understood as a finite tree built from formal symbols without any predefined meaning assigned to them. Define the set $\mathcal{E}$ of ...
4
votes
0answers
133 views

The theory of two finite linear orders

My colleague Matthias Baaz is looking for a reference for the following question (or possibly theorem): Let T be the "theory of pairs of finite linear orders". That is, consider all finite ...
2
votes
0answers
115 views

What is the general feeling for Hilbert's 10th problem for Q?

We know that Hilbert's 10th problem for $\mathbb{Z}$ is undecidable. I was wondering whether there is a strong opinion in the mathematical community on the decidability of Hilbert's 10th for ...
2
votes
0answers
91 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 ...
1
vote
0answers
62 views

What is the generic complexity of First Order Predicate Calculus?

I suspect that it should be the same as that of the Turing machine halting problem, which wikipedia gives as GenP and attributes this result to Hamkins and Miasnikov, but I am not sure. Is the generic ...
1
vote
0answers
74 views

unique types and decidability

Suppose $\mathcal{M}$ is an infinite structure which has the property that every type that is realised is realised uniquely. Also assume that every element of $\mathcal{M}$ is definable but there is ...
0
votes
0answers
45 views

Is the question whether a FO formula F has a model of size k (k is a finite number) decidable?

Hi all, can someone please tell me whether the question whether a FO formula F has a model of size k (where k is a finite number) is decidable? Thanks in advance! TL