[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.
More information about the FOM
mailing list