# 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? – Trevor Wilson Mar 18 '13 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). – Pierre-Yves Gaillard Mar 18 '13 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}$. – Trevor Wilson Mar 18 '13 at 2:05
...and $\emptyset$ would also be a model if our logic allowed empty models. – Trevor Wilson Mar 18 '13 at 2:06
The notion of monoid is not crucial here. The point is: Do you agree that the consistency of $\mathcal T$ can be translated into a combinatorial statement, or, if you prefer, into a standard mathematical statement? – Pierre-Yves Gaillard Mar 18 '13 at 2:15

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)$. – Trevor Wilson Mar 18 '13 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$? – Pierre-Yves Gaillard Mar 18 '13 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.) – Trevor Wilson Mar 18 '13 at 1:50
How do you state and prove $0=0$ (or $0\not=1$) in $\mathcal T$? – Pierre-Yves Gaillard Mar 18 '13 at 1:59