The error in MOST logic studybooks (not in ZFC)

0 users think it is non-scientific; after 15 it will be moderated.

TL;DR: I found an error in most logic textbooks (in metalogic, not in ZF). That’s a security hazard.

This shows something that appears to be a contradiction in ZF:

I will denote the set described by a set comprehension (more precisely, its numeric encoding, such as Godel’s encoding) X as S(X).

Let M be the set comprehension

{ set comprehension X | X not in S(X) }.


M in S(M) <=> M not n S(M).


So, we have a logical paradox. What’s wrong?

S is a function in a model of ZF, not in the formal system the proof is written. So, it’s illegal to use it in the proof.

What happens if we try to define S inside ZF? It should fail (unless ZF is contradictory). But how does it fails? (This is not yet researched by me.)

Digging deeper: If we would be able to prove that S exists, this would be enough to trigger the contradiction in ZF.

Note that this paradox is pertinent not to only to ZF but even to predicate logic with equality and predicate symbols (but only if we encode by the same number formulas differing only by variable names):

Let S(x, P) be the logical function from a pair of a variable x and encoding P of a logical formula where x is the only free variable into a one-variable predicate determining trueness of this formula for a given x. Then define Q(P) as encoding of the predicate `not (S(x, P))(P)` (for some variable x not present in P). Then S(y, Q)(Q) <=> not S(y, Q)(Q) (for some variable y not present in Q), because Q = `not (S(y, Q))(Q)`.

Oops! Mathematicians commonly do this trick: “Let S be a function from some expression X of our formal system to another expression S(X) of our formal system.” (This pattern of reasoning is called definition or substitution.) This pattern of reasoning is pertinent to logic studybooks! And that was an error (not in ZF, but in their metalogic)!

So, we have a wrong meta-logic in almost every math logic studybook. That’s a hazard.

I am not yet sure whether automatic proof checkers such as Coq and Lean are affected. As I remember in Lean (maybe, in Coq, too) there is something called metalogic – that could be vulnerable.

Coq, Lean, Isabelle may be used to verify CPUs, OSes, thermonuclear weapons, nuclear power plants, air traffic control, etc. This error is a hazard.

A good news is that modern automated proof checkers (logic verifiers) use lambda-calculus not ZF or predicate logic. But they indeed may use ZF or predicate logic sometimes (in their proof libraries). Moreover, metalogics of proof checkers may have a similar bug to this bug.

The kind of the hazard is: “We built a nuclear plant. Our software is verified with an automatic logic checker, we don’t even need to debug it before turning it on. Debugging is for people who don’t know modern software security. Bump!”

P.S. Hire me! I sent the world-best engineering security bug report, in other words I am to be considered the world best security researcher.

0 users think it is non-scientific; after 15 it will be moderated.
Victor Porton

By Victor Porton

I am the chief editor of this journal and creator of this site.