TheInfoList

In
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 ...
, a set is a collection of elements. The elements that make up a set can be any kind of
mathematical object A mathematical object is an abstract concept arising in mathematics. In the usual language of mathematics, an ''object'' is anything that has been (or could be) formally defined, and with which one may do deductive reasoning and mathematical proofs ...
s: numbers, symbols, points in space, lines, other geometrical shapes, variables, or even other sets. The set with no element is 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 ...

; a set with a single element is a singleton. A set may have a finite number of elements or be an
infinite set 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 ...
. Two sets are equal
if and only if 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:λογική, λογική, l ...
they have precisely the same elements. Sets are ubiquitous in modern mathematics. Indeed,
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 ...
, more specifically
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 ...
, has been the standard way to provide rigorous foundations for all branches of mathematics since the first half of the 20th century.

# Origin

The concept of a set emerged in mathematics at the end of the 19th century. The German word for set, ''Menge'', was coined by
Bernard Bolzano Bernard Bolzano (, ; ; ; born Bernardus Placidus Johann Nepomuk Bolzano; 5 October 1781 – 18 December 1848) was a Bohemian A Bohemian () is a resident of Bohemia Bohemia ( ; cs, Čechy ; ; hsb, Čěska; szl, Czechy) is the westernmost a ...

in his work '' Paradoxes of the Infinite''.
Georg Cantor Georg Ferdinand Ludwig Philipp Cantor ( , ;  – January 6, 1918) was a German mathematician. He created set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence be ...
, one of the founders of set theory, gave the following definition at the beginning of his ''Beiträge zur Begründung der transfiniten Mengenlehre'':
Bertrand Russell Bertrand Arthur William Russell, 3rd Earl Russell (18 May 1872 – 2 February 1970) was a British , , , , , , , , and .Stanford Encyclopedia of Philosophy"Bertrand Russell" 1 May 2003 Throughout his life, Russell considered himself a , a and ...
called a set a ''class'': "When mathematicians deal with what they call a manifold, aggregate, ''Menge'', ''ensemble'', or some equivalent name, it is common, especially where the number of terms involved is finite, to regard the object in question (which is in fact a class) as defined by the enumeration of its terms, and as consisting possibly of a single term, which is in that case ''is'' the class."

## Naïve set theory

The foremost property of a set is that it can have elements, also called ''members''. Two sets are
equal Equal or equals may refer to: Arts and entertainment * Equals (film), ''Equals'' (film), a 2015 American science fiction film * Equals (game), ''Equals'' (game), a board game * The Equals, a British pop group formed in 1965 * "Equal", a 2016 song b ...
when they have the same elements. More precisely, sets ''A'' and ''B'' are equal if every element of ''A'' is a member of ''B'', and every element of ''B'' is an element of ''A''; this property is called the ''
extensionality In logic, extensionality, or extensional equality, refers to principles that judge objects to be equality (mathematics), equal if they have the same external properties. It stands in contrast to the concept of intensionality, which is concerned with ...
of sets''. The simple concept of a set has proved enormously useful in mathematics, but
paradoxes A paradox, also known as an antinomy, is a logically self-contradictory statement or a statement that runs contrary to one's expectation. It is a statement that, despite apparently valid reasoning from true premises, leads to a seemingly self-con ...
arise if no restrictions are placed on how sets can be constructed: *
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 ...

shows that the "set of all sets that ''do not contain themselves''", i.e., , cannot exist. *
Cantor's paradox 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 ar ...
shows that "the set of all sets" cannot exist. Naïve set theory defines a set as any ''
well-defined 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 ...
'' collection of distinct elements, but problems arise from the vagueness of the term ''well-defined''.

## Axiomatic set theory

In subsequent efforts to resolve these paradoxes since the time of the original formulation of naïve set theory, the properties of sets have been defined by
axioms An axiom, postulate or assumption is a statement that is taken to be truth, true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Greek ''axíōma'' () 'that which is thought worthy or fit' or ...
.
Axiomatic set theory illustrating the intersection (set theory), intersection of two set (mathematics), sets Set theory is the branch of mathematical logic that studies Set (mathematics), sets, which can be informally described as collections of objects. Although ob ...
takes the concept of a set as a primitive notion. The purpose of the axioms is to provide a basic framework from which to deduce the truth or falsity of particular mathematical propositions (statements) about sets, using
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses Quantificat ...
. According to
Gödel's incompleteness theorems Gödel's incompleteness theorems are two theorems of mathematical logic Mathematical logic, also called formal logic, is a subfield of mathematics Mathematics (from Ancient Greek, Greek: ) includes the study of such topics as quantity (nu ...
however, it is not possible to use first-order logic to prove any such particular axiomatic set theory is free from paradox.

# How sets are defined and set notation

Mathematical texts commonly denote sets by
capital letters Letter case (or just case) is the distinction between the Letter (alphabet), letters that are in larger uppercase or capitals (or more formally ''majuscule'') and smaller lowercase (or more formally ''minuscule'') in the written representation ...

in italic, such as , , . A set may also be called a ''collection'' or ''family'', especially when its elements are themselves sets.

## Roster notation

Roster or enumeration notation defines a set by listing its elements between
curly bracket A bracket is either of two tall fore- or back-facing punctuation Punctuation (or sometimes interpunction) is the use of spacing, conventional signs (called punctuation marks), and certain typographical devices as aids to the understanding ...
s, separated by commas: : :. In a set, all that matters is whether each element is in it or not, so the ordering of the elements in roster notation is irrelevant (in contrast, in a
sequence In 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 t ...

, a
tuple 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). ...
, or a
permutation In , a permutation of a is, loosely speaking, an arrangement of its members into a or , or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or process of changing the linear order o ...

of a set, the ordering of the terms matters). For example, and represent the same set. For sets with many elements, especially those following an implicit pattern, the list of members can be abbreviated using an
ellipsis The ellipsis , , or (as a single glyph) , also known informally as dot-dot-dot, is a series of (usually three) dots that indicates an intentional omission of a word, sentence, or whole section from a text without altering its original meaning. ...
''. For instance, the set of the first thousand positive integers may be specified in roster notation as :.

### Infinite sets in roster notation

An
infinite set 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 ...
is a set with an endless list of elements. To describe an infinite set in roster notation, an ellipsis is placed at the end of the list, or at both ends, to indicate that the list continues forever. For example, the set of
nonnegative integers In mathematics, the natural numbers are those 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, words coll ...
is : and the set of all
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
s is :

## Semantic definition

Another way to define a set is to use a rule to determine what the elements are: :Let be the set whose members are the first four positive
integers An integer (from the Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of t ...
. :Let be the set of colors of the
French flag French (french: français(e), link=no) may refer to: * Something of, from, or related to France France (), officially the French Republic (french: link=no, République française), is a transcontinental country This is a list of co ...

. Such a definition is called a ''semantic description''.

## Set-builder notation

Set-builder notation specifies a set as a selection from a larger set, determined by a condition on the elements. For example, a set can be defined as follows: : $= \.$ In this notation, the
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 ...
", " means "such that", and the description can be interpreted as " is the set of all numbers such that is an integer in the range from 0 to 19 inclusive". Some authors use 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 ...

":" instead of the vertical bar.

## Classifying methods of definition

Philosophy Philosophy (from , ) is the study of general and fundamental questions, such as those about Metaphysics, existence, reason, Epistemology, knowledge, Ethics, values, Philosophy of mind, mind, and Philosophy of language, language. Such questio ...

uses specific terms to classify types of definitions: *An ''
intensional definition 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:λογική, λογική, label ...
'' uses a ''rule'' to determine membership. Semantic definitions and definitions using set-builder notation are examples. *An ''
extensional definition In logic Logic (from Ancient Greek, Greek: grc, wikt:λογική, λογική, label=none, lit=possessed of reason, intellectual, dialectical, argumentative, translit=logikḗ)Also related to (''logos''), "word, thought, idea, argument, a ...
'' describes a set by ''listing all its elements''. Such definitions are also called '' enumerative''. *An ''
ostensive definitionAn ostensive definition conveys the meaning of a term by pointing out examples. This type of definition is often used where the term is difficult to define verbally, either because the words will not be understood (as with children and new speakers ...
'' is one that describes a set by giving ''examples'' of elements; a roster involving an ellipsis would be an example.

# Membership

If is a set and is an element of , this is written in shorthand as , which can also be read as "''x'' belongs to ''B''", or "''x'' is in ''B''". The statement "''y'' is not an element of ''B''" is written as , which can also be read as or "''y'' is not in ''B''". For example, with respect to the sets , , and , : and ; and : and .

# The empty set

The ''empty set'' (or ''null set'') is the unique set that has no members. It is denoted or $\emptyset$ or or (or ).

# Singleton sets

A ''singleton set'' is a set with exactly one element; such a set may also be called a ''unit set''. Any such set can be written as , where ''x'' is the element. The set and the element ''x'' mean different things; Halmos draws the analogy that a box containing a hat is not the same as the hat.

# Subsets

If every element of set ''A'' is also in ''B'', then ''A'' is described as being a ''subset of B'', or ''contained in B'', written ''A'' ⊆ ''B'', or ''B'' ⊇ ''A''. The latter notation may be read ''B contains A'', ''B includes A'', or ''B is a superset of A''. The
relationship Relationship most often refers to: * Interpersonal relationship The concept of interpersonal relationship involves social associations, connections, or affiliations between two or more people. Interpersonal relationships vary in their degre ...
between sets established by ⊆ is called ''inclusion'' or ''containment''. Two sets are equal if they contain each other: ''A'' ⊆ ''B'' and ''B'' ⊆ ''A'' is equivalent to ''A'' = ''B''. If ''A'' is a subset of ''B'', but ''A'' is not equal to ''B'', then ''A'' is called a ''proper subset'' of ''B''. This can be written ''A'' ⊊ ''B''. Likewise, ''B'' ⊋ ''A'' means ''B is a proper superset of A'', i.e. ''B'' contains ''A'', and is not equal to ''A''. A third pair of operators ⊂ and ⊃ are used differently by different authors: some authors use ''A'' ⊂ ''B'' and ''B'' ⊃ ''A'' to mean ''A'' is any subset of ''B'' (and not necessarily a proper subset), while others reserve ''A'' ⊂ ''B'' and ''B'' ⊃ ''A'' for cases where ''A'' is a proper subset of ''B''. Examples: * The set of all humans is a proper subset of the set of all mammals. * ⊂ . * ⊆ . The empty set is a subset of every set, and every set is a subset of itself: * ∅ ⊆ ''A''. * ''A'' ⊆ ''A''.

# Euler and Venn diagrams

An
Euler diagram An Euler diagram (, ) is a diagrammatic means of representing Set (mathematics), sets and their relationships. They are particularly useful for explaining complex hierarchies and overlapping definitions. They are similar to another set diagramm ...

is a graphical representation of a collection of sets; each set is depicted as a planar region enclosed by a loop, with its elements inside. If is a subset of , then the region representing is completely inside the region representing . If two sets have no elements in common, the regions do not overlap. A
Venn diagram A Venn diagram is a widely used diagram A diagram is a symbolic representation Representation may refer to: Law and politics *Representation (politics) Political representation is the activity of making citizens "present" in public policy ...
, in contrast, is a graphical representation of sets in which the loops divide the plane into zones such that for each way of selecting some of the sets (possibly all or none), there is a zone for the elements that belong to all the selected sets and none of the others. For example, if the sets are , , and , there should be a zone for the elements that are inside and and outside (even if such elements do not exist).

# Special sets of numbers in mathematics

There are sets of such mathematical importance, to which mathematicians refer so frequently, that they have acquired special names and notational conventions to identify them. Many of these important sets are represented in mathematical texts using bold (e.g. $\bold Z$) or
blackboard bold Image:Blackboard bold.svg, 250px, An example of blackboard bold letters Blackboard bold is a typeface style that is often used for certain symbols in mathematics, mathematical texts, in which certain lines of the symbol (usually vertical or near-v ...

(e.g. $\mathbb Z$) typeface. These include * $\bold N$ or $\mathbb N$, the set of all
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: $\bold N=\$ (often, authors exclude ); * $\bold Z$ or $\mathbb Z$, the set of all
integer An integer (from the Latin Latin (, or , ) is a classical language A classical language is a language A language is a structured system of communication Communication (from Latin ''communicare'', meaning "to share" or "to ...
s (whether positive, negative or zero): $\bold Z=\$; * $\bold Q$ or $\mathbb Q$, the set of all
rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction (mathematics), fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (e.g. ) ...
s (that is, the set of all proper and
improper fraction A fraction (from Latin Latin (, or , ) is a classical language belonging to the Italic languages, Italic branch of the Indo-European languages. Latin was originally spoken in the area around Rome, known as Latium. Through the power of the Rom ...
s): $\bold Q=\left\$. For example, and ; * $\bold R$ or $\mathbb R$, the set of all
real numbers Real may refer to: * Reality, the state of things as they exist, rather than as they may appear or may be thought to be Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish col ... , including all rational numbers and all irrational Irrationality is cognition Cognition () refers to "the mental action or process of acquiring knowledge and understanding through thought, experience, and the senses". It encompasses many aspects of intellectual functions and processes such as: ... numbers (which include algebraic number An algebraic number is any complex number 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 ... s such as $\sqrt2$ that cannot be rewritten as fractions, as well as transcendental numbers 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 ... such as and ); * $\bold C$ or $\mathbb C$, the set of all complex number In mathematics, a complex number is an element of a number system that contains the real numbers and a specific element denoted , called the imaginary unit, and satisfying the equation . Moreover, every complex number can be expressed in the for ... s: , for example, . Each of the above sets of numbers has an infinite number of elements. Each is a subset of the sets listed below it. Sets of positive or negative numbers are sometimes denoted by superscript plus and minus signs, respectively. For example, $\mathbf^+$ represents the set of positive rational numbers. # Functions A '' 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 ... '' (or '' mapping Mapping may refer to: * Mapping (cartography), the process of making a map * Mapping (mathematics), a synonym for a mathematical function and its generalizations ** Mapping (logic), a synonym for functional predicate Types of mapping * Animated ... '') from a set to a set is a rule that assigns to each "input" element of an "output" that is an element of ; more formally, a function is a special kind of relation, one that relates each element of to ''exactly one'' element of . A function is called * injective In 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 ... (or one-to-one) if it maps any two different elements of to ''different'' elements of , * surjective 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 ... (or onto) if for every element of , there is at least one element of that maps to it, and * bijective In 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 ... (or a one-to-one correspondence) if the function is both injective and surjective — in this case, each element of is paired with a unique element of , and each element of is paired with a unique element of , so that there are no unpaired elements. An injective function is called an ''injection'', a surjective function is called a ''surjection'', and a bijective function is called a ''bijection'' or ''one-to-one correspondence''. # Cardinality The cardinality of a set , denoted , is the number of members of . For example, if , then . Repeated members in roster notation are not counted, so , too. More formally, two sets share the same cardinality if there exists a one-to-one correspondence between them. The cardinality of the empty set is zero. ## Infinite sets and infinite cardinality The list of elements of some sets is endless, or '' infinite Infinite may refer to: Mathematics *Infinite set, a set that is not a finite set *Infinity, an abstract concept describing something without any limit Music *Infinite (band), a South Korean boy band *''Infinite'' (EP), debut EP of American musi ... ''. For example, the set $\N$ of natural numbers 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 ... is infinite. In fact, all the special sets of numbers mentioned in the section above, are infinite. Infinite sets have ''infinite cardinality''. Some infinite cardinalities are greater than others. Arguably one of the most significant results from set theory is that the set of real numbers Real may refer to: * Reality, the state of things as they exist, rather than as they may appear or may be thought to be Currencies * Brazilian real (R$) * Central American Republic real * Mexican real * Portuguese real * Spanish real * Spanish col ...
has greater cardinality than the set of natural numbers. Sets with cardinality less than or equal to that of $\N$ are called '' countable sets''; these are either finite sets or '' countably infinite sets'' (sets of the same cardinality as $\N$); some authors use "countable" to mean "countably infinite". Sets with cardinality strictly greater than that of $\N$ are called '' uncountable sets''. However, it can be shown that the cardinality of a
straight line 290px, A representation of one line segment. In geometry, the notion of line or straight line was introduced by ancient mathematicians to represent straight objects (i.e., having no curvature In mathematics, curvature is any of several str ...

(i.e., the number of points on a line) is the same as the cardinality of any
segment Segment or segmentation may refer to: Biology *Segmentation (biology), the division of body plans into a series of repetitive segments **Segmentation in the human nervous system *Internodal segment, the portion of a nerve fiber between two Nodes of ...

of that line, of the entire
plane Plane or planes may refer to: * Airplane An airplane or aeroplane (informally plane) is a fixed-wing aircraft A fixed-wing aircraft is a heavier-than-air flying machine Early flying machines include all forms of aircraft studied ...
, and indeed of any
finite-dimensional In mathematics, the dimension of a vector space ''V'' is the cardinality (i.e. the number of vectors) of a Basis (linear algebra), basis of ''V'' over its base Field (mathematics), field. p. 44, §2.36 It is sometimes called Hamel dimension (after ...
Euclidean space Euclidean space is the fundamental space of classical geometry. Originally, it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean spaces of any nonnegative integer dimension (mathematics), dimens ...
.

## The Continuum Hypothesis

The Continuum Hypothesis, formulated by Georg Cantor in 1878, is the statement that there is no set with cardinality strictly between the cardinality of the natural numbers and the cardinality of a straight line. In 1963,
Paul Cohen :''For other people named Paul Cohen, see Paul Cohen (disambiguation). Not to be confused with Paul Cohn.'' Paul Joseph Cohen (April 2, 1934 – March 23, 2007) was an United States, American mathematician. He is best known for his proofs that t ...

proved that the Continuum Hypothesis is
independent Independent or Independents may refer to: Arts, entertainment, and media Artist groups * Independents (artist group), a group of modernist painters based in the New Hope, Pennsylvania, area of the United States during the early 1930s * Independent ...
of the axiom system ZFC consisting of
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 ...
with the
axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product#Infinite Cartesian products, Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the a ...

. (ZFC is the most widely-studied version of axiomatic set theory.)

# Power sets

The power set of a set is the set of all subsets of . 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 ...

and itself are elements of the power set of , because these are both subsets of . For example, the power set of is . The power set of a set is commonly written as or . If has elements, then has elements. For example, has three elements, and its power set has elements, as shown above. If is infinite (whether
countable In 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 ...
or
uncountable 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 ...

), then is uncountable. Moreover, the power set is always strictly "bigger" than the original set, in the sense that any attempt to pair up the elements of with the elements of will leave some elements of unpaired. (There is never a
bijection In 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 ...

from onto .)

# Partitions

A
partition of a set The traditional Japanese symbols for the 54 chapters of the '' Tale of Genji'' are based on the 52 ways of partitioning five elements (the two red symbols represent the same partition, and the green symbol is added for reaching 54). In mathemati ...

''S'' is a set of nonempty subsets of ''S'', such that every element ''x'' in ''S'' is in exactly one of these subsets. That is, the subsets are
pairwise disjoint Two disjoint sets. 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 anal ...
(meaning any two sets of the partition contain no element in common), and the union of all the subsets of the partition is ''S''.

# Basic operations

There are several fundamental operations for constructing new sets from given sets.

## Unions

Two sets can be joined: the ''union'' of and , denoted by , is the set of all things that are members of ''A'' or of ''B'' or of both. Examples: * * * Some basic properties of unions: * * * * * *
if and only if 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:λογική, λογική, l ...

## Intersections

A new set can also be constructed by determining which members two sets have "in common". The ''intersection'' of ''A'' and ''B'', denoted by is the set of all things that are members of both ''A'' and ''B''. If then ''A'' and ''B'' are said to be ''disjoint''. Examples: * * * Some basic properties of intersections: * * * * * *
if and only if 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:λογική, λογική, l ...

## Complements

Two sets can also be "subtracted". The ''relative complement'' of ''B'' in ''A'' (also called the ''set-theoretic difference'' of ''A'' and ''B''), denoted by (or ), is the set of all elements that are members of ''A,'' but not members of ''B''. It is valid to "subtract" members of a set that are not in the set, such as removing the element ''green'' from the set ; doing so will not affect the elements in the set. In certain settings, all sets under discussion are considered to be subsets of a given
universal set 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 ty ...
''U''. In such cases, is called the ''absolute complement'' or simply ''complement'' of ''A'', and is denoted by ''A''′ or Ac. * Examples: * * * If ''U'' is the set of integers, ''E'' is the set of even integers, and ''O'' is the set of odd integers, then ''U'' \ ''E'' = ''E''′ = ''O''. Some basic properties of complements include the following: * for . * * * * * * * * and * and * . * if then An extension of the complement is the
symmetric difference 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 ...
, defined for sets ''A'', ''B'' as :$A\,\Delta\,B = \left(A \setminus B\right) \cup \left(B \setminus A\right).$ For example, the symmetric difference of and is the set . The power set of any set becomes a
Boolean ringIn 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 ha ...
with symmetric difference as the addition of the ring (with the empty set as neutral element) and intersection as the multiplication of the ring.

## Cartesian product

A new set can be constructed by associating every element of one set with every element of another set. The ''Cartesian product'' of two sets ''A'' and ''B'', denoted by ''A'' × ''B,'' is the set of all ordered pairs (''a'', ''b'') such that ''a'' is a member of ''A'' and ''b'' is a member of ''B''. Examples: * * * Some basic properties of Cartesian products: * * * Let ''A'' and ''B'' be finite sets; then the
cardinality 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 ...
of the Cartesian product is the product of the cardinalities: * , ''A'' × ''B'', = , ''B'' × ''A'', = , ''A'', × , ''B'', .

# Applications

Sets are ubiquitous in modern mathematics. For example,
structures A structure is an arrangement and organization of interrelated elements in a material object or system A system is a group of Interaction, interacting or interrelated elements that act according to a set of rules to form a unified whole. A sy ...
in
abstract algebra In algebra, which is a broad division of mathematics, abstract algebra (occasionally called modern algebra) is the study of algebraic structures. Algebraic structures include group (mathematics), groups, ring (mathematics), rings, field (mathema ...
, such as
groups A group is a number of people or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic identi ...
,
fields File:A NASA Delta IV Heavy rocket launches the Parker Solar Probe (29097299447).jpg, FIELDS heads into space in August 2018 as part of the ''Parker Solar Probe'' FIELDS is a science instrument on the ''Parker Solar Probe'' (PSP), designed to mea ...
and
rings Ring most commonly refers either to a hollow circular shape or to a high-pitched sound. It thus may refer to: *Ring (jewellery), a circular, decorative or symbolic ornament worn on fingers, toes, arm or neck Ring may also refer to: Sounds * Ri ...
, are sets closed under one or more operations. One of the main applications of naive set theory is in the construction of
relations Relation or relations may refer to: General uses *International relations, the study of interconnection of politics, economics, and law on a global level *Interpersonal relationship, association or acquaintance between two or more people *Public ...
. A relation from a
domain Domain may refer to: Mathematics *Domain of a function In mathematics, the domain of a Function (mathematics), function is the Set (mathematics), set of inputs accepted by the function. It is sometimes denoted by \operatorname(f), where is th ...
to a
codomain 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 ...

is a subset of the Cartesian product . For example, considering the set of shapes in the
game A game is a structured form of play Play most commonly refers to: * Play (activity), an activity done for enjoyment * Play (theatre), a work of drama Play may refer also to: Computers and technology * Google Play, a digital content serv ...

of the same name, the relation "beats" from to is the set ; thus beats in the game if the pair is a member of . Another example is the set of all pairs , where is real. This relation is a subset of , because the set of all squares is subset of the set of all real numbers. Since for every in , one and only one pair is found in , it is called a
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 ...
. In functional notation, this relation can be written as .

# Principle of inclusion and exclusion

The inclusion–exclusion principle is a counting technique that can be used to count the number of elements in a union of two sets—if the size of each set and the size of their intersection are known. It can be expressed symbolically as :$, A \cup B, = , A, + , B, - , A \cap B, .$ A more general form of the principle can be used to find the cardinality of any finite union of sets: :$\begin \left, A_\cup A_\cup A_\cup\ldots\cup A_\=& \left\left(\left, A_\+\left, A_\+\left, A_\+\ldots\left, A_\\right\right) \\ & - \left\left(\left, A_\cap A_\+\left, A_\cap A_\+\ldots\left, A_\cap A_\\right\right) \\ & + \ldots \\ & + \left\left(-1\right\right)^\left\left(\left, A_\cap A_\cap A_\cap\ldots\cap A_\\right\right). \end$

# De Morgan's laws

Augustus De Morgan Augustus De Morgan (27 June 1806 – 18 March 1871) was a British mathematician A mathematician is someone who uses an extensive knowledge of mathematics Mathematics (from Greek: ) includes the study of such topics as numbers ( and ), f ...

stated two laws about sets. If and are any two sets then, * The complement of union equals the complement of intersected with the complement of . * The complement of intersected with is equal to the complement of union to the complement of .

*
Algebra of sets 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 ...
*
Alternative set theoryIn a general sense, an alternative set theory is any of the alternative mathematical approaches to the concept of Set (mathematics), set and any alternative to the de facto standard set theory described in axiomatic set theory by the axioms of Zermel ...
* Category of sets * Class (set theory) * Dense set * Family of sets * Fuzzy set * Internal set * Mereology * Multiset * Principia Mathematica * Rough set

* * * *