Naive Set Theory - Specifying Sets

Specifying Sets

The simplest way to describe a set is to list its elements between curly braces (known as defining a set extensionally). Thus {1,2} denotes the set whose only elements are 1 and 2. (See axiom of pairing.) Note the following points:

• Order of elements is immaterial; for example, {1,2} = {2,1}.
• Repetition (multiplicity) of elements is irrelevant; for example, {1,2,2} = {1,1,1,2} = {1,2}.

(These are consequences of the definition of equality in the previous section.)

This notation can be informally abused by saying something like {dogs} to indicate the set of all dogs, but this example would usually be read by mathematicians as "the set containing the single element dogs".

An extreme (but correct) example of this notation is {}, which denotes the empty set.

We can also use the notation {x : P(x)}, or sometimes {x | P(x)}, to denote the set containing all objects for which the condition P holds (known as defining a set intensionally). For example, {x : x is a real number} denotes the set of real numbers, {x : x has blonde hair} denotes the set of everything with blonde hair, and {x : x is a dog} denotes the set of all dogs.

This notation is called set-builder notation (or "set comprehension", particularly in the context of Functional programming). Some variants of set builder notation are:

• {x ∈ A : P(x)} denotes the set of all x that are already members of A such that the condition P holds for x. For example, if Z is the set of integers, then {x ∈ Z : x is even} is the set of all even integers. (See axiom of specification.)
• {F(x) : x ∈ A} denotes the set of all objects obtained by putting members of the set A into the formula F. For example, {2x : x ∈ Z} is again the set of all even integers. (See axiom of replacement.)
• {F(x) : P(x)} is the most general form of set builder notation. For example, {x's owner : x is a dog} is the set of all dog owners.