PUBLICATIONS DE L’INSTITUT MATHÉMATIQUE Nouvelle série, tome 78(92) (2005), 107–115

PROBABILITIES ON FIRST ORDER MODELS

Miklós Ferenczi

Communicated by Žarko Mijajlović

Abstract. It is known that set algebras corresponding to first order models (i.e., cylindric set algebras associated with first order interpretations) are not σ-closed, but closed w.r.t. certain infima and suprema i.e.,

(∗)  |∃x α| = ⋃_{i∈ω} |α(y_{i})| and |∀x α| = ⋂_{i∈ω} |α(y_{i})|

for any infinite subsequence y_{1}, y_{2}, … y_{i}, … of the individuum variables in the language. We investigate probabilities defined on these set algebras and being continuous w.r.t. the suprema and infima in (∗). We can not use the usual technics, because these suprema and infima are not the usual unions and intersections of sets. These probabilities are interesting in computer science among others, because the probabilities of the quantifier-free formulas determine that of any formula, and the probabilities of the former ones can be measured by statistical methods.

1. Introduction

We define and investigate probabilities on first order models i.e. on the main components of first order semantics. Investigating probabilities defined on first order models is an important device of modelling the physical reality and modelling by computer.

Interpretations of first order formulas in a model M form a certain algebra of relations, a cylindric set algebra A′. We consider the probabilities (probability measures) to be defined on these kind of algebras. A well-known property is that cylindric set algebras corresponding to first order models are closed for the Boolean joins and meets (suprema and infima) corresponding to the existential and universal quantifiers, thus

(1.1)  |∃x α| = ⋃_{i∈ω} |α(y_{i})| and |∀x α| = ⋂_{i∈ω} |α(y_{i})|

2000 Mathematics Subject Classification: Primary 03B48; Secondary 03G15. Partially supported by the OTKA grants T035192, T043242.

are true where y_{1}, y_{2}, … y_{i}, … is any infinite subsequence with infinite range of the ω-sequence x_{1}, x_{2}, … x_{j}, … of the individuum variables in the language, the formula α may contain free variables other than x, |α| denotes the set of the evaluations satisfying the formula α on the model (|α| is the interpretation of α), ⋃ and ⋂ mean Boolean join and meet (suprema and infima).

We investigate probabilities p’s which are continuous with respect to the joins and meets in (1.1) (partially continuous probabilities), that is p has the following properties:

(1.2)  p |∃x α| = sup_{n∈ω} p(⋃_{i∈n} |α(y_{i})|),  p |∀x α| = inf_{n∈ω} p(⋂_{i∈n} |α(y_{i})|)

for any infinite subsequence y_{1}, y_{2}, … y_{i}, … with infinite range of the ω-sequence x_{1}, x_{2}, … x_{j}, … of the individuum variables in the language (the two properties above are equivalent to each other). This kind of continuity is remarkable why it means a kind of extensionality in probability logic: probabilities of quantifier free formulas determine the probability of any formula (while probability logic is not extensional, in general). Probabilities of quantifier free formulas can be already measured by statistical methods. Property (1.2) is unusual since the joins and meets in (1.1) are different from the ordinary infinite unions and intersections for sets (see [16]), therefore the σ-additivity of standard distributions is not applicable, special technics are needed to investigate (1.2). Another aspect of this kind of continuity is: with |∃xα| we can associate a projection of the set |α| parallel to the x-axis, thus from the viewpoint of measure theory, property (1.2) implies that the measure of the projection of |α| is determined by the measures of certain transformations ⋃_{i∈n} |α(y_{i})| of |α|, and this is unusual in the classical theory of measures

and topology (see [3]).

Probabilities defined on certain kinds of algebras of relations are investigated by several authors, e.g. in [2], [4], [5], [9], [10], [11], [13], [15], [17] (the relevant algebraic properties are investigated e.g. in [3], [6], [7], [8], [12], [14] and [16]). In these papers probabilities are considered on algebras of closed formulas or they are only finitely additive, and mainly the existence is treated. Here we give constructions for probabilities defined for all the formulas with property (1.2).

These investigations play role in probability logic, in inductive and stochastic programming, in program verification, in stochastic prediction, in artificial intelligence and uncertain reasonings among others.

A relation like (1.1) is true for Lindenbaum–Tarski algebras of formulas of the language, and for dimension restricted cylindric algebras, in general. Therefore property (1.2) can be defined also for these algebras. Using that the cylindric set algebra A′ corresponding to a model is a homomorphic image of the Lindenbaum– Tarski algebra, probabilities with property (1.2) can be transformed by canonical homomorphism from the model to the Lindenbaum–Tarski algebra.

First, in Theorem 3.1. we construct probabilities for countable models and languages, applying only discrete distributions. Making use of the property of elementary equivalent models, that algebras corresponding them are isomorphic, probabilities can be transformed from countable models to non-countable models. In Theorem 3.2. we show that the Lebesgue measure considered on the unions of finite dimensional intervals restricted to an infinite power of [0, 1) has property (1.2). This is an example for continuity of type (1.2) on a non-countable model.

2. Concepts

Let L be a usual first order language. For the sake of simplicity we suppose that L does not contain function symbols other than constant symbols.

We suppose the knowledge of the concept of cylindric set algebra corresponding to a first order model M with universe U, of type of L. An element of A is the set |α| of the evaluations of the individuum variables satisfying the formula α in M, that is the interpretation of α in M (a set of sequences with members from U). Thus A is the structure:

(2.1)  A = ⟨A, ∪, ∩, ∼_{U^{T}} , U^{T} , ∅, C_{j}, D_{jk}⟩_{j,k∈ω}

where T is the set of individuum variables in L and the following known relations are true for the operations and constants included in (2.1):

|α| ∪ |β| = |α ∨ β| ,  |α| ∩ |β| = |α ∧ β| ,
∼_{U^{T}} |α| = |¬α| ,  C_{j} |α| = |∃x_{j} α| ,
D_{jk} = |x_{j} = x_{k}| .

If L does not contain equality symbol then D_{jk} is missing in (2.1) and A is called a diagonal free cylindric set algebra (see [7]). We remark that, by definition of the quantification ∃x_{j}, the meaning of the “cylindrification” C_{j} |α| is: forming a cylinder set with base |α| in U^{T} parallel to the x_{j}-axis (forming a projection parallel to the x_{j}-axis).

By infinite sequence through the paper we mean a sequence with infinite range and consisting infinitely many members.

Relations in (1.1) are really true for A(moreover, in a sense, these are the only infinite joins and meets which are included in the algebras A’s in (2.1) (see [8],[15]). These joins and meets must be different from the ordinary unions ⋃_{i∈ω}^{∗} |α(y_{i})| and intersections ⋂_{i∈ω}^{∗} |α(y_{i})| of sets (here ⋃^{∗} and ⋂^{∗} are defined in the powerset P(U^{T})). For example, ⋃_{i∈ω}^{∗} |α(y_{i})| ⊆ |∃x α| is obvious, but equality can not valid in general.

Now we list some definitions concerning probabilities (see [4], [5], [11], [12], [13], [15]). Let A be the set algebra in (2.1).

Definition 2.1. A non-negative real function p defined on A is a probability on A (or probability measure on A), if it is a finitely additive probability on the Boolean part of A in the usual sense, that is

(i) 0 ⩽ p |α| ⩽ 1 for every formula α (ii) p (U^{T} ) = 1 (iii) p (|α| ∪ |β|) = p |α| + p |β| for every formulas α and β with |α| ∩ |β| = ∅.

Definition 2.2. A probability p defined on A is said to be continuous with respect to the quantifiers or said to be a quantifier probability measure (in short, quantifier probability, or Q-probability) if the condition (1.2) is satisfied.

In (1.2) we can suppose that the subsequence y_{1}, y_{2}, … y_{i} … does not contain free variables from α. Namely if (1.2) is satisfied under this restriction then it is also satisfied without this restriction because α has only finitely many free variables and p is monotonic, this latter implies p (⋃_{i∈n} |α(y_{i})|) ⩽ p (⋃_{i∈m} |α(y_{i})|) if n ⩽ m.

Definition 2.3. A probability p defined on A has the product property if p (|α| ∩ |β|) = p |α| · p |β| for every α and β such that α and β have no common free variables. A probability p defined on A is said to be symmetrical if p |α| = p |β| for every α and β such that there is a one-to-one correspondence between the free variables of α and β.

The product property obviously corresponds to the concept “independency” in probability theory.

In [15] a version of the following concept of continuity is investigated: There is an infinite subsequence y_{1}, y_{2}, … y_{i}, … of the ω-sequence x_{1}, x_{2}, … x_{j}, … of the individuum variables such that p |∃x α| = sup_{n∈ω} p (⋃_{i∈n} |α(y_{i})|). This property is obviously weaker than (1.2) but it is equivalent to (1.2) for the so called symmetrical probabilities, as it can be proven.

Definitions above for probabilities can be generalized to any dimension restricted cylindric algebra (e.g., to classical Lindenbaum–Tarski algebras).

3. Quantifier probability measures

First, we use σ-additive discrete distributions and their infinite powers. Assume that U is the universe of a countable model M of a countable language L. Consider a strictly positive σ- additive probability distribution on U (a distribution is strictly positive if there is no element with zero probability). This yields a distribution on the power set P(U) considering it as a Boolean σ set algebra. Let p the T th power of this distribution on the T th power (P(U))^{T} of the σ set algebra P(U), where T is the set of the individuum variables in L. Let A be the cylindric set algebra corresponding to M as in (2.1) and H be the Boolean part of A.

Theorem 3.1. The restriction of p to A is a quantifier probability measure, it is symmetrical and has the product property.

The main idea of the proof is: the symmetry and product properties will be obvious by construction. We use these properties to prove condition (1.2), first for a formula having only one free variable beyond x. If α has more than one free variables, so α is of the form α(x, z_{1}, z_{2}, … z_{k}), we eliminate the free variables other than x from α by substituting constant symbols for the variables z_{1}, z_{2}, … z_{k}. Further we use the decompositions of the probabilities in terms of conditional distributions.

Proof. The elements of A are finite dimensional cylinder sets of U^{T}, because these elements are interpretations of formulas with finitely many free variables, so they are subsets of some finite dimensional space. U is countable, consequently any finite dimensional cylinder set S belongs to (P(U))^{T}, because S is a countable union of points in a given finite dimensional space. Therefore H ⊂ P(U)^{T}. The restriction of p can be considered as a probability on H, thus also on A. The symmetry and product properties follow from the power distribution property.

We have to prove property (1.2). It is sufficient to prove the infimum part, for example. We should use the elements of U, therefore let us extend the language L by a set of constants corresponding to the elements of U and interpret every constant by the original element. Let A^{∗} be the cylindric set algebra corresponding to the extended language L′ and model. Evidently H ⊂ H^{∗} ⊂ P(U)^{T} where H^{∗} is the Boolean part of A^{∗}. p can be considered also on A^{∗} and it has the symmetry and product properties, too. It is sufficient to prove the infimum property for A^{∗}.

So let an element of A of the form |∀x α| and let y_{1}, y_{2}, … y_{i}, … be an arbitrary subsequence of the individuum variables. Let z_{1}, z_{2}, … z_{k} be the free variables of α beyond x.

Let u_{1}, u_{2}, … u_{k} be arbitrary fixed constants corresponding to the elements in U, among those by which the language has been extended. Our first claim is as follows:

(3.1)  p |∀x α(x, u_{1}, u_{2}, … u_{k})| = inf_{n∈ω} p(⋂_{i∈n} |α(y_{i}, u_{1}, u_{2}, … u_{k})|).

∀x α(x, u_{1}, u_{2}, … u_{k}) is a closed formula, thus it is true or false on M and by the definition of the concept probability, the left hand side is equal to either 0 or 1. In the case 1, there exist no u_{0} such that α(u_{0}, u_{1}, u_{2}, … u_{k}) is false, since ∀xα(x, u_{1}, u_{2}, … u_{k}) is true. Thus the set |α(y_{i}, u_{1}, u_{2}, … u_{k})| coincides with the whole space U^{T} for every i, hence the right hand side of (3.1) is equal to 1. If the left-hand side of (3.1) equals 0, then the formula ∀x α(x, u_{1}, u_{2}, … u_{k}) is false in the model, therefore there exists a u_{0} such that α(u_{0}, u_{1}, u_{2}, … u_{k}) is false. Thus the set |α(y_{i}, u_{1}, u_{2}, … u_{k})| is different from the whole space, therefore the probability m of |α(y_{i}, u_{1}, u_{2}, … u_{k})| is less than 1, because of the strict positivity of the original distribution on U. p does not depend on i because of symmetry. The product property of p implies

p(⋂_{i∈n} |α(y_{i}, u_{1}, u_{2}, … u_{k})|) = m^{n}

thus the infimum is zero in (3.1), that is (3.1) is true.

Now consider formulas with two free variables. Notice that the following property holds for any formula of the form ϑ′(x, z):

(3.2)  p |ϑ′(x, z)| = ∑_{j=1}^{∞} p |u_{j}| p^{u_{j}}|ϑ′(x, u_{j})|

where we apply the summation property concerning conditional distributions in the space {(x, z) : (x, z) ∈ U × U} for the sets |ϑ′(x, z)|, |ϑ′(x, u_{j})| and |u_{j}|, where p^{u_{j}} denotes the conditional distribution of p with respect the condition z = u_{j} (j = 1, 2, …), and the u_{j}’s run over the constant symbols corresponding to the elements in U.

Relation (3.2) can be generalized for formulas of the form ϑ(y_{1}, … y_{n}, z_{1}, … z_{k}) having n + k free variables:

(3.3)  p |ϑ(y_{1}, … y_{n}, z_{1}, … z_{k})| = ∑_{j=1}^{∞} p |v_{j}| p^{v_{j}}|ϑ(y_{1}, … y_{n}, v_{j})|

where v_{j} denotes a k-tuples of constants in U, and the v_{j}’s (j = 1, 2, …) is an enumeration of the finitely dimensional points in the space U^{k}.

Specially if ϑ in (3.3) is of the form ∀x α(x, z_{1}, … z_{k}) then

(3.4)  p |∀x α(x, z_{1}, … z_{k})| = ∑_{j=1}^{∞} p |v_{j}| p^{v_{j}}|∀x α(x, v_{j})|.

Returning to the original infimum condition in (1.2), assume that x, z_{1}, … z_{k} are the free variables of α. Then for the left hand side:

\begin{aligned}p |∀x α(x, z_{1}, … z_{k})| & = ∑_{j=1}^{∞} p |v_{j}| p^{v_{j}}|∀x α(x, v_{j})| \\ & = ∑_{j=1}^{∞} p |v_{j}| inf_{n∈ω} p^{v_{j}}(⋂_{i∈n} |α(y_{i}, v_{j})|) \end{aligned} ; (3.5)

because of (3.4) and (3.1) ((3.1) is true for p^{v_{j}} too, since p and p^{v_{j}} are different only in a constant for fixed v_{j}).

Let us consider the right hand side of the infimum part of (1.2). Let us denote the formula ⋀_{i∈n} α(y_{i}) by ϑ(y_{1}, … y_{n}, z_{1}, … z_{k}). By the remark following the definition of Q-probability we can suppose without the loss of generality that {z_{1}, … z_{k}} ∩ {y_{1}, … y_{n}} = ∅.

Using the fact that |⋀_{i∈n} α(y_{i})| = ⋂_{i∈n} |α(y_{i})|, apply (3.3) to the right-hand side of the infimum condition:

inf_{n∈ω} p ⋂_{i∈n} |α(y_{i})| = inf_{n∈ω} p|⋀_{i∈n} α(y_{i})| = inf_{n∈ω} ∑_{j=1}^{∞} p |v_{j}| p^{v_{j}}|ϑ(y_{1}, … y_{n}, v_{j})|

= ∑_{j=1}^{∞} p |v_{j}| inf_{n∈ω} p^{v_{j}}(⋂_{i∈n} |α(y_{i}, v_{j})|).

We got the right hand side of (3.5) and the proof is finished. □

There are some consequences of Theorem 3.1 applying the Löwenheim–Skolem theorem: by Löwenheim–Skolem theorem, for a countable language L, arbitrary infinite model N has an elementary submodel M with countable universe. It is known that cylindric set algebras corresponding to these models are isomorphic. Therefore the problem to construct probability on the algebra corresponding to N can be reduced to a problem solved (in Theorem 3.1).

If the language is countable, theories has a countable model by Löwenheim– Skolem theorem. Theorem 3.1 applies to this model and the canonical homomorphism transforms the Q-probability from A to the Lindenbaum–Tarski algebra of the language (see [1], [6], [12]). As a consequence, there exists a quantifier probability measure on any Lindenbaum–Tarski algebra corresponding to a countable language.

***

Now we come to another case of quantifier probabilities. We give a construction for quantifier probability defined for a non-countable model.

Consider the usual real interval [0, 1) and the product set [0, 1)^{T} where T is any set. Take the finite unions of the finite dimensional intervals in [0, 1)^{T}, where the sides of these intervals are non-degenerate subintervals of [0, 1). It is known that these finite unions form a Boolean set algebra and the same is true for the collection A of the corresponding cylinder sets of infinite dimension. A is obviously closed with respect to the cylindrifications in [0, 1)^{T}. So A is closed with respect to all the diagonal free cylindric algebraic operations, therefore A can be considered as a universe of a diagonal free cylindric set algebra A.

In order to investigate A, let us choose a first order language L′ with individuum variables x_{1}, x_{2}, … x_{j}, … without equality and let T be the set of these individuum variables. Every finite dimensional interval should have a name, therefore let us associate with each real interval [0, r) a unary predicate symbol P_{r}, where r ∈ [0, 1). L′ is a monadic language. Consider the model with universe [0, 1) of type L′, with the natural interpretations of P_{r}’s. L′ and also the universe [0, 1) are non-countable. Obviously the sets in A have Lebesgue measure and property (1.2) is defined for A.

We are going to use the following version of infimum property in (1.2): for every formula α

(3.6)  |∀x α| = ∅ implies inf_{n∈ω} p(⋂_{i∈n} |α(y_{i})|) = 0

(the proof of the equivalence of the original property and (3.6) is easy and left to the Reader).

Theorem 3.2. The Lebesgue measure on A is a quantifier probability measure.

Proof. Suppose in (3.6) that α has only one additional free variable z other than x, so α is of the form α(x, z). This case can be generalized for k + 1 free variables as in Theorem 3.1. Further suppose that α is given in a disjunctive normal form. By definitions of L′ and the finitely dimensional intervals, |α(x, z)| can be considered as a finite union of disjoint finite dimensional intervals.

The projections of the members of this union to the z-axis define a partition {I_{1}, I_{2}, … I_{m}} of [0, 1). Let us consider the common refinement F of the members of the union |α(x, z)| and the two dimensional cylinders with base intervals in {I_{1}, I_{2}, … I_{m}}. For fixed j let the members of this refinement: K_{1}^{j} × I_{j}, …, K_{i(j)}^{j} × I_{j}, (where K_{i}^{j}’s are one dimensional intervals). Then

λ |α(x, z)| = λ( ⋃_{j=1}^{m} ⋃_{i=1}^{i(j)}(K_{i}^{j} × I_{j})) = ∑_{j=1}^{m} ∑_{i=1}^{i(j)} λ(K_{i}^{j}) × λ(I_{j}),

where λ is the Lebesgue measure.

By assumption (3.6), |∀x α(x, z)| = ∅. Therefore for any j and z, z ∈ I_{j}, there is a point (x_{0}, z) not included in |α(x, z)|, thus K_{i}^{j} ≠ [0, 1) (i = 1, 2, … i(j)), therefore λ(K_{i}^{j}) < 1.

Furthermore, in the space (y_{1}, y_{2}, z)

λ(|α(y_{1}, z)| ∩ |α(y_{2}, z)|) = λ( ⋃_{j=1}^{m} ⋃_{i=1}^{i(j)}(K_{i}^{j} × K_{i}^{j} × I_{j})) = ∑_{j=1}^{m} ∑_{i=1}^{i(j)} λ^{2}(K_{i}^{j}) × λ(I_{j}).

More generally,

λ(⋂_{i∈n} |α(y_{i}, z)|) = ∑_{j=1}^{m} ∑_{i=1}^{i(j)} λ^{n}(K_{i}^{j}) × λ(I_{j})

where we can suppose that y_{i} ≠ z by the remark following the definition of Qprobability. λ(K_{i}^{j}) < 1 implies that the limit of the right hand side is 0 for n → ∞, hence the limit of λ(⋂_{i∈n} |α(y_{i}, z)|) is also 0, just as we have to prove. □

We remark that probabilities defined for different models corresponding to the same language L can be “mixed” taking their average according to a distribution. In this way we can get a probability on the Lindenbaum–Tarski algebra of the language and supposed that the components are Q-probabilities, this average is also a Qprobability. Moreover, every probability defined on the Lindenbaum–Tarski algebra can be composed in this way choosing suitable component probabilities (see [5]).

References

[1] H. Andreka, J. Madarasz and I. Nemeti, Algebras of relations of various rank, some current trends and applications, J. Relational Methods Comput. Sci. 1 (2004),27–48.

[2] T. Williamson and D. Gabbay (eds), Combining Probability and Logic, 4th De Morgan workshop, King’s College, London, 2002, J. Appl. Logic, 1(3-4) (2003).

[3] C. J. Everett, S. Ulam, Projective algebras, Am. J. Math. 68 (1946), 17–28.

[4] S. Fajardo, H. J. Keisler, Existence theorems in probability theory, Adv. Math. 120(2) (1996).

[5] J. E. Fenstad, Representation of probabilities defined on first order languages, in: Sets, Models, Recursion Theory, North Holland, 1967, pp. 156–172.

[6] M. Ferenczi, On homomorphisms between relation algebras, Algebra Universalis 27 (1990), 474–479.

[7] M. Ferenczi, On diagonals in representable cylindric algebras, Algebra Universalis 41 (1999), 187–199.

[8] M. Ferenczi, On representability of neat embeddable cylindric algebras, J. Appl. Non-Classical Logics 4(10) (2000), 300–315.

[9] I. Hacking, I. An Introduction to Probability and Inductive Logic, Cambridge University Press, 2001.

[10] E. T. Jaynes, Probability Theory. The Logic of Science, Cambridge University Press, 2003.

[11] Z. Ognjanović, M. Rašković, Some first order probability logics, Theor. Comput. Sci. 247(1-2) (2000), 191–212.

[12] M. Rašković, R. S. -Dor - dević, M. Bradić, Weak cylindric probability algebras, Publ. Inst. Math. (Beograd) 61(75) (1997) 6–16.

[13] M. Rašković, R. S. -Dor - dević, Cylindric probability algebras, Publ. Inst. Math. (Beograd) 68(82) (2000), 20–36.

[14] G. Sagi, A note on algebras of substitutions, Studia Logica 72 (2009), 265–284.

[15] D. Scott, P. Krauss, Assigning probabilities to logical formulas, in: J. Hinitikka, P. Suppes (eds), Aspects of Inductive Logic, North-Holland, 1966, pp. 219–264.

[16] R. Sikorski, Boolean Algebras, Springer-Verlag, 1960

[17] Sayed-Ahmed Tarek, Algebraic Logic, where does it stand today?, Bull. Symb. Logic 11:4 (2005), 465–516.

[18] A. M. Verstik, Randomization of algebra and algebraization of probability, in: B. Engquist (ed.), Mathematics unlimited – 2001 and beyond, Springer-Veralg, 2001.

Department of Algebra (Received 06 05 2005) Institute of Mathematics (Revised 29 12 2005) Budapest University of Technology and Economics H1111 Budapest, Egry József utca 1

    ferenczi@math.bme.hu