4. Relations_1682314545734

Discrete Mathematics Overview

Overview of Discrete Mathematics

• Focuses on structures that are fundamentally discrete rather than continuous.

• Relevant to the Texas College of Management & IT curriculum.

Cartesian Product

• Definition: The Cartesian product of two sets, A and B, is written as A × B.

• It includes all possible pairs where the first element comes from A and the second comes from B.

• Notation: A × B = {(a,b) | a ∈ A, b ∈ B}

• Example: If A = {1, 2} and B = {x, y, z}, then A × B = {(1,x), (1,y), (1,z), (2,x), (2,y), (2,z)}.

• Relation Count: The number of possible relations between two sets is 2^(mn) where m and n are the sizes of sets A and B, respectively.

Relations

• Definition: A relation R from set A to set B is simply a selection of pairs from A × B.

• Notation: If (a, b) is in the relation R, we say "a is related to b" or we write it as aRb.

• Example: With A = {1,2} and B = {x,y,z}, some possible relations R can be:

  • Empty set

  • R = {(1,x), (2,y)}

  • R = {(1,y), (2,x)}

Types of Relations

Key Types:

• Reflexive

• Irreflexive

• Symmetric

• Anti-symmetric

• Asymmetric

• Transitive

Reflexive Relations

• Definition: A relation R is reflexive if every element relates to itself, meaning (a, a) is in R for all a in A.

• Examples:

  • R = {}: Not reflexive

  • R = A × A: Reflexive

  • R = {(a,a), (b,b), (c,c)}: Reflexive

Irreflexive Relations

• Definition: A relation R is irreflexive if no element relates to itself, meaning (a, a) is not in R for all a in A.

• Examples:

  • R = {}: Irreflexive

  • R = {(a,b), (b,c)}: Irreflexive

Symmetric Relations

• Definition: A relation R is symmetric if for every (a, b) in R, the pair (b, a) is also in R.

• Examples:

  • R = {(a,b), (b,a)}: Symmetric

  • R = {(a,b), (c,a)}: Not symmetric

Anti-symmetric Relations

• Definition: A relation is anti-symmetric if (a, b) in R and (b, a) in R implies a must equal b.

• Examples:

  • R = {(a,b)}: Anti-symmetric

  • R = {(a,b), (b,a)}: Not anti-symmetric

Asymmetric Relations

• Definition: A relation is asymmetric if (a, b) is in R, then (b, a) cannot be in R.

• Examples:

  • R = {(1,2)}: Asymmetric

  • R = {(1,2), (2,1)}: Not asymmetric

Transitive Relations

• Definition: A relation is transitive if whenever (a, b) and (b, c) are in R, then (a, c) must also be in R.

• Examples:

  • R = {(1,2), (2,3)}: Transitive

  • R = {(1,2), (2,1)}: Not transitive

Equivalence Relations

• Definition: For a relation to be equivalence, it must be reflexive, symmetric, and transitive.

• Example: Analyze relations on A = {1, 2, 3, 4} to determine if they exhibit these properties.

Congruence Modulo m

• Definition: Two integers 'a' and 'b' are congruent modulo m if they leave the same remainder when divided by m.

• Key Requirement: (a - b) must be divisible by m.

• Example: For a = 7, b = 9, m = 2, both 7 and 9 leave remainder 1 when divided by 2.

Showing Equivalence for Congruence Modulo m

• Reflexivity: For any a, (a, a) must be part of R since (a-a) = 0 is divisible by m.

• Symmetry: If (a,b) is in R, then (b,a) must also be in R because b-a = - (a-b).

• Transitivity: If (a,b) and (b,c) are in R, then (a,c) must also be in R, which validates the transitive property.