Set Theory — Functions

Describing Behavior With Bijectives, Surjectives, & Injectives

February 9, 2019

Code & Design

Today we’re going to expand on functions within the world of set theory. Similar to previous concepts introduced, the nomenclature for standard functions within sets is slightly different than other branches of math, & therefore requires reviewing. There are quite a few terms to introduce, so let’s jump right in! This first table of function terms below mirrors the idea of domain, range, & output for a standard function:

Image for post

A function in set theory world is simply a mapping of some (or all) elements from Set A to some (or all) elements in Set B. In the example above, the collection of all the possible elements in A is known as the domain; while the elements in A that act as inputs are specially named arguments. On the right, the collection of all possible outputs (also known as “range” in other branches), is referred to as the codomain; while the collection of actual output elements in B mapped from A is known as the image.

Nothing too complicated thus far, only a new way of defining the parameters of functions with. Next, we’ll cover how to describe the behaviors of these mapping functions with common function types.

Injections, Surjections & Bijections

In Set Theory, three terms are commonly used to classify set mappings: injectives, surjectives & bijectives. These terms, unfortunately, have a few different names that amplify the confusion —we’ll therefore first review each definition, then, afterwards, step through some visual examples. All three terms describe the manner in which arguments & images are mapped:

  • A function is injective (a.k.a “one-to-one”) if each element of the codomain is mapped to by at most one element of the domain.
  • A function is surjective (a.k.a “onto”) if each element of the codomain is mapped to by at least one element of the domain. (That is, the image and the codomain of the function are equal.)
  • A function is bijective (a.k.a “one-to-one & onto,” “one-to-one correspondence”) if each element of the codomain is mapped to by exactly one element of the domain.

The proverbial cherry-on-top of the complex nomenclature here extends to the possible connotations of the words “injective,” “surjective,” & “bijective.” While used to describe a function (mapping), the former connotation is correct; however, it’s also correct to identify functions(mapping) purely by these characteristics. So a function with injective behavior is called an injection, a function with surjective behavior is called a surjection, & finally, a function with bijective behavior is called a bijection.

Re-read the bullet points above. A bijection is simply a function that fills both previous requirements — that is, the function is both injective & surjective. An injective function need not be surjective, & a surjective function need not be injective. Moving on to a visual example, these three classifications lead to set functions following four possible combinations of injective & surjective features summarized below:

Image for post

And there we go! We now possess an elementary understanding of the common types of mappings seen in the world of sets. This is by no means, however, the end of the journey as we kept this review to high-level introductions — quite opposite this is the very beginning.

The fundamentals of set theory are key to unlocking an understanding in higher-branches of mathematics. In order to continue our ascend in the many branches, we’ll next digest one of the absolutely most ground-breaking theories in all history of math by leveraging our set theory knowledge: the Zermelo-Fraenkel set theory.