In [9] we introduced a new framework for asymptotic probabilities, in which a $\sigma-additive$ measure is defined on the sample space of all sequences $A = $ of finite models, where the universe of An is {1, 2, .., n}. In this framework we investigated the strong 0-1 law for sentences, which states that each sentence either holds in An eventually almost surely or fails in An eventually almost surely. In this paper we define the strong convergence law for formulas, (...) which carries over the ideas of the strong 0-1 law to formulas with free variables, and roughly states that for each formula φ(x), the fraction of tuples a in An, which satisfy the formula φ(x), almost surely has a limit as n tends to infinity. We show that the infinitary logic with finitely many variables has the strong convergence law for formulas for the uniform measure, and further characterize the measures on random graphs for which the strong convergence law holds. (shrink)

We introduce a new framework for asymptotic probabilities of sentences, in which we have a σ-additive measure on the sample space of all sequences A = {A n } of finite models, where the universe of A n is {1,2... n}, and use this framework to strengthen 0-1 laws for logics.

We introduce a new framework for asymptotic probabilities of sentences, in which we have a σ-additive measure on the sample space of all sequencesA= {} of finite models, where the universe ofis {1,2, …, n}. and use this framework to strengthen 0-1 laws for logics.

We obtain an almost everywhere quantifier elimination for (the noncritical fragment of) the logic with probability quantifiers, introduced by the first author in [10]. This logic has quantifiers like $\exists ^{ \ge 3/4} y$ which says that "for at least 3/4 of all y". These results improve upon the 0-1 law for a fragment of this logic obtained by Knyazev [11]. Our improvements are: 1. We deal with the quantifier $\exists ^{ \ge r} y$ , where y is a tuple (...) of variables. 2. We remove the closedness restriction, which requires that the variables in y occur in all atomic subformulas of the quantifier scope. 3. Instead of the unbiased measure where each model with universe n has the same probability, we work with any measure generated by independent atomic probabilities pR for each predicate symbol R. 4. We extend the results to parametric classes of finite models (for example, the classes of bipartite graphs, undirected graphs, and oriented graphs). 5. We extend the results to a natural (noncritical) fragment of the infinitary logic with probability quantifiers. 6. We allow each pR , as well as each r in the probability quantifier $(\exists ^{ \ge r} y)$ , to depend on the size of the universe. (shrink)

We prove convergence laws for logics of the form equation image, where equation image is a properly chosen collection of generalized quantifiers, on very sparse finite random structures. We also study probabilistic collapsing of the logics equation image, where equation image is a collection of generalized quantifiers and k ∈ ℕ+, under arbitrary probability measures of finite structures.

We carry out a systematic investigation of the definability of linear order on classes of finite rigid structures. We obtain upper and lower bounds for the expressibility of linear order in various logics that have been studied extensively in finite model theory, such as least fixpoint logic LFP, partial fixpoint logic PFP, infinitary logic Lω∞ω with a finite number of variables, as well as the closures of these logics under implicit definitions. Moreover, we show that the upper and lower bounds (...) established here cannot be made substantially tighter, unless outstanding conjectures in complexity theory are resolved at the same time. (shrink)

Throughout the development of finite model theory, the fragments of first-order logic with only finitely many variables have played a central role. This survey gives an introduction to the theory of finite variable logics and reports on recent progress in the area.For each k ≥ 1 we let Lk be the fragment of first-order logic consisting of all formulas with at most k variables. The logics Lk are the simplest finite-variable logics. Later, we are going to consider infinitary variants and (...) extensions by so-called counting quantifiers.Finite variable logics have mostly been studied on finite structures. Like the whole area of finite model theory, they have interesting model theoretic, complexity theoretic, and combinatorial aspects. For finite structures, first-order logic is often too expressive, since each finite structure can be characterized up to isomorphism by a single first-order sentence, and each class of finite structures that is closed under isomorphism can be characterized by a first-order theory. The finite variable fragments seem to be promising candidates with the right balance between expressive power and weakness for a model theory of finite structures. This may have motivated Poizat [67] to collect some basic model theoretic properties of the Lk. Around the same time Immerman [45] showed that important complexity classes such as polynomial time or polynomial space can be characterized as collections of all classes of finite structures definable by uniform sequences of first-order formulas with a fixed number of variables and varying quantifier-depth. (shrink)

We explain and summarize the use of logic to provide a uniform perspective for studying limit laws on finite probability spaces. This work connects developments in stability theory, finite model theory, abstract model theory, and probability. We conclude by linking this context with work on the Urysohn space.