12
$\begingroup$

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.

What is the correct answer?

  • 0
    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.2012-09-21

6 Answers 6

37

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).

  • 5
    @Mechanicalsnail: Some sources write $\subset$ and $\subsetneq$, instead of $\subseteq$ and $\subset$.2012-11-24
33

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.

  • 0
    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. :)2012-11-24
20

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.

7

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.

  • 1
    Although `HashSet` implements the `Set` interface in `Java` it still allows for a particular HashSet to contain itself. See this question on SO: http://goo.gl/vbHQp42013-09-02
5

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

3

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.