Return to search

Zero-one laws and almost sure validities on finite structures

M.Sc. / 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

Identiferoai:union.ndltd.org:netd.ac.za/oai:union.ndltd.org:uj/uj:10130
Date12 September 2012
CreatorsSchamm, Rainer Franz
Source SetsSouth African National ETD Portal
Detected LanguageEnglish
TypeThesis

Page generated in 0.0018 seconds