I have an assignment where I need to count the number of models of a certain sort which satisfy a given sentence, and I keep finding that the number of models I count exceeds the total number of possible models, so I'm wondering where I'm going wrong.
I need models for languages having only predicates $F$ and $G$, and having domain $U=\{1,2,3,4,5\}$. By my count, the number of possible denotations of $F$ is the number of subsets of the domain, $2^5$ and likewise for $G$ so that the total number of possible models is $2^{10}=1024$.
Of these I want to count the models that satisfy $(\exists x)(Fx\land Gx)$ but not $(\forall x)(Fx\lor Gx)$. Thus I need models in which at least one element is shared in the denotations of $F$ and at least one element is in neither denotation.
I reason that there are 5 choices for the element that they certainly share and 4 for the element they certainly do not share. Of the remaining three elements it doesn't matter whether it's in either $F$ or $G$, I figure for each it's in or out of $F$ and in or out of $G$, so my total count is $5\cdot 4\cdot 2^3\cdot 2^3 = 1280$ which is bigger than the space of possible models.
Can anyone point out the mistake or suggest a better strategy?
We use Inclusion/Exclusion. Note that the procedure works in essentially the same way in general.
We say that a point $x\in \{1,2,3,4,5\}$ is of Type $A$ if both $F$ and $G$ hold at $x$, of Type $B$ if neither holds at $x$, of Type $C$ if $F$ holds but not $G$, and of Type $D$ if $G$ holds but not $F$.
The number of possible unconstrained truth assignments is the number of functions from our $5$ point set to $\{A,B,C,D\}$. This is $4^5$, which you knew already.
We first count the bad assignments, where nothing is mapped to $A$ and nothing is mapped to $B$. There are $3^5$ functions that miss $A$, and the same number that miss $B$. But $2\cdot 3^5$ double-counts the $2^5$ assignments that miss both $A$ and $B$. So there are $2\cdot 3^5-2^5$ bad assignments. It follows that the number of good assignments is $$4^5-2\cdot 3^5+2^5.$$
Remark: The solution proposed in the OP does multiple counting. For example, maybe when you choose something to have both properties, it is $1$. Later, maybe you chose $2$ to have both properties. But the same result has also been counted as $2$ "first" and $1$ later.