[FOM] Counting models

[Andy Fugard]

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.