Cantor digraphs and abbreviations of formulas

Abstract

A digraph $D=⟨V,E⟩$ ($E\subset V\times V$) is Cantor if Cantor's theorem - for no set there is a surjection from it to its power set - holds in $D$, in the sense we explain. We construct a ZF formula $\ddot{I}†$ with length $494$ such that $D\models \ddot{I}†$ iff $D$ is Cantor. In order to obtain $\ddot{I}†$, which is a word over the alphabet $$\{x_1,x_2,\dots \}\cup \{\in ,=,\neg ,\to ,\leftrightarrow ,\wedge ,\vee ,\exists ,\forall ,(,)\},$$ we devise abbreviation schemes of ZF formulas. We introduce extensive and strongly extensive digraphs and show, by the standard argument, that they are Cantor. We construct a countable strongly extensive digraph with arbitrarily large finite in-degrees.

21 pages; restated in terms of digraphs