Unit II: Set Theory and Ordered Sets

Course: Discrete Mathematics
Code: CADSC102

Basic Concepts of Set Theory

Set theory is the fundamental language of mathematics. A set is a well-defined collection of distinct objects.

• Elements: The objects belonging to a set are called its members or elements.
• Notation: Sets are usually denoted by capital letters (A, B, C) and elements by small letters (a, b, x).
• Universal Set (U): The set containing all objects under consideration.
• Empty Set (Ø): A set with no elements.

Operations with Sets

Common operations used to manipulate sets include:

• Union (A ∪ B): Elements in A, or B, or both.
• Intersection (A ∩ B): Elements common to both A and B.
• Difference (A - B): Elements in A that are not in B.
• Complement (A'): Elements in the Universal set not in A.
• Cartesian Product (A × B): The set of all ordered pairs (a, b) where a is in A and b is in B.

Functions

A function is a special type of relation where every element in the domain is mapped to exactly one element in the codomain.

• Domain: The set of all possible inputs.
• Range: The set of all actual outputs.
• One-to-One (Injective): Every element in the range has only one pre-image.
• Onto (Surjective): Every element in the codomain is an image of at least one element in the domain.

Relations and Properties

A relation R from set A to B is a subset of A × B.

Properties of Relations

• Reflexive: (a, a) is in R for every a in A.
• Symmetric: If (a, b) is in R, then (b, a) must be in R.
• Transitive: If (a, b) and (b, c) are in R, then (a, c) must be in R.
• Anti-symmetric: If (a, b) and (b, a) are in R, then a = b.

Composition and Closures of Relations

• Representing Relations: Can be done via sets of pairs, matrices, or directed graphs (digraphs).
• Composition: If R is a relation from A to B and S is from B to C, S ∘ R is a relation from A to C.
• Closures: The smallest relation containing R that satisfies a specific property (Reflexive, Symmetric, or Transitive closure).

Ordered Sets and Hasse Diagrams

A set with a partial ordering relation is called a Partially Ordered Set or Poset.

Hasse Diagrams

A Hasse diagram is a simplified graphical representation of a finite partially ordered set.

• Eliminates reflexive loops.
• Eliminates transitive edges.
• Direction is understood to be upwards.