# [FOM] Counting models

Andy Fugard a.fugard at ed.ac.uk
Fri Jul 25 07:14:02 EDT 2008

```Dear all,

Last year I posted a message on counts of first-order models of
syllogistic premises, and how many of these were counter-models of
conclusions.  (Message posted again below.)  This week I got around to
playing with this again, and found some (conjectures for) closed forms.

I was wondering if anyone recognises any of these?  I got two hits on
the On-Line Encyclopedia of Integer Sequences: A051588, the number of 3
x n binary matrices such that any two rows have a common 1; and twice
A016103, described as "Expansion of 1/(1-4x)(1-5x)(1-6x)".

For the premises, the number of models with n individuals is given by:

--------------------------------------------------------------
Has valid conclusion?  Quantifiers         Models
--------------------------------------------------------------
Yes                    Both universal      2^{2n}
Yes                    Mixed univ + exist  6^n - 5^n
No                     Both universal      5^n
No                     Mixed univ + exist  6^n - 4^n
No                     Both existential    8^n + 5^n - 2 * 6^n
--------------------------------------------------------------

I haven't yet found a concise way to characterise the counts of
countermodels, but these are the formulae:

0      (i.e., no countermodels as classically valid)
2^n
3^n
4^n - 3^n
4^n
5^n - 4^n
6^n + 4^n - 2*5^n
5^n - 3^n
6^n + 3^n - 5^n - 4^n
6^n - 5^n
2^n + 6^n - 2*4^n
8^n - 3*6^n + 3*4^n - 2^n
8^n - 3*6^n + 2*4^n - 3^n + 5^n
8^n - 2*6^n - 6^n + 2*5^n
8^n - 3*6^n + 3*5^n - 4^n

If anyone is interested, I can supply a large table.

Thanks,

Andy

Andy Fugard wrote:
> Dear all,
>
> For various kinds of model I'm interested in how tricky it is to find
> counter models for a given conjecture.  To begin playing with this, I
> have enumerated first-order models of all 512 conjectures of
> syllogistic form with the number of individuals from 1 to 5.
>
> For instance for
>
>    forall x. A(x) => B(x)
>    forall x. B(x) => C(x)
>    ----------------------
>    forall x. A(x) => C(x)
>
> The number of models of the premises are:
>
>    individuals   1      2      3      4      5
>    models        4     16     64    256   1024
>
> Presumably 2^(2n) in general.  (There are obviously no counter models
> for the conclusion in the set of models of the premises.)
>
> For
>
>    exists x. A(x) & ~B(x)
>    forall x. B(x) => C(x)
>    ----------------------
>    forall x. C(x) => A(x)
>
> the table looks like
>
>    individuals     1      2      3      4      5
>    models          2     20    152   1040   6752
>    countermodels   0      8     96    800   5760
>
> where "countermodels" is how many of the models of the premises are
> counter models of the conclusion.
>
> My question: does anyone know of examples of work where these kinds
> of things (not necessarily for syllogisms) are counted, e.g.
> analytically?
>
> Best wishes,
>
> Andy

--
Andy Fugard, Postgraduate Research Student
Psychology (Room S6), The University of Edinburgh,
7 George Square, Edinburgh EH8 9JZ, UK
+44 (0)78 123 87190   http://figuraleffect.googlepages.com/

The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.

```