Set-builder notation

In set theory and its applications to logic, mathematics, and computer science, set-builder notation (sometimes simply "set notation") is a mathematical notation for describing a set by stating the properties that its members must satisfy. Forming sets in this manner is also known as set comprehension, set abstraction or as defining a set's intension.

Building sets

Let Φ("x") be a schematic formula in which "x" appears free. Set builder notation has the form {"x" : Φ("x")} (some write {"x" | Φ("x")}, using the vertical bar instead of the colon), denoting the set of all individuals in the universe of discourse satisfying the predicate Φ("x"), that is, the set whose members are every individual "x" such that Φ("x") is true: formally, the extension of the predicate. Set builder notation binds the variable "x" and must be used with the same care applied to variables bound by quantifiers.

Examples (the universe of discourse can be taken to be, for example, all complex numbers):
* {x : x = x^2 } ,! is the set {0, 1},
* {x : x in mathbb{R} and x > 0} is the set of all positive real numbers. This, like all sets involving real numbers, is an example of a set that cannot be given by enumeration.
* {k : n in mathbb{N} and k = 2n} is the set of all even natural numbers,
* {a : exists p, q in mathbb{Z} (q ot = 0 land aq=p) } is the set of rational numbers, or numbers that can be written as the ratio of two integers.
* mathbb{N}_m = {x in mathbb{Z} : x ge m } = { m, m + 1, m + 2, ...}. Thus, e.g., x_1 = m, x_2 = m + 1, etc. (n.b.: in the case of sets, the order is not important, so that one could call x_1 = m + 2 and so forth). As an example, mathbb{N}_3 = {x in mathbb{Z} : x ge 3 } = { 3, 4, 5, ...}. This shows how convenient set-builder notation is.

The and sign stands for "and", requiring both conditions be fulfilled simultaneously. It is often replaced by a comma (,) semicolon (;) or written out as "and". Alternatively, sets of the form { x : x in X and phi(x) } can be written as { x in X : phi(x) }. The set of positive real numbers would then be notated { x in mathbb{R} : x > 0 } .

Logical equivalence

An important fact is the logical equivalence:

Big [ { x in U : P(x) } = { x in U : Q(x) } Big] equiv Big [ ( forall x in U ) ig [ P(x) Leftrightarrow Q(x) ig] Big] .

This means that sets two sets are equal if and only if their "membership requirements" are logically equivalent.

For example, { x in mathbb{R} : x^2 = 1 } = { x in mathbb{R} : |x| = 1 } because, for any real number "x", "x"2 = 1 if and only if |"x"| = 1.

Russell's paradox

Let {"S" : "S" is a set and "S" does not belong to "S"} denote the set of all sets that do not belong to themselves. This set cannot exist; Russell's paradox explains why.

Solutions to the paradox restrict set-builder notation in certain ways. Let "X" = {"x" ∈ "A" : "P"("x")} denote the set of every element of "A" satisfying the predicate "P"("x"). The canonical restriction on set builder notation asserts that "X" is a set only if "A" is already known to be a set. This restriction is codified in the axiom schema of separation present in standard axiomatic set theory. Note that this axiom schema excludes {"S" : "S" is a set and "S" does not belong to "S"} from sethood.

Other problems

The notation can be complicated, especially as in the previous example, and abbreviations are often employed when context indicates the nature of a variable. For example:
* {"x" : "x" > 0}, in a context where the variable "x" is used only for real numbers, indicates the set of all positive real numbers;
* {"p"/"q" : "q" is not zero}, in a context where the variables "p" and "q" are used only for integers, indicates the set of all rational numbers; and
* {"S" : "S" does not belong to "S"}, in a context where the variable "S" is used only for sets, indicates the set of all sets that don't belong to themselves.As the last example shows, such an abbreviated notation again might not denote an actual nonparadoxical set, unless there is in fact a set of all objects that might be described by the variable in question.

Variations

Defining sets in terms of other sets

Another variation on set-builder notation describes the members of the set in terms of members of some other set.Specifically, {"F"("x") : "x" in "A"}, where "F" is a function symbol and "A" is a previously defined set, indicates the set of all values of members of "A" under "F".For example:
* {2"n" : "n" in N}, where N is the set of all natural numbers, is the set of all even natural numbers.In axiomatic set theory, this set is guaranteed to exist by the axiom schema of replacement.

These notations can be combined in the form {"F"("x") : "x" in "A", "P"("x")}, which indicates the set of all values under "F" of those members of "A" that satisfy "P".For example:
* {"p"/"q" : "p" in Z, "q" in Z, "q" is not zero}, where Z is the set of all integers, is the set of all rational numbers (Q).This example also shows how multiple variables can be used (both "p" and "q" in this case). This notation is acceptable even though e.g. 2/3 and 4/6 are both included in this definition, and a set can not contain multiple copies of an element; the case "p"=4, "q"=6 says with harmless redundancy that 2/3 is in the set.

Parallels in programming languages

Set-builder notation is closely related to a construct in some programming languages, most notably Python and Haskell, called list comprehension.

In Python, list comprehensions are denoted by square brackets, and have a different syntax to set-builder, but are fundamentally the same. Consider these examples, given in both set-builder notation and Python list comprehension.
* Set-builder:
** {"l": "l" ∈ "L"}
** "k", "x"}: "k" ∈ "K" ⋀ "x" ∈ "X" ⋀ "P(x)" }
*List comprehension:
** Python:
*** [l for l in L]
*** [(k, x) for k in K for x in X if P(x)]
** Haskell
*** (Haskell does not allow uppercase names so ks = K, xs = X and p = P)
*** [l | l <- L]
*** [(k,x) | k <- ks, x <- xs, p(x)]

Note that in Python [l for l in L] equals to just list(L).

While Python's list comprehension works similarly to set-builder notation, it does not denote a set but rather creates a mathematical tuple (as opposed to Python's native tuple datatype; the actual returned value's type is list) based on existing tuples. It is possible to use true sets in Python with the set keyword and set class, but this causes additional deviations from set-builder notation:
* set(l for l in L)
* set((k, x) for k in K for x in X if P(x))The first can be written just as:
* set(L).

Note that the upcoming Python 3.0 supports proper set comprehensions using a hybrid of mathematical set-builder and Python list comprehension notation: [ [http://docs.python.org/dev/3.0/reference/expressions.html#set-displays Set displays - Python 3.0 Language Reference] ]
* {(k, x) for k in K for x in X if P(x)}

References

ee also

*Set notation
*SQL - Structured Query Language, used to implement set operations upon a relational database


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • set-builder notation — noun a mathematical notation for describing a set by stating the properties that its members must satisfy …   Wiktionary

  • Set notation — Sets are fundamental objects in mathematics. Intuitively, a set is merely a collection of elements or members . There are various conventions for textually denoting sets. In any particular situation, an author typically chooses from among these… …   Wikipedia

  • Set (mathematics) — This article gives an introduction to what mathematicians call intuitive or naive set theory; for a more detailed account see Naive set theory. For a rigorous modern axiomatic treatment of sets, see Set theory. The intersection of two sets is… …   Wikipedia

  • Notation — The term notation can refer to: Contents 1 Written communication 1.1 Biology and Medicine 1.2 Chemistry 1.3 Dance and movement …   Wikipedia

  • Naive set theory — This article is about the mathematical topic. For the book of the same name, see Naive Set Theory (book). Naive set theory is one of several theories of sets used in the discussion of the foundations of mathematics.[1] The informal content of… …   Wikipedia

  • Implementation of mathematics in set theory — This article examines the implementation of mathematical concepts in set theory. The implementation of a number of basic mathematical concepts is carried out in parallel in ZFC (the dominant set theory) and in NFU, the version of Quine s New… …   Wikipedia

  • Intersection (set theory) — Intersections of the Greek, Latin and Russian alphabet (upper case graphemes) (The intersection of Greek and Latin letters is used for the Greek licence plates.) …   Wikipedia

  • List comprehension — A list comprehension is a syntactic construct available in some programming languages for creating a list based on existing lists. It follows the form of the mathematical set builder notation (set comprehension) as distinct from the use of map… …   Wikipedia

  • Natural number — Natural numbers can be used for counting (one apple, two apples, three apples, ...) from top to bottom. In mathematics, the natural numbers are the ordinary whole numbers used for counting ( there are 6 coins on the table ) and ordering ( this is …   Wikipedia

  • Interval (mathematics) — This article is about intervals of real numbers. For intervals in general mathematics, see Partially ordered set. For other uses, see Interval. In mathematics, a (real) interval is a set of real numbers with the property that any number that lies …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”