
## B2. Infinite Sets Of Models

More research has to be done to extend the notion of evidence to systems with infinite sets of models. Here is one possible approach.

Since the set of predicate symbols occurring in a first-order **system** S is finite, the reason for infiniteness of the set of its models is the infiniteness of the domain of its terms3. Let D **be an infinite enumerable domain of** S, d denote a finite subset of D**, and** S
(d)stand for the original system S **for which**
the original domain D is replaced with d. Then S **can be viewed as a limit of** S
(d) while d approaches D. The set of models MOD(S
(d)**) is finite allowing the**
following definition.

Definition 8.2 Given S and its domain D, let d1, d2, . . . **be a sequence of finite**
subsets of D such that limi→∞ di = D**. Then the evidence of a formula** F in S
is E(S, F**) = lim**
i→∞
E(S
(di ), F**) = lim**
i→∞
|MOD(S
(di ) ∪ {F})| |MOD(S(di))|**(29)**
if the latter limit exists. ✷
Applicability of this definition depends on the nature of S, D and F**, and**
on a proper construction of the sequence of finite subsets of D **for computing**
the limit of E(S
(di ), F).

Example 8.1 S = (∀x){(P(x) → R(x)) ∧ (Q(x) → R(a))}**, and the domain of** x **is the set of all natural numbers.**
Let us define di = {1, . . . , a + i}**. Then in** S
(di) **we have:**
If R(a) is false then P(a) is false and for all x ∈ di Q(x**) is false; for every**
value of x ∈ (di − {a}) the clause P(x) → R(x**) has 3 satisfying assignments;**
so |MOD(S
(di) ∪ {¬R(a)})| = 3a+i−1.

If R(a) is true then 2 assignments satisfy P(a) → R(a**) and** Q(x) → R(a)
for all x ∈ di, and 3 assignments satisfy P(x) → R(x) for all x ∈ (di − {a}**); so**
|MOD(S
(di) ∪ {R(a)}**) = 2**a+i+13 a+i−1.

Hence, |MOD(S
(di))| = (2a+i+1 + 1)3a+i−1, E(S
(di ), R(a)) = (2a+i+1)/(2a+i+1 **+ 1)**.

(30)
A similar calculation gives E(S
(di ), P(a)) = 2a+i / (2a+i+1 **+ 1);**
for all x ∈ (di − {a}) E(S
(di ), P(x**)) =** 13
, E(S
(di ), R(x**)) =** 23
;
for all x ∈ di E(S
(di), Q(x)) = 2a+i / (2a+i+1 **+ 1).**
In the limit i → ∞ we get E(S, P(a**)) =** 12
, E(S, R(a**)) = 1;**
for all natural x 6= a E(S, P(x**)) =** 13
, E(S, R(x**)) =** 23
;
for all natural x E(S, Q(x**)) =** 12
. ✷
3In particular, Herbrand domain of S becomes infinite if S contains function symbols or existential quantifiers producing Skolem functions.