Relations & Functions (Quick Summary)

1. Relations

Linking data from one set to another (or to itself)

• Reflexive: Every element is related to itself (aRa)
• Symmetric: If a is related to b, then b must be related to a (aRb -> bRa)
• Transitive: If a is related to b and b is related to c, then a must be related to c (aRb ∧ bRc -> aRc)
• Equivalence Relation: A relation that has all 3 properties above

2. Functions

A special relation where one input (Domain) maps to exactly one output (Codomain)

• Injective (One-to-One): No two inputs map to the same output
• Surjective (Onto): Every element in the codomain is mapped to (none left unmapped)
• Bijective (One-to-One and Onto): Both Injective and Surjective (exact 1:1 pairing, allows finding an Inverse Function)
• Applications: Cryptography (encryption, Hash functions) and image data transformation