1
$\begingroup$

I am seeking advice or an answer to the following question that is bugging me:

How long a list of non-equivalent pure monadic schemata containing only the predicate letters “F” and “G” is there?

I can get an answer for one predicate letter, but I do not Know two nor do I know three. I would like to find the general formula for this. that is, given n predicate letters, there will be z amount of non-equivalent schemata.

  • 0
    They are schema that do not have the same interpretation for every universe of discourse. So, (∃x)(Fx V Gx) is eq. to (∃x)Fx V (∃x)Gx. While (∀x)(Fx V Gx) is not eq.to (∀x)Fx V (∀x)Gx. Pure Monadic means that you can not have any unbound variables, and the main connective can not be a negation. So, you can't have something like ~∃xFx2012-10-28

2 Answers 2

1

If identity is part of your first-order logical framework, then of course the answer is "countably infinite", even with just one predicate letter, as you can write (the formal versions of) "there are exactly $n$ $F$s", for each $n$.

Even without identity, if your language has the usual unending supply of constants, then the answer is "countably infinite", even with just one predicate letter, since $Fa_1$, $Fa_1 \land Fa_2$, $Fa_1 \land Fa_2 \land Fa_3$, etc. are non-equivalent.

If there's no identity and no constants (and open sentences are banned), then the only closed formulae are the quantified sentences without constants. Every such wff is equivalent to its prenex normal form, so it just a question of counting distinct prenex normal forms. Exercise! (How many non-equivalent at-most-$n$-quantifier prefixes are there? how many non-equivalent wffs after the quantifiers if you have only $n$-predicates to play with?)

  • 0
    Now, the way I have been thinking about this is to think of the way the extensions of the predicate letters could look like. That is, the predicate letter “F” could be assigned everything, something, or nothing. This could be wrong way to think through this problem.2012-10-28
0

I think that Seth's last comment is on the right track.

For the two predicate case ("F" and "G"), each element in the universe can be placed either in the "F" and not "G" (and vice versa), in both, or in neither. We also know that any combination of simple monadic schema has a verifying universe with 2 or fewer elements since there are, at most, two existential generalizations. So there are 2^4 = 16 possible assignments. Since each interpretation of a schema must realize at least one of these assignments, there are 2^4 - 1 = 15 mutually exclusive interpretations. [Or, at least, this is according to my instructor, still trying to figure it out. Perhaps they are mutually dependent in some way?]

[This is where I get into guesswork.] There are 15 different interpretations, so find combinations of each of these interpretations for each possible number of verifying interpretations.

That is, use "15 choose r" for r from 0 to 15. This is a sum over r of 15!/[r!(15-r)!], which is symmetric.

When I do this I get a huge number (~60k), which makes me suspicious. Maybe there are duplicates in there?