Relations

•  arrow diagram


  a graphical way to specify a relation using arrows
•  matrix representation


  representation of relation R between A and B in a rectangular array if numbers |A| rows and |B| columns. Each row corresponds to an element of A and each column corresponds to an element of B
• Example of matrix representation


  .

  
• Self-Loop


   An element that is related to itself is indicated by an arrow, the arrow  leaves the element and then turns around to point to itself again
• Reflexive binary relation


  every element in the set must be related to itself
• Anti-reflexive Binary Relation


  every element in the set must not be related to itself
• x is related to y if y = x + 1 (is this reflexive or anti-reflexive or neither

  Anti-reflexive
• X is related to y if y = 1/x ( is this reflexive or anti-reflexive or neither)

  Neither
• x is related to y if [x] <= [y] ( is this reflexive or anti - reflexive or niether)

  Reflexive
• Symmetric binary relations


  if for every pair of elements x and y in the domain: xRy and yRx are both true OR neither xRy nor yRx is true
• x is related to y if x/y = 2 (is this symmetric or not symmetric)

  Not Symmetric
• x is related to y if y = 1/x (is this symmetric or not symmetric)

  Symmetric
• Relation


  Set of pairs that is a subset of the product of two sets A and B
• Types of Relation Representation

  Graphs

  Arrow Diagrams

  Matrix
• Current domain and range

  Domain and range that may change over time
• Declared domain and range

  domain and range that represents all possibilities
• Functions

  Describe the relation between the domain and range
• Partial Functions

  Relation R from domain A to range B• For every a in A, there is at most one b in B such that aRb
• Total Functions

  Relation R from domain A to range B• For every a in A, there is one b in B such that aRb
• Injection

  For every element a in A, there is a distinct element b in B such that f(a) = b.• Aka one-to-one function
• Surjection

  For every b in B, there is at least one a in A such that f(a) = b.• Does not require a unique domain element• Aka onto
• Bijection

  Must be injective AND surjective AND no two elements of Acan map to the same element in B
• What are the two types of functions

  Partial and Total
• One-To-One Correspondence

  + For every element a in A, there is a distinct element b in B suchthat F(a) = b.+ For every b in B, there is at least one a in A such that F(a) = b.+ For no b in B are there two elements a1 and a2 in A such thatF(a1) and F(a2) are both b.
• Inverse


  If a function f() maps a to b then the inverse f-1() would map b to a
• Composition


  If a function f() maps a to b and function g() maps b to c then the composition of g() with f() maps a to c• g o f(a) is the same as g(f(a))
• Identify


  If a function f() maps a to b and the inverse f-1() maps b to a,then the identity maps a to a• f-1 o f(a) is the same as f-1(f(a))
• What are the 6 Binary Relation Properties

  + Transitivity

  + Reflexivity

  + Anti-reflexivity

  + Symmetry

  + Anti-symmetry

  + Equivalence
• Transitivity


  A relation R is transitive if• aRb and bRc, then aRc must also exist
• Reflexivity


  A relation R is reflexive if it contains the pair (a,a)• aRa• Must have one loop for each element in the domain
• Anti-Reflexivity


  A relation R is anti-reflexive if it does not contain any pair (a,a)• aRa• There must be no self-loops for any domain element
• Symmetry

  R is symmetric if for every aRb there exists a bRa
• Anti-Symmetric

  R is anti-symmetric if both aRb and bRa are true onlywhen a = b
• Equivalence Relation


  R is an equivalence relation if R is symmetric, reflexive, and transitive
• Finite set


  A set that does not have a one-to-one correspondence with any of its proper subsets
• Infinite set


  A set that has a one-to-one correspondence with at least one of its proper subsets
• Equipotent

  If two sets cardinalities are equal
• Countable


  A set which is equipotent to some subset of the set of naturalnumbers
• Uncountable


  A set who’s cardinality is greater than the cardinality of the set of natural numbers
• Example of Countably Finite


  {1,2,3}