Relations vs. Functions in Discrete Mathematics: Defining Relationships and Mappings

Understand the difference between relations and functions in discrete mathematics. This guide explains relations as sets of ordered pairs, introduces the concept of the Cartesian product, and clarifies how functions are a specific type of relation with unique mappings.

Relations vs. Functions in Discrete Mathematics

Relations

In discrete mathematics, a relation is a set of ordered pairs that links elements from one set (the domain) to elements in another set (the range). If (a, b) is an ordered pair in the relation, we say that 'a' is related to 'b'.

Cartesian Product and Relations

The Cartesian product of two sets A and B (written A x B) is the set of all possible ordered pairs (a, b) where a is from A and b is from B. A relation R from A to B is a subset of A x B.

Types of Relations

• Empty Relation: No elements are related (R = Ø).
• Universal Relation: Every element in A is related to every element in B.
• Identity Relation: Each element is related only to itself.
• Inverse Relation: The relation obtained by swapping the elements in each ordered pair (R^-1 = {(b, a) | (a, b) ∈ R}).
• Reflexive Relation: Every element is related to itself.
• Symmetric Relation: If (a, b) is in the relation, then (b, a) is also in the relation.
• Transitive Relation: If (a, b) and (b, c) are in the relation, then (a, c) is also in the relation.
• Equivalence Relation: A relation that is reflexive, symmetric, and transitive.

Example of a Relation

Imagine buying fabric swatches. Three swatches cost $4. Each additional swatch costs $2. The relation between cost and number of swatches could be represented as:

{(4, 1), (4, 2), (4, 3), (6, 4), (8, 5), (10, 6), (12, 7)}

Notice that a single cost ($4) can correspond to multiple numbers of swatches. This is a many-to-one relation.

Functions

A function is a special kind of relation where each element in the domain maps to exactly one element in the range. A function can be written as f: A → B, where A is the domain and B is the range (or co-domain).

Conditions for a Relation to be a Function

• Completeness: Every element in the domain (A) must be mapped to an element in the range (B).
• Uniqueness: Each element in the domain can only map to one element in the range. (If (a, b) ∈ f and (a, c) ∈ f, then b = c)

Types of Functions

• One-to-One (Injective): Each element in the domain maps to a unique element in the range.
• Many-to-One: Multiple elements in the domain map to the same element in the range.
• Onto (Surjective): Every element in the range is mapped to from at least one element in the domain.

Examples of Functions

(Illustrative examples of one-to-one, many-to-one, and onto functions, with explanations, should be included here, using both sets and function notation.)

Bijective Functions

A bijective function is both one-to-one and onto. Each element in the domain is paired with exactly one element in the range, and vice versa. Bijective functions are invertible (they have an inverse function).

(An illustrative example of a bijective function and its inverse should be included here.)

Properties of Bijective Functions

• The domain and range have the same number of elements.
• The range and codomain are equal.
• A bijective function has an inverse.
• Not all functions are bijective.

Other Types of Functions

(This section should include examples and short descriptions of constant functions, inverse functions, absolute value functions, identity functions, and linear functions.)

Example Illustrating the Difference

(An example that clearly demonstrates the difference between a function and a relation, possibly using a table of ordered pairs, should be included here.)

Conclusion

Relations and functions are fundamental concepts in discrete mathematics. The key difference lies in the uniqueness of the mapping: functions have a one-to-one mapping, whereas relations do not necessarily require this.

Functions vs. Relations: Key Differences

Summary of Key Differences

• A function is a special type of relation where each input has only one output.
• A relation can have multiple outputs for a single input; a function cannot.

Example 1: A Relation that is Also a Function

In this example, each element in set A maps to exactly one element in set B. This satisfies the definition of a function.

Example 2: A Relation that is NOT a Function

Here, the input value 2 maps to two different output values (2 and 1). This violates the definition of a function; a single input can only have one output.

Example 3: Identifying a Function

This relation is a function because each input in set A has only one corresponding output in set B.

Conclusion

The fundamental difference between a function and a relation lies in the uniqueness of the output. Functions guarantee a single output for each input, making them more structured than relations. Relations are more general, allowing for multiple outputs from a single input.