i get stuck in logic problem.
suppose $L=\{P,Q\}$ which $P$ and $Q$ are one-place predicate. if $A$ is a set with three element. how many way we can convert $A$ into a Structure for $L$ that Interpretation $P$ and $Q$ has non-empty intersection?
i see the result is $37$. how this be calculated? any idea? thanks.
You have to use a combinatorial argument:
Let $A=\{a_{1},a_{2},a_{3}\}$. Clearly at lease one of $P(a_{1})$, $P(a_{2})$, $P(a_{3})$ has to hold.
Now if $P$ holds true of all three elements, then as long as $Q$ holds true of at least one element the result holds. Now there are 7 different ways (${3 \choose 1} + {3 \choose 2} + {3 \choose 3}$) in ways in which $Q$ can be interpreted so that the intersection you are looking for is non-empty.
Now suppose $P$ holds true of one element. Say $a_{i}$. Now if $Q$ only holds of one element it has to be $a_{i}$ as well in order to meet the conditions. If $Q$ holds true of two elements then there are $2$ possibilities, i.e. $Q$ holds true of $a_i$ and one other element (e.g. if $i=1$, then we have to have either $Q(a_{1})$ and $Q(a_{2})$ in $A$ or $Q(a_{1})$ and $Q(a_{3})$ in $A$). If $Q$ holds true of all three elements, then you have the required property. Since $i$ was arbitrary, we have $3\times(1+2+1)=12$ different interpretations.
Now try and figure out what happens if $P$ holds of two elements? The argument is very similar to what I've written down. Once you count those, add all three up and you will have your answer.
EDIT: The last answer is $37$ and if you finish the counting argument above you'll get this answer. Since you asked for clarification; Suppose that only $P(a_{1})$ holds in $A$. i.e. $A\models{P(a_{1})}\wedge\neg{P(a_{2})}\wedge\neg{P(a_{3})}$, then in order for the intersection to be non-empty, you need either $A\models{Q(a_{1})\wedge\neg{Q(a_{2})}\wedge\neg{Q(a_{3})}}$ or $A\models{Q(a_{1})\wedge{Q(a_{2})}\wedge\neg{Q(a_{3})}}$ or $A\models{Q(a_{1})\wedge{Q(a_{2})}\wedge{Q(a_{3})}}$ or $A\models{Q(a_{1})\wedge\neg{Q(a_{2})}\wedge{Q(a_{3})}}$ (note that no two of these can occur at once). Now if you consider cases where only $P(a_2)$ and where only $P(a_3)$ holds in $A$, when you add all these together you get $4+4+4=12$ different cases. You have to count the number of other possibilities too.
Note that my original answer does the same by counting $3\times{(1+2+1)}=12$.
Edit: The last case can be calculated by $3\times{(2+3+1)}=18$ (note here if $Q$ holds true of any two elements in $A$, then the intersection we are looking for is non-empty hence the three). Adding all three together we have 37.