UJDigispace Repository

Zero-one laws and almost sure validities on finite structures

Show simple item record

dc.contributor.advisor Prof. V. Goranko en_US
dc.contributor.author Schamm, Rainer Franz
dc.date.accessioned 2012-09-12T06:40:03Z
dc.date.available 2012-09-12T06:40:03Z
dc.date.issued 2012-09-12
dc.date.submitted 2002
dc.identifier.uri http://hdl.handle.net/10210/7511
dc.description M.Sc. en_US
dc.description.abstract This short dissertation is intended to give a brief account of the history and current state of affairs in the field of study called 'Zero-one Laws'. The probability of a property P on a class of finite relational structures is defined to be the limit of the sequence of fractions, of the n element structures that satisfy the property P, as n tends to infinity. A class of properties is said to have a Zero-One law if the above limit, which is usually called the asymptotic probability of the property with respect to the given class of finite structures, is either 0 or 1 for each property. The connection to the field of Mathematical Logic is given by the surprising fact that the class of properties definable by a first-order sentence has a Zero-One law with respect to the class of all finite relational structures of the common signature. We cover this result in more detail and discuss several further Zero- One laws for higher-order logics. In particular we will be interested in all those modal formulae which are 'almost surely' frame valid in the finite, i.e. those which have an asymptotic probability equal to 1 with respect to the class of all finite frames. Our goal is to find a purely logical characterization of these formulae by finding a set of axioms which describe such modal formulae absolutely. We devise a strategy and provide some Java programs to aid in this search for future research en_US
dc.language.iso en en_US
dc.subject First-order logic en_US
dc.subject Logic, Symbolic and mathematical en_US
dc.title Zero-one laws and almost sure validities on finite structures en_US
dc.type Thesis en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search UJDigispace


My Account