Discussion
Before we dive into the exercise, it is worth comparing the Axiom 3.6 of Specification and this new interesting Axiom 3.9 of Universal Specification.
Let's write them out:
Axiom 3.6 (Axiom of specification, or axiom of separation). Let $A$ be a set, and for each $x \in A$, let $P(x)$ be a property pertaining to $x$. Then there exists a set, called $\{x \in A : P(x)\}$, whose elements are precisely the elements $x$ in $A$ for which $P(x)$ is true. In other words, for any object $y$,
$$y \in \{x \in A:P(x)\} \iff (y \in A \land P(y))$$
Axiom 3.9 (Universal specification, or axiom of comprehension). (Dangerous!) Suppose for every object $x$ we have a property $P(x)$ pertaining to $x$. Then there exists a set $\{x : P(x)\}$ such that for every object $y$,
$$y \in \{x : P(x)\} \iff P(y)$$
The key differences are:
- Axiom 3.9 says any property over a set of objects can form a set.
- Axiom 3.6 says a set can be formed from an existing set.
Axiom 3.9 leads to Russell's paradox. This is because the assumption that any property $P()$ corresponds to a set is too general. If we chose a property $P(x): x \text{ is a set, and } x\notin x$, then we can form a set $\Omega$ of all sets that are not members of themselves. Asking if $\Omega$ is a member of itself leads to a contradiction. If it does, then $P(\Omega)$ is true, and which means $\Omega$ doesn't contain itself. If it doesn't, then by definition $P(\Omega)$ is true, which means $\Omega \in \Omega$, a contradiction.
The problem is allowing a set to contain itself.
Axion 3.6 does not lead to Russell's paradox because it takes an existing set, and uses $P()$ to create a subset. The basis, an existing set, and the process, subsetting, are sound, and so do not lead to a contradiction.
The textbook presents Axiom 3.10 as a resolution.
Axiom 3.10 (Regularity). If $A$ is a non-empty set, then there is at least one element $x$ of $A$ which is either not a set, or is disjoint from $A$.
This axiom essentially rules out any member of $A$ being $A$. That is, prevents a $A$ containing itself.
Exercise 3.2.1
Show that the universal specification axiom, Axiom 3.9, if assumed to be true, would imply Axioms 3.3, 3.4, 3.5, 3.6, and 3.7. (If we assume that all natural numbers are objects, we also obtain Axiom 3.8.) Thus, this axiom, if permitted, would simplify the foundations of set theory tremendously (and can be viewed as one basis for an intuitive model of set theory known as “naive set theory”). Unfortunately, as we have seen, Axiom 3.9 is “too good to be true”!
Axiom 3.9 Implies Axiom 3.3 (Empty Set)
If we choose a property $P(x)$ which is always false for any $x$,
$$\forall x (\neg P(x))$$
then no $x$ is a member of the set formed by this property. That set is the empty set.
Axiom 3.9 states this empty set exists, which is Axiom 3.3. $\square$
Axiom 3.9 Implies Axiom 3.4 (Singleton and Pair Sets)
If we choose a property $P(x)$ which is only true when $x=a$,
$$P(a)$$
then only $a$ can be a member of the set formed by this property. The set $\{a\}$ is a singleton. If $x\neq a$ then $P(x)$ is not true, and so $x$ is not in the set formed by the property, so only $a$ is a member.
Axiom 3.9 states this set exists, which is Axiom 3.4 for singletons. $\square$
Similarly for pair sets, we can choose a property $P(x)$ which is only true when $x=a$ or $x=b$,
$$P(a) \lor P(b)$$
then only $a$ and $b$ are members of the set formed by this property. The set $\{a,b\}$ is a pair set.
Axiom 3.9 states this set exists, which is Axiom 3.4 for pair sets. $\square$
Axiom 3.9 Implies Axiom 3.5 (Pairwise Union)
If we choose a property $P(x)$ which is true if $x$ is a member of a set $A$ or is a member of a set $B$,
$$P(x) \iff (x \in A) \lor (x \in B)$$
then the set formed by the property is the pairwise union of sets $A$ and $B$, that is $A \cap B$. This is by the definition of pairwise union, Axiom 3.5.
Axiom 3.9 states this set exists, which is Axiom 3.5. $\square$
Axiom 3.9 Implies Axiom 3.6 (Axiom of Specification)
If we choose a property $P(x)$ which is true when $x$ is a member of a set $A$ and also a property $Q(x)$ is true,
$$P(x) \iff (x \in A) \land Q(x)$$
then the set formed by $P(x)$ is the same as that formed by the Axiom 3.6 with property $Q(x)$ applied to $x\in A$.
Axiom 3.9 states this set exists, which is Axiom 3.6. $\square$
Axiom 3.9 Implies Axiom 3.7 (Replacement)
If we choose a property $P(x,y)$ which is true for at most one $y$, and where $x \in A$, then the set of $y$ formed by this property is the same set formed by the Axiom 3.7.
Axiom 3.9 states this set exists, which is Axiom 3.7. $\square$
No comments:
Post a Comment