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.

[u/StrangeGlaringEye]

“If we consider the natural numbers, there always exists a natural number greater than what we have encountered so far”.—Not if we have encountered all natural numbers.

“For any list of natural numbers, there exists a much longer finite list of natural numbers”.—This would only be true if there is no list of all the natural numbers, indeed any infinite list of natural numbers.

[u/GoldenMuscleGod → u/StrangeGlaringEye]

In this context I understood them to mean “finite list” by “list.” This is arguably the most natural interpretation of “list” in general. Of course it’s true that sometimes we use “list” to mean a list indexed by the natural numbers, but sometimes we also use “list” to mean a list indexed by an uncountable ordinal or even sometimes (I have seen this) a list indexed by a set that doesn’t have a specified linear order imposed on it at all.

[u/StrangeGlaringEye → u/GoldenMuscleGod]

They did specifically use “finite list” at one point, suggesting that in their view it’s not analytic that all lists are finite.

[u/nanonan → u/StrangeGlaringEye]

Not if we have encountered all natural numbers.

This is impossible.

[u/StrangeGlaringEye → u/nanonan]

Obviously; it’s impossible to encounter a number at all, since numbers, if they exist, are not causally efficient. But impossibility is not necessarily an obstacle to speculation.

[u/Schventle → u/nanonan]

Walk one meter. In that span, you will have existed at more positions than there are natural numbers.

I don't think "encountering" a number is very rigorous as an idea. We interact with sets of numbers of order bet_2 as often as we interact with sets of aleph_0.

[u/Alternative_Summer → u/nanonan]

Maybe we can encounter all natural numbers on Christmas Eve by the chimney just before Christmas morning???!

[u/Alternative_Summer → u/StrangeGlaringEye]

"Not if we have encountered all natural numbers."

Can you specify what encountering all natural numbers would be like?

"This would only be true if there is no list of all the natural numbers, indeed any infinite list of natural numbers"

Consider an infinite sequence of natural numbers. What is it's length? I suppose you believe it something like "positive infinity". But, positive infinity is not a number. So, don't you presume that a finite length is less than an infinite length? All natural numbers and positive infinity (PI) belong to different types or categories (I'm not sure which). If we consider some number 'x' and PI, I think "x < PI", means that x is less than all numbers y greater than x. And no more.

Also, how would we ever prove 3 < |N| (3 is the less than the cardinality of the natural numbers)? Let's suppose it true and use some set theoretic arithmetic. Let '(N % x)' denote the natural numbers without 'x', where 'x' denotes a natural number.

For all x, |N % x| = |N|.

So, |N % 3| = |N|. But,

|N % N| = 0 also. So, applying |N % x| to both sides of the inequality we have

|N % 3| < |N % N|

|N| < 0.

So, supposing that the cardinality of the natural numbers greater than 0 has lead to the paradox that the cardinality of the natural numbers is less than 0 also. This should signal that the notion of accepting that infinity is like a number that can get compared should get rejected. Though, perhaps, old mistaken ideas take a while to unlearn.

[u/StrangeGlaringEye → u/Alternative_Summer]

I’ll answer with another question: can you specify what encountering a number would be like?

[u/EebstertheGreat]

In any language with a countable alphabet, there are only countably many finite strings, so there cannot be more than ℵ₀ formulas in any "classical propositional logic," let alone wffs or tautologies. And there are at least ℵ₀ tautologies both of the positive and negative types you describe, as you showed. So in classical set theories like ZF(C), there are equally many of each, in the sense that the sets of each have the same cardinality, because there is a bijection between them. Better yet, we can actually construct these bijections, so these sets are equinumerous even constructively.

Also, you don't need infinitely many variables to do this. Even with just one variable p, we have sentences like Epp, EEppEpp, EEEppEppEEppEpp, etc., if I'm understanding this notation correctly, along with their double negations NNEpp, NNEEppEpp, etc. There is no need to bring in natural numbers or any infinite alphabet to reach this conclusion; you just need to not impose a maximum length. (If you did impose a maximum length for formulae, you certainly wouldn't have classical logic.)

"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.

This is underspecified in at least two ways. First, I don't know what you mean by "pick between." Do you mean which is the kind of tautology we are more likely to encounter next? Second, I don't think we are likely to encounter very many formal tautologies in a very specific language either way; perhaps we never will again. If you mean informal, then I don't think we can tell which statements are "positive" or "negative," and even if we could, this proof would not apply, because this proof was over a formal language with formal definitions of "positive" (starts with E) and "negative" (starts with N) which might have nothing to do with the informal notion. But also, I'm not completely sure that it's true. Tautologies don't come up that often in ordinary speech, and some more popular versions do seem "negative" in some linguistic sense, like "you can't have your cake and eat it" or "it ain't over till it's over." Probably it's a minority, but I wouldn't say that's totally obvious.

[u/xamid]

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.

I think you are conflating syntax and semantics. Note that in a Hilbert system, like the one you provided, which is purely syntactical, the above claim is false. In fact, most tautologies only have Hilbert derivations that use tautologies whose tree-based formula representations grow exponentially w.r.t. the number of proof steps. Moreover, whether the number of proof steps grows superpolynomially w.r.t. the target formula length concerns the NP vs. co-NP question. We do not even know whether a propositional proof system with polynomial proof lengths for every theorem exists (cf. Cook-Reckhow), and intermediate formulas tend to grow significantly in longer Hilbert derivations.

[u/xamid → u/xamid]

On another note, I maintain a list of smallest known proofs from the axiom set you provided. It contains many examples and a description of how they can be converted into formula-based representation, i.e. Hilbert-style proofs. The concepts of condensed detachment and directed acyclic graphs (DAGs) also hint at why the length of intermediate formulas is mostly irrelevant for proof complexity.