🤔Mathematical Logic Unit 7 – Relations and Functions

Key Concepts and Definitions

• Relations define a connection or association between elements of two sets
• A relation from set A to set B is a subset of the Cartesian product A × B
• The domain of a relation is the set of all first elements (x-coordinates) in the ordered pairs
• The range of a relation is the set of all second elements (y-coordinates) in the ordered pairs
• Functions are special types of relations where each element in the domain maps to exactly one element in the codomain
• The codomain of a function is the set of possible output values
• The image of a function is the set of actual output values produced by the function

Types of Relations

• Reflexive relations have every element related to itself ($(a, a)$ is in the relation for all $a$ in the set)
• Symmetric relations have the property that if $(a, b)$ is in the relation, then $(b, a)$ is also in the relation
• Transitive relations follow the rule that if $(a, b)$ and $(b, c)$ are in the relation, then $(a, c)$ is also in the relation
• Equivalence relations are reflexive, symmetric, and transitive (congruence modulo n, similarity of triangles)
• Partial order relations are reflexive, antisymmetric, and transitive (less than or equal to $\leq$ on real numbers)
• Total order relations are partial order relations where every pair of elements is comparable (standard order $\leq$ on integers)
• Strict order relations are irreflexive, asymmetric, and transitive (strict inequality $<$ on real numbers)

Properties of Relations

• Reflexivity: A relation R on a set A is reflexive if $(a, a) \in R$ for all $a \in A$
• Symmetry: A relation R on a set A is symmetric if $(a, b) \in R$ implies $(b, a) \in R$ for all $a, b \in A$
• Transitivity: A relation R on a set A is transitive if $(a, b) \in R$ and $(b, c) \in R$ imply $(a, c) \in R$ for all $a, b, c \in A$
• Antisymmetry: A relation R on a set A is antisymmetric if $(a, b) \in R$ and $(b, a) \in R$ imply $a = b$ for all $a, b \in A$
• Irreflexivity: A relation R on a set A is irreflexive if $(a, a) \notin R$ for all $a \in A$
• Asymmetry: A relation R on a set A is asymmetric if $(a, b) \in R$ implies $(b, a) \notin R$ for all $a, b \in A$
• Connectivity: A relation R on a set A is connected if for all $a, b \in A$, either $(a, b) \in R$ or $(b, a) \in R$

Functions as Special Relations

• Functions are relations that assign a unique output to each input
• For every element $x$ in the domain, there is exactly one element $y$ in the codomain such that $(x, y)$ is in the function
• Injective (one-to-one) functions have distinct elements in the domain mapping to distinct elements in the codomain
• Surjective (onto) functions have every element in the codomain being mapped to by at least one element in the domain
• Bijective functions are both injective and surjective (one-to-one correspondence between domain and codomain)
• The inverse of a bijective function $f$, denoted as $f^{-1}$, maps each element $y$ in the codomain to the unique element $x$ in the domain such that $f(x) = y$

Representing Relations and Functions

• Relations can be represented using sets of ordered pairs, tables, graphs, or matrices
• Functions can be represented using equations, tables, graphs, or sets of ordered pairs
• The graph of a relation is the set of points $(x, y)$ in the Cartesian plane such that $(x, y)$ is in the relation
• The graph of a function is the set of points $(x, y)$ in the Cartesian plane such that $y = f(x)$
• A function's graph passes the vertical line test: any vertical line intersects the graph at most once
• Matrices can represent relations using 1's and 0's to indicate the presence or absence of ordered pairs

Operations on Relations and Functions

• The union of two relations R and S, denoted as $R \cup S$, is the set of ordered pairs that belong to either R or S (or both)
• The intersection of two relations R and S, denoted as $R \cap S$, is the set of ordered pairs that belong to both R and S
• The complement of a relation R, denoted as $R^c$, is the set of ordered pairs that do not belong to R
• The composition of two functions $f$ and $g$, denoted as $g \circ f$, is the function that first applies $f$ to the input and then applies $g$ to the result
  • Formally, $(g \circ f)(x) = g(f(x))$ for all $x$ in the domain of $f$ such that $f(x)$ is in the domain of $g$
• The inverse of a function $f$, denoted as $f^{-1}$, is the function that "undoes" the action of $f$
  • If $f(x) = y$, then $f^{-1}(y) = x$ for all $x$ in the domain of $f$ and $y$ in the codomain of $f$

Applications in Mathematical Logic

• Relations and functions are fundamental concepts in mathematical logic
• Propositional logic uses truth functions to map propositional variables to truth values
• First-order logic employs predicates, which are functions that map elements of a domain to truth values
• Relations in first-order logic represent connections between elements in the domain (e.g., "is greater than," "is a parent of")
• Functions in first-order logic assign unique values to elements in the domain (e.g., "the square of," "the father of")
• Logical connectives (e.g., conjunction, disjunction, implication) can be viewed as truth functions
• Quantifiers in first-order logic (universal and existential) express properties of relations and functions

Common Challenges and Misconceptions

• Confusing the terms "codomain" and "range" for functions (codomain includes all possible outputs, while range is the set of actual outputs)
• Mistakenly believing that all relations are functions (functions are a special type of relation with unique outputs for each input)
• Incorrectly applying the vertical line test to determine if a graph represents a function (the test should be applied to the entire graph, not just a portion)
• Struggling to identify the domain and range of a relation or function from its graph or equation
• Misunderstanding the concept of inverse functions (not all functions have inverses, and the inverse of a function is not always a function)
• Confusing the properties of relations (e.g., mistaking symmetry for transitivity or reflexivity)
• Incorrectly composing functions (the order of composition matters, and the domain of the inner function must match the codomain of the outer function)