New Foundations is consistent

4.1 Base approximations

Definition 4.1 base approximation
#

A base approximation is a pair \( \psi = (\psi ^{E{\mathcal A}}, \psi ^{\mathcal L}) \) such that \( \psi ^{E{\mathcal A}} \) and \( \psi ^{\mathcal L}\) are permutative relations of atoms and litters respectively (definition A.1), and for each litter \( L \), the set

\[ \operatorname {\mathsf{LS}}(L) \cap \operatorname {\mathsf{coim}}\psi ^{E{\mathcal A}} \]

is small. The relation \( \psi ^{E{\mathcal A}} \) is called the exceptional atom graph, and \( \psi ^{\mathcal L}\) is called the litter graph. We make the following definitions.

  • The inverse of a base approximation is \( \psi ^{-1} = ((\psi ^{E{\mathcal A}})^{-1}, (\psi ^{\mathcal L})^{-1}) \).

  • If \( \psi \) and \( \chi \) are base approximations where \( \operatorname {\mathsf{coim}}\psi ^{E{\mathcal A}} = \operatorname {\mathsf{coim}}\chi ^{E{\mathcal A}} \) and \( \operatorname {\mathsf{coim}}\psi ^{\mathcal L}= \operatorname {\mathsf{coim}}\chi ^{\mathcal L}\), then their composition \( \psi \circ \chi \) is the base approximation \( (\psi ^{E{\mathcal A}} \circ \chi ^{E{\mathcal A}}, \psi ^{\mathcal L}\circ \chi ^{\mathcal L}) \).

  • The \( \psi \)-sublitter of a litter \( L \), written \( L_\psi \), is the near-litter \( (L, \operatorname {\mathsf{LS}}(L) \setminus \operatorname {\mathsf{coim}}\psi ^{E{\mathcal A}}) \).

Definition 4.2 atom graph of an approximation
#

The typical atom graph of \( \psi \) is the relation \( \psi ^{T{\mathcal A}} \) given by the following constructor. If \( (L_1, L_2) \in \psi ^{\mathcal L}\), then

\[ (h_{(L_1)_\psi }(i), h_{(L_2)_\psi }(i)) \in \psi ^{T{\mathcal A}} \]

for some \( i : \kappa \), where for any near-litter \( N \), \( h_N \) is an equivalence \( \kappa \simeq N \) chosen in advance.

The atom graph of \( \psi \) is the relation \( \psi ^{\mathcal A}= \psi ^{E{\mathcal A}} \sqcup \psi ^{T{\mathcal A}} \): the join of the exceptional and typical atom graphs.

Proposition 4.3
#

\( (\psi ^{T{\mathcal A}})^{-1} = (\psi ^{-1})^{T{\mathcal A}} \) and hence \( (\psi ^{\mathcal A})^{-1} = (\psi ^{-1})^{\mathcal A}\).

Proof

This follows directly from the fact that \( L_\psi = L_{\psi ^{-1}} \) for any litter \( L \).

The graphs \( \psi ^{T{\mathcal A}} \) and \( \psi ^{\mathcal A}\) are permutative.

Proof

The typical atom graph is injective, because the equation \( h_{L_\psi }(i)^\circ = L \) can be used to establish the the parameters of the relevant \( h \) maps coincide. Furthermore, we can use the fact that \( \psi ^{\mathcal L}\) has equal image and coimage to produce images of any image element of this relation. We then appeal to symmetry using proposition 4.3 to conclude that \( \psi ^{T{\mathcal A}} \) is permutative.

The (co)image of \( \psi ^{T{\mathcal A}} \) is

\[ \bigcup _{L \in \operatorname {\mathsf{coim}}\psi ^{\mathcal L}} L_\psi = \bigcup _{L \in \operatorname {\mathsf{coim}}\psi ^{\mathcal L}} (\operatorname {\mathsf{LS}}(L) \setminus \operatorname {\mathsf{coim}}\psi ^{E{\mathcal A}}) \]

which is clearly disjoint from the coimage of \( \psi ^{E{\mathcal A}} \). 1 So \( \psi ^{\mathcal A}\) is permutative by one of the results of proposition A.2.

Proposition 4.5

If \( \psi , \chi \) have equal exceptional atom and litter coimages, then \( (\psi \circ \chi )^{T{\mathcal A}} = \psi ^{T{\mathcal A}} \circ \chi ^{T{\mathcal A}} \).

Proof

Suppose that \( (a_1, a_3) \in (\psi \circ \chi )^{T{\mathcal A}} \), so

\[ a_1 = h_{(L_1)_{\psi \circ \chi }}(i);\quad a_3 = h_{(L_3)_{\psi \circ \chi }}(i);\quad (L_1, L_3) \in (\psi \circ \chi )^{\mathcal L} \]

Since \( (\psi \circ \chi )^{\mathcal L}= \psi ^{\mathcal L}\circ \chi ^{\mathcal L}\), there is \( L_2 \) such that \( (L_1, L_2) \in \chi ^{\mathcal L}\) and \( (L_2, L_3) \in \psi ^{\mathcal L}\). Hence

\[ (h_{(L_1)_\chi }(i), h_{(L_2)_\chi }(i)) \in \chi ^{T{\mathcal A}};\quad (h_{(L_2)_\psi }(i), h_{(L_3)_\psi }(i)) \in \psi ^{T{\mathcal A}} \]

But \( L_{\psi \circ \chi } = L_\psi = L_\chi \), so we obtain

\[ (a_1, h_{(L_2)_\chi }(i)) \in \chi ^{T{\mathcal A}};\quad (h_{(L_2)_\chi }(i), a_3) \in \psi ^{T{\mathcal A}} \]

For the converse, suppose that \( (a_1, a_2) \in \chi ^{T{\mathcal A}} \) and \( (a_2, a_3) \in \psi ^{T{\mathcal A}} \). Then

\[ a_1 = h_{(L_1)_\chi }(i);\quad a_2 = h_{(L_2)_\chi }(i);\quad a_2 = h_{(L_2')_\psi }(j);\quad a_3 = h_{(L_3)_\psi }(j) \]

We obtain \( L_2 = L_2' \), and \( (L_2)_\chi = (L_2)_\psi \) so we also conclude \( i = j \). Since \( (L_1, L_2) \in \chi ^{\mathcal L}\) and \( (L_2, L_3) \in \psi ^{\mathcal L}\), we conclude \( (L_1, L_3) \in (\psi \circ \chi )^{\mathcal L}\), as required.

Definition 4.6 near-litter graph of an approximation
#

The near-litter graph of \( \psi \) is the relation \( \psi ^{\mathcal N}\) given by setting \( (N_1, N_2) \in \psi ^{\mathcal N}\) if and only if \( (N_1^\circ , N_2^\circ ) \in \psi ^{\mathcal L}\), \( N_1 \) and \( N_2 \) are subsets of \( \operatorname {\mathsf{coim}}\psi ^{\mathcal A}\), and the image of \( \psi ^{\mathcal A}\) on \( N_1 \) is \( N_2 \) (or equivalently, by proposition A.2, the coimage of \( \psi ^{\mathcal A}\) on \( N_2 \) is \( N_1 \)).

Proposition 4.7
#

Let \( s \) be a set of atoms near \( \operatorname {\mathsf{LS}}(L) \) for some litter \( L \). If \( (L, L') \in \psi ^{\mathcal L}\), then the image of \( \psi ^{\mathcal A}\) on \( s \) is near \( \operatorname {\mathsf{LS}}(L') \).

Proof

We calculate

\begin{align*} \operatorname {\mathsf{im}}\psi ^{\mathcal A}|_s & = \operatorname {\mathsf{im}}\psi ^{\mathcal A}|_{\operatorname {\mathsf{LS}}(L)} \mathrel {\triangle }\operatorname {\mathsf{im}}\psi ^{\mathcal A}|_{s \mathrel {\triangle }\operatorname {\mathsf{LS}}(L)} \\ & \mathrel {\overset {N}{\sim }}\operatorname {\mathsf{im}}\psi ^{\mathcal A}|_{\operatorname {\mathsf{LS}}(L)} \\ & = \operatorname {\mathsf{im}}\psi ^{\mathcal A}|_{\operatorname {\mathsf{LS}}(L) \setminus \operatorname {\mathsf{coim}}\psi ^{E{\mathcal A}}} \cup \operatorname {\mathsf{im}}\psi ^{\mathcal A}|_{\operatorname {\mathsf{LS}}(L) \cap \operatorname {\mathsf{coim}}\psi ^{E{\mathcal A}}} \\ & \mathrel {\overset {N}{\sim }}\operatorname {\mathsf{im}}\psi ^{\mathcal A}|_{\operatorname {\mathsf{LS}}(L) \setminus \operatorname {\mathsf{coim}}\psi ^{E{\mathcal A}}} \\ & = \operatorname {\mathsf{im}}\psi ^{T{\mathcal A}}|_{L_\psi } \\ & = L’_\psi \\ & \mathrel {\overset {N}{\sim }}\operatorname {\mathsf{LS}}(L’) \end{align*}

\( (\psi ^{-1})^{\mathcal N}= (\psi ^{\mathcal N})^{-1} \), and \( \psi ^{\mathcal N}\) is permutative.

Proof

The first part follows from proposition 4.3. To show \( \psi ^{\mathcal N}\) is permutative, it suffices to show that it is injective and that its image is contained in its coimage; then, by taking inverses, the converses will also hold. Suppose that \( (N_1, N_3), (N_2, N_3) \in \psi ^{\mathcal N}\). Then the coimage of \( \psi ^{\mathcal A}\) on \( N_3 \) is equal to both \( N_1 \) and \( N_2 \), so \( N_1 = N_2 \), giving injectivity.

Now suppose that \( (N_1, N_2) \in \psi ^{\mathcal N}\). As \( (N_1^\circ , N_2^\circ ) \in \psi ^{\mathcal L}\), we must have \( (N_2^\circ , L) \in \psi ^{\mathcal L}\) for some \( L \). By proposition 4.7, the image \( s \) of \( \psi ^{\mathcal A}\) on \( N_2 \) is near \( \operatorname {\mathsf{LS}}(L) \), so \( (L, s) \) is a near-litter, and \( (N_2, (L, s)) \in \psi ^{\mathcal N}\) as required.

Definition 4.9

Base approximations act on base supports in the following way. If \( S^{\mathcal A}= (i, f) \), then \( \psi (S)^{\mathcal A}= (i, f') \) where

\[ f' = \{ (j, a_2) \mid (j, a_1) \in f \wedge (a_1, a_2) \in \psi ^{\mathcal A}\} \]

The same definition is used for near-litters.

  1. This result should of course be its own lemma.