HOME

TheInfoList




In
set theory Set theory is the branch of that studies , which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of , is mostly concerned with those that are relevant to ...
and its applications to
logic Logic is an interdisciplinary field which studies truth and reasoning. Informal logic seeks to characterize Validity (logic), valid arguments informally, for instance by listing varieties of fallacies. Formal logic represents statements and ar ...

logic
,
mathematics Mathematics (from Greek: ) includes the study of such topics as numbers (arithmetic and number theory), formulas and related structures (algebra), shapes and spaces in which they are contained (geometry), and quantities and their changes (cal ...
, and
computer science Computer science deals with the theoretical foundations of information, algorithms and the architectures of its computation as well as practical techniques for their application. Computer science is the study of , , and . Computer science ...
, set-builder notation is a
mathematical notation Mathematical notation is a system of symbol A symbol is a mark, sign, or word In linguistics, a word of a spoken language can be defined as the smallest sequence of phonemes that can be uttered in isolation with semantic, objective or prag ...
for describing a set by enumerating its elements, or stating the properties that its members must satisfy. Defining sets by properties is also known as set comprehension, set abstraction or as defining a set's
intension In linguistics Linguistics is the science, scientific study of language. It encompasses the analysis of every aspect of language, as well as the methods for studying and modeling them. The traditional areas of linguistic analysis include ...

intension
.


Sets defined by enumeration

A set can be described directly by enumerating all of its elements between curly brackets, as in the following two examples: * \ is the set containing the four numbers 3, 7, 15, and 31, and nothing else. * \=\ is the set containing , , and , and nothing else (there is no order among the elements of a set). This is sometimes called the "roster method" for specifying a set. When it is desired to denote a set that contains elements from a regular sequence, an
ellipses Ellipses is the plural form of two different English words: *Ellipse, a type of conic section in geometry *Ellipsis, a three-dot punctuation mark (…) Ellipses may also refer to: *''Ellipses'', a French publication under the direction of Aymeric ...

ellipses
notation may be employed, as shown in the next examples: * \ is the set of integers between 1 and 100 inclusive. * \ is the set of
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...
s. * \= \ is the set of all integers. There is no order among the elements of a set (this explains and validates the equality of the last example), but with the ellipses notation, we use an ordered sequence before (or after) the ellipsis as a convenient notational vehicle for explaining which elements are in a set. The first few elements of the sequence are shown, then the ellipses indicate 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. In general, \ denotes the set of all natural numbers i such that 1\leq i\leq n. Another notation for \ is the bracket notation /math>. A subtle special case is n=0, in which = \ is equal to the
empty set #REDIRECT Empty set#REDIRECT Empty set In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, cha ...

empty set
\emptyset. Similarly, \ denotes the set of all a_i for 1\leq i\leq n. In each preceding example, each set is described by enumerating its elements. Not all sets can be described in this way, or if they can, their enumeration may be too long or too complicated to be useful. Therefore, many sets are defined by a property that characterizes their elements. This characterization may be done informally using general prose, as in the following example. * \ is the set of all addresses on Pine Street. However, the prose approach may lack accuracy or be ambiguous. Thus, set-builder notation is often used with a predicate characterizing the elements of the set being defined, as described in the following section.


Sets defined by a predicate

Set-builder notation can be used to describe a set that is defined by a
predicate Predicate or predication may refer to: Computer science *Syntactic predicate (in parser technology) guidelines the parser process Linguistics *Predicate (grammar), a grammatical component of a sentence Philosophy and logic * Predication (philo ...
, that is, a logical formula that evaluates to ''true'' for an element of the set, and ''false'' otherwise. In this form, set-builder notation has three parts: a variable, a
colon Colon commonly refers to: * Colon (punctuation) (:), a punctuation mark * Major part of large intestine, the final section of the digestive system Colon may also refer to: Places * Colon, Michigan, US * Colon, Nebraska, US * Kowloon, Hong Kong, s ...

colon
or
vertical bar The vertical bar, , is a glyph with various uses in mathematics, computing, and typography. It has many names, often related to particular meanings: Sheffer stroke (in mathematical logic, logic), pipe, vbar, stick, vertical line, bar, verti-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: :\ or :\. The vertical bar (or colon) is a separator that can be read as "such that", "for which", or "with the property that". The formula is said to be the ''rule'' or the ''predicate''. All values of ''x'' for which the predicate holds (is true) belong to the set being defined. All values of for which the predicate does not hold do not belong to the set. Thus \ is the set of all values of that satisfy the formula . It may be the
empty set #REDIRECT Empty set#REDIRECT Empty set In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, cha ...

empty set
, if no value of satisfies the formula.


Specifying the domain

A domain can appear on the left of the vertical bar: :\, or by adjoining it to the predicate: :\\quad\text\quad\. The ∈ symbol here denotes
set membership In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
, while the \land symbol denotes the logical "and" operator, known as
logical conjunction In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, ...
. This notation represents the set of all values of that belong to some given set for which the predicate is true (see " Set existence axiom" below). If \Phi(x) is a conjunction \Phi_1(x)\land\Phi_2(x), then \ is sometimes written \, using a comma instead of the symbol \land. In general, it is not a good idea to consider sets without defining a
domain of discourse In the formal sciences Formal science is a branch of science studying formal language disciplines concerned with formal system A formal system is used for inferring theorems from axioms according to a set of rules. These rules, which are used f ...
, as this would represent the
subset In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). ...

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 In the foundations of mathematics Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theori ...

Russell's paradox
shows that the expression \, although seemingly well formed as a set builder expression, cannot define a set without producing a contradiction. In cases where the set ''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 in which 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. * \ is the set of all strictly
positive Positive is a property of Positivity (disambiguation), positivity and may refer to: Mathematics and science * Converging lens or positive lens, in optics * Plus sign, the sign "+" used to indicate a positive number * Positive (electricity), a po ...
real number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no g ...
s, which can be written in interval notation as (0, \infty). * \ is the set \. This set can also be defined as \; see
equivalent predicates yield equal sets Equivalence or Equivalent may refer to: Arts and entertainment *Album-equivalent unit The album-equivalent unit is a measurement unit in music industry to define the consumption of music that equals the purchase of one album copy. This consumpti ...
below. * For each integer ''m'', we can define G_m = \ = \. As an example, G_3 = \ = \ and G_ = \. * \ is the set of pairs of real numbers such that ''y'' is greater than 0 and less than ''f''(''x''), for a given
function Function or functionality may refer to: Computing * Function key A function key is a key on a computer A computer is a machine that can be programmed to carry out sequences of arithmetic or logical operations automatically. Modern comp ...
''f''. Here the
cartesian product In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). I ...
\mathbb\times\mathbb denotes the set of ordered pairs of real numbers. * \ is the set of all even
natural number In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and total order, ordering (as in "this is the ''third'' largest city in the country"). In common mathematical terminology, w ...
s. The \land sign stands for "and", which is known as
logical conjunction In logic Logic is an interdisciplinary field which studies truth and reasoning Reason is the capacity of consciously making sense of things, applying logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, ...
. The ∃ sign stands for "there exists", which is known as
existential quantification In predicate logic, an existential quantification is a type of Quantification (logic), quantifier, a logical constant which is interpretation (logic), interpreted as "there exists", "there is at least one", or "for some". It is usually denoted by ...
. So for example, (\exists x) P(x) is read as 'there exists an ''x'' such that ''P''(''x'')". * \ is a notational variant for the same set of even natural numbers. It is not necessary to specify that is a natural number, as this is implied by the formula on the right. * \ is the set of
rational number In mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), formulas and related structures (), shapes and spaces in which they are contained (), and quantities and their changes ( and ). There is no ...
s; that is, real numbers that can be written as the ratio of two
integer An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the Roman Re ...
s.


More complex expressions on the left side of the notation

An extension of set-builder notation replaces the single variable with an expression. So instead of \, we may have \, which should be read :\=\. For example: * \, where \mathbb N is the set of all natural numbers, is the set of all even natural numbers. * \, where \mathbb Z is the set of all integers, is \mathbb, the set of all rational numbers. * \ is the set of odd integers. * \ 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 \. Make the substitution u = 2t + 1, which is to say t = (u-1)/2, then replace ''t'' in the set builder notation to find :\ = \.


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 : \=\ if and only if : (\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, : \ = \ because the two rule predicates are logically equivalent: : (x \in \mathbb \land x^2 = 1) \Leftrightarrow (x \in \mathbb \land , x, = 1). This equivalence holds because, for any real number ''x'', we have x^2 = 1 if and only if ''x'' is a rational number with , x, =1. In particular, both sets are equal to the set \.


Set existence axiom

In many formal set theories, such as
Zermelo–Fraenkel set theory In set theory illustrating the intersection (set theory), intersection of two set (mathematics), sets. Set theory is a branch of mathematical logic that studies Set (mathematics), sets, which informally are collections of objects. Although any t ...
, set builder notation is not part of the formal syntax of the theory. Instead, there is a set existence axiom scheme, which states that if is a set and is a formula in the language of set theory, then there is a set whose members are exactly the elements of that satisfy : :(\forall E)(\exists Y)(\forall x) \in Y \Leftrightarrow x \in E \land \Phi(x) The set obtained from this axiom is exactly the set described in set builder notation as \.


Parallels in programming languages

A similar notation available in a number of
programming languages A programming language is a formal language comprising a set of Formal language#Words over an alphabet, strings that produce various kinds of Machine code, machine code output. Programming languages are one kind of computer language, and are us ...
(notably
Python Python may refer to: * Pythonidae The Pythonidae, commonly known as pythons, are a family of nonvenomous snakes found in Africa, Asia, and Australia. Among its members are some of the largest snakes in the world. Ten genera and 42 species ...
and Haskell) is the
list comprehensionA list comprehension is a syntactic In linguistics, syntax () is the set of rules, principles, and processes that govern the structure of Sentence (linguistics), sentences (sentence structure) in a given Natural language, language, usually includ ...
, which combines
map A map is a symbol A symbol is a mark, sign, or that indicates, signifies, or is understood as representing an , , or . Symbols allow people to go beyond what is n or seen by creating linkages between otherwise very different s and s. A ...
and
filter Filter, filtering or filters may refer to: Science and technology Device * Filter (chemistry), a device which separates solids from fluids (liquids or gases) by adding a medium through which only the fluid can pass ** Filter (aquarium), critical ...
operations over one or more
lists A ''list'' is any set of items. List or lists may also refer to: People * List (surname)List or Liste is a European surname. Notable people with the surname include: List * Friedrich List (1789–1846), German economist * Garrett List (1943 ...
. 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. The same can be achieved in Scala using Sequence Comprehensions, where the "for" keyword returns a list of the yielded variables using the "yield" keyword. Consider these set-builder notation examples in some programming languages: 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 Monad may refer to: Philosophy * Monad (philosophy) Monad (from Greek Greek may refer to: Greece Anything of, from, or related to Greece Greece ( el, Ελλάδα, , ), officially the Hellenic Republic, is a country located in Southeas ...
with a
zero element In mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (number theory), mathematical structure, structure (algebra), space (geometry), and calculus, change (mathematical analysis, analysis). It ...
.


See also

*
Glossary of set theory This is a glossary of set theory illustrating the intersection (set theory), intersection of two set (mathematics), sets. Set theory is a branch of mathematical logic that studies Set (mathematics), sets, which informally are collections of objec ...


Notes

{{bots, deny=Yobot Set theory Mathematical notation Articles with example Haskell code Articles with example Python (programming language) code is:Mengjaskilgreiningarritháttur