On linear order and computation : The expressiveness of interactive computations on linear orders and computations indexed by ordinals

Show full item record



Permalink

http://urn.fi/URN:ISBN:978-952-10-5089-3
Title: On linear order and computation : The expressiveness of interactive computations on linear orders and computations indexed by ordinals
Author: Bissell-Siders, Ryan
Contributor: University of Helsinki, Faculty of Science, Department of Mathematics and Statistics
MALJA graduate school in Algebra, Set Theory, Logic and analysis, Model theory, and Finite model theory
The Finite Model Theory group
The Helsinki logic group.
Publisher: Helsingin yliopisto
Date: 2008-11-21
Language: en
URI: http://urn.fi/URN:ISBN:978-952-10-5089-3
http://hdl.handle.net/10138/21260
Thesis level: Doctoral dissertation (article-based)
Abstract: We solve the Dynamic Ehrenfeucht-Fra\"iss\'e Game on linear orders for both players, yielding a normal form for quantifier-rank equivalence classes of linear orders in first-order logic, infinitary logic, and generalized-infinitary logics with linearly ordered clocks. We show that Scott Sentences can be manipulated quickly, classified into local information, and consistency can be decided effectively in the length of the Scott Sentence. We describe a finite set of linked automata moving continuously on a linear order. Running them on ordinals, we compute the ordinal truth predicate and compute truth in the constructible universe of set-theory. Among the corollaries are a study of semi-models as efficient database of both model-theoretic and formulaic information, and a new proof of the atomicity of the Boolean algebra of sentences consistent with the theory of linear order -- i.e., that the finitely axiomatized theories of linear order are dense.Lineaarijärjestysten kvanttoriastehierarkiassa olemme onnistunut laskemaan varsin tarkasti tiettyyn kvanttoriasteeseen asti ei-ekvilaenttien lineaarijärjesysten äärellisen lukumäärän. Ääretöaikaisten koneiden malleistä näimme että Turing-kone ja päättymät automaatteja pystyvät Gödelin konstruoituvan universumin laskemiseen.
Subject: matematiikka
Rights: This publication is copyrighted. You may download, display and print it for Your own personal use. Commercial use is prohibited.


Files in this item

Total number of downloads: Loading...

Files Size Format View
onlinear.pdf 791.8Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record