uu.seUppsala University Publications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Stability theory in finite variable logic
Uppsala University, Disciplinary Domain of Science and Technology, Mathematics and Computer Science, Department of Mathematics.
2000 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

This thesis studies finite variable theories. To be more precise. complete Ln -theories, where Ln is the set of formulas in a first order language L in which at most n distinct variables occur. These need not be complete in the usual first order sense. We use ideas from infinite model theory, in particular stability theory, to define a class of complete Ln -theories which, as we show, has a tractable model theory, also with respect to finite models.

The three main properties of such theories that we consider are (1) a finite bound on the number of Ln -types, (2) an amalgamation property and (3) stability. We prove that any complete Ln -theory with an infinite model and with properties (l),(2) and (3) has an infinite model M which is ω-categorical and ω-stable from which it follows that it has arbitrarily large finite models. In fact, M almost admits elimination of quantifiers, in the sense that there exists an expansion of M by finitely many new n-ary relation symbols which admits elimination of quantifiers. This together with the stability of M allows us to obtain finer information about complete Ln -theories with properties (1)-(3).

We show that there exists a recursive function f : ω2 → ω such that every theory T as above has a finite model of size at most f(n, |Snn(T)|), where Snn(T) is the set of Ln -types of T in n free variables.

Then we derive some results about forking in stable structures where there exists n < ω such that any type (with any number of free variables) over ω is determined by its subtypes with at most n free variables. We use this to give a different proof of a result due to Lachlan. saying that in a stable structure which almost admits elimination of quantifiers every strictly minimal set is indiscernible.

Finally. using the theory of stable structures which admit elimination of quantifiers, we show how to construct new (finite and infinite) models of Ln -theories T with an infinite model and properties (l)-(3). Moreover, every sufficiently saturated model of T which is Ln -elementarily embeddable in a stable structure which almost admits elimination of quantifiers can be constructed in this way and the amount of saturation that is needed can be effectively computed from |Snn(T)|.

Place, publisher, year, edition, pages
Uppsala: Acta Universitatis Upsaliensis, 2000. , 60 p.
Series
Uppsala Dissertations in Mathematics, ISSN 1401-2049 ; 16
Keyword [en]
Mathematics
Keyword [sv]
MATEMATIK
National Category
Mathematics
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:uu:diva-1212ISBN: 91-506-1417-7 (print)OAI: oai:DiVA.org:uu-1212DiVA: diva2:160769
Public defence
2000-09-20, Rum 247, Polacksbacken, Uppsala, 13:15
Available from: 2000-08-30 Created: 2000-08-30 Last updated: 2012-04-20Bibliographically approved

Open Access in DiVA

No full text

Authority records BETA

Djordjevic, Marko

Search in DiVA

By author/editor
Djordjevic, Marko
By organisation
Department of Mathematics
Mathematics

Search outside of DiVA

GoogleGoogle Scholar

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 599 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf