Sets, Subsets, and Set Operations

Sets and Subsets

• A set is a collection of distinct objects, considered as an object
• Sets are denoted by capital letters
• The elements within a set are enclosed in curly braces
• Example of a set of natural numbers less than 5: A={1,2,3,4} and B={1,2,3,4}
• A subset is a set whose elements are all contained within another set
• If set B is a subset of set A, then every element of B is also an element of A
• Denoted as BCA
• Example: if A={1,2,3,4} and B={1,2,3,4}, then B={1,2} is a subset of A. Written as BCA
• A proper subset is a subset that is not identical to the original set. Meaning, it contains some but not all elements of the original set
• Denoted as BCA
• Example: C={1,2}CA={1,2,3,4}
• Consider the set A of even numbers less than 10: A={2,4,6,8}

Operations on Sets

• Union (U): The union of two sets A and B is the set of elements that are in either A, B, or both.
• Denoted as AUB
• Example: Let A={1,2,3} and B={3,4,5}, then AUB={1,2,3,4,5}
• Intersection ( n ): The intersection of two sets A and B is the set of elements that are in both A and B.
• Denoted as AnB
• Example: Let A={1,2,3} and B={3,4,5}, then AnB={3}
• Difference ( - ): The difference of two sets A and B (also known as the complement of B in A) is the set of elements that are in A but not in B
• Denoted as A-B or A\B
• Example: Let A={1,2,3} and B={3,4,5}, then A−B={1,2}
• Symmetric Difference (A): The symmetric difference of two sets A and B is the set of elements that are in either A or B but not in both
• Denoted as ΑΔΒ
• Example: Let A={1,2,3} and B={3,4,5}, then ΑΔΒ={1,2,4,5}
• Complement (A'): The complement of a set A is the set of all elements in the universal set U that are not in A
• Denoted as A'
• Example: Let U={1,2,3,4,5} and A={1,2,3}, then A'={4,5}
• These operations help in combining, comparing, and analyzing sets in various ways

Sequences in Discrete Structures

• In discrete mathematics, sequences are an important concept used to represent ordered lists of elements, typically numbers, that follow a specific rule or pattern
• Sequences can be finite or infinite
• Sequences are often used to model and solve problems in computer science, combinatorics, and other areas of discrete mathematics

Types of Sequences

• Arithmetic Sequence: A sequence of numbers in which the difference between consecutive terms is constant.
• This difference is called the common difference (d)
• Example: Consider the sequence: 3,7,11,15,19,....
• The common difference d=4
• The n-th term of an arithmetic sequence can be found using the formula: a₁=a₁+(n-1)d where a₁ is the first term and n is the term number
• Geometric Sequence: A sequence of numbers in which the ratio between consecutive terms is constant
• This' ratio is called the common ratio (r)
• Example: Consider the sequence: 2,6,18,54,162,...
• The common ratio r=3
• The n-th term of a geometric sequence can be found using the formula: an=a₁·r(n-1) where a1 is the first term and n is the term number
• Fibonacci Sequence: A sequence of numbers in which each term is the sum of the two preceding terms
• The sequence starts with 0 and 1
• Example: The Fibonacci sequence: 0,1,1,2,3,5,8,13,21...
• The n-th term of the Fibonacci sequence can be found using the formula: F₁=Fn-1+Fn-2 Where F₁=0 and F₂=1

Example in Discrete Structures

• Consider an arithmetic sequence with the first term a₁=5 and a common difference d=3: 5,8,11,14,17,...
• To find the 6th term (a₆): a₆=a₁+(6-1)d a₆=5+5·3a₆=5+15a₆=20
• Discrete structures often use sequences to describe and analyze patterns, algorithms, and other mathematical constructs
• Understanding sequences and their properties is fundamental to solving many problems in discrete mathematics

Properties of Integers

• Integers are a fundamental concept in discrete mathematics and have several important properties
• Closure: The set of integers is closed under addition, subtraction, and multiplication
• If a and b are integers, then a+b, a−b, and a·b are also integers
• Example: If a=3 and b=-5, then: a+b=3+(-5)=-2, a−b=3-(-5)=8, ab=3·(-5)=-15
• Commutativity: Addition and multiplication of integers are commutative
• The order in which you add or multiply two integers does not affect the result
• Example: If a=4 and b=7, then: a+b=b+a=4+7=7+4=11, ab=b.a=4·7=7·4=28
• Associativity: Addition and multiplication of integers are associative
• The way you group integers when adding or multiplying does not affect the result
• Example: If a=2, b=3, and c=5, then: (a+b)+c=a+(b+c)=(2+3)+5=2+(3+5)=10, (ab)·c=a(b·c)=(2·3)·5=2·(3.5)=30
• Identity Elements: The additive identity is 0, and the multiplicative identity is 1
• Adding 0 to any integer does not change its value, and multiplying any integer by 1 does not change its value
• Example: If a=9, then: a+0=9+0=9, α·1=9·1=9
• Distributivity: Multiplication distributes over addition
• For any integers a, b, and c: d·(b+c)=(a·b)+(a·c)
• Example: If a=2, b=3, and c=4, then: 2.(3+4)=2.7=14, (2.3)+(2.4)=6+8=14

Matrices

• A matrix is a rectangular array of numbers, symbols, or expressions arranged in rows and columns
• Matrices are used in various fields to represent and solve problems involving linear equations, transformations, and more

Basic Concepts

• Matrix Notation: A matrix is usually denoted by a capital letter (e.g., A)
• The elements of a matrix are arranged in rows and columns and are typically enclosed in brackets
• For example, a matrix A with 2 rows and 3 columns (a 2x3 matrix) can be written as: A = 1 2 3, 4 5 6
• Types of Matrices:
• Square Matrix: A matrix with the same number of rows and columns (e.g., 3x3, 4x4)
• Row Matrix: A matrix with only one row (e.g., 1x3)
• Column Matrix: A matrix with only one column (e.g., 3x1)
• Zero Matrix: A matrix in which all elements are zero
• Identity Matrix: A square matrix with ones on the diagonal and zeros elsewhere

Matrix Operations

• Addition: Two matrices can be added if they have the same dimensions
• The sum is obtained by adding corresponding elements
• Example: A = 1 2, 3 4 and B = 5 6 , 7 8, then A + B = 1+5 2+6, 3+7 4+8 = 6 8, 10 12
• Multiplication: Two matrices can be multiplied if the number of columns in the first matrix is equal to the number of rows in the second matrix
• The product is obtained by taking the dot product of rows and columns
• C=A·BC=A·B Where CC is the resulting matrix
• Example in Discrete Structures:
• Consider the adjacency matrix of a graph
• An adjacency matrix is a square matrix used to represent a finite graph
• The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph
• Example: Consider a simple undirected graph with 3 vertices A, B, C and edges A-B and B-C
• Let's assign index numbers to the vertices:
• A → 0, B → 1, C → 2
• Build the adjacency matrix M, where:
• M[i][j] = 1 if there is an edge between vertex i and j
• M[i][j] = 0 otherwise
• Since it's undirected, the matrix will be symmetric
• M = 0 1 0 , 1 0 1 , 0 1 0
• Row 0 (A): connected to B → 1 at column 1
• Row 1 (B): connected to A and C → 1s at columns 0 and 2
• Row 2 (C): connected to B → 1 at column 1

Mathematical Structures

• Mathematical structures are abstract concepts used to organize and analyze mathematical objects and their relationships
• Several key structures are commonly studied in discrete mathematics including, sets, graphs, and algebraic structures
• Sets: A set is a collection of distinct objects, considered as an object in its own right
• Sets are fundamental to discrete mathematics and are used to define other structures
• Example: Let A be a set of natural numbers less than 5: A={1,2,3,4}
• Graphs: A graph is a collection of vertices (nodes) and edges (connections) that represent relationships between pairs of objects
• Graphs are used to model networks, pathways, and connections
• Example: Consider a graph G with vertices V={A,B,C} and edges E={(A,B),(B,C)}
• This graph can be represented visually as: A -- B -- C
• Algebraic Structures: Algebraic structures include groups, rings, and fields which are sets equipped with operations that satisfy certain properties
• A group (G,·) is a set G with a binary operation that satisfies the following properties:
• Closure: For all a,b∈G, a·b∈G
• Associativity: For all a,b,c∈G, (a·b)·c=a·(b·c)
• Identity Element: There exists an element e∈G such that for all a∈G, e·a=a·e=a
• Inverse Element: For each a∈G, there exists an element b∈G such that a·b=b·a=e
• Example: Consider the set of integers Z with the operation of addition
• This forms a group (Z,+) because:
• Closure: The sum of any two integers is an integer
• Associativity: Addition of integers is associative
• Identity Element: The identity element is 0
• Inverse Element: The inverse of any integer a is -a
• Relations: A relation is a set of ordered pairs that describe a relationship between elements of two sets
• Example: Let A={1,2,3} and B={a,b}
• A relation R from A to B can be: R={(1,a),(2,b),(3,a)}
• Functions: A function is a special type of relation where each element of the domain is related to exactly one element of the codomain
• Example: Let f:N→N be a function defined by f(x)=x2
• This function maps each natural number to its square
• Matrices: Matrices are rectangular arrays of numbers used to represent and solve systems of linear equations, transformations, and more
• A matrix A representing a system of linear equations example:
• System of linear equations: 2x+3y=5, 4x-y=6
• The system can be represented in matrix form as: A · X = B, Where B= 5,6
• A is the coefficient matrix: A= 2 3 , 4 -1
• X is the variable matrix: X= x , y
• System with variables : 2 3 x = 5, 4 -1 y 6