# Decision problems concerning sets of equations

### Kalfa, Kornilia

#### (1980)

Kalfa, Kornilia (1980)
*Decision problems concerning sets of equations*.

#### Abstract

This thesis is about "decision problems concerning properties of sets of equations".

If L is a first-order language with equality and if P is a property of sets of L-equations, then "the decision problem of P in L" is the problem of the existence or not of an algorithm, which enables us to decide whether, given a set Sigma of L-equations, Sigma has the property P or not. If such an algorithm exists, P is decidable in L. Otherwise, it is undecidable in L.

After surveying the work that has been done in the field, we present a new method for proving the undecidability of a property P, for finite sets of L-equations. As an application, we establish the undecidability of some basic model-theoretical properties, for finite sets of equations of non-trivial languages. Then, we prove the non-existence of an algorithm for deciding whether a field is finite and, as a corollary, we derive the undecidability of certain properties, for recursive sets of equations of infinite non-trivial languages. Finally, we consider trivial languages, and we prove that a number of properties, undecidable in languages with higher complexity, are decidable in them.

#### Information about this Version

This is a Accepted version

This version's date is:
1980

This item
is not peer reviewed

#### Link to this Version

https://repository.royalholloway.ac.uk/items/a1340102-6aef-451f-ac7a-a20aa17639fd/1/

Item Type | Thesis (Doctoral) |
---|---|

Title | Decision problems concerning sets of equations |

Authors | Kalfa, Kornilia |

Uncontrolled Keywords | Mathematics; Pure Sciences; Concerning; Decision; Equations; Problems; Sets; Sets Of Equations; Sets Of Equations |

Departments | |

## Identifiers |

Deposited by David Morgan (UBYL020) on 31-Jan-2017 in Royal Holloway Research Online.Last modified on 06-Feb-2017

#### Notes

Digitised in partnership with ProQuest, 2015-2016. Institution: University of London, Bedford College (United Kingdom).

### Details

- Owner: David Morgan
- Collection: Royal Holloway Research Online
- Version: 1 (show all)
- Status: Live