# Can you make an unlimited number of connectives with $p$ and $q$?

One of the questions in my exercise asks:

We have made several logical connectives using the propositions p and q. For instance p ∧ q, p ∨ q and p ↑ q . Can this go on indefinitely; that is, making an unlimited number of connectives with p and q ? Or is there a finite number of distinct connectives? If so, can you determine how many there can be?

I was trying to come up with an answer but got stuck. Does it mean an unlimited number of connectives with p and q such that $$p \land q$$ $$p \land (p \land q)$$ $$p \land (p \land (p \land q))$$

In that way you definitely can keep going forever, or for another example: $$\neg p$$ $$\neg (\neg p)$$ $$\neg (\neg (\neg p))$$

So does it mean

Can you create infinite connectives using the same operation?

or

How many connectives can be made using unique operations?

Also, for the last question

If so, can you determine how many there can be?

Wouldn't it be the number of conjunctions available? (That mean something different to each other)

I would really appreciate some help and a better explanation of the question at hand, maybe even hints so that I can complete it on my own.

• There are infinitely many formulas that differ in syntax, but there are only finitely many functions of type $\{0,1\}\times\{0,1\}\to\{0,1\}$. – dtldarek Aug 8 '16 at 7:33

It makes a difference whether you talk about syntactically or semantically distinct connectives.

Syntactically, $$p \land q$$ $$p \land (p \land q)$$ $$p \land (p \land (p \land q))$$

are different: The formulas obviously have a different form, they have a different number of atoms and connectives and thus they can syntactically not be identical.
Now you could make up a connective defined as $p \land q$ and one that is shorthand for $p \land (p \land q)$ and have two connectives. By their form, they are indeed distinct entities, so yes, there is theoretically an infinite number of connectives. This observation is already given by simple recursion (as you exemplified).

Semantically, however, they are equivalent: All of the formulas yield the same truth conditions, namely $1$ if both $p$ and $p$ are true and $0$ else, so you can not get any new logical meaning by creating $p \land (p \land q)$ because the truth value of this statement is already defined by another connective (namely the simple $\land$).
If you understand a connective by its semantics, i.e. the meaning of a connective is exactly the conditions under which the formla becomes true and "a connective" corresponds to "a certain permutation of truth values in a truth table" (when you write the formulas out in a truth table, the last column would always look the same for any of the connectives you used), then the number of possible connectives is limited, since there are only finitely many possible permutations of truth values for a given number of atoms there are and the number of truth values a statement can have.

More precisely, the number of possible semantically distinct $n$-ary connectives in an $m$ valued logic is given by $m^{m^{n}}$, so in the case of a classical two-valued logic and binary connectives, there are $2^{2^{2}} = 16$ possible semantically distinct connectives.
For unary connectives in a two-valued logic, (like negation), there are $2^{2^{1}} = 4$ different possibilities to assign a truth value to the combination of connective + variable, and so on.

Hence, the number of syntactically differently defined connectives is theoretically infinite, but if you understand a distinct connective by its semantics, then the number of possible connectives is restricted; in the case of binary connectives for a two-valued logic to 16.

I assume the textbook refers to semantically distinct connectives because any logical element is normally defined by its truth conditions, thus the answer would be yes, there is a finite number of distinct connectives, given by $m^{m^{n}}$ for $n$-ary connectives in an $m$-valued logic.

The question as stated is indeed ambiguous (at least assuming you haven't been given a precise definition of "logical connective"). You have provided one reasonable sense in which there are infinitely many "connectives" you can make.

However, I suspect the question is intended to be interpreted in a different way. Notice that, for instance, $p\wedge q$ and $p\wedge(p\wedge q)$ aren't really different: they are logically equivalent, i.e. they have the same truth table. So for the purposes of this question, they should not be considered different connectives. More precisely, a "connective" for the purposes of this question is a binary operation that takes a pair of truth values and gives another truth value. That is, we identify a "connective" with its truth table, so two connectives with the same truth table are the same.

So the question is really asking, how many different such truth tables are there? Are infinitely many, or finitely many? And if there are only finitely many, how many are there exactly?

• Well wouldn't there be $4!/2$ = 12 different such truth tables? – Samir Chahine Aug 8 '16 at 6:59
• How did you get that number? – Eric Wofsey Aug 8 '16 at 6:59
• I took the number of rows there are (4) and since I'm trying to rearrange the truth values in the third column as many times as possible but I realise that it's completely wrong and I don't know If I'm on the right track. Are factorials used here at all ? – Samir Chahine Aug 8 '16 at 7:04
• You're not rearranging the truth values; you're assigning a truth value to each row (but true and false each might appear any number of times). How many ways are there to do that? – Eric Wofsey Aug 8 '16 at 7:24
• I can think of and write out 17 different ways, where there there could be all f, all t or anywhere in between, but I'm not sure how to do this with out my "brute" solution tttt fttt fftt ffft ftft tfff tttf ttff tftf fftf ttft tfft fttf ttft tftt ftff – Samir Chahine Aug 8 '16 at 7:36

It's not talking about "infinite connectives," it's talking about an infinite number of connectives.

Two ostensibly different-looking connectives can actually "the same," for instance de Morgan's law tells us $\neg (p\wedge q)$ and $(\neg p)\vee(\neg q)$ are equivalent. Whether two are equivalent or not can be determined by looking at the truth table.

How many possible truth tables are there involving $p$, $q$ and a third column?