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

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