Relations

Relations and Cartesian Products

• Ordered Pair: A pair consisting of a first and a second element is denoted as (a, b).

  • Ordered Nature: The order is significant, thus (a, b) ≠ (b, a) unless a = b.

  • Equality of Pairs: Two pairs (a, b) and (x, y) are equal if and only if a = x and b = y.

• n-tuple: An extension of a pair allowing for more than two elements.

  • Example: (a, b, c, d) is a 4-tuple.

  • Recursive Definition: Tuples can be recursively defined; for instance, (a, b, c, d) is represented as (a, (b, (c, d))).

• Cartesian Product: The Cartesian product of two sets X and Y, denoted as X × Y, is defined as the set of all ordered pairs formed by taking one element from X and one from Y.

  • Formal Representation:
    $X\cdot Y=\left\lbrace(x,y)|x\in X,y\in Y\right\rbrace$

• Definition for Tuples: For tuples, the Cartesian product can also be extended, for instance, X × Y × Z represents a 3-tuple.

• Alternative Notation:

  • The product X × X can be written as X², and X × X × X can be written as X³.

  • Quantifiers can be rewritten:
    $∀x∈X,y∈Y (. . .)$ can be written as $∀(x,y)∈X×Y (. . .)$

  • For existential quantification:
    $∃x∈X,y∈Y (. . .)$ can be written as $∃(x,y)∈X×Y (. . .)$

Relations

• Definition of Relation: A relation R between sets X and Y is defined as a set of pairs where $R=\left\lbrace{(x,y)|x\in X\land y\in Y\land P(x,y)}\rbrace\right.$

• Membership Condition: The relation R between x and y holds if and only if (x, y) is an element of R:
  $(x, y) \in R$

• Subset Relation: A relation R is a subset of the Cartesian product; denoted as
  $R\subseteq X\cdot Y$

• Example of Relation: For sets

  • Let X = {mary, john, fred} and Y = {fluffy, snowball, felix}.

  • The ownership relation R is given by:
    $R=\left\lbrace(mary,snowball),(john,fluffy),(fred,snowball)\right\rbrace$

  • Interpretation: In this case, Mary and Fred both own 'snowball', indicating they may share a household, while 'felix' is identified as a stray cat.

Sets in Relation

• Sets Defined in Relation: For R ⊆ X × Y, we have:

  • Set of Departure (X): The set from which elements originate in the relation.

  • Set of Destination (Y): The set into which elements are mapped.

  • Domain (D): The set of all x in X such that there exists a y in Y for which (x, y) is in R:
    $D=\left\lbrace x\in X|\exists y\in Y((x,y)\in R)\rbrace\right.$

  • Image (I): The set of all y in Y such that there exists an x in X for which (x, y) is in R:
    $I={\left\lbrace y\in Y|\exists x\in X((x,y)\in R)\right\rbrace}$

• Homogeneous Relation: A relation is homogeneous if the set of departure equals the set of destination, i.e., X = Y.

Properties of Homogeneous Relations

• Reflexivity:

  • A relation is reflexive if every element relates to itself.

  • Formally:
    $\forall x\in X((x,x)\in R)$

• Symmetry:

  • A relation is symmetric if for any elements x, y, if x relates to y, then y relates to x.

  • Formally:
    $∀x∈X,y∈X((x, y) ∈ R ⇒ (y, x) ∈ R)$

• Transitivity:

  • A relation is transitive if whenever x relates to y and y relates to z, then x relates to z.

  • Formally:
    $∀x∈X,y∈X,z∈X(((x, y) ∈ R ∧ (y, z) ∈ R) ⇒ (x, z) ∈ R)$

• Irreflexivity:

  • A relation is irreflexive if no element relates to itself.

  • Formally:
    $∀x∈X((x, x) 6∈ R)$

• Antisymmetry:

  • A relation is antisymmetric if x relates to y and y relates to x imply x equals y.

  • Formally:
    $∀x∈X,y∈X(((x, y) ∈ R ∧ (y, x) ∈ R) ⇒ x = y)$

• Connexity:

  • A relation is connex if for any two elements, at least one relates to the other.

  • Formally:
    $∀x∈X,y∈X((x, y) ∈ R ∨ (y, x) ∈ R)$

Types of Relations and Their Properties

• Equality (=):

  • Properties: Reflexive, Symmetric, Transitive.

• At most (≤):

  • Properties: Reflexive, Antisymmetric, Transitive, Connex.

• Less than (<):

  • Properties: Irreflexive, Antisymmetric, Transitive, Semi-Connex (connex when x ≠ y).

• Subset (⊆):

  • Properties: Reflexive, Antisymmetric, Transitive.

Understanding Relation Notation

• Relation Notation: Relations are often expressed as xRy to mean (x, y) ∈ R.

• Partial Function: A relation R is a partial function if for every element x in X, there is at most one (x, y) ∈ R.

  • Formal definition is:
    $∀x∈X,y∈Y,z∈Y (((x, y) ∈ R ∧ (x, z) ∈ R) ⇒ y = z)$

• Multi-valued Function: A relation R is multi-valued if for every element x in X, there is at least one (x, y) ∈ R.

  • Formal definition:
    $∀x∈X(∃y∈Y ((x, y) ∈ R))$

• Function: A relation R is a function if for every element x in X, there is exactly one (x, y) ∈ R.

  • Formal definition:
    $\forall x\in X(\exists^1y\in Y((x,y)\in R))$

Functions

• Common Symbolism: Letters such as f, g, h are frequently employed to denote functional relations. Instead of stating f ⊆ A × B, it is typically written as f: A → B.

• Functional Relations Definition: If f is a functional relation, it is conventional to represent it as f(a) = b instead of (a, b) ∈ f.

• Types of Functions:

  • Injective Functions: Defined such that
    $∀a∈A,b∈A(f(a) = f(b) ⇒ a = b)$

  • Surjective Functions: Ensures that
    $∀x∈X(∃a∈A(x = f(a)))$

  • Bijective Functions: Defined as a function that is both injective and surjective.
    $\forall x\in X(\exists^1a\in A(x=f(a)))$

Inverses and Composition of Functions

• Inverse of a Function: A relation f⁻¹ that contains (a, b) if and only if (b, a) ∈ f.

  • If f is bijective, then f⁻¹ is also a function.

  • If f is injective/surjective, then f⁻¹ is a partial/multi-valued function, respectively.

• Function Composition: If $f: A → B$ and $g: B → C$ , then the composition $g ◦ f: A → C$ is defined such that
  $(g \circ f)(x) = g(f(a))$

• Operations as Functions: An operation is considered a function of type $X^{n}\rightarrow X$ .

  • Binary Operations: Defined as
    $X\cdot X\rightarrow X$ such as +, ·, ×, ∧.

  • Alternate Representation: Usually written as
    $x \oplus y = z$ instead of $\oplus\left(x,y\right)=z$ or $\left(x,y,z\right)$ .

• Closure of a Set: A set X is defined as closed under an operation $f: Y → Z$ when $∀x∈X(f(x) ∈ X)$ , if for all x in X, the operation satisfies: $\forall(n,m)\in N^{2(n+m\in N)}$

  • Example: The result of adding two natural numbers is always a natural number.

  • Non-Closure Example: Natural numbers are not closed under subtraction since
    $3 - 5 \notin N$.

• Closure of a Set Under Operation: The closure of a set X under an operation ⊕ is the smallest superset of X which is closed under ⊕.

  • Example: The closure of natural numbers (N) under subtraction is the integers (Z).

• Transitive Closure of a Relation: The transitive closure S of a relation R is defined by:
  $(a,b)\in R\Rightarrow(a,b)\in S$ and $(a, b)∈S ∧ (b, c)∈S ⇒ (a, c)∈S$