Abstract
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