Relations, Functions, and Morphisms

Mappings allow us to transition from static sets to dynamic interactions. They allow us to compare sets, group elements by shared properties, and transform data while preserving structure.

Binary Relations

A Binary Relation $R$ between sets $A$ and $B$ is a subset of the Cartesian product $A \times B$ . If $(a, b) \in R$ , we write $aRb$ .

A relation $R$ on set $A$ can be:

Reflexive: $aRa$ .
Symmetric: $aRb \implies bRa$ .
Transitive: $aRb \land bRc \implies aRc$ .

Interactive Lab

def check_properties(elements, relation):
  reflexive = all((e, e) in relation for e in elements)
  symmetric = all((b, a) in relation for (a, b) in relation)
  transitive = all((a, c) in relation 
                   for (a, b1) in relation 
                   for (b2, c) in relation if b1 == b2)
  return {"Reflexive": reflexive, "Symmetric": symmetric, "Transitive": transitive}

S = {1, 2, 3}
R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}
print(f"Set: {S}, Relation: {R}")
print(f"Properties: {check_properties(S, R)}")

python

1def check_properties(elements, relation):

2 reflexive = all((e, e) in relation for e in elements)

3 symmetric = all((b, a) in relation for (a, b) in relation)

4 transitive = all((a, c) in relation

5 for (a, b1) in relation

6 for (b2, c) in relation if b1 == b2)

7 return {"Reflexive": reflexive, "Symmetric": symmetric, "Transitive": transitive}

9S = {1, 2, 3}

10R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}

11print(f"Set: {S}, Relation: {R}")

12print(f"Properties: {check_properties(S, R)}")

Equivalence Relations and Partitions

A relation that is reflexive, symmetric, and transitive is an Equivalence Relation. It partitions a set into disjoint Equivalence Classes.

Interactive Lab

def get_equivalence_classes(elements, relation):
  classes = []
  seen = set()
  for e in elements:
      if e not in seen:
          # Class [e] = {x | xRe}
          cls = {x for x in elements if (x, e) in relation}
          classes.append(cls)
          seen.update(cls)
  return classes

print(f"Equivalence Classes: {get_equivalence_classes(S, R)}")

python

1def get_equivalence_classes(elements, relation):

2 classes = []

3 seen = set()

4 for e in elements:

5 if e not in seen:

6 # Class [e] = {x | xRe}

7 cls = {x for x in elements if (x, e) in relation}

8 classes.append(cls)

9 seen.update(cls)

10 return classes

12print(f"Equivalence Classes: {get_equivalence_classes(S, R)}")

Classification of Mappings

A function $f: A \to B$ is a relation where every input has exactly one output.

Injection (One-to-One): $f(x) = f(y) \implies x = y$ .
Surjection (Onto): Range equals Codomain.
Bijection: Both injective and surjective (invertible).

Interactive Lab

def classify_function(domain, codomain, f_map):
  # f_map is a dict {x: y}
  injective = len(set(f_map.values())) == len(f_map)
  surjective = set(f_map.values()) == codomain
  
  if injective and surjective: return "Bijection"
  if injective: return "Injection"
  if surjective: return "Surjection"
  return "General Function"

A = {1, 2, 3}
B = {'a', 'b', 'c'}
f = {1: 'a', 2: 'b', 3: 'c'}
print(f"Function mapping: {f}")
print(f"Classification: {classify_function(A, B, f)}")

python

1def classify_function(domain, codomain, f_map):

2 # f_map is a dict {x: y}

3 injective = len(set(f_map.values())) == len(f_map)

4 surjective = set(f_map.values()) == codomain

6 if injective and surjective: return "Bijection"

7 if injective: return "Injection"

8 if surjective: return "Surjection"

9 return "General Function"

11A = {1, 2, 3}

12B = {'a', 'b', 'c'}

13f = {1: 'a', 2: 'b', 3: 'c'}

14print(f"Function mapping: {f}")

15print(f"Classification: {classify_function(A, B, f)}")

Morphisms: Structural Preservation

In abstract algebra, we study functions that preserve operations:

Homomorphism: Preserves algebraic structure $(f(a \cdot b) = f(a) \cdot f(b))$ .
Isomorphism: A bijective homomorphism.

A relation that is reflexive, symmetric, and transitive is known as what?

Pre-images and Images

For a subset $T \subseteq B$ , the Pre-image is $f^{-1}(T) = \{x \in A \mid f(x) \in T\}$ .

Relations, Functions, and Morphisms

Relations, Functions, and Morphisms

Binary Relations

Equivalence Relations and Partitions

Classification of Mappings

Morphisms: Structural Preservation

A relation that is reflexive, symmetric, and transitive is known as what?

Pre-images and Images

If f: A -> B is an injection, and |A| = |B| is finite, what must f also be?