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

• 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.

• 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

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

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

  • 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 if every element of the domain is mapped to at most one element in the codomain. More formally

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

• A function is bijective 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.

• If , then .

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

Theorems §

• (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

Footnotes §

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