The decidability tag has no wiki summary.

**19**

votes

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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

**0**answers

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