Set-builder notation

From Free net encyclopedia

In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by indicating the properties that its members must satisfy. This is also known as set comprehension.

Contents 1 Building sets 2 Russell's paradox 2.1 Solutions 3 Other problems 4 Variations 4.1 Defining sets in terms of other sets 4.2 Parallels in programming languages

Building sets

The simplest sort of set-builder notation is {x : P(x)}, where P is a predicate in one variable. This indicates the set of everything satisfying the predicate P, that is, the set of every object x such that P(x) is true. Some authors use the pipe symbol | rather than : to indicate the conditional. For example:

• {x : x is a real number and x > 0} is the set of all positive real numbers;
• {k : for some natural number n, k = 2n} is the set of all even natural numbers;
• {a : for some integers p and q, q is not zero and a = p/q} is the set of rational numbers.

Russell's paradox

Consider the set {S : S is a set and S does not belong to S}. Simply put, this is the set of all sets that don't belong to themselves. This example shows how set-builder notation can be tricky. The set described here, in fact, cannot exist. See Russell's paradox for precisely why.

Solutions

For this reason, set-builder notation can be modified to certain special forms. One of these is {x in A : P(x)}, where A is a previously defined set. This indicates the set of every element of A that satisfies the predicate P. For example:

• {x in R : x > 0}, where R is the set of real numbers, is the set of all positive real numbers.

In axiomatic set theory, this set is guaranteed to exist by the axiom schema of separation. We avoid Russell's paradox here because there is no set of all sets (at least not in the usual development of axiomatic set theory).

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:

• {2n : 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

Template:Main 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 in L}
  • {{k, x}: k in K and x in X if P(x)
• List comprehension:
  • [l for l in L]
  • [(k, x) for k in K for x in X if P(x)]

Note: 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.bn:সেট গঠনকারী পদ্ধতি is:Mengjaskilgreiningarritháttur