1
$\begingroup$

Wikipedia defines the notion of a pure set as follows:

a hereditary set (or pure set) is a set whose elements are all hereditary sets.

Why does this definition make sense? It seems to be circular.

Also, wikipedia says:

The inductive definition of hereditary sets presupposes that set membership is well-founded (i.e., the axiom of regularity), otherwise the recurrence may not have a unique solution.

Why does the definition sometimes not have a unique solution? Is the problem the existence or the uniqueness? Can you give an example of a situation where the recursive definition from above does not have a unique solution in a setting where we don't assume regularity?

$\endgroup$
  • 1
    $\begingroup$ If there is a strange set with $A = \{A\}$, then is $A$ a pure set? To check whether it is, we need to check whether all its elements are pure sets... $\endgroup$ – GEdgar Nov 16 '16 at 16:06
  • 1
    $\begingroup$ It's as though you stopped reading after the first sentence the not-very-long page on Wikipedia. $\endgroup$ – Asaf Karagila Nov 16 '16 at 20:03
1
$\begingroup$

The axiom of regularity implies that there is no infinite descending sequence of sets. That is, the recursion in the definition has a finite limit and is thus well-defined.

Without that axiom, you are into the realm of non-well founded set theory where sets can be elements of themselves (which would form an infinite loop in the recursive definition of hereditary sets).

$\endgroup$
  • $\begingroup$ Wow! That is mind boggling. $\endgroup$ – TeeJ Lockwood Nov 16 '16 at 16:13
  • $\begingroup$ @Alexis: What I find hard to understand from the definition of "pure set" given by wikipedia, is that the recursion seems not to involve a sort of "ordering". So in the realm of natural numbers, we have a base case and a recursion step for the other cases, and in this, one can refer to instances of the definition previously (for smaller numbers) derived. Maybe it's more enlightening to think of the definition as 1. $\varnothing$ is pure. 2. A nonempty set X is pure iff all elements of X are pure. $\endgroup$ – user384011 Nov 16 '16 at 16:19
  • $\begingroup$ @rere The set inclusion ordering is the implicit ordering. Without well-foundedness, this ordering stops making sense and recursion no longer works as expected. I like your definition building from the ground up. It's easier to understand what the sets look like. $\endgroup$ – Alexis Olson Nov 16 '16 at 16:30
  • $\begingroup$ @AlexisOlson: In which sense is set inclusion the implicit ordering here? I meant with ordering this: If one wants to define by recursion a predicate P on a class C of objects, the recursive definition has the following form: P(b) is … where b is the base case, i.e. the least element of the considered ordering <. 2. For every x define P(x) is … where we use only objects < x in this definition. In what sense can the definition of "pure set" be written in such a form using the inclusion ordering? $\endgroup$ – user384011 Nov 16 '16 at 17:09
  • $\begingroup$ @rere: $0$ (the empty set) vacuously satisfies the definition, since it has no elements; there’s your base case, if you really feel a need to specify it explicitly. In a great many constructions by recursion and proofs by induction it is not necessary to specify an explicit base, because the recursion (induction, resp.) hypothesis is vacuously satisfied (true, resp.) at the initial step. $\endgroup$ – Brian M. Scott Nov 16 '16 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy