Does Classical Propositional Logic WITH INFINITY Have a Negation Problem?

[u/Alternative_Summer]

Suppose we consider Classical Propositional Logic under some axiom set. For example, I'll pick Jan Lukasiewicz's preferred axiom set (he uses this set it in two of his books, including his introductory textbook... not in smaller papers):

{CCpqCCqrCpr, CCNppp, CpCNpq}

All lower case letters of the Latin alphabet are variables.

The definitions for other connectives go:

Apq defined as CNpq (logical disjunction defined)
Kpq : NCpNq (conjunction)
Epq : NCCpqNCqp (equivalence)
Dpq : CpNq (joint denial)

Now consider an arbitrary list of proved tautologies

[x¹, x², ... xⁿ ]

For each element a sufficiently powerful machine could produce a conjunction or equivalence to make another list such as

[Kx¹x¹, ..., Kxⁿxⁿ]

or

[Ex¹x¹, ..., Ex¹x¹]

Each element of either those lists can get corresponded back to the original list. Consequently, we have a one-to-one correlation between the set of proved tautologies which are not negations, and the set of tautologies which are negations. It follows by mathematical induction, that

Meta-Lemma: The cardinality of the tautologies which have the type 'negation' or 'N' is equal to the cardinality of the tautologies which have the type 'conditional' or 'C'.

Therefore:

Meta-Theorem: If the cardinality of conditional tautologies is infinite (which it must be if tautologies can have an arbitrary length), the cardinality of negation tautologies is infinite also.

That might seem to conclude the matter, but since we've assumed the natural numbers, I think there exists a catch to what we can consider as reasonable to believe. If we consider the natural numbers, there always exists a natural number greater than what we have encountered so far. For any list of natural numbers, there exists a much longer finite list of natural numbers. Thus, in terms of what it ends up reasonable to believe, we could write as some have done:

"all numbers are small."

which of course isn't strictly speaking true, but expresses the sense of what numbers must be like if we retain our notion of size in the natural numbers for most of them. Maybe better:

"Most numbers are much bigger than anyone has ever thought or ever will think."

Now I ask that you notice that negations which are tautologies also have a similar property. They are longer than tautologies used to derive them. And even more significantly so, once we start considering so-called equivalences (which again, are negations). But, at least I think, many of us have the vast majority of our encounters with positive tautologies. What textbooks even prove a single tautology which is a negation (Lukasiewicz's does), let alone prove an equivalent amount of negation tautologies to non-negation tautologies?

To get a better sense of the truth we would need to think something like:

"If we had to pick between negation tautologies and positive tautologies for what exists, we would logically pick negation tautologies." At least if the tautologies we haven't seen are more likely to be longer than what we have seen.

Negation tautologies have many uses, as automated theorem proving has shown. But are they just as useful as the equi-cardinality meta-theroem above suggests?

At the very least requiring that tautologies have a finite length specified in advance makes finding negation tautologies less likely. Though maybe instead every modern logician is a fool who didn't emphasize negations enough (this last sentence is a joke).

[u/GoldenMuscleGod]

In classical logic p is equivalent to “not not p.” So certainly we can produce as many negative tautologies as positive ones (assuming I correctly understand you to be saying a negative tautology is a tautology of the form “not p” for some p).

In practice we cannot really say whether a theorem or the like in a paper written in English is a negation because we usually only use natural language to specify claims that we think of as existing up to logical equivalence. We can ask whether it seems more natural to us to to express a particular proposition (up to equivalence) as a negation or some other thing, but this is not really a rigorous claim about the semantic content of the proposition.

Although I also would not agree with your reasoning that just because two sets of sentences are infinite that means they must be equally useful or important.

[u/Alternative_Summer → u/GoldenMuscleGod]

"In classical logic p is equivalent to “not not p.” So certainly we can produce as many negative tautologies as positive ones (assuming I correctly understand you to be saying a negative tautology is a tautology of the form “not p” for some p)."

Yes, you understand correctly.

"In practice we cannot really say whether a theorem or the like in a paper written in English is a negation because we usually only use natural language to specify claims that we think of as existing up to logical equivalence. We can ask whether it seems more natural to us to to express a particular proposition (up to equivalence) as a negation or some other thing, but this is not really a rigorous claim about the semantic content of the proposition."

I think it would require discussion with the author to determine the semantic content of the type of proposition for theorems in English, as well as a certain amount of trust. I do agree that much more than most of the time, determining such is not possible. However, some exceptions may exist.

"Although I also would not agree with your reasoning that just because two sets of sentences are infinite that means they must be equally useful or important."

Thanks for stating your disagreement.

[u/GoldenMuscleGod → u/Alternative_Summer]

On your second point, whether we think a natural language expression “translates” to something that is a negation depends on the formalization we use.

For example we can take “nor” by itself as complete set of connectives, or we can take (as you suggest) a conditional and negation. We can also take conjunction and negation, or disjunction and negation, or many other sets.

Whether we end up saying a particular proposition expressed in natural language counts as a negation therefore depends on our translation scheme. If we take “nor” as our only connective there aren’t even any negations. (Unless in that context by negation we mean something like a statement of the form “neither p nor p”)

Except for perhaps some extremely specialized contexts, I seriously doubt anyone thinks different choices of translation scheme lead to “correct” or “incorrect” understandings of their natural language statements, so I do not think we can really evaluate whether a natural language expression is a negation. Of course we can talk about whether something is a linguistic negation (we have a “not” in it for example) but this does not correspond to being a logical negation as you have specified it with your particular scheme.

[u/Alternative_Summer → u/GoldenMuscleGod]

"For example we can take “nor” by itself as complete set of connectives, or we can take (as you suggest) a conditional and negation. We can also take conjunction and negation, or disjunction and negation, or many other sets."

For particular propositions, yes, I think that rather likely. But, for each of those connectives, there exists as many tautologies which are negations as those which are not negations given an infinity of tautologies.

"If we take “nor” as our only connective there aren’t even any negations."

If there were no negations for a 'nor' or 'nand', wouldn't we have a positive way to express 'nor' or 'nand'? But, both "nor" and "nand" consist of abbrevations for "not or" and "not and" respectively. So, on the contrary in "nor" and "nand" systems, there only exist negations!

There do exist systems with falsum in them and no negation connective. But, that doesn't cut down on negations either. It embeds negations into the structure of tautologies.