Mathematics - Discrete Mathematics

Mathematics - Discrete Mathematics - Sets and Relations

Introduction

Hey it's a me again @drifter1!

Today we continue with Mathematics, and more specifically the branch of "Discrete Mathematics", in order to get into Sets and Relations.

So, without further ado, let's get straight into it!

Cartesian Product of Sets

The Cartesian Product of two non-empty sets A and B (in that order), denoted by A x B, is the set of all ordered pairs, where the first member belongs to set A and the second member belongs to set B.

In set builder notation:

(Binary) Relation

Each subset of A x B is called a (binary) relation R from set A to B. As such, if (x, y) ∈ R and R ⊆ A x B then x is related to y by R. If A = B then R ⊆ A x A is known as a relation on A.

Function

A relation R is called a function when there's exactly one output for each input. In other words, there have to be no ordered pairs with the same first member and different second member.

Example

For example, if A = {1, 3, 5} and B = {2, 4, 6} then the following would be valid relations for the cartesian product A x B:

R₁ = { (1, 2), (1, 4), (3, 2), (3, 6), (5, 4) }
R₂ = { (1, 4), (1, 6), (3, 4), (5, 2) }
R₃ = { (1, 2), (3, 6), (5, 2) }

Only the last one is also a function!

Relation Terminology

A relation is commonly denoted as R : A → B.

Domain and Range

The set of all first members in the ordered pairs of R (the inputs) is known as the domain of relation, and commonly denoted by DOM (R).

The set of all second members in the ordered pairs of R (the outputs) is known as the range of the definition, and commonly denoted by RAN (R).

As such, if R : D → S, D would be the domain of definition and S the range of the relation.

Types and Properties

Relations are classified into types depending on the properties they satisfy.

A relation R on set A is:

Reflexive : (x, x) ∈ R for every x ∈ A
Irreflexive : (x, x) ∉ R for every x ∈ A
Symmetric : (x, y) ∈ R ⟺ (y, x) ∈ R for every x ∈ A, y ∈ A
Antisymmetric : (x, y) ∈ R ⟺ (y, x) ∈ R only when x = y
Asymmetric : (x, y) ∈ R ⟺ (y, x) ∉ R for every x ∈ A, y ∈ A
Transitive : (x, y) ∈ R and (y, z) ∈ R ⟺ (x, z) ∈ R
Identity or Equivalence: Reflexive, Symmetric and Transitive
Partial Order : Reflexive, Antisymmetric and Transitive

Example

Consider the set A = { 1, 2, 3 }.

Valid relations of the form R : A → A are:

R₁ = { (1, 1), (2, 2), (3, 3) }, which is reflexive
R₂ = { (1, 2), (1, 3), (2, 1), (3, 1) }, which is symmetric

Function Terminology

A function is commonly denoted as f : A → B.

Domain, Co-Domain and Range

Each element from set A is uniquely associated to an element in set B. The set A is called the Domain of the function, whilst the set B is called the Co-Domain of the function. The range of a function is the image of the domain, and thus a subset of the co-domain.

Types and Properties

Functions are classified into types depending on properties they satisfy.

As such, a function f is:

Injective : Each element of the Domain set is connected to an element of the Co-Domain Set
Surjective : Each element of the Co-Domain set has a pre-image from the Domain Set (the co-domain and range are equal)
Bijective : Both Injective and Surjective

The set cardinalities will be related in the following way: