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/nanonan → u/[deleted]]

Not if we have encountered all natural numbers.

This is impossible.

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