Discrete Mathematics: Chapter 6, Functions & Equivalence Relations

Document Type

Book Chapter

Publication Date



Mathematics, Statistics, and Computer Science


functions, algebra, algorithms, set theory, binary system


Modern science and contemporary Western culture are unthinkable without high-level mathematics. Quantitative modes of thinking, mathematical ideas, algorithmic techniques, and symbolic reasoning permeate the way we conceptualize and interact with the world today. After number and its use in computation, the notion of function, usually expressed in terms of a symbolic formula, is probably the most pervasive mathematical idea used in scientific applications. Functions help formulate important causal connections between different types of measures in numerous scientific fields, and they provide a way to compare different algebraic structures in advanced mathematics.

Our interest in functions here will be different than it is in calculus. Calculus graphs functions and explores certain features of those graphs such as local extreme values or the area under a curve by making certain specialized function calculations. Here we will instead investigate some general algebraic features of functions that come up in various discrete mathematics applications as well as in more advanced areas of mathematics.


This material is no longer available for download. A revised, improved version is now available as a chapter of Introduction to Discrete Mathematics via Logic and Proof (see https://www.springer.com/us/book/9783030253578), published by Springer as part of their Undergraduate Texts in Mathematics series.

This document is currently not available here.