For the computer science term, see Sets (ADT).
A set is an unordered group of items (called elements). For example, is a set of animals, is a set of even numbers, and is a set of letters. Though sets are pretty simple data structures, they are important for understanding concepts in combinatorics, probability, and number theory.
A set is an unordered group of elements denoted by a sequence of items (separated by commas) between curly braces "" and "".
What does it mean to be unordered?
Sets are not organized in any particular way. For example, the set appears to be the set of ordered numbers between 1 and 5, but this set is actually equivalent to . The order of elements in a set does not matter. Two sets are equal if they contain all of the same elements.
Repeated elements make no difference in a set. is equal to . In fact, sets are generally not written to include repeated elements.
There are several useful operations one can use to combine, compare, and analyze sets.
Union: The union of two sets, denoted (which is called a cup), refers to the set of all the elements that are in at least one of the two sets. For example, In Boolean logic, union is expressed as a logical OR.
Intersection: The intersection of two sets, denoted (which is called a cap), refers to the set of the elements that are in both sets. For example, In Boolean logic, intersection is expressed as a logical AND.
Complement (Absolute): Denoted , the absolute complement refers to the set of all the elements that are not in a set. If we consider the universal set, , as the set of all integers, would represent all integers except for 1, 2, and 3. In Boolean logic, complement is expressed as a logical NOT.
Complement (Relative): Relative complement, denoted , refers to the set of elements that are in the first set but not in the second. For example, Relative complement can also be expressed by the minus sign, and thus
Symmetric Difference: Symmetric difference, denoted , refers to the set of elements which are in one of the two sets but not both. For example, In Boolean logic, symmetric difference is expressed as a logical XOR.
The symbol refers to the union of the two sets.
Given the following two sets
if what is
From we know that both sets and must have as an element. Therefore, for set we have
If the value of is 1, set is
If the value of is 3, set is
Thus, the value of that satisfies is
The symbol denotes symmetric difference, which means the set of elements which are in one of the two sets but not both.
De Morgan's laws are useful for showing equivalencies, transforming, and simplifying logical expressions.
- De Morgan's First Law:
It states that the complement of the union of two sets is the intersection of their complements. For two sets and
In Boolean logic, De Morgan's first law is expressed as
- De Morgan's Second Law:
It states that the complement of the intersection of two sets is the union of the complements. Specifically,
In Boolean logic, De Morgan's second law is expressed as: .
Given the following, use De Morgan's second law to determine
- where is the set of all possible values for this problem
De Morgan's second law is Since we are looking for , we will first determine the left side of the equation, .
To find , determine is the set of elements that are in both and so
To find , compare the elements in with the elements in , and the elements in will be the elements that are in but not in . So, .
We know from De Morgan's second law that = . In other words, elements that are not in both and must either be missing from or (or both).
Examine for yourself to verify that elements in are missing from either or or both.
Here are some important concepts and terms about sets:
Universal Set: Denoted a universal set is the set of all possible elements for a particular problem. For example, if a problem deals only with positive, nonzero integers, .
Empty/Null Set: Denoted by or , a set is said to be null or empty if it does not contain any elements. For example, if is the set of all integers that satisfy then the set has no elements, and thus
Subsets: If every element of a set is also a member of the set then we say that is a subset of For example if and then is a subset of or When two sets are equal, they are subsets of each other.
Cardinality: The cardinality of a set written as is the number of distinct elements in For example, if is the set of all the letters in "Mississippi", then and hence
Inclusion-Exclusion Principle: The inclusion-exclusion principle states that any two sets and satisfy In other words, to get the size of the union of sets and , we first add (include) all the elements of , then we add (include) all the elements of , and then we remove (exclude) the elements in their intersection , since those elements were counted twice i.e. once for and once for For a concrete example, let and , which gives . Then , , and . By the inclusion-exclusion principle, which we can verify directly by counting the elements of Note that the elements in the intersection (4 and 5) were counted once in and once in , necessitating their exclusion.
For this problem, the universal set is
and its three subsets and are as follows:
Then what is
The symbol means the set of all elements that are not in Since the set is