Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
What are non-equivalent pure monadic schemata? – Gerry Myerson Oct 28 '12 at 6:48
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 (∀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 ~∃xFx – Seth Roberts Oct 28 '12 at 21:20

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?)

share|cite|improve this answer
I appreciate your response, but I am not clear on some of the terminology here. What exactly is prefix of a quantifier? Also, prenex normal for, from what I just looked up, seems to mean some thing very similar to what I mean about pure monadic. Let me see if you agree. – Seth Roberts Oct 28 '12 at 17:37
By pure monadic I mean that you take any open one variable schema, such as Fx V Gx, and place a one quantifier in front of it to bound the variable, x in this case. So the above could become (∃x)(Fx V Gx), which is pure monadic. So, there can’t be any open sentence, there can only be one variable, and thus one quantifier ranging who scope is the entire schema. – Seth Roberts Oct 28 '12 at 17:37
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. – Seth Roberts Oct 28 '12 at 17:37

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?

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.