| dc.description.abstract | Glebskii et al. (1969) and Fagin (1975) first proved a Zero-One Law with respect to First Order-logic on the Erdos-Renyi random graph \(G(n,p)\) with \(p=\frac12\). Since then, multiple classes of graphs have been proven to obey a Zero-One Law or not, on different kinds of logical languages. The class of labeled caterpillars does not obey a Zero-One law in First Order Logic; however, there's a convergence law, as is proven in this thesis. Subsequently, it's also proven for the class of unlabeled caterpillars.
While proving these convergence laws, we use the fact that only the 'outer parts' of a caterpillar can be different, while the 'inside' tends to be the same for large enough caterpillars. In the final chapter we therefore introduce the group of caterpillars, having their outer vertices attached to each other to create bracelets. The class of bracelets is proven to obey a Zero-One Law. | |
