[FOM] Counting models

[Andy Fugard]

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?  I'm pretty sure for syllogisms it has been done for  
Euler Circle type models (and as an aside, logically, I'm not quite  
sure what those beasts are).

Best wishes,

Andy

--
Andy Fugard, Postgraduate Research Student
Psychology (Room F15), The University of Edinburgh,
   7 George Square, Edinburgh EH8 9JZ, UK
Mobile: +44 (0)78 123 87190   http://www.possibly.me.uk