Sets & Set Operations

Basic Structures: Sets, Functions, Sequences, Sums, and Matrices

• Discrete mathematics involves the study of discrete structures used to represent discrete objects
• Sets are used as the foundation for many important discrete structures like combinations, relations, graphs, and finite state machines

Functions

• Functions are a core concept in discrete mathematics, assigning each element of a first set to exactly one element of a second set
• Functions represent algorithm complexity, study set size, and count objects
• Sequences and strings are special types of functions

Sequences and Sums

• Sequences are ordered lists of elements
• Terms of a sequence can be defined using earlier terms
• Summation notation is used for adding terms from sequences or indexed sets
• Summations are used in the analysis of algorithm efficiency

Cardinality

• The relative sizes of infinite sets are studied through the concept of cardinality
• A set is countable if it's finite or has the same size as the set of positive integers
• The set of rational numbers is countable, but the set of real numbers is not

Matrices

• Matrices represent discrete structures in discrete mathematics
• Matrix arithmetic is used to solve problems involving these structures and represent relations and graphs

Sets - Introduction

• Sets are fundamental discrete structures used to group objects together, often with similar properties
• The language of sets provides a means to study collections of objects

Definition of a Set

• A set is an unordered collection of distinct objects, called elements or members
• Sets can contain other sets
• A set contains its elements
• a ∈ A denotes that a is an element of set A
• a ∉ A denotes that a is not an element of set A
• Sets are commonly denoted by uppercase letters and elements by lowercase letters

Describing Sets

• Listing all members (roster method): V = {a, e, i, o, u} represents vowels in the English alphabet
• Using set builder notation: Characterizing elements by properties, e.g., {x | x has property P}
• The set of all odd positive integers less than 10: O = {x | x is an odd positive integer less than 10} or O = {x ∈ Z+ | x is odd and x < 10}
• The set of all positive rational numbers: Q+ = {x ∈ R | x = p/q, for some positive integers p and q}

Important Sets in Discrete Mathematics

• N = {0, 1, 2, 3, ...}, the set of all natural numbers
• Z = {..., -2, -1, 0, 1, 2, ... }, the set of all integers
• Z+ = {1, 2, 3, ...}, the set of all positive integers
• Q = {p/q | p ∈ Z, q ∈ Z, and q ≠ 0}, the set of all rational numbers
• R, the set of all real numbers
• R+, the set of all positive real numbers
• C, the set of all complex numbers

Intervals

• Intervals are sets of real numbers between two numbers a and b
• [a, b] = {x | a ≤ x ≤ b} (closed interval)
• [a, b) = {x | a ≤ x < b}
• (a, b] = {x | a < x ≤ b}
• (a, b) = {x | a < x < b} (open interval)

Nested Sets

• Sets can have other sets as its elements
• {N, Z, Q, R} contains four elements, which are the sets of natural numbers, integers, rationals, and reals
• datatype (or type) in computer science is based on the concept of a set and a set of operations is performed on objects from that set
• For example, boolean is the name of the set {0, 1}, together with operators such as AND, OR, and NOT

Equality of Sets

• Two sets are equal if and only if they have the same elements
• A = B if and only if ∀x(x ∈ A ↔ x ∈ B)

Naive Set Theory

• The theory that results from intuitive notion that for any property whatever, there is a set consisting of exactly the objects with this property, leads to paradoxes, or logical inconsistencies

Venn Diagrams

• Venn diagrams graphically represent sets
• The universal set U is represented by a rectangle
• Sets are represented by circles (or other geometrical figures) inside the rectangle
• Venn diagrams indicate the relationships between sets

Subsets and Supersets

• Set A is a subset of B if every element of A is also an element of B i.e. A ⊆ B
• Set B is a superset of A i.e. B ⊇ A
• A ⊆ B is true if and only if the quantification ∀x(x ∈ A → x ∈ B) is true

Showing Subsets and Non-Subsets

• Showing A ⊆ B: show that if x belongs to A, then x also belongs to B
• Showing A ⊈ B: find a single x ∈ A such that x ∉ B

Examples of Subsets

• All odd positive integers less than 10 is a subset of all positive integers less than 10
• The set of rational numbers is a subset of the set of all real numbers

Theorems About Sets

• Every nonempty set S is guaranteed to have at least two subsets, the empty set (Ø) and the set S itself
• Ø ⊆ S and S ⊆ S
• Proof: (i) Ø ⊆ S and (ii) S⊆ S.

Proper Subsets

• A is a proper subset of B, written as A ⊂ B, if A ⊆ B and there exists an element x of B that is not an element of A
• it must be the case that A C B and there must exist an element x of B that is not an element of A. That is, A is a proper subset of B if and only if ∀x(x ∈ A → x ∈ B) ∧∃x(x ∈ B ∧ x ∉ A)

Proving set equality

• To show that two sets A and B are equal, show that A ⊆ B and B ⊆ A

The Size of a Set

• The size of a set is also its cardinality
• If S has exactly n distinct elements, then S is a finite set and n is the cardinality of S, denoted by |S|
• The term cardinality comes from the common usage of the term cardinal number as the size of a finite se

Cardinality Examples

• If A is the set of odd positive integers less than 10, then |А| = 5
• If S is the set of letters in the English alphabet, then |S| = 26
• The null set has no elements: |Ø| = 0
• Sets that are not finite are called infinite

Power Sets

• The power set of S, denoted by P(S), is the set of all subsets of S

Power Set Examples

• The power set of {0, 1, 2} includes all its subsets:P({0, 1, 2}) = {Ø, {0}, {1}, {2}, {0, 1}, {0, 2}, {1, 2}, {0, 1, 2}}
• Power set of the empty set: P(Ø)={Ø} and P({Ø}) = {Ø, {Ø}}
• If set has n elements its power set has 2^n elements

Cartesian Products

• An ordered n-tuple is an ordered collection of elements, written as (a1, a2, ..., an)
• Two ordered n-tuples are equal if and only if each corresponding pair of their elements is equal: In other words, (a1, a2, ..., an) = (b1, b2, ..., bn) if and only if aᵢ = bᵢ, for i = 1, 2, ..., n
• A set of ordered 2-tuples are called ordered pairs
• If A and B are sets, the Cartesian product of A and B, denoted by A × B, is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B:
  • A × B = {(a, b) | a ∈ A ∧ b ∈ B}
• Cartesian products A × B and B × A are not equal unless A = Ø or B = Ø (so that A × B = Ø) or A = B

Cartesian Product Generalization

• A Cartesian Product of the sets A₁, A₂, ..., Aₙ, denoted by A₁ × A₂ × ... × Aₙ is the set of ordered n-tuples (a₁, a₂, ..., aₙ), where aᵢ belongs to Aᵢ
• If A, B, and C are sets, (A × B) × C is not the same as A × B × C
• The notation A² denotes A × A, A³ = A × A × A, and so on

Relations

• A subset R of Cartesian product of A × B is called relation A to set B
• A relation need not contain all a pair for every element A
• A relation from set A to itself is called also relation to A

Set Notation with Quantifiers

• ∀x ∈ S(P(x)) denotes universal quantification of P(x) over all elements in the set S
• ∃x ∈ S(P(x)) denotes existential quantification of P(x) over all elements in the set S
• Statement ∀x ∈ R(x² ≥ 0) means that for every real number x, x² ≥ 0 which is a true statement
• Statement ∃x ∈ Z(x² = 1) means that there exists an integer x such that x² = 1, that is also a true statement

Truth Sets

• Given a predicate P and domain D, truth set of P is the set of elements x if D where P(x) is true
• Truth set P(x) denoted by {x ∈ D | P(x)}