1. Collectivizing relations

1. The theory of sets

The theory of sets is a theory which contains the relational signs $=$, $\in$ and the substantific sign $\supset$ (all these signs being of weight 2); in addition to the schemes S1 to S7 given in Chapter I, it contains the scheme S8, which will be introduced in no. 6, and the explicit axioms A1 (no. 3.) A2 (no. 5), A3 (§ 2, no. 1), A4 (§ 5, no. 1), and A5 (Chapter III, § 6, no. 1), These explicit axioms contain no letters; in other words, the theory of sets is a theory without constants.

Since the theory of sets is an equalitarian theory, the results of Chapter I are applicable.

¶ From now on, unless the contrary is expressly stated, we shall always argue in a theory which is stronger (Chapter I, § 2, no. 4) than the theory of sets; if the theory is not mentioned, it is to be assumed that the theory of sets is implied. It will be evident in many cases that this hypothesis is superfluous, and the reader should have no difficulty in determining in what theory weaker than the theory of sets the results stated are valid.

If $T$ and $U$ are terms, the assembly $\in TU$ is a relation (called the relation of membership) which in practice we write in one of the following ways : $T \in U$, $(T) \in (U)$, "$T$ belongs to $U$", "$T$ is an element of $U$". The relation "not $(T \in U)$" is written $T \notin U$.

From a "naive" point of view, many mathematical entities can be considered as collections or "sets" of objects. We do not seek to formalize this notion, and in the formalistic interpretation of what follows, the word "set" is to be considered as strictly synonymous with "term". In particular, phrases such as "let X be a set" are, in principle, quite superfluous, since every letter is a term. Such phrases are introduced only to assist the intuitive interpretation of the text.

2. Inclusion

This follows immediately from CS9 (Chapter I, § 4, no. 1) and CS5 (Chapter I, § 1, no. 2).

CF13. If $T$ and $U$ are terms, $T \subset U$ is a relation.

This follows immediately from CF8 (Chapter I, § 1, no. 4).

¶ Every relation of the form $T \subset U$ (where $T$ and $U$ are terms) is called an inclusion relation.

From now on we shall no longer write down explicitly the criteria of substitution and the formative criteria which should follow the definitions. It should be noted, however, that these criteria will often be used implicitly in proofs.

To prove the relation $x \subset y$ in a theory $\mathscr{T}$, it is enough, by C27 (Chapter I, § 4, no. 1), to prove that $z \in y$ in the theory obtained by adjoining $z \in x$ to the axioms of $\mathscr{T}$, where $z$ is a letter distinct from $x$, $y$ and the constants of the theory. In pratice we say "let $z$ be an element of $x$", and we attempt to prove $z \in y$.

3. The axiom of extent

The axiom of extent is the following axiom :

A1. $\qquad (\forall x)(\forall y)((x \subset y \text{ and } y \subset x) \Rightarrow (x = y))$.

Intuitively, this axiom expresses the fact that two sets which have the same elements are equal.

To prove that $x = y$ it is therefore enough to prove $z \in y$ in the theory obtained by adjoining the hypothesis $z \in x$, and $z \in x$ in the theory obtained by adjoining the hypothesis $z \in y$, where $z$ is a letter distinct from $x$, $y$, and the constants.

C48. Let $\mathbf{R}$ be a relation, $x$ a letter, and $y$ a letter distinct from $x$ which does not appear in $\mathbf{R}$. Then the relation $(\forall x)((x \in y) \Leftrightarrow \mathbf{R})$ is single-valued in $y$.

Let $z$ be a letter distinct from $x$ which does not appear in $\mathbf{R}$. Adjoin the hypotheses

Then we have successively the theorems

By A1 we have then $y = z$. This proves C48.

4. Collectivizing relations

Let $\mathbf{R}$ be a relation and let $x$ be a letter. If $y$ and $y'$ denote letters distinct from $x$ which do not appear in $\mathbf{R}$, then the relations

are identical by CS8 (Chapter I, §4, no. 1). The relation thus defined (which does not contain $x$) is denoted by $\operatorname{Coll}_xR$.

¶ If $\operatorname{Coll}_xR$ is a theorem in a theory $\mathscr{T}$, $R$ is said to be collectivizing in $x$ in $\mathscr{T}$. When this is so, we may introduce an auxiliary constant $a$, distinct from $x$ and the constants of $\mathscr{T}$, and which does not appear in $R$, with the introductory axiom $(\forall x)((x \in a) \Longleftrightarrow R)$, or equivalently (if $x$ is not a constant of $\mathscr{T}$) $(x \in a) \Longleftrightarrow R$.

Intuitively, to say that $R$ is collectivizing in $x$ is to say that there exists a set $a$ such that the objects $x$ which possess the property $R$ are precisely the elements of $a$.

Examples

5. The axiom of the set of two elements

A2. $\qquad\qquad (\forall x)(\forall y)\ \mathrm{Coll}_z(z = x \text{ or } z = y).$

This axiom says that if $x$ and $y$ are objects, then there is a set whose only elements are $x$ and $y$.

The relation $z \in \{x, y\}$ is therefore equivalent to "$z = x$ or $z = y$"; it follows from C50 that $\{y, x\} = \{x, y\}$.

Let $R\{z\}$ be a relation and let $x, y$ be letters distinct from $z$. From the criteria C32, C33 (Chapter I, §4, no. 3), and C43 (Chapter I, §5, no. 1) it follows easily that the relation $(\exists z)((z \in \{x, y\})$ and $R\{z\})$ is equivalent to "$R\{x\}$ or $R\{y\}$"; consequently the relation $(\forall z)((z \in \{x, y\}) \Rightarrow R\{z\})$ is equivalent to "$R\{x\}$ and $R\{y\}$".

The set $\{x, x\}$, which is denoted simply by $\{x\}$, is called the set whose only element is $x$; the relation $z \in \{x\}$ is equivalent to $z = x$, and the relation $x \in \mathrm{X}$ is equivalent to $\{x\} \subset \mathrm{X}$.

6. The scheme of selection and union

The scheme of selection and union is the following :

S8. Let $R$ be a relation, let $x$ and $y$ be distinct letters, and let $X$ and $Y$ be letters distinct from $x$ and $y$ which do not appear in $R$. Then the relation

(1) $\quad (\forall y)(\exists X)(\forall x)(R \Rightarrow (x \in X)) \Rightarrow (\forall Y)\ \mathrm{Coll}_X((\exists y)((y \in Y) \text{ and } R))$ is an axiom.

Let us first show that this rule is indeed a scheme. Let $S$ denote the relation (1), and let us substitute a term $T$ for a letter $z$ in $S$; by CS8 (Chapter I, §4, no. 1) we may suppose that $x$, $y$, $X$, $Y$ are distinct from $z$ and do not appear in $T$. Then $(T|z)S$ is identical with

where $R'$ is $(T|z)R$.

Intuitively, the relation $(\forall y)(\exists X)(\forall x)(R \Rightarrow (x \in X))$ means that for every object $y$ there exists a set $X$ (which may depend on $y$) such that the objects $x$ which are in the relation $R$ with the given object $y$ are elements of $X$ (but not necessarily the whole of $X$). The scheme of selection and union asserts that if this is the case and if $Y$ is any set, then there exists a set whose elements are precisely the objects $x$ which are in the relation $R$ with at least one object $y$ of the set $Y$.

C51. Let $P$ be a relation, let $A$ be a set, and let $x$ be a letter which does not appear in $A$. Then the relation "$P$ and $x \in A$" is collectivizing in $x$.

Let $R$ denote the relation "$P$ and $x = y$", where $y$ is a letter distinct from $x$ which appears neither in $P$ nor in $A$. The relation

is true by C27 (Chapter I, §4, no. 1). Let $X$ be a letter distinct from $x$ and $y$ which does not appear in $P$. The preceding relation is identical with $(\{y\}|X)((\forall x)(R \Rightarrow (x \in X)))$ (because $x$ is distinct from $y$), and therefore the relation $(\forall y)(\exists X)(\forall x)(R \Rightarrow (x \in X))$ is true by virtue of S5 and C27 (Chapter I, §4, nos. 1 and 2). If follows from S8 and C30 (Chapter I, §4, no. 3) that the relation

(where $Y$ is a letter which does not appear in $R$) is true, and this relation is identical with $\mathrm{Coll}_x(\exists y)(y \in A \text{ and } R)$ (because neither $x$ nor $y$ appears in $A$). Finally, the relation "$y \in A$ and $R$" is equivalent to "$x = y$ and $x \in A$ and $P$" by C43 (Chapter I, §5, no. 1); since $x$ appears neither in $P$ nor in $A$, the relation

is equivalent to "$((\exists y)(x = y))$ and $x \in A$ and $P$" by C33 (Chapter I, §4, no. 3) and therefore to "$P$ and $x \in A$" because $(\exists y)(x = y)$ is true.

¶ The set $\mathscr{E}_x(P$ and $x \in A)$ is called the set of all $x \in A$ such that $P$ (\* thus we may speak of the set of all real numbers such that $P_*$).

C52. Let $R$ be a relation, $A$ a set, and $x$ a letter which does not appear in $A$. If the relation $R \Rightarrow (x \in A)$ is a theorem, then $R$ is collectivizing in $x$.

For $R$ is then equivalent to "$R$ and $x \in A$".

7. Complement of a set. The empty set

The relation $(x \notin \mathrm{A}$ and $x \in \mathrm{X})$ is collectivizing in $x$ by C51.

Let A be a subset of a set X; the relations "$x \in \mathrm{X}$ and $x \notin \mathrm{A}$" and $x \in \complement_{\mathrm{X}}\mathrm{A}$ are then equivalent. Consequently the relation "$x \in \mathrm{X}$ and $x \notin \complement_{\mathrm{X}}\mathrm{A}$" is equivalent to "$x \in \mathrm{X}$ and $(x \notin \mathrm{X}$ or $x \in \mathrm{A})$", hence to $x \in A$. In other words, $A = \complement_X(\complement_X A)$ is a true relation. Similarly, one shows that if B is a subset of X, the relations $A \subset B$ and $\complement_X B \subset \complement_X A$ are equivalent.

Exercises

See the exercises for § 1.

[^1]: The term denoted by $\emptyset$ is therefore $\tau \neg \neg \in \tau \neg \neg \in \square\square\square$.