Set-builder notation: Difference between revisions

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Set-builder notation" – news · newspapers · books · scholar · JSTOR (July 2011) (Learn how and when to remove this message)

In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by stating the properties that its members must satisfy.^[1] Forming sets in this manner is also known as set comprehension, set abstraction or as defining a set's intension. Although some simply refer to it as set notation, that label may be better reserved for the broader class of means of denoting sets.

Let Φ(x) be a formula in which the variable x appears free. Set builder notation has the form {x : Φ(x)} (or {x | Φ(x)} according to the international standard ISO 31-11 using the vertical bar instead of the colon), denoting the set of all individuals in the universe of discourse satisfying the formula Φ(x), that is, the set whose members are every individual x such that Φ(x) is true: formally, the extension of the predicate. Φ(x) is here referred to as the rule. Sometimes the universe of discourse is established within the notation; writing ${\displaystyle \{x|x\in \mathrm {U} \land \Phi (x)\}}$ (or sometimes ${\displaystyle \{x\in \mathrm {U} :\Phi (x)\}}$, though this is done at the expense of making the set membership operator ambiguous in the formal set builder notation, as explained with some additional examples at the end of the section) establishes that the universe of discourse is ${\displaystyle \mathrm {U} }$ for purposes of the set being built. Set builder notation binds the variable x and must be used with the same care applied to variables bound by quantifiers. Unless specifically stated the variable is universally quantified over the rule, which means we include in the set all possible values for the variable for which the rule is true.

Examples:

• ${\displaystyle \{3,7,15,31\}}$ is a set holding the four numbers 3, 7, 15, and 31.
• ${\displaystyle \{0,1,2,\ldots \}}$ is the set of natural numbers.
• ${\displaystyle \{1,2,3,\ldots 100\}}$ is the set of integers between 1 and 100 inclusive.
• ${\displaystyle \{a,b,c\}}$ is the set containing 'a','b', and 'c'.
• ${\displaystyle \{x~|~x\in \mathbf {R} \land x=x^{2}\}\,\!}$ is the set ${\displaystyle \{0,1\}}$,
• ${\displaystyle \{x~|~x\in \mathbf {R} \land x>0\}}$ is the set of all positive real numbers.
• ${\displaystyle \{(x,y)~|~0<y<f(x)\}}$ is the set of (x,y) such that y is greater than 0 and less than f(x).
• ${\displaystyle \{k~|~(\exists n\in \mathbf {N} )\land (k=2n)\}}$ is the set of all even natural numbers,
• ${\displaystyle \{a~|~(\exists p,q\in \mathbf {Z} )\land (q\not =0\land aq=p)\}}$ is the set of rational numbers; that is, numbers that can be written as the ratio of two integers.
• ${\displaystyle \mathbf {N} _{m}=\{x~|~x\in \mathbf {Z} \land x\geq m\}=\{m,m+1,m+2,\ldots \}.}$ Thus, e.g., ${\displaystyle x_{1}=m,\ x_{2}=m+1}$, etc. (n.b.: in the case of sets, the order is not important; ${\displaystyle x_{1}=m+2}$ could be used). As an example, ${\displaystyle \mathbf {N} _{3}=\{x~|~x\in \mathbf {Z} \land x\geq 3\}=\{3,4,5,\ldots \}.}$

The ellipses means that the simplest interpretation should be applied for continuing the sequence. Should no terminating value appear to the right of the ellipses then the sequence is considered to be unbounded.

The ${\displaystyle ~|~}$ is read as "such that", and it separates the variables list on the left from the rule for assigning values to those variables on the right. Oftentimes the rule on the right is a formal logic predicate. However it can be anything that is clear to readers including simple prose. When the meaning is clear the ${\displaystyle ~|~}$ and the rule may be omitted.

When the rule is a predicate then formal logic connectors may be used within the rule. For example, the ${\displaystyle \land }$ sign stands for and, requiring both clauses to the left of it and to the right of it to be 'true'. As another example, The ${\displaystyle \exists }$ sign stands for "there exists" and is formally known as existential quantification. Sometimes multiple rules are given separated by a comma (,) or semicolon (;), in this case we take the rules in conjunction, i.e. we interpret the comma or semicolon to mean the same as ${\displaystyle \land }$.

The ${\displaystyle \in }$ sign denotes set membership, and can be read as "member of" or informally as "in". In a predicate a clause of the form ${\displaystyle x\in \{1,2,3\}}$ is either true or false, or when used as a constraint means that ${\displaystyle x}$ can only be one of the values 1, 2, or 3.

When the domain over which the set is defined is already clear it is not necessary to provide it within the rule clause. One could say something such as, "The universe of discourse can be taken to be the set of real numbers, where not specified inside the notation:" and then write:

• ${\displaystyle \{x~|~x=x^{2}\}\,\!}$ is the set ${\displaystyle \{0,1\}}$

Rather than the fuller form as shown in the original example given above.

One can also use an expression in the variable list. For example:

• ${\displaystyle \{2t+1~|~t\in \mathbf {Z} \}}$ is the set of odd integers.
• ${\displaystyle \{(t,2t+1)~|~t\in \mathbf {Z} \}}$ creates a set of pairs, where each pair puts an integer into correspondence with an odd integer.
• ${\displaystyle \{2x+1=5~|~x\in \mathbf {N} \}}$ is the set ${\displaystyle \{true,false\}}$ because the expression ${\displaystyle 2x+1=5}$ evaluates to either true or false given the various natural numbers.

It is known in the literature to just place the domain qualifiers directly in the variable list. For the prior example this would produce:

• ${\displaystyle \{x\in \mathbf {R} ~|~x=x^{2}\}\,\!}$ is the set ${\displaystyle \{0,1\}}$,

Technically this would generate the set ${\displaystyle \{true,false\}}$ as the expression to the left of the 'such that' evaluates to either true or false, but at the expense of introducing ambiguity into our set builder notation we may instead decide to interpret this to mean that x has an additional qualification of being a real number. As another example, consider:

• ${\displaystyle \{x\in \mathbf {Z} ~|~x\in \mathbf {N} \land x<1\}}$

If we interpret ${\displaystyle x\in \mathbf {Z} }$ to be a domain qualifier, then this is the set ${\displaystyle \{0\}}$; however, if we interpret ${\displaystyle x\in \mathbf {Z} }$ to be an expression then this set is ${\displaystyle \{true\}}$. Such ambiguities can be resolved by convention, for example by foregoing the ability to put the set inclusion operator in variable expressions. Another convention for eliminating such ambiguity, one that does not require us to reduce the richness of expressions, is to simply not use domain qualifiers in the variable list, but instead to put them with the rule predicates. For example, the expression

• ${\displaystyle \{x~|~x\in \mathbf {Z} \land x\in \mathbf {N} \land x<1\},}$

denotes the first interpretation of the set given above, and can't be read in the second way.

When we do proofs that reason about the predicate rules, such as shown in the next section, the shortcut of leaving domain qualifiers with the variables is not an option, rather we must rigorously put domain qualifiers into the predicate rules we are operating on. Otherwise we may get fallacious results.

Suppose we have two predicates we intend to use as rules for building sets, say these two predicates are ${\displaystyle P(x)}$ and ${\displaystyle Q(x)}$. Suppose we have not added additional qualifiers or expressions to the variable list (left of the 'such that'). Now furthermore assume that any value x comes from a domain defined by set ${\displaystyle U}$, i.e. ${\displaystyle x\in U}$. Now suppose also that we build two sets from these predicates:

${\displaystyle T=\{t~|~t\in U\land P(t)\}}$

and,

${\displaystyle S=\{s~|~s\in U\land Q(s)\}}$

As we already said that the domain is ${\displaystyle U}$ we could have left out the ${\displaystyle t\in U}$ and ${\displaystyle s\in U}$. Indeed, we leave out the understood ${\displaystyle x\in U}$ qualifier in the next statement. Note also we can give the variable used for building the set any name, as we have overused ${\displaystyle x}$ here we built the sets against ${\displaystyle t}$ and ${\displaystyle s}$. Now we have an interesting result from the field of mathematical logic:

${\displaystyle [T=S]~\Leftrightarrow ~\forall x:[P(x)~\Leftrightarrow ~Q(x)]}$

Here we use the square brackets for purposes of grouping. This says that if the two predicates always have the same true or false value given the same argument over the domain ${\displaystyle U}$, then the two sets T and S will be the same. Also, conversely, if the two sets T and S are identical, i.e. have the same elements,then our two predicates always produce the same logic value for the same argument over the domain U. The use of the colon here after the universal quantifier simply means the quantifier applies to what follows. Note this result is very general as it applies to any such sets and predicates over any given domain U.

The former author of this wiki section chose to state the equivalence between sets with equivalent predicates theorem in the following manner, note he uses the somewhat ambiguous shorthand of putting some simple qualifiers with the variables, and he prefers to use a ':' rather than a vertical bar for 'such that'. This usage of the colon is not to be confused with the use of the colon above after the universal quantifier that means 'apply to'. It is to avoid such confusion that many mathematicians prefer the vertical bar for 'such that':

${\displaystyle {\Big [}\{x\in U:P(x)\}=\{x\in U:Q(x)\}{\Big ]}\equiv {\Big [}(\forall x\in U){\big [}P(x)\Leftrightarrow Q(x){\big ]}{\Big ]}}$.

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

For example, ${\displaystyle \{x\in \mathbf {R} :x^{2}=1\}=\{x\in \mathbf {R} :|x|=1\}}$ because, for any real number x, x² = 1 if and only if |x| = 1; and, therefore, both constructions produce the same set {-1,1}.

Let ${\displaystyle R=\{S~|~S\notin S\}}$ denote the set R of all sets S that do not belong to themselves. The inconsistency of the existence of this set is known as Russell's paradox.

Solutions to the paradox restrict the notion of set construction in some way. To illustrate this in terms of our notation, 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 R from sethood.

Another variation on set-builder notation replaces the single variable x with a term T which may include one or more variables, combined with functions acting on them. So instead of {x : Φ(x)}, we would have {T : Φ(x₁ ... x_n)}, where T is a term involving variables x₁ through x_n. For example:

• {2n : n ∈ N}, where N is the set of all natural numbers, is the set of all even natural numbers.
• {p/q : p,q ∈ Z, q≠0}, where Z is the set of all integers, is the set of all rational numbers (Q).

In Z notation, the set of all x (in a universe of discourse A) satisfying the condition P(x) would be written ${\displaystyle \{x:A\ |\ P(x)\}}$. In Z, an element x's set membership is written as ${\displaystyle (x:A)}$ instead of ${\displaystyle (x\in A)}$; the vertical bar is used to indicate a predicate. Versions of set builder notation are also available in Z which allow for terms more complicated than a single variable, using a bullet to indicate the form of members of the set. So ${\displaystyle \{x:A\ |\ P(x)\bullet F(x)\}}$ denotes the set of all values F(x), where x is in A and P(x) holds.

A similar notation available in a number of programming languages (notably Python and Haskell) is the list comprehension, which combines map and filter operations over one or more lists.

In Python, the set-builder's braces are replaced with square brackets, parentheses, or curly braces, giving list, generator, and set objects, respectively. Python uses an English based syntax. Haskell replaces the set-builder's braces with square brackets and uses symbols, including the standard set-builder vertical bar. Consider these examples given in set-builder notation, Python, and Haskell:

	Example 1	Example 2
Set-builder	${\displaystyle \{l\ |\ l\in L\}}$	${\displaystyle \{(k,x)\ |\ k\in K\wedge x\in X\wedge P(x)\}}$
Python	{l for l in L}	{(k, x) for k in K for x in X if P(x)}
Haskell	[l | l <- ls]	[(k, x) | k <- ks, x <- xs, p x]

The set builder notation and list comprehension notation are both instances of a more general notation known as monad comprehensions, which permits map/filter-like operations over any monad with a zero element.^[2] oippo