Editing Set-builder notation

{{short description|Use of braces for specifying sets}}
{{Use dmy dates|date=December 2020}}
{{Quote box
| quote = <math>\{n \mid \exists k\in \mathbb{Z}, n = 2k \} </math>
| source = The set of all [[even integer]]s, <br/> expressed in set-builder notation.
}}

In [[mathematics]] and more specifically in [[set theory]], '''set-builder notation''' is a [[mathematical notation|notation]] for specifying a [[Set (mathematics)|set]] by a property that characterizes its members.<ref>{{cite book | last=Rosen| first=Kenneth| year=2007 | title=Discrete Mathematics and its Applications | edition=6th | publisher=McGraw-Hill | location=New York, NY | isbn=978-0-07-288008-3| pages=111–112 |url=https://books.google.com/books?id=ZYZfQgAACAAJ&pg=PA111 }}</ref>

Specifying sets by member properties is allowed by the [[axiom schema of specification]]. This is also known as '''set comprehension''' and '''set abstraction'''.

== Sets defined by a predicate ==
Set-builder notation can be used to describe a set that is defined by a [[predicate (mathematical logic)|predicate]], that is, a logical formula that evaluates to ''true'' for an element of the set, and ''false'' otherwise.<ref>Michael J Cullinan, 2012, ''A Transition to Mathematics with Proofs'', Jones & Bartlett, pp.&nbsp;44ff.</ref> In this form, set-builder notation has three parts: a variable, a [[Colon (punctuation)|colon]] or [[vertical bar]] separator, and a predicate. Thus there is a variable on the left of the separator, and a rule on the right of it. These three parts are contained in curly brackets:
:<math>\{x \mid \Phi(x)\}</math>
or
:<math>\{x : \Phi(x)\}.</math>
The vertical bar (or colon) is a separator that can be read as "'''such that'''", <!--bold, because "such that" redirects here--> "for which", or "with the property that".  The formula {{math|&Phi;(''x'')}} is said to be the ''rule'' or the ''predicate''. All values of {{math|''x''}} for which the predicate holds (is true) belong to the set being defined. All values of {{math|''x''}} for which the predicate does not hold do not belong to the set.  Thus <math>\{x \mid \Phi(x)\}</math> is the set of all values of {{math|''x''}} that satisfy the formula {{math|&Phi;}}.<ref>{{Cite web|last=Weisstein|first=Eric W.|title=Set|url=https://mathworld.wolfram.com/Set.html|access-date=2020-08-20|website=mathworld.wolfram.com|language=en}}</ref> It may be the [[empty set]], if no value of {{math|''x''}} satisfies the formula.

=== Specifying the domain ===

A domain {{math|''E''}} can appear on the left of the vertical bar:<ref>{{Cite web|title=Set-Builder Notation|url=https://www.mathsisfun.com/sets/set-builder-notation.html|access-date=2020-08-20|website=mathsisfun.com}}</ref> 
:<math>\{x \in E  \mid  \Phi(x)\},</math> 
or by adjoining it to the predicate:
:<math>\{ x \mid x \in E \text{ and } \Phi(x)\}\quad\text{or}\quad\{ x \mid x \in E \land \Phi(x)\}.</math> 
The &isin; symbol here denotes [[set membership]], while the <math>\land</math> symbol denotes the logical "and" operator, known as [[logical conjunction]]. This notation represents the set of all values of {{math|''x''}} that belong to some given set {{math|''E''}} for which the predicate is true (see "[[#Set existence axiom|Set existence axiom]]" below). If <math>\Phi(x)</math> is a conjunction <math>\Phi_1(x)\land\Phi_2(x)</math>, then <math>\{x \in E  \mid  \Phi(x)\}</math> is sometimes written <math>\{x \in E  \mid  \Phi_1(x), \Phi_2(x)\}</math>, using a comma instead of the symbol <math>\land</math>.

In general, it is not a good idea to consider sets without defining a [[domain of discourse]], as this would represent the [[subset]] of ''all possible things that may exist'' for which the predicate is true. This can easily lead to contradictions and paradoxes. For example, [[Russell's paradox]] shows that the expression <math>\{x ~|~ x\not\in x\},</math> although seemingly well formed as a set builder expression, cannot define a set without producing a contradiction.<ref>{{cite encyclopedia | first1=Andrew David | last1=Irvine | first2=Harry | last2=Deutsch | orig-year=1995 | date=9 October 2016 | url=http://plato.stanford.edu/entries/russell-paradox/ | title=Russell's Paradox | encyclopedia=Stanford Encyclopedia of Philosophy | access-date=6 August 2017}}</ref>

In cases where the set {{math|''E''}} is clear from context, it may be not explicitly specified. It is common in the literature for an author to state the domain ahead of time, and then not specify it in the set-builder notation. For example, an author may say something such as, "Unless otherwise stated, variables are to be taken to be natural numbers," though in less formal contexts where the domain can be assumed, a written mention is often unnecessary.

=== Examples ===
The following examples illustrate particular sets defined by set-builder notation via predicates. In each case, the domain is specified on the left side of the vertical bar, while the rule is specified on the right side. 
* <math>\{ x \in \mathbb{R}   \mid  x > 0\}</math> is the set of all strictly [[positive number|positive]] [[real number]]s, which can be written in [[interval notation]] as <math>(0, \infty)</math>.
<!-- -->
* <math>\{ x \in \mathbb{R}  \mid |x| = 1 \}</math> is the set <math>\{-1, 1\}</math>. This set can also be defined as <math>\{x \in \mathbb{R} \mid x^2 = 1\}</math>; see [[#Equivalent predicates yield equal sets|equivalent predicates yield equal sets]] below.
* For each integer {{math|''m''}}, we can define <math>G_m = \{x  \in \mathbb{Z}  \mid  x \ge m \} = \{ m, m + 1, m + 2, \ldots\}</math>. As an example, <math>G_3 = \{x \in \mathbb{Z} \mid x \ge 3 \} = \{ 3, 4, 5, \ldots\}</math> and <math>G_{-2} = \{ -2, -1, 0, \ldots\}</math>.
<!-- -->
* <math>\{ (x,y) \in \mathbb{R} \times \mathbb{R} \mid 0 < y < f(x) \}</math>  is the set of pairs of real numbers such that ''y'' is greater than 0 and less than {{math|''f''(''x'')}}, for a given [[function (mathematics)|function]] {{math|''f''}}.   Here the [[cartesian product]] <math>\mathbb{R}\times\mathbb{R}</math> denotes the set of ordered pairs of real numbers. 
<!-- -->
* <math>\{n   \in \mathbb{N} \mid  (\exists k)  [k\in \mathbb{N}\land n = 2k]  \} </math> is the set of all [[even number|even]] [[natural number]]s. The <math>\land</math> sign stands for "and", which is known as [[logical conjunction]]. The &exist; sign stands for "there exists", which is known as [[existential quantification]]. So for example, <math> (\exists x) P(x)</math> is read as  "there exists an {{math|''x''}} such that {{math|''P''(''x'')}}".
<!-- -->
*  <math>\{n \mid  (\exists k \in \mathbb{N} )  [n = 2k]  \} </math> is a notational variant for the same set of even natural numbers. It is not necessary to specify that {{math|''n''}} is a natural number, as this is implied by the formula on the right.
<!-- -->
* <math>\{a \in \mathbb{R} \mid (\exists p\in \mathbb{Z} )(\exists q\in \mathbb{Z} )[ q \not = 0 \land aq=p] \}</math> is the set of [[rational number]]s; that is, real numbers that can be written as the ratio of two [[integer]]s.

== More complex expressions on the left side of the notation ==

An extension of set-builder notation replaces the single variable {{math|''x''}} with an [[expression (mathematics)|expression]]. So instead of  <math>\{ x \mid \Phi(x)\}</math>, we may have <math>\{ f(x) \mid \Phi(x)\},</math> which should be read
:<math>\{ f(x) \mid \Phi(x)\}=\{y\mid\exists x (y=f(x)\wedge\Phi(x))\}</math>.

For example:

* <math>\{2 n \mid n \in \mathbb N\}</math>, where <math>\mathbb N</math> is the set of all natural numbers, is the set of all even natural numbers.
* <math>\{p/q  \mid p,q \in \mathbb Z, q \not = 0 \}</math>, where <math>\mathbb Z</math> is the set of all integers, is <math>\mathbb{Q},</math> the set of all rational numbers.
* <math>\{ 2 t + 1 \mid  t \in  \mathbb Z\}</math> is the set of odd integers.
* <math>\{ (t, 2 t + 1) \mid  t \in \mathbb Z\}</math>  creates a set of pairs, where each pair puts an integer into correspondence with an odd integer.

When inverse functions can be explicitly stated, the expression on the left can be eliminated through simple substitution. Consider the example set <math>\{ 2 t + 1 \mid  t \in  \mathbb Z\}</math>. Make the substitution <math>u = 2t + 1</math>, which is to say <math> t = (u-1)/2</math>, then replace ''t'' in the set builder notation to find 
:<math>\{ 2 t + 1 \mid  t \in \mathbb Z\} = \{ u \mid  (u- 1)/2 \in  \mathbb Z\}.</math>

== Equivalent predicates yield equal sets ==

Two sets are equal if and only if they have the same elements. Sets defined by set builder notation are equal if and only if their set builder rules, including the domain specifiers, are equivalent. That is 
:<math> \{ x \in A \mid P(x) \}=\{ x \in B \mid Q(x) \} </math> 
if and only if 
:<math> (\forall t)[ (t \in A \land P(t)) \Leftrightarrow (t \in B \land Q(t))]</math>.
Therefore, in order to prove the equality of two sets defined by set builder notation, it suffices to prove the equivalence of their predicates, including the domain qualifiers.

For example,
:<math> \{ x \in \mathbb{R}\mid  x^2 = 1 \} = \{ x \in \mathbb{Q} \mid |x| = 1 \} </math>
because the two rule predicates are logically equivalent:
:<math> (x \in \mathbb{R} \land x^2 = 1) \Leftrightarrow (x \in \mathbb{Q} \land |x| = 1).</math>
This equivalence holds because, for any real number ''x'', we have <math>x^2 = 1</math> if and only if ''x'' is a rational number with <math>|x|=1</math>. In particular, both sets are equal to the set <math>\{-1,1\}</math>.

== Set existence axiom ==
In many formal set theories, such as [[Zermelo–Fraenkel set theory]], set builder notation is not part of the formal syntax of the theory. Instead, there is a [[axiom of comprehension|set existence axiom scheme]], which states that if {{math|''E''}} is a set and {{math|Φ(''x'')}} is a formula in the language of set theory, then there is a set {{math|''Y''}} whose members are exactly the elements of {{math|''E''}} that satisfy {{math|Φ}}:
:<math>(\forall E)(\exists Y)(\forall x)[x \in Y \Leftrightarrow x \in E \land \Phi(x)].</math>
The set {{math|''Y''}} obtained from this axiom is exactly the set described in set builder notation as <math>\{ x \in E \mid \Phi(x)\}</math>.

== In programming languages ==
{{main article|List comprehension}}

A similar notation available in a number of [[programming languages]] (notably [[Python (programming language)|Python]] and [[Haskell (programming language)|Haskell]]) is the [[list comprehension]], which combines [[map (higher-order function)|map]] and [[filter (higher-order function)|filter]] operations over one or more [[list (computing)|lists]].

{{section move from|List comprehension|date=December 2023|discuss=Talk:Set-builder notation#Move programming language details and comparison into List comprehension}}

In Python, the set-builder's braces are replaced with square brackets, parentheses, or curly braces, giving list, [[generator (computer science)|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.

The same can be achieved in [[Scala (programming language)|Scala]] using Sequence Comprehensions, where the "for" keyword returns a list of the yielded variables using the "yield" keyword.<ref>{{cite web | publisher=Scala | url=http://docs.scala-lang.org/tutorials/tour/sequence-comprehensions.html | title=Sequence Comprehensions | access-date=6 August 2017 }}</ref>

Consider these set-builder notation examples in some programming languages:
{| class="wikitable"
|-
! !! Example 1 !! Example 2
|-style="text-align:center;"
! Set-builder
| <math>\{l\ |\ l \in L\}</math> || <math>\{(k, x)\ |\ k \in K \wedge x \in X \wedge P(x) \}</math>
|-
! scope="row" | [[Python (programming language)|Python]]
| <syntaxhighlight lang="python">{l for l in L}</syntaxhighlight> || <syntaxhighlight lang="python">{(k, x) for k in K for x in X if P(x)}</syntaxhighlight>
|-
! scope="row" | [[Haskell (programming language)|Haskell]]
| <syntaxhighlight lang="haskell">[l | l <- ls]</syntaxhighlight> || <syntaxhighlight lang="haskell">[(k, x) | k <- ks, x <- xs, p x]</syntaxhighlight>
|-
! scope="row" | [[Scala (programming language)|Scala]]
| <syntaxhighlight lang="scala">for (l <- L) yield l</syntaxhighlight> || <syntaxhighlight lang="scala">for (k <- K; x <- X if P(x)) yield (k,x)</syntaxhighlight>
|-
! scope="row" | [[C Sharp (programming language)|C#]]
| <syntaxhighlight lang="csharp">from l in L select l</syntaxhighlight> || <syntaxhighlight lang="csharp">from k in K from x in X where P(x) select (k,x)</syntaxhighlight>
|-
! scope="row" | [[SQL]]
| <syntaxhighlight lang="sql">SELECT l FROM L_set</syntaxhighlight> || <syntaxhighlight lang="sql"> SELECT k, x FROM K_set, X_set WHERE P(x)</syntaxhighlight>
|-
! scope="row" | [[Prolog]]
| <syntaxhighlight lang="prolog">setof(L,member(L,Ls),Result)</syntaxhighlight> || <syntaxhighlight lang="prolog">setof((K,X),(member(K,Ks),member(X,Xs),call(P,X)),Result)</syntaxhighlight>
|-
![[Erlang (programming language)|Erlang]]
|<syntaxhighlight lang="erlang">
[L || L <- Ls]


</syntaxhighlight>
|<syntaxhighlight lang="erlang">
[{K,X} || K <- Ks, X <- Xs, p(X)]


</syntaxhighlight>
|-
![[Julia (programming language)|Julia]]
|<syntaxhighlight lang="julia">[l for l ∈ L]</syntaxhighlight>
|<syntaxhighlight lang="julia">
[(k, x) for k ∈ K for x ∈ X if P(x)]
</syntaxhighlight>
|-
![[Wolfram Mathematica|Mathematica]]
|<syntaxhighlight lang="mathematica">
(l |-> l) /@ L
</syntaxhighlight>
|<syntaxhighlight lang="mathematica">
Cases[Tuples[{K, X}], {k_, x_} /; P[x]]
</syntaxhighlight>
|}

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 (functional programming)|monad]] with a [[zero element]].

== See also ==
* [[Glossary of set theory]]

== Notes ==
{{Reflist}}

{{Set theory}}

{{bots|deny=Yobot}}

[[Category:Set theory]]
[[Category:Mathematical notation]]
[[Category:Articles with example Haskell code]]
[[Category:Articles with example Python (programming language) code]]

[[is:Mengjaskilgreiningarritháttur]]