# Cantor's diagonal argument without equality

Trevor Wilson posted an answer while I was preparing an edit to the question. I think Trevor would have given essentially the same answer to the modified question. But, to make things as clear as possible, I will leave the old version after the statement of the new one. (I will also change a few details to the old version.) (Thank you to Trevor for his answer.)

## New version of the question

Let $\mathcal T$ be the theory one gets by admitting only Axioms schema 3 (Axiom schema of specification) of Zermelo-Fraenkel set theory as described here --- and forbidding the (direct or indirect) use of the equal sign.

Is $\mathcal T$ consistent?

## Old version of the question

Here is one of the first exercises of Roger Godement's book Cours d'algèbre:

Let $A$ be a set, and let $\mathcal P(A)$ be the set of all subsets of $A$. Then the inclusion $\mathcal P(A)\subset A$ does not hold.

Of course, this follows immediately from Cantor's diagonal argument. But what I find striking is that, in this form, the diagonal argument does not involve the notion of equality. This prompts the question:

(A) Are there other interesting examples of mathematical reasonings which don't involve the notion of equality?

Take your favorite set theory and remove everything which involves, directly or indirectly, the equal sign. Let $\mathcal T$ be the resulting theory. Then one can ask:

(B) Is $\mathcal T$ complete? Is $\mathcal T$ consistent?

Here is one way to make Question (B) precise. Take Bourbaki's set theory, and drop:

• the equal sign,

• Axiom Schemata S6 and S7,

• Axioms A1, A2, A3 and A4.

For the sake of completeness, let's spell out Cantor's diagonal argument (in the present setting): Assume by contradiction
$$X\subset A\quad\implies\quad X\in A,$$ let $B$ be a set such that $$X\in B\quad\iff\quad X\in A\text{ and }X\notin X,$$ and observe $$B\in B\quad\iff\quad B\notin B.$$ [We could not have said "let $B$ be the set such that ...", because this would have involved an implicit use of the notion of equality --- more precisely: of Axiom 1 of extensionality.]

• Assuming that ZFC is consistent, any of its sub-theories (such as the one you ask about in the new question, $\mathcal{T}$) must also be consistent. Are you wondering whether $\mathcal{T}$ has strictly lower consistency strength than ZFC, i.e. whether ZFC proves $\mathcal{T}$ to be consistent? Commented Mar 18, 2013 at 1:29
• Dear Trevor: I also agree with your first sentence. I'm not wondering whether ZFC proves $\mathcal T$ to be consistent. Do you agree that the consistency of $\mathcal T$ can be translated into a combinatorial statement (in term of free monoids)? If you do, then you can ask whether this statement can be proved (like any statement about monoids). Commented Mar 18, 2013 at 1:56
• I'm afraid I don't know anything about the theory of monoids. But notice that $\{\emptyset\}$ is a model of your theory $\mathcal{T}$. Commented Mar 18, 2013 at 2:05
• ...and $\emptyset$ would also be a model if our logic allowed empty models. Commented Mar 18, 2013 at 2:06
• Yes, this time I am sure. You can write down a complete description of the structure, say, $V_3$, and check that it satisfies the axiom schema of specification. No (non-naive) set theory is involved, just finitary reasoning. Commented Mar 18, 2013 at 5:46

If we consider ZFC as a theory in first-order logic without equality (that is, we remove the non-logical axioms mentioning equality) then the Axiom of Extensionality, which says that two sets are equal if and only if they have the same elements, can be considered as a definition of equality. Then we can rewrite every axiom and every theorem to avoid mentioning equality by replacing every occurrence of "$x = y$" in the logical and non-logical axioms with "$\forall z\,(z \in x \iff z \in y)$" (replacing $x$, $y$, and $z$ with appropriate variable names.) The resulting theory is essentially the same as ZFC. In particular, they are not complete, and seem so far to be consistent.
• You are correct that an inconsistent theory is complete (at least my definition says it is also.) So I should have said that if it is consistent, then it is incomplete. (Sometimes I tacitly assume that ZFC, inaccessible cardinals, etc. are consistent.) For your second question, note that without equality we cannot define objects at all, only predicates. We cannot prove that any predicate defines a unique object, because there is no longer any notion of uniqueness. So all we can do is define a "zero-ness" predicate $\varphi(x)$ that says $\neg \exists y\,(y\in x)$. Commented Mar 18, 2013 at 1:23
• Dear Trevor: I'm happy to see that we agree on the first point. I dropped the completeness aspect in the new version. It was a bad idea of mine to talk about completeness. I also agree with the phrase: "without equality we cannot define objects at all". That's precisely my point! Do you agree that, without equality, we can still prove $\mathcal P(A)\not\subset A$? Commented Mar 18, 2013 at 1:43
• Yes, we can still prove anything we could prove before, provided that we first rewrite it by substituting "$\forall z\, (z \in x \iff z \in y)$" for "$x=y$". We just can't define objects in the same way, because there is no way to tell whether a definition picks out a unique object (whatever that would mean.) Commented Mar 18, 2013 at 1:50
• How do you state and prove $0=0$ (or $0\not=1$) in $\mathcal T$? Commented Mar 18, 2013 at 1:59