Discrete Structures short notes: Relations and Functions

The notes below are condensed from ideas from Kenneth Rosen’s Discrete Mathematics and its applications (Chapter 9: Relations, Chapter 2.3: Functions), UTMSPACE Discrete structures subject notes, and my own notes.

Relations

  • Relation, R is a subset of Cartesian product A x B. Elements of R is called ordered pairs.
  • e.g. R = {(squirrel, mammal), (human, mammal), (kangaroo, mammal), (shark, fish), (salmon, fish), (parrot, bird)}.
  • a R b, means (a,b) ordered pair is an element of R, where \mbox{a}\in\mbox{A}, and \mbox{b}\in\mbox{B}.
  • Relations can be represented in set, arrow diagram, zero-one matrix, and diagraph.
  • Reflexive relation – Relation on A is reflexive if every element of A is related to itself. In diagraph, each elements of the A will have a loop to itself, alternatively, we can say that each vertex has a loop to itself. In zero-one matrix, the main diagonal will all be 1.
  • Irreflexive – All element of A is not related to itself. There is no loop to itself for every element of A. In zero-one matrix, the main diagonal will all be 0.
  • Not reflexive – There exists some element of A that is related to itself. There is some element of A that loop to itself. In zero-one matrix, the main diagonal have some 1s and 0s.
  • Symmetric – if (a,b) element of R, (b,a) is also element of R, for every a,b. In matrix, the Mij value is same as Mji value, main diagonal can be any value. Alternatively, the transpose of the matrix must be same as itself. Diagraph, if there is an edge from a to b, there is an edge from b to a.
  • Antisymmetric – if (a,b) element of R, (b,a) is not element of R, for every a,b. In matrix, the Mij value is opposite of Mji value, main diagonal can be any value. Diagraph, if there is an edge from a to b, there is no edge from b to a. There must be some loop to ownself.
  • Asymmetric – if it is both antisymmetric and irreflexive. In matrix, the Mij value is opposite of Mji value, main diagonal are all 0s. Diagraph, if there is an edge from a to b, there is no edge from b to a. There is no loop to ownself.
  • Not symmetric. In matrix, the Mij value sometimes is the same, sometimes is opposite of Mji value, main diagonal can be any value. Diagraph, if there is an edge from a to b, sometimes there is an edge from b to a. There may be loop to ownself.
  • Transitive. Can only shown by matrix. Product of boolean. if after product of matrix, the result is same as original matrix, it is transitive.
  • Equivalence relations. If it is reflexive, symmetric, and transitive.

Functions

  • Function, all preimage can only have one image.
  • Domain, codomain, image, preimage, range.
  • It is a different function if the domain or codomain changes. e.g. domain change from Z (integers) to Z+ (positive integers).
  • One-to-one function, all image can only have one preimage.
  • Onto function, all elements in codomain has at least one preimage.
  • Bijection/ one-to-one correspondence, both one-to-one and onto.
  • Example of one-to-one but not onto function, onto but not one-to-one function.
  • Inverse function – only for bijection.
  • Composition of functions – (f ◦ g)(a) = f (g(a)).

Leave a Reply