Table of contents
1.1 Sets
A set is a collection of objects.
Example L = {a,b,c,d}
The objects comprising a set are called its elements or members.
In a set, we do not distinguish repetitions of the element.
Example: {red, blue, red} = {red, blue}
Similarly, the order of the elements is not important.
Two sets are equal if and only if they have the same elements.
The elements of a set need not to be related.
A set with only one element is called a singleton.
An infinite set is denoted by writing N = {1,2,3,..}
Another way to specify a set is by referring to other sets and to properties that elements may or may not have.
Example: I = {1,3,9} and G = {3,9}
G = {x: x Î I and x is greater than 2}
A set A is a subset of a set B (A Í B) if each element of A is also an element of B. Any set is a subset of itself. If A is a subset of B, but A is not the same as B, we say A is a proper subset of B and write A Ì B.
The union of two sets is that set having as elements the objects that are elements of at least one of the two given sets, and possibly of both.
The intersection of two sets is the collection of all elements the two sets have in common.
The difference of two sets A and B, denoted by A – B, is the sets of all elements of A that are not elements of B.
If A, B and C are sets, the following laws hold:
Idempotency A È A = A
A Ç A = A
Commutativity A È B = B È A
A Ç B = B Ç A
Associativity (A È B) È C = A È (B È C)
(A Ç B) Ç C = A Ç (B Ç C)
Distributivity (A È B) Ç C = (A Ç B) È (B Ç C)
(A Ç B) È C = (A È B) Ç (B È C)
Absorption (A È B) Ç A = A
(A Ç B) È A = A
DeMorgan’s law A – (B È C) = (A – B) Ç (A – C)
A – (B Ç C) = (A – B) È (A – C)
Two sets are disjoint if they have no elements in common, that is, if their intersection in empty.
It is possible to form intersections and unions of more than two sets. If S is any collection of sets, we write U S for the set whose elements are the elements of all sets in S.
The collection of all subsets of A is itself a set, called the powerset of A and denoted 2A.
A partition of a nonempty set A is a subset p of 2A such that Æ is not an element of p and such that each element of A is in one and only one set of p.
Example: { {a,b},{c},{d} } is a partition of {a,b,c,d}
but { {b,c},{c,d} } is not.
1.2 Relations and Functions
We write the ordered pair of two objects a and b as (a,b). a and b are called the components of the ordered pair (a,b). The ordered pair (a, b) is not the same as the set {a,b}. First, the order matters: (a,b) is different from (b,a), whereas {a,b} = {b,a}. Second, the two components of an ordered pair need not be distinct.
Ordered pairs are used to distinguish two parts of a pair in a relation.
The carthesian product of two sets A and B, denoted by AxB, is the set of all ordered pairs (a,b) with aÎA and bÎB.
A binary relation on two sets A and B is a subset of AxB.
Example: {(1,b),(1,c),(3,d),(9,d)} is a binary relation on {1,3,9} and {b,c,d}
More generally, let n be any natural number. Then if a1, …, an are any n objects, not necessarily distinct, (a1, …, an) is an ordered tuple: for each i = 1, …, n, ai is the ithcomponent of (a1, …, an).
Comments