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?

  • 21
    $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.2012-09-21
  • 4
    $1\in\{1,2,3,4\}$ but $1\ne\{1,2,3,4\}$2012-09-21
  • 6
    $\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.2012-09-21
  • 4
    @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).2012-09-21
  • 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