Ch 4. Key Terms

Antisymmetric Relation: A relation [latex]R[/latex] on a set [latex]A[/latex] where [latex](a, b) \in R[/latex] and [latex](b, a) \in R[/latex] imply [latex]a = b[/latex].

Binary Operator: An operator that acts on two operands, such as [latex]+[/latex], [latex]\times[/latex], logical AND, or set union.

Binary Relation: A subset of a Cartesian product [latex]A \times B[/latex]; a set of ordered pairs.

Bijective Function: A function that is both injective and surjective

Cartesian Product: The set [latex]A \times B = \{ (a, b) \mid a \in A, b \in B \}[/latex].

Closure (of a Relation): The smallest relation containing a given relation that satisfies a property (reflexive, symmetric, transitive).

Codomain: The set of possible outputs of a function.

Composition of Relations: For relations [latex]R \subseteq A \times B[/latex] and [latex]S \subseteq B \times C[/latex], the composition [latex]S \circ R = \{ (a, c) \mid \exists b[/latex] such that [latex](a, b) \in R, (b, c) \in S \}[/latex].

Complement (of a Set): The set of all elements in the universal set not in a given set [latex]A[/latex], written [latex]A^{c}[/latex].

Directed Graph (Digraph): A graphical representation of a relation where vertices represent elements and directed edges represent ordered pairs.

Domain (of a Relation): The set of first components of ordered pairs in a relation.

Equivalence Class: For an equivalence relation [latex]R[/latex], the set [latex][a] = \{ x \in A \mid x \; R \; A \}[/latex].

Equivalence Relation: A relation that is reflexive, symmetric, and transitive.

Field (of a Relation): The union of the domain and range of a relation.

Function: A relation where each input has exactly one output.

Injective Function (One‑to‑One): A function where different inputs always produce different outputs.

Inverse of a Function: For a bijection [latex]f: A \rightarrow B[/latex], the function [latex]f^{-1}: B \rightarrow A[/latex] satisfying [latex]f^{-1}(f(a)) = a[/latex].

Inverse Relation: For a relation [latex]R[/latex], the set [latex]R^{-1} = \{ (b, a) \mid (a, b) \in R \}[/latex].

Modulus Operator (mod): Returns the remainder when one integer is divided by another.

Ordered Pair: A pair [latex](a, b)[/latex] where order matters; [latex](a, b) \neq (b, a)[/latex] unless [latex]a = b[/latex]

Pairwise Disjoint: A family of sets in which every two distinct sets have an empty intersection.

Partition: A collection of nonempty, pairwise disjoint subsets whose union is the entire set.

Partial Order: A relation that is reflexive, antisymmetric, and transitive.

Power Set: The set of all subsets of a set [latex]A[/latex], written [latex]\mathcal{P}(A)[/latex].

Range (of a Relation or Function): The set of second components of the ordered pairs (actual outputs).

Reflexive Relation: A relation that contains [latex](a, a)[/latex] for all elements [latex]a[/latex] in the set.

Relation: Any subset of a Cartesian product of sets.

Relation Matrix: A matrix representation of a relation using 1’s for present pairs and 0’s otherwise.

Relational Algebra: A set of operations (selection, projection, join, etc.) used to manipulate relations in databases.

Relational Database: A database model that stores data as relations (tables), each containing tuples.

Set: A well-defined collection of distinct objects.

Subset: A set [latex]A[/latex] is a subset of [latex]B[/latex] if every element of [latex]A[/latex] is in [latex]B[/latex].

Surjective Function (Onto): A function whose range equals its codomain.

Symmetric Relation: A relation where [latex](a, b) \in R[/latex] implies [latex](b, a) \in R[/latex].

Total Order: A partial order in which every pair of elements is comparable.

Transitive Relation: A relation where [latex](a, b) \in R[/latex] and [latex](b, c) \in R[/latex] imply [latex](a, c) \in R[/latex].

Transitive Closure: The smallest transitive relation containing a given relation.

Tuple/n‑Tuple: An ordered list of elements (e.g., a database row).

Unary Operator: An operator that acts on a single operand, such as negation or absolute value.

Union/Intersection/Difference: Fundamental set operations: “or,” “and,” and “in one set but not the other.”

Universal Set: The set containing all elements under consideration.

Venn Diagram: A visual diagram showing relationships between sets.

Warshall’s Algorithm: An algorithm that computes the transitive closure of a relation represented as a matrix.