# Is the statement $A \in A$ true or false?

In last week's discrete math homework, one question had us evaluate the truthness of several set notation statements, where $A$ was defined as an arbitrary set. One such statement was

$$A \in A$$

I selected true as my answer. The reasons include

1. The definition of $A \in B$ means that for all elements in $A$, there must be a one and only one corresponding match in $B$. Let $A= \{1, 2, 4, 7\}$ and $B= \{1, 2, 4, 7\}$. Therefore, $A \in B$ identical to $A \in A$, which is shorthand for $\{1, 2, 4, 7\} \in \{1, 2, 4, 7\}$

2. Set operations in most programming languages are implementations of set theory in computer code and return true if the code evaluates the equality of two sets referencing the same location. In Java, if we initialize a Set A and B to the values in #1,

• A.equals(B) and B.equals(A) will both return true
• A.retainAll(B) and B.retainAll(A) will both return false, as the calling operation will not modify the set.
• A.removeAll(B) and B.removeAll(A), if called singularly, will return true and will result in an empty set

In an email, the professor cited Wikipedia's Axiom of Regularity as a source for discussion on the issue, and it holds that $A\notin A$ due to the definition of disjoint.

However, Van Ormen Quine's New Foundations set theory allows for the existence of a universal set $V$ and that $V\in V$. Most of that math is beyond my comprehension, but the article cited seems to fit my arguments.

-
$A\in A$ means that $A$ is an element of $A$ and not what you write in 1. The truthfulness of the statement depends on your set theoretic axioms. If you assume regularity there are no sets that belong to themselves. – Apostolos Sep 21 '12 at 12:33
$1\in\{1,2,3,4\}$ but $1\ne\{1,2,3,4\}$ – E.O. Sep 21 '12 at 12:34
$\in \ne \subseteq$. Also, with regard to NF, $A \in A$ is not a stratified formula, and even if it were, it wouldn't hold for all sets. – Clive Newstead Sep 21 '12 at 13:08
@CliveN, tangentially: It is true that $A\in A$ is not stratified, but that does not mean that it is inherently meaningless in NF. It only means that NF forbids it to occur inside set builder brackets $\{x\mid \cdots \}$. (It is categorically meaningless in type theory, but exactly that restriction is what NF attempts to lift). – Henning Makholm Sep 21 '12 at 13:38
In the language of java, $A \in A$ is the equivalent of A.contains(A) and will typically return false. Some implementations may allow a java Set to contain itself, but in the standard axioms of mathematical set theory (either ZFC or just ZF) it cannot occur. – MartianInvader Sep 21 '12 at 21:06

It seems that you confused $A\in B$ ($A$ is an element of $B$) and $A\subset B$ ($A$ is a subset of $B$, that is, every element of $A$ is an element of $B$).

Edit: Example: $1\in \{1,2\}$, and $\{1\}\subset \{1,2\}$.

Every set is a subset of itself (this is what you argue in 1), but a set can never be an element of itself (at least in standard set theory, that is, Zermelo-Fraenkel set theory, where the axiom of regularity forbids this).

-
Well technically, proper subset. – Mechanical snail Sep 22 '12 at 3:48
@Mechanicalsnail: Some sources write $\subset$ and $\subsetneq$, instead of $\subseteq$ and $\subset$. – Cameron Buie Nov 24 '12 at 4:02

First let us get things in order.

The $\in$ symbol is for membership, whereas $\subseteq$ is for being a subset. Therefore $x\in A$ if $x$ is an element of $A$; whereas $B\subseteq A$ if every element of $B$ is also an element of $A$.

Reading your question again shows the discrepancy between the mathematical notation and the words explaining it. While $A\in A$ is not necessarily true, $A\subseteq A$ is always true.

Returning to the question whether or not it is true or false that $A$ is an element of itself is a vastly more complicated question because it cannot be discussed in a naive set theoretical setting. In the usual axiomatization of set theory, i.e. Zermelo-Fraenkel with Choice (ZFC), we include the axiom of regularity (known as axiom of foundation as well) which ensures that $A\notin A$ for any set.

However there are merits for using non-well founded set theory as well, in such set theory we do have that for some sets it is possible to have $A\in A$, but for example $\varnothing\notin\varnothing$ even in such settings. There have been uses for sets of the form $x=\{x\}$ in the past, however these uses often end up having reasonable equivalents in well-founded set theories (i.e. set theories which include the axiom of regularity).

So for most mathematicians the question is it true that $A\in A$ is always false, because working in ZFC (or an extension thereof) we never have this sort of situation.

Some people, however, do work in theories such as New Foundations which you have mentioned, and in such theories it is true for some sets that they are members of themselves, e.g. the universal set $V$ has this property that $V\in V$. However it is still true that $\varnothing\notin\varnothing$, so we cannot prove that every set is a member of itself. We cannot prove that every non-empty set is a member of itself since for $A=\{\varnothing\}$ we have that $A$ is non-empty (it has one element) but $A\notin A$ since the only element of $A$ is empty and $A$ is not empty.

-
Huh? A downvote? If only I knew why, this is actually a good answer by my standards. – Asaf Karagila Nov 24 '12 at 0:53
Hmmm... Maybe someone's level of mathematical maturity wasn't sufficient enough to handle discussions about axiomatic set theory. Anyway, your answer is a good one in my opinion, so I'm casting my vote for it. :) – Haskell Curry Nov 24 '12 at 7:30

False. Everything you wrote in 1. is plain wrong, and you should unlearn it. A is a set, a single element. the elements of B are 1,2,4 and 7, the set {1,2,4,7} is not equal to any element of B, its not even a number.

-

While your #1 has been thoroughly debunked, it might be worth noting that #2 is also fundamentally flawed. While some other languages may permit a set to be contained in itself (in which case it does not faithfully model set theory), the Java documentation explicitly says (highlighting added):

Note: Great care must be exercised if mutable objects are used as set elements. The behavior of a set is not specified if the value of an object is changed in a manner that affects equals comparisons while the object is an element in the set. A special case of this prohibition is that it is not permissible for a set to contain itself as an element.

In general, the choices made by computer scientists (who must deal with additional pragmatic considerations) are an extremely unreliable proxy for what is purely a mathematical question. For the vast majority of programming languages, $\pi$ is rational.

-
Does not model ZFC, you mean. There are certainly non-well-founded set theories which allow sets to be members of themselves, e.g. the Quine atom Q = {Q}. – Charles Sep 21 '12 at 19:45
It works in Python, but only if you subclass set. >>> class HashableSet(set): ... def __hash__(self): ... return hash(tuple(sorted(self))) ... >>> A = HashableSet() >>> A.add(A) >>> A HashableSet({HashableSet(...)}) – Dan Sep 22 '12 at 5:26
@Dan What does A in A return? Just adding a set to itself doesn't necessarily guarantee that the end result contains itself. There are serious issues with ensuring uniqueness which is why Java only tries to work on immutable objects. – Erick Wong Sep 22 '12 at 7:13
Also, in statically-typed languages, there's the issue that you can't put a Set<T> inside itself unless T is a superclass/interface of Set. – Dan Sep 23 '12 at 3:00
Although HashSet<T> implements the Set<T> interface in Java it still allows for a particular HashSet to contain itself. See this question on SO: goo.gl/vbHQp4 – Derek W Sep 2 '13 at 19:56

The axiom of foundation excludes $A\in A$. The reference you cite is a non-standard definition.

-

What if the question were "does x = 1"? If you're using a system that does not include 1, then it is certainly false. But even if you're in a system which has 1, that doesn't mean that x has to be equal to it.

Analogously, there are some forms of set theory where $A\in A$ is always false, and others in which it is only sometimes false. In either case you should not say that the statement is true, because it isn't known to be true.

In your example you look at A = {1,2,4,7}. For that example $A\in A$ is false, because A does not equal 1, 2, 4, or 7.

-