A
set is a collection of well defined and distinct objects, considered as an object in its own right. Sets are one of the most fundamental concepts in
mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
. Developed at the end of the 19th century, set theory is now a ubiquitous part of mathematics, and can be used as a foundation from which nearly all of mathematics can be derived. In
mathematics educationIn contemporary education, mathematics education is the practice of teaching and learning mathematics, along with the associated scholarly research....
, elementary topics such as
Venn diagramVenn diagrams or set diagrams are diagrams that show all possible logical relations between a finite collection of sets . Venn diagrams were conceived around 1880 by John Venn...
s are taught at a young age, while more advanced concepts are taught as part of a university degree.
Definition
Georg CantorGeorg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
, the founder of set theory, gave the following definition of a set at the beginning of his
Beiträge zur Begründung der transfiniten Mengenlehre:
The
elements or members of a set can be anything: numbers, people, letters of the alphabet, other sets, and so on. Sets are conventionally denoted with capital letters. Sets
A and
B are equal
if and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
they have precisely the same elements.
As discussed below, the definition given above turned out to be inadequate for formal mathematics; instead, the notion of a "set" is taken as an undefined primitive in axiomatic set theory, and its properties are defined by the Zermelo–Fraenkel axioms. The most basic properties are that a set "has" elements, and that two sets are equal (one and the same) if and only if they have the same elements.
Describing sets
There are two ways of describing, or specifying the members of, a set. One way is by
intensional definitionIn logic and mathematics, an intensional definition gives the meaning of a term by specifying all the properties required to come to that definition, that is, the necessary and sufficient conditions for belonging to the set being defined....
, using a rule or semantic description:
- A is the set whose members are the first four positive integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s.
- B is the set of colors of the French flag
The national flag of France is a tricolour featuring three vertical bands coloured royal blue , white, and red...
.
The second way is by
extensionIn any of several studies that treat the use of signs - for example, in linguistics, logic, mathematics, semantics, and semiotics - the extension of a concept, idea, or sign consists of the things to which it applies, in contrast with its comprehension or intension, which consists very roughly of...
– that is, listing each member of the set. An
extensional definitionAn extensional definition of a concept or term formulates its meaning by specifying its extension, that is, every object that falls under the definition of the concept or term in question....
is denoted by enclosing the list of members in curly brackets:
- C = {4, 2, 1, 3}
- D = {blue, white, red}.
Every element of a set must be unique; no two members may be identical. (A
multisetIn mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
is a generalized concept of a set that that relaxes this criterion.) All set operations preserve this property. The order in which the elements of a set or multiset are listed is irrelevant (unlike for a
sequenceIn mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
or
tupleIn mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
). Combining these two ideas into an example
- {6, 11} = {11, 6} = {11, 11, 6, 11}
because the extensional specification means merely that each of the elements listed is a member of the set.
For sets with many elements, the enumeration of members can be abbreviated. For instance, the set of the first thousand positive integers may be specified extensionally as:
- {1, 2, 3, ..., 1000},
where the
ellipsisEllipsis is a series of marks that usually indicate an intentional omission of a word, sentence or whole section from the original text being quoted. An ellipsis can also be used to indicate an unfinished thought or, at the end of a sentence, a trailing off into silence...
("...") indicates that the list continues in the obvious way. Ellipses may also be used where sets have infinitely many members. Thus the set of positive even numbers can be written as
The notation with braces may also be used in an intensional specification of a set. In this usage, the braces have the meaning "the set of all ...". So,
E = {playing card suits} is the set whose four members are A more general form of this is
set-builder notationIn 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...
, through which, for instance, the set
F of the twenty smallest integers that are four less than
perfect squareIn mathematics, a square number, sometimes also called a perfect square, is an integer that is the square of an integer; in other words, it is the product of some integer with itself...
s can be denoted:
- F = {n2 − 4 : n is an integer; and 0 ≤ n ≤ 19}.
In this notation, the
colonThe colon is a punctuation mark consisting of two equally sized dots centered on the same vertical line.-Usage:A colon informs the reader that what follows the mark proves, explains, or lists elements of what preceded the mark....
(":") means "such that", and the description can be interpreted as "
F is the set of all numbers of the form
n2 − 4, such that
n is a whole number in the range from 0 to 19 inclusive." Sometimes the
vertical barThe vertical bar is a character with various uses in mathematics, where it can be used to represent absolute value, among others; in computing and programming and in general typography, as a divider not unlike the interpunct...
("|") is used instead of the colon.
One often has the choice of specifying a set intensionally or extensionally. In the examples above, for instance,
A =
C and
B =
D.
Membership
The key relation between sets is
membership – when one set is an element of another. If
a is a member of
B, this is denoted
a ∈
B, while if
c is not a member of
B then
c ∉
B.
For example, with respect to the sets
A = {1,2,3,4},
B = {blue, white, red}, and
F = {
n2 − 4 :
n is an integer; and 0 ≤
n ≤ 19} defined above,
- 4 ∈ A and 285 ∈ F; but
- 9 ∉ F and green ∉ B.
Subsets
If every member of set
A is also a member of set
B, then
A is said to be a
subset of
B, written
A ⊆
B (also pronounced
A is contained in B). Equivalently, we can write
B ⊇
A, read as
B is a superset of A,
B includes A, or
B contains A. The
relationshipIn set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
between sets established by ⊆ is called
inclusion or
containment.
If
A is a subset of, but not equal to,
B, then
A is called a
proper subset of
B, written
A ⊊
B (
A is a proper subset of B) or
B ⊋
A (
B is a proper superset of A).
Note that the expressions
A ⊂
B and
B ⊃
A are used differently by different authors; some authors use them to mean the same as
A ⊆
B (respectively
B ⊇
A), whereas other use them to mean the same as
A ⊊
B (respectively
B ⊋
A).
Example:
- The set of all men is a proper subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of the set of all people.
- {1, 3} ⊊ {1, 2, 3, 4}.
- {1, 2, 3, 4} ⊆ {1, 2, 3, 4}.
The empty set is a subset of every set and every set is a subset of itself:
An obvious but useful identity, which can often be used to show that two seemingly different sets are equal:
Power sets
The power set of a set
S is the set of all subsets of
S. This includes the subsets formed from all the members of
S and the empty set. If a finite set
S has cardinality
n then the power set of
S has cardinality 2
n. The power set of
S can be written as
P(
S).
If
S is an infinite (either countable or uncountable) set, then the power set of
S is always uncountable. Moreover, if
S is a set, then there is never a
bijectionA bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
from
S onto
P(
S). In other words, the power set of
S is always strictly "bigger" than
S.
As an example, the power set of {1, 2, 3} is
{{dablink|This article gives an introduction to what mathematicians call "intuitive" or "naive" set theory; for a more detailed account see Naive set theoryNaive set theory is one of several theories of sets used in the discussion of the foundations of mathematics. The informal content of this naive set theory supports both the aspects of mathematical sets familiar in discrete mathematics , and the everyday usage of set theory concepts in most...
. For a rigorous modern axiomIn traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
atic treatment of sets, see Set theorySet theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
.}}
A set is a collection of well defined and distinct objects, considered as an object in its own right. Sets are one of the most fundamental concepts in mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
. Developed at the end of the 19th century, set theory is now a ubiquitous part of mathematics, and can be used as a foundation from which nearly all of mathematics can be derived. In mathematics educationIn contemporary education, mathematics education is the practice of teaching and learning mathematics, along with the associated scholarly research....
, elementary topics such as Venn diagramVenn diagrams or set diagrams are diagrams that show all possible logical relations between a finite collection of sets . Venn diagrams were conceived around 1880 by John Venn...
s are taught at a young age, while more advanced concepts are taught as part of a university degree.
Definition
Georg CantorGeorg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
, the founder of set theory, gave the following definition of a set at the beginning of his Beiträge zur Begründung der transfiniten Mengenlehre:
{{quote|A set is a gathering together into a whole of definite, distinct objects of our perception [Anschauung] and of our thought – which are called elements of the set.}}
The elements or members of a set can be anything: numbers, people, letters of the alphabet, other sets, and so on. Sets are conventionally denoted with capital letters. Sets A and B are equal if and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
they have precisely the same elements.
As discussed below, the definition given above turned out to be inadequate for formal mathematics; instead, the notion of a "set" is taken as an undefined primitive in axiomatic set theory, and its properties are defined by the Zermelo–Fraenkel axioms. The most basic properties are that a set "has" elements, and that two sets are equal (one and the same) if and only if they have the same elements.
Describing sets
There are two ways of describing, or specifying the members of, a set. One way is by intensional definitionIn logic and mathematics, an intensional definition gives the meaning of a term by specifying all the properties required to come to that definition, that is, the necessary and sufficient conditions for belonging to the set being defined....
, using a rule or semantic description:
- A is the set whose members are the first four positive integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s.
- B is the set of colors of the French flag
The national flag of France is a tricolour featuring three vertical bands coloured royal blue , white, and red...
.
The second way is by extensionIn any of several studies that treat the use of signs - for example, in linguistics, logic, mathematics, semantics, and semiotics - the extension of a concept, idea, or sign consists of the things to which it applies, in contrast with its comprehension or intension, which consists very roughly of...
– that is, listing each member of the set. An extensional definitionAn extensional definition of a concept or term formulates its meaning by specifying its extension, that is, every object that falls under the definition of the concept or term in question....
is denoted by enclosing the list of members in curly brackets:
- C = {4, 2, 1, 3}
- D = {blue, white, red}.
Every element of a set must be unique; no two members may be identical. (A multisetIn mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
is a generalized concept of a set that that relaxes this criterion.) All set operations preserve this property. The order in which the elements of a set or multiset are listed is irrelevant (unlike for a sequenceIn mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
or tupleIn mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
). Combining these two ideas into an example
- {6, 11} = {11, 6} = {11, 11, 6, 11}
because the extensional specification means merely that each of the elements listed is a member of the set.
For sets with many elements, the enumeration of members can be abbreviated. For instance, the set of the first thousand positive integers may be specified extensionally as:
- {1, 2, 3, ..., 1000},
where the ellipsisEllipsis is a series of marks that usually indicate an intentional omission of a word, sentence or whole section from the original text being quoted. An ellipsis can also be used to indicate an unfinished thought or, at the end of a sentence, a trailing off into silence...
("...") indicates that the list continues in the obvious way. Ellipses may also be used where sets have infinitely many members. Thus the set of positive even numbers can be written as {{nowrap|{2, 4, 6, 8, ... }.}}
The notation with braces may also be used in an intensional specification of a set. In this usage, the braces have the meaning "the set of all ...". So, E = {playing card suits} is the set whose four members are {{nowrap|♠, ♦, ♥, and ♣.}} A more general form of this is set-builder notationIn 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...
, through which, for instance, the set F of the twenty smallest integers that are four less than perfect squareIn mathematics, a square number, sometimes also called a perfect square, is an integer that is the square of an integer; in other words, it is the product of some integer with itself...
s can be denoted:
- F = {n2 − 4 : n is an integer; and 0 ≤ n ≤ 19}.
In this notation, the colonThe colon is a punctuation mark consisting of two equally sized dots centered on the same vertical line.-Usage:A colon informs the reader that what follows the mark proves, explains, or lists elements of what preceded the mark....
(":") means "such that", and the description can be interpreted as "F is the set of all numbers of the form n2 − 4, such that n is a whole number in the range from 0 to 19 inclusive." Sometimes the vertical barThe vertical bar is a character with various uses in mathematics, where it can be used to represent absolute value, among others; in computing and programming and in general typography, as a divider not unlike the interpunct...
("|") is used instead of the colon.
One often has the choice of specifying a set intensionally or extensionally. In the examples above, for instance, A = C and B = D.
Membership
{{Main|Element (mathematics)}}
The key relation between sets is membership – when one set is an element of another. If a is a member of B, this is denoted a ∈ B, while if c is not a member of B then c ∉ B.
For example, with respect to the sets A = {1,2,3,4}, B = {blue, white, red}, and F = {n2 − 4 : n is an integer; and 0 ≤ n ≤ 19} defined above,
- 4 ∈ A and 285 ∈ F; but
- 9 ∉ F and green ∉ B.
Subsets
{{Main|Subset}}
If every member of set A is also a member of set B, then A is said to be a subset of B, written A ⊆ B (also pronounced A is contained in B). Equivalently, we can write B ⊇ A, read as B is a superset of A, B includes A, or B contains A. The relationshipIn set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
between sets established by ⊆ is called inclusion or containment.
If A is a subset of, but not equal to, B, then A is called a proper subset of B, written A ⊊ B (A is a proper subset of B) or B ⊋ A (B is a proper superset of A).
Note that the expressions A ⊂ B and B ⊃ A are used differently by different authors; some authors use them to mean the same as A ⊆ B (respectively B ⊇ A), whereas other use them to mean the same as A ⊊ B (respectively B ⊋ A).
Example:
- The set of all men is a proper subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of the set of all people.
- {1, 3} ⊊ {1, 2, 3, 4}.
- {1, 2, 3, 4} ⊆ {1, 2, 3, 4}.
The empty set is a subset of every set and every set is a subset of itself:
An obvious but useful identity, which can often be used to show that two seemingly different sets are equal:
- {{nowrap|1=A = B}} if and only if {{nowrap|A ⊆ B}} and {{nowrap|B ⊆ A}}.
Power sets
{{Main|Power set}}
The power set of a set S is the set of all subsets of S. This includes the subsets formed from all the members of S and the empty set. If a finite set S has cardinality n then the power set of S has cardinality 2n. The power set of S can be written as P(S).
If S is an infinite (either countable or uncountable) set, then the power set of S is always uncountable. Moreover, if S is a set, then there is never a bijectionA bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
from S onto P(S). In other words, the power set of S is always strictly "bigger" than S.
As an example, the power set of {1, 2, 3} is
{{dablink|This article gives an introduction to what mathematicians call "intuitive" or "naive" set theory; for a more detailed account see Naive set theoryNaive set theory is one of several theories of sets used in the discussion of the foundations of mathematics. The informal content of this naive set theory supports both the aspects of mathematical sets familiar in discrete mathematics , and the everyday usage of set theory concepts in most...
. For a rigorous modern axiomIn traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
atic treatment of sets, see Set theorySet theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
.}}
A set is a collection of well defined and distinct objects, considered as an object in its own right. Sets are one of the most fundamental concepts in mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
. Developed at the end of the 19th century, set theory is now a ubiquitous part of mathematics, and can be used as a foundation from which nearly all of mathematics can be derived. In mathematics educationIn contemporary education, mathematics education is the practice of teaching and learning mathematics, along with the associated scholarly research....
, elementary topics such as Venn diagramVenn diagrams or set diagrams are diagrams that show all possible logical relations between a finite collection of sets . Venn diagrams were conceived around 1880 by John Venn...
s are taught at a young age, while more advanced concepts are taught as part of a university degree.
Definition
Georg CantorGeorg Ferdinand Ludwig Philipp Cantor was a German mathematician, best known as the inventor of set theory, which has become a fundamental theory in mathematics. Cantor established the importance of one-to-one correspondence between the members of two sets, defined infinite and well-ordered sets,...
, the founder of set theory, gave the following definition of a set at the beginning of his Beiträge zur Begründung der transfiniten Mengenlehre:
{{quote|A set is a gathering together into a whole of definite, distinct objects of our perception [Anschauung] and of our thought – which are called elements of the set.}}
The elements or members of a set can be anything: numbers, people, letters of the alphabet, other sets, and so on. Sets are conventionally denoted with capital letters. Sets A and B are equal if and only ifIn logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
they have precisely the same elements.
As discussed below, the definition given above turned out to be inadequate for formal mathematics; instead, the notion of a "set" is taken as an undefined primitive in axiomatic set theory, and its properties are defined by the Zermelo–Fraenkel axioms. The most basic properties are that a set "has" elements, and that two sets are equal (one and the same) if and only if they have the same elements.
Describing sets
There are two ways of describing, or specifying the members of, a set. One way is by intensional definitionIn logic and mathematics, an intensional definition gives the meaning of a term by specifying all the properties required to come to that definition, that is, the necessary and sufficient conditions for belonging to the set being defined....
, using a rule or semantic description:
- A is the set whose members are the first four positive integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s.
- B is the set of colors of the French flag
The national flag of France is a tricolour featuring three vertical bands coloured royal blue , white, and red...
.
The second way is by extensionIn any of several studies that treat the use of signs - for example, in linguistics, logic, mathematics, semantics, and semiotics - the extension of a concept, idea, or sign consists of the things to which it applies, in contrast with its comprehension or intension, which consists very roughly of...
– that is, listing each member of the set. An extensional definitionAn extensional definition of a concept or term formulates its meaning by specifying its extension, that is, every object that falls under the definition of the concept or term in question....
is denoted by enclosing the list of members in curly brackets:
- C = {4, 2, 1, 3}
- D = {blue, white, red}.
Every element of a set must be unique; no two members may be identical. (A multisetIn mathematics, the notion of multiset is a generalization of the notion of set in which members are allowed to appear more than once...
is a generalized concept of a set that that relaxes this criterion.) All set operations preserve this property. The order in which the elements of a set or multiset are listed is irrelevant (unlike for a sequenceIn mathematics, a sequence is an ordered list of objects . Like a set, it contains members , and the number of terms is called the length of the sequence. Unlike a set, order matters, and exactly the same elements can appear multiple times at different positions in the sequence...
or tupleIn mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
). Combining these two ideas into an example
- {6, 11} = {11, 6} = {11, 11, 6, 11}
because the extensional specification means merely that each of the elements listed is a member of the set.
For sets with many elements, the enumeration of members can be abbreviated. For instance, the set of the first thousand positive integers may be specified extensionally as:
- {1, 2, 3, ..., 1000},
where the ellipsisEllipsis is a series of marks that usually indicate an intentional omission of a word, sentence or whole section from the original text being quoted. An ellipsis can also be used to indicate an unfinished thought or, at the end of a sentence, a trailing off into silence...
("...") indicates that the list continues in the obvious way. Ellipses may also be used where sets have infinitely many members. Thus the set of positive even numbers can be written as {{nowrap|{2, 4, 6, 8, ... }.}}
The notation with braces may also be used in an intensional specification of a set. In this usage, the braces have the meaning "the set of all ...". So, E = {playing card suits} is the set whose four members are {{nowrap|♠, ♦, ♥, and ♣.}} A more general form of this is set-builder notationIn 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...
, through which, for instance, the set F of the twenty smallest integers that are four less than perfect squareIn mathematics, a square number, sometimes also called a perfect square, is an integer that is the square of an integer; in other words, it is the product of some integer with itself...
s can be denoted:
- F = {n2 − 4 : n is an integer; and 0 ≤ n ≤ 19}.
In this notation, the colonThe colon is a punctuation mark consisting of two equally sized dots centered on the same vertical line.-Usage:A colon informs the reader that what follows the mark proves, explains, or lists elements of what preceded the mark....
(":") means "such that", and the description can be interpreted as "F is the set of all numbers of the form n2 − 4, such that n is a whole number in the range from 0 to 19 inclusive." Sometimes the vertical barThe vertical bar is a character with various uses in mathematics, where it can be used to represent absolute value, among others; in computing and programming and in general typography, as a divider not unlike the interpunct...
("|") is used instead of the colon.
One often has the choice of specifying a set intensionally or extensionally. In the examples above, for instance, A = C and B = D.
Membership
{{Main|Element (mathematics)}}
The key relation between sets is membership – when one set is an element of another. If a is a member of B, this is denoted a ∈ B, while if c is not a member of B then c ∉ B.
For example, with respect to the sets A = {1,2,3,4}, B = {blue, white, red}, and F = {n2 − 4 : n is an integer; and 0 ≤ n ≤ 19} defined above,
- 4 ∈ A and 285 ∈ F; but
- 9 ∉ F and green ∉ B.
Subsets
{{Main|Subset}}
If every member of set A is also a member of set B, then A is said to be a subset of B, written A ⊆ B (also pronounced A is contained in B). Equivalently, we can write B ⊇ A, read as B is a superset of A, B includes A, or B contains A. The relationshipIn set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
between sets established by ⊆ is called inclusion or containment.
If A is a subset of, but not equal to, B, then A is called a proper subset of B, written A ⊊ B (A is a proper subset of B) or B ⊋ A (B is a proper superset of A).
Note that the expressions A ⊂ B and B ⊃ A are used differently by different authors; some authors use them to mean the same as A ⊆ B (respectively B ⊇ A), whereas other use them to mean the same as A ⊊ B (respectively B ⊋ A).
Example:
- The set of all men is a proper subset
In mathematics, especially in set theory, a set A is a subset of a set B if A is "contained" inside B. A and B may coincide. The relationship of one set being a subset of another is called inclusion or sometimes containment...
of the set of all people.
- {1, 3} ⊊ {1, 2, 3, 4}.
- {1, 2, 3, 4} ⊆ {1, 2, 3, 4}.
The empty set is a subset of every set and every set is a subset of itself:
An obvious but useful identity, which can often be used to show that two seemingly different sets are equal:
- {{nowrap|1=A = B}} if and only if {{nowrap|A ⊆ B}} and {{nowrap|B ⊆ A}}.
Power sets
{{Main|Power set}}
The power set of a set S is the set of all subsets of S. This includes the subsets formed from all the members of S and the empty set. If a finite set S has cardinality n then the power set of S has cardinality 2n. The power set of S can be written as P(S).
If S is an infinite (either countable or uncountable) set, then the power set of S is always uncountable. Moreover, if S is a set, then there is never a bijectionA bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...
from S onto P(S). In other words, the power set of S is always strictly "bigger" than S.
As an example, the power set of {1, 2, 3} is {{1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3}, ∅}. The cardinality of the original set is 3, and the cardinality of the power set is 23 = 8. This relationship is one of the reasons for the terminology power set.
Cardinality
{{Main|Cardinality}}
The cardinality | S | of a set S is "the number of members of S." For example, if {{nowrap|1=B = {blue, white, red}}}, {{nowrap|1={{!}} B {{!}} = 3.}}
There is a unique set with no members and zero cardinality, which is called the empty setIn mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
(or the null set) and is denoted by the symbol ∅ (other notations are used; see empty setIn mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
). For example, the set of all three-sided squares has zero members and thus is the empty set. Though it may seem trivial, the empty set, like the number zero0 is both a numberand the numerical digit used to represent that number in numerals.It fulfills a central role in mathematics as the additive identity of the integers, real numbers, and many other algebraic structures. As a digit, 0 is used as a placeholder in place value systems...
, is important in mathematics; indeed, the existence of this set is one of the fundamental concepts of axiomatic set theory.
Some sets have infinite cardinality. The set N of natural numberIn mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s, for instance, is infinite. Some infinite cardinalities are greater than others. For instance, the set of real numberIn mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s has greater cardinality than the set of natural numbers. However, it can be shown that the cardinality of (which is to say, the number of points on) a straight line is the same as the cardinality of any segmentIn geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
of that line, of the entire planeIn mathematics, a plane is a flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...
, and indeed of any finite-dimensional Euclidean spaceIn mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
.
Special sets
There are some sets which hold great mathematical importance and are referred to with such regularity that they have acquired special names and notational conventions to identify them. One of these is the empty setIn mathematics, and more specifically set theory, the empty set is the unique set having no elements; its size or cardinality is zero. Some axiomatic set theories assure that the empty set exists by including an axiom of empty set; in other theories, its existence can be deduced...
, denoted {} or ∅. Another is the unit set {x} which contains exactly one element, namely x. Many of these sets are represented using blackboard boldBlackboard bold is a typeface style that is often used for certain symbols in mathematical texts, in which certain lines of the symbol are doubled. The symbols usually denote number sets...
or bold typeface. Special sets of numbers include:
- P or ℙ, denoting the set of all primes
A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. A natural number greater than 1 that is not a prime number is called a composite number. For example 5 is prime, as only 1 and 5 divide it, whereas 6 is composite, since it has the divisors 2...
: P = {2, 3, 5, 7, 11, 13, 17, ...}.
- N or ℕ, denoting the set of all natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
s: N = {1, 2, 3, . . .}.
- Z or ℤ, denoting the set of all integer
The integers are formed by the natural numbers together with the negatives of the non-zero natural numbers .They are known as Positive and Negative Integers respectively...
s (whether positive, negative or zero): Z = {... , −2, −1, 0, 1, 2, ...}.
- Q or ℚ, denoting the set of all rational number
In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
s (that is, the set of all proper and improper fractions): Q = {a/b : a, b ∈ Z, b ≠ 0}. For example, 1/4 ∈ Q and 11/6 ∈ Q. All integers are in this set since every integer a can be expressed as the fraction a/1 (Z ⊊ Q).
- R or ℝ, denoting the set of all real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s. This set includes all rational numbers, together with all irrationalIn mathematics, an irrational number is any real number that cannot be expressed as a ratio a/b, where a and b are integers, with b non-zero, and is therefore not a rational number....
numbers (that is, numbers which cannot be rewritten as fractions, such as π' is a mathematical constant that is the ratio of any circle's circumference to its diameter. is approximately equal to 3.14. Many formulae in mathematics, science, and engineering involve , which makes it one of the most important mathematical constants...
, eExponentiation is a mathematical operation, written as an, involving two numbers, the base a and the exponent n...
, and √2, as well as numbers that cannot be defined).
- C or ℂ, denoting the set of all complex number
A complex number is a number consisting of a real part and an imaginary part. Complex numbers extend the idea of the one-dimensional number line to the two-dimensional complex plane by using the number line for the real part and adding a vertical axis to plot the imaginary part...
s: C = {a + bi : a, b ∈ R}. For example, 1 + 2i ∈ C.
- H or ℍ, denoting the set of all quaternion
In mathematics, the quaternions are a number system that extends the complex numbers. They were first described by Irish mathematician Sir William Rowan Hamilton in 1843 and applied to mechanics in three-dimensional space...
s: H = {a + bi + cj + dk : a, b, c, d ∈ R}. For example, 1 + i + 2j − k ∈ H.
Each of the above sets of numbers has an infinite number of elements, and each can be considered to be a proper subset of the sets listed below it. The primes are used less frequently than the others outside of number theoryNumber theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...
and related fields.
Basic operations
There are several fundamental operations for constructing new sets from given sets.
Unions
{{Main|Union (set theory)}}
Two sets can be "added" together. The union of A and B, denoted by A ∪ B, is the set of all things which are members of either A or B.
Examples:
- {{nowrap|1={1, 2} ∪ {red, white}}} {{nowrap|1
{1, 2, red, white}. }}
- {{nowrap|1={1, 2, green} ∪ {red, white, green}}} {{nowrap|1{1, 2, red, white, green}. }}
- {{nowrap|1={1, 2} ∪ {1, 2} = {1, 2}. }}
Some basic properties of unions:
- {{nowrap|1=A ∪ B = B ∪ A.}}
- {{nowrap|1=A ∪ (B ∪ C) = (A ∪ B) ∪ C.}}
- {{nowrap|1=A ⊆ (A ∪ B).}}
- {{nowrap|A ⊆ B}} if and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
{{nowrap|1=A ∪ B = B.}}
- {{nowrap|1=A ∪ A = A.}}
- {{nowrap|1=A ∪ ∅ = A.}}
Intersections
{{Main|Intersection (set theory)}}
A new set can also be constructed by determining which members two sets have "in common". The intersection of A and B, denoted by {{nowrap|A ∩ B,}} is the set of all things which are members of both A and B. If {{nowrap|1=A ∩ B = ∅,}} then A and B are said to be disjoint.
Examples:
- {{nowrap|1={1, 2} ∩ {red, white} = ∅.}}
- {{nowrap|1={1, 2, green} ∩ {red, white, green} = {green}.}}
- {{nowrap|1={1, 2} ∩ {1, 2} = {1, 2}.}}
Some basic properties of intersections:
- {{nowrap|1=A ∩ B = B ∩ A.}}
- {{nowrap|1=A ∩ (B ∩ C) = (A ∩ B) ∩ C.}}
- {{nowrap|A ∩ B ⊆ A.}}
- {{nowrap|1=A ∩ A = A.}}
- {{nowrap|1=A ∩ ∅ = ∅.}}
- {{nowrap|A ⊆ B}} if and only if
In logic and related fields such as mathematics and philosophy, if and only if is a biconditional logical connective between statements....
{{nowrap| 1=A ∩ B = A.}}
Complements
{{Main|Complement (set theory)}}
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 {{nowrap|A \ B}} (or {{nowrap|A − B}}), is the set of all elements which are members of A but not members of B. Note that it is valid to "subtract" members of a set that are not in the set, such as removing the element green from the set {{nowrap|{1, 2, 3};}} doing so has no effect.
In certain settings all sets under discussion are considered to be subsets of a given universal setIn mathematics, and particularly in set theory and the foundations of mathematics, a universe is a class that contains all the entities one wishes to consider in a given situation...
U. In such cases, {{nowrap|U \ A}} is called the absolute complement or simply complement of A, and is denoted by A′.
Examples:
- {{nowrap|1={1, 2} \ {red, white} = {1, 2}.}}
- {{nowrap|1={1, 2, green} \ {red, white, green} = {1, 2}.}}
- {{nowrap|1={1, 2} \ {1, 2} = ∅.}}
- {{nowrap|1={1, 2, 3, 4} \ {1, 3} = {2, 4}.}}
- If U is the set of integers, E is the set of even integers, and O is the set of odd integers, then E′ = O.
Some basic properties of complements:
- {{nowrap|1=A \ B ≠ B \ A.}}
- {{nowrap|1=A ∪ A′ = U.}}
- {{nowrap|1=A ∩ A′ = ∅.}}
- {{nowrap|1=(A′)′ = A.}}
- {{nowrap|1=A \ A = ∅.}}
- {{nowrap|1=U′ = ∅}} and {{nowrap|1=∅′ = U.}}
- {{nowrap|1=A \ B = A ∩ B′}}.
An extension of the complement is the symmetric differenceIn mathematics, the symmetric difference of two sets is the set of elements which are in either of the sets and not in their intersection. The symmetric difference of the sets A and B is commonly denoted by A\,\Delta\,B\,orA \ominus B....
, defined for sets A, B as
For example, the symmetric difference of {7,8,9,10} and {9,10,11,12} is the set {7,8,11,12}.
Cartesian product
{{Main|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:
- {{nowrap|1={1, 2} × {red, white} = {(1, red), (1, white), (2, red), (2, white)}.}}
- {{nowrap|1={1, 2, green} × {red, white, green} = {(1, red), (1, white), (1, green), (2, red), (2, white), (2, green), (green, red), (green, white), (green, green)}.}}
- {{nowrap|1={1, 2} × {1, 2} = {(1, 1), (1, 2), (2, 1), (2, 2)}.}}
Some basic properties of cartesian products:
- {{nowrap|1=A × ∅ = ∅.}}
- {{nowrap|1=A × (B ∪ C) = (A × B) ∪ (A × C).}}
- {{nowrap|1=(A ∪ B) × C = (A × C) ∪ (B × C).}}
Let A and B be finite sets. Then
- | A × B | = | B × A | = | A | × | B |.
Applications
Set theory is seen as the foundation from which virtually all of mathematics can be derived. For example, structuresIn abstract algebra, an algebraic structure consists of one or more sets, called underlying sets or carriers or sorts, closed under one or more operations, satisfying some axioms. Abstract algebra is primarily the study of algebraic structures and their properties...
in abstract algebraAbstract algebra is the subject area of mathematics that studies algebraic structures, such as groups, rings, fields, modules, vector spaces, and algebras...
, such as groupsIn mathematics, a group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity...
, fieldsIn abstract algebra, a field is a commutative ring whose nonzero elements form a group under multiplication. As such it is an algebraic structure with notions of addition, subtraction, multiplication, and division, satisfying certain axioms...
and ringsIn mathematics, a ring is an algebraic structure consisting of a set together with two binary operations usually called addition and multiplication, where the set is an abelian group under addition and a semigroup under multiplication such that multiplication distributes over addition...
, are sets closed under one or more operations.
One of the main applications of naive set theory is constructing relationsIn set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
. A relation from a domainIn mathematics, the domain of definition or simply the domain of a function is the set of "input" or argument values for which the function is defined...
A to a codomainIn mathematics, the codomain or target set of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation...
B is a subset of the Cartesian product A × B. Given this concept, we are quick to see that the set F of all ordered pairs (x, x2), where x is real, is quite familiar. It has a domain set R and a codomain set that is also R, because the set of all squares is subset of the set of all reals. If placed in functional notation, this relation becomes f(x) = x2. The reason these two are equivalent is for any given value, y that the function is defined for, its corresponding ordered pair, (y, y2) is a member of the set F.
Axiomatic set theory
{{Main|Axiomatic set theory}}
Although initially naive set theoryNaive set theory is one of several theories of sets used in the discussion of the foundations of mathematics. The informal content of this naive set theory supports both the aspects of mathematical sets familiar in discrete mathematics , and the everyday usage of set theory concepts in most...
, which defines a set merely as any well-defined collection, was well accepted, it soon ran into several obstacles. It was found that this definition spawned several paradoxes, most notably:
- Russell's paradox
In the foundations of mathematics, Russell's paradox , discovered by Bertrand Russell in 1901, showed that the naive set theory created by Georg Cantor leads to a contradiction...
—It shows that the "set of all sets which do not contain themselves," i.e. the "set" { x : x is a set and x ∉ x } does not exist.
- Cantor's paradox
In set theory, Cantor's paradox is derivable from the theorem that there is no greatest cardinal number, so that the collection of "infinite sizes" is itself infinite...
—It shows that "the set of all sets" cannot exist.
The reason is that the phrase well-defined is not very well defined. It was important to free set theory of these paradoxes because nearly all of mathematics was being redefined in terms of set theory. In an attempt to avoid these paradoxes, set theory was axiomatized based on first-order logicFirst-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
, and thus axiomatic set theory was born.
For most purposes however, naive set theoryNaive set theory is one of several theories of sets used in the discussion of the foundations of mathematics. The informal content of this naive set theory supports both the aspects of mathematical sets familiar in discrete mathematics , and the everyday usage of set theory concepts in most...
is still useful.
Principle of inclusion and exclusion
{{Main|Inclusion-exclusion principle}}
This principle gives us the cardinality of intersection of sets.
|A1 ∩ A2 ∩ A3 ∩ A4 ∩ ....... ....∩ An|=(|A1| + |A2| + |A3| +...+ |An|)-(|A1 ∩ A2| +|A2 ∩ A3| + ....+|An-1 ∩ An|) + .........+(−1)n-1(|A1 ∩ A2 ∩ A3 ∩.....∩ An|)
External links
{{Logic}}