SETS

• A set is a well-defined collection of objects called elements.
• Upper case letters are usually used to name sets.
• A set A can be commonly described in three ways, by

  • descriptive method uses a short verbal statement to describe a set.
• • listing (roster) method describes the set by listing all the elements between braces and separated by commas (note: in enumerating the elements of a certain set, each element is listed only once and the arrangement of elements in the list is immaterial).
• • set-builder notation uses a variable (a symbol, usually a letter, that can represent different elements of a set), braces, and a vertical bar I that is read as "such that". This is usually used when the elements are too many to list down.
• For future discussion, we will use the following notations:

  • N for the set of natural or counting numbers (positive integers): {1, 2, 3, 4, ...}
  • Z for the set of integers: {... − 4, −3, −2, −1, 0, 1, 2, 3, ...}
  • Q for the set of rational numbers: {a/b | a, b ∈ Z, b 6 ≠ 0}
  • R for the set of real numbers
• A set with no elements is called an empty set or null set. The symbols used to represent the empty set are {} or φ.
• A set with only one element is called a unit set or a singleton.
• A set A is said to be finite if it is possible to list down all the elements of A in a list. Otherwise, A is said to be infinite.
• If A is finite, the cardinality of A is the number of elements of A, which is denoted by n(A).
• Two sets A and B are equal (written A = B) if they have exactly the same members or elements. Two finite sets A and B are said to be equivalent (written A ∼= B) if and only if they have the same number of elements, that is, n(A) = n(B).
• Equal sets are necessarily equivalent but equivalent sets need not be equal.
• Two sets have a one-to-one correspondence of elements if each element in the first set can be paired with exactly one element of the second set and each element of the second set can be paired with exactly one element of the first set.
• Two sets are equivalent if you can put their elements in one-to-one

  correspondence.
• The universal set for a given situation, written as U, is the set of all objects that are reasonable to consider in that situation.
• The complement of a set A, written as A' is the set of all elements in the universal set that are not in A. That is, A' = { x | x ∈ U and x ∈/ A }.
• If every element of a set A is also an element of a set B, then A is called a subset of B, written as A ⊆ B.
• If a set A is a subset of a set B and is not equal to B, then we call A as a

  proper subset of B, and write A ⊂ B. That is, A ⊆ B and A 6 ≠ B.
• The set containing all the subsets of a set S is called power set of S, denoted as P(S).
• • Every set is a subset of itself. That is, for any set A, A ⊆ A.
  • An empty set is a subset of every set. That is, for any set A, ∅ ⊆ A.
  • The symbol 6 ⊂ is used to indicate that a set is not a proper subset and 6 ⊆ is used to indicate that a set is not a subset.
• If a finite set has n elements, then the cardinality of its power set is 2n
• The intersection of two sets A and B, written as A ∩ B, is the set of all

  elements that are in both sets. That is, A ∩ B = {x | x ∈ A and x ∈ B}.
• The union of two sets A and B, written as A ∪ B, is the set of all elements

  that are in either set A or set B (or both). That is, A ∪ B = {x | x ∈ A or

  x ∈ B}.
• The difference of two sets A and B, written as A\B or (A − B), is the set

  of all elements in A that are not in B. That is, A\B = {x | x ∈ A and x ∈/ B}.

  A\B = A ∩ B'
• • If the intersection of two sets is the empty set, the sets are said to be disjoint.
  • n(A ∪ B) = n(A) + n(B) − n(A ∩ B)
  • A' = U\A
  • A\B 6 ≠ B\A
• Let A, B ⊆ U. The cartesian product (cross product) of A and B, is the set

  defined by A × B = {(x, y) | x ∈ A and y ∈ B}.
• A relation R on A 6= ∅ is a subset of A × A. In symbols, R ⊆ A × A. If

  (a, b) ∈ A, then we say “a is related to b”, denoted by a R b, if and only if

  (a, b) ∈ R.
• A relation R is said to be reflexive if for every a ∈ A, (a, a) ∈ R.
• A relation R is said to be symmetric if (a, b) ∈ R implies (b, a) ∈ R.
• A relation R is said to be anti-symmetric if (a, b) and (b, a) ∈ R implies a = b.
• A relation R is said to be transitive if (a, b) and (b, c) ∈ R implies (a, c) ∈ R.
• A relation R is said to be an equivalence relation if and only if R is reflexive, symmetric, and transitive.
• A relation R is said to be a partial order if and only if R is reflexive, anti-symmetric, and transitive.