Relation

• Let and be sets. A Relation between and is a subset of .

  If two objects are in a relation we denote it as (read as is in an -relation with or )

  The order of the tuple in the relation is important

  • We denote the set of relations between and as

• An equivalence relation is a relation on the set such that the following properties are true

  • Reflexivity:
  • Symmetry:
  • Transitivity:

• An equivalence class of with respect to an equivalence relation on the set is a set such that

  It allows us to cluster different elements of the set into families.

• The diagonal relation is defined as the relation from such that

• A partial ordering is a relation defined for pairs of elements of such that the following are true for certain elements.

  • Reflexivity: .
  • Antisymmetry:
  • Transitivity:

Functions §

• A function is a mapping between two sets and that associates each element in to one element in . This is denoted .

  • and are called the domain and codomain respectively.
  • We denote and such that . This defines a mapping. We say that is the value of the function at .
  • The graph of a function is the set of ordered pairs
    Thus, the graph of a function defines a relation with the functional property that there is one and only one such that is in the graph.
  • The domain, codomain, and graph of a function uniquely determine the function. Conversely, the function uniquely determines the domain, codomain and graph.

• Most functions in mathematics preserve some kind of structure.

• The image / range of under a subset is defined as the set

  If contains a single element , we denote the image of as ¹

  If we do not specify , we implicitly assume we have so that the image of in this case is

• The pre-image of under a subset is defined as the set

  If contains a single element , then we say that is a pre-image of where .

• We say that the pre-image of in its entirety is

  Likewise the image of is .

• A function is injective / one-to-one if every element of the domain is mapped to at most one element in the codomain. More formally

  Or the contrapositive

• A function is surjective / onto if every element of the codomain is the image of at least one element in the domain. More formally

  Equivalently, a function is surjective if

• A function is bijective / one-to-one correspondence if it is both injective and surjective. Specifically, every element in the domain is mapped to one and only one element in the codomain.

• Let and . The composition of with is a function defined as where

  We denote this as .

  • The composition of two injections is an injection
  • The composition of two surjections is a surjection
  • The composition of two bijections is a bijection.

• The inclusion map is the function that sends to , treated as an element of .

• If are sets, then the cartesian product has associated projection functions denoted where if then

  That is, we disregard all but the -th element in the ordered tuple.

• Let be sets and be functions. The function is defined by

• Let be sets and be functions. Then the Cartesian product of two functions is is defined by

• Let and . The restriction of to , denoted is the function defined as

  It can also be described as the composite where is the inclusion function.

  We say that extends .

• If Then is called the corestriction of the function to where is the inclusion function.

• A function’s restriction makes the domain smaller. A function’s corestriction makes the codomain smaller.

Theorems §

• If , then .

  • Proof: Take . Then such that But also since . Therefore as well.

• (Schroeder-Bernstein Theorem) Let and be sets. If there exists injective mappings and , then there exists a bijective mapping .

  Proof (Konig):

  Assume without loss of generality that and are disjoint otherwise we may label some of the elements of and to make them different.

  Consider the sequence for and .

  We show that each and appears exactly once in this sequence.

  It follows that if or appeared in more than one such sequence, all elements to their left and to their right must be the same (by the injectivity of and ). As such, these sequences form a partition of and . Call this sequence a family of .

  This implies, that we only need to consider a bijective mapping for each family.

  Let be a family. Now, for each element in this sequence, any of these cases may happen. Define the bijection according to these cases.

1. The sequence ends with an element in . In which case, define .
2. The sequence ends with an element in . In which case define
3. The sequence has the same endpoints (i.e., it will eventually lead back to ). In which case, either or will do for .
4. The sequence is infinitely long. In which case, either or will do.

Links §

• Set Theory
• Category Theory for Computing Sciences by Barr and Wells

Footnotes §

1. We sometimes notate this as if the context is unclear ↩