Introduction to Sets

Lesson 1: Sets

• G. Cantor, a German mathematician, introduced sets as collections of definite and distinguishable objects, determined by rules or descriptions.
• Set theory forms the basis for counting theory, relations, graph theory, and finite state machines.
• A set is an unordered collection of different elements.
• Sets can be written explicitly using set brackets; order and repetition of elements do not change the set.
• Roster/Tabular Form: Lists elements enclosed in braces, separated by commas.
  • Example: set of vowels = {a, e, i, o, u}
• Set Builder Notation: Defines a set by specifying a property its elements share, written as A = {x: p(x)}.
  • Example: {a, e, i, o, u} = {x: x is a vowel in the English alphabet}
• x ∈ S denotes element x being a member of set S; x ∉ S denotes x not being a member of S.
• Important Sets:
  • ℕ (natural numbers) = {0, 1, 2, 3, 4, 5, ...}
  • ℤ (integers) = {..., -3, -2, -1, 0, 1, 2, 3, ...}
  • ℤ⁺ (positive integers) = {1, 2, 3, 4, 5, ...}
  • Q (rational numbers) = {..., -1/3, -1/2, 1/2, 1/3, ...}
  • R (real numbers) = {..., -√2, -1.5, 0, 1, √2, ...}
  • W (whole numbers) = {0, 1, 2, 3, 4, 5, ...}
• Cardinality: Denoted as |S|, is the number of elements in set S; infinite sets have a cardinality of ∞.
  • Example: |{1, 4, 3, 5}| = 4

Types of Sets

• If there are two sets X and Y:
  • |X|=|Y| indicates X and Y have same cardinality, with a bijective function 'f' from X to Y.
  • |X|≤|Y| indicates X's cardinality is less than or equal to Y's, with an injective function 'f' from X to Y.
  • |X|<|Y| indicates X's cardinality is less than Y's, with an injective but not bijective function 'f' from X to Y.
  • If X≤Y and |X|≥|Y|, then |X|=|Y|, sets X and Y are equivalent.
• Finite Set: Contains a definite number of elements.
  • Example: S = {x | x ∈ N and 10>x>5}
• Infinite Set: Contains infinite number of elements.
  • Example: S = {x | x ∈ N and x>5}
• Subset: X is a subset of Y (X⊆Y) if every element of X is also an element of Y.
  • Example: X={1,2,3,4,5,6} and Y={1,2}; Y ⊆ X
• Proper Subset: (X⊂Y) if every element of X is in Y and |X|<|Y|
  • Example: X={1,2,3} and Y={1,2}: Y⊂X
• Universal Set: Collection of all elements in a specific context, denoted as U.
• Empty/Null Set: Contains no elements, denoted by Ø; cardinality is zero.
  • Example: S = {x | x ∈ N and 4<x<5}
• Singleton Set: Contains only one element, denoted by {s}.
  • Example: S = {x | x ∈ N, 3<x<5} = {4}
• Equal Sets: Contain the same elements.
  • Example: X={1,2,6}, Y={2,6,1}
• Equivalent Sets: Have the same cardinality.
  • Example: X={1,2,6} and Y={16,17,22}: |A| = |B| = 3
• Overlapping Sets: Have at least one common element.
  • n(AUB)=n(A)+n(B)-n(A∩B)
  • n(AUB)=n(A-B)+n(B-A)+n(A∩B)
• Disjoint Sets: Have no elements in common
  • n(A∩B)= Ø
  • n(AUB)=n(A)+n(B)

Lesson 2: Set Operations

• Set operations are mathematical operations on sets, which are collections of distinct objects or elements.
• These operations are used to manipulate sets, define relationships, and solve problems involving collections.
• Venn diagrams, invented by John Venn in 1880, illustrate logical relations between different mathematical sets.
• Set Union: (AUB) is the set of elements in A, in B, or in both.
  • A U B={x|x∈ A OR x ∈ B}
  • If A={10,11,12,13) and B={13,14,15), then AUB={10,11,12,13, 14,15}.
• Intersection: (A∩B) is the set of elements common to both A and B.
  • A∩B={x|x∈ A AND x∈B}
  • If A={11,12,13) and B={13,14,15), then A∩B={13}.
• Disjoint Sets: Two sets are disjoint if their intersection is the empty set.
• Set Difference/Relative Complement: (A-B) is the set of elements only in A but not in B.
  • A-B={x|x∈ A AND x∉B}
  • If A={10,11,12,13) and B={13,14,15), then (A-B)={10,11,12) and (B-A)={14,15}.
• Complement of a Set: (A' or Ac) is the set of elements not in A, specifically A'=(U-A) where U is the universal set.
  • A'= {x|x∉A}
  • A = {x|x belongs to set of odd integers} then A'={y|y does not belongs to set of odd integers}
• Operations on Sets:
  • Addition and subtraction of sets follows the same rule but with the subtraction operation on the elements
  • Set addition is commutative while set subtraction is not.
  • n (AUB) = n(A) + n(B) - n (A ∩ B)
  • A-B = A ∩ B'
• Cartesian Product/Cross Product: The Cartesian product of n sets A1, A2, ... An is denoted as A1 × A2 × ... × An , consisting of possible ordered pairs (x1, x2, ... xn) where xi ∈ Ai
  • If A={a,b} and B={1,2}, then A×B= { {a,1}, {a,2}, {b,1}, {b,2} }
• Power set: of a set S is the set of all subsets of S, including the empty set (Ø). The cardinality of a power set of a set S of cardinality n is 2n. Power set is denoted as P(S). Example: For a set S={a,b,c,d} • Subsets with 0 elements - {} (empty sets) • Subsets with 1 element - {a},{b},{c},{d} • Subsets with 2 elements - {a,b},{a,c},{a,d}, {b,c}, {b,d}, {c,d} • Subsets with 3 elements - {a,b,c},{a,b,d}, {a,c,d}, {b,c,d} • Subsets with 4 elements - {a,b,c,d}
• Partioning a set $P_1,P_2,P_3...P_n$ that satisfies the following conditions
• $[P_i\neq {}, for all:0<i<n]$
• $[P_1 \cup P_2 \cup ...\cup P_n]=s$
• The union of the subsets must equal the original set.
• $[P_i \cap P_i={}, for ai\neq b when 2\geq a,b \geq 0]$
• The intersection of any two distinct sets is empty
• Example: Let S={a,b,c,d,e,f,g,h}
• One probable partitioning is
• {a},{b,c,d}, {e,f,g,h}
• Another probable partitioning is
• {a,b},{c,d},{e,f,g,h}
• Bell Numbers
• Bell numbers give the count of the number of ways to partition a set.
• They are denoted by $B_n$ where n is the cardinality of the set. Example:Let S={1,2,3}, n=\SI|S|=3 Alternate partions
• *{0},{1,2,3}
• {1},{2,3}
• {1,2},{3}
• {1,3},{2}
• {1},{2},{3}

Properties of Set Operations

• Closure: Set operations are closed under their respective operations.
• Commutative:
  • Union: AUB=BUA
  • Intersection: A ∩ B = B ∩ A
• Associative:
  • Union: (AUB) UC = AU (BUC)
  • Intersection: (A ∩ B) N C = A ∩ (B∩C)
• Distributive:
  • Union over Intersection: A U (B ∩C) = (A U B) ∩ (AUC)
  • Intersection over Union: A ∩ (B U C) = (A ∩ B) U (ANC)
• Identity:
  • Union: A U Ø = A
  • Intersection: A ∩ U = A, where U represents the universal set
• Complement:
  • Union: A U A' = U, where U is the universal set
  • Intersection: A ∩ A' = Ø (the empty set)
• Absorption:
  • Union over Intersection: A U (A ∩ B) = A
  • Intersection over Union: A ∩ (A U B) = A
• Examples:
  • Find the union of two sets A = {8, 10, 14} and B = {7, 16} (AUB) = {8, 10, 14} ∪ {7,16} (A U B) = {{8, 10, 14}, }
• Find the intersection of sets P = (a, n,x} and Q = {x, y, z) (P ∩ Q) = {a, n, x} ∩ {x, y, z)
• (PNQ) = {x}
• Find the complement of set X = {4, 6, 9} where Universal set U = {1, 2, 3, 4, 6, 9} Solution:
• X' = U - X
• X' = {1, 2, 3, 4, 6, 9} - {4, 6, 9)
• X' = {1, 2, 3}
• Given two sets A = {5, 6, 9, 10) and B = {3, 6, 12) then find, A - B and B - A Solution:
• *A - B = {5, 6, 9, 10) - {3, 6, 12)
• A - B = {5, 9, 10 }

• * B - A = (3, 6, 12) – (5, 6, 9, 10}
• * B - A = {3, 12}
  • Find the number of elements in set (A U B) given that n(A) = 10, n(B) = 4 and n (A ∩ B) = 5. Solution

• -To find n (A U B) we use formula:
• -n (A U B) = n(A) + n(B) – n (A∩B)
• -n (A U B) = 10 + 4-5
• -n (A U B) = 9

Lesson 3: Binary Vectors and Binary Strings

• Binary Vector: Has an expression (a1, a2, .., aₙ ) where aᵢ = 0 or aᵢ = 1 for each 1 ≤ i ≤ n.
  • Example: binary vector of 8 {1, 1, 1, 0, 0, 0, 0, 0}
• Binary String: A sequence of 0s and 1s.
  • Example: 11100000
• Algorithm: Set of rules for constructing/listing certain objects or determining properties.
• Theorem:
• If A is a set with n elements, where k ≤ n, the number of k-element subsets is (n choose k).
• If A is a set with n elements, then A has 2ⁿ subsets.
• The number of binary vectors of length n with exactly k 1s Is (n choose k) -There are 2ⁿ binary vectors of length n
• Standard Gray Code Algorithm: Orders binary vectors of length n so successive vectors differ by one element.
  • Begin with (0) (1)
  • To extend a list of length n to n+1, prepend each vector with 0, then append the reversed list with each vector prepended with 1.
• Knapsack Problem: Filling a knapsack with a max weight capacity with objects of varying weights to maximize total weight.
• Solved by listing binary vectors representing subsets of objects and finding the combination closest to weight capacity.
• Set Operations.
• {} Set: A collection of elements
• AUB Union: in A or B (or both)
• ANB Intersection: in both A and B
• A⊆B: Subset: every element of A is in B
• A⊂B: Proper Subset: every element of A is in B, but B has more elements.
• A⊈B: Not a Subset: A is not a subset of B
• A⊇B: Superset: A has same elements as B, or more
• A⊋B: Proper Superset: A has B's elements and more.
• A⊈B;: Not a Superset: A is not a superset of B
• A’ Complement: elements not in A
• A - B Difference: in A but not in B

Lesson 4: Standard Gray Code

• Standard gray code uses a list of binary vectors of length 2 in such a code as
• n1=3
• n2=4
• n3=5
• Solving the knapsack problem; Example = N=28 with weights n1=3,n2=4,n3=5 Binary Vector length 4 for:
• ( )
• ()

Lesson 5: Recursion

• Fibonacci Numbers:

• Leonardo Fibonacci (Leonardo Pisa) published the Liber Abaci, containing the first description of Fibonacci sequence(sequence which is defined as given numbers or initial values and a rule that expains how something is to be compared in terms of previous ones).

• Fibonacci numbers Fn have an initial value of F0=0 and F1=1 and the recursion:

• If n≥ 2.

• Then $F_n=F_{n-1}+F_{n-2}$

• Lucas Numbers:

• The Lucas Numbers The Lucas numbers Ln have the initial value of LO = 2, L1=1 and the recursion If n≥ 2.

• Then $L_n=L_{n-1}+L_{n-2}$

• Tribonacci Numbers:

• Tribonacci numbers Tn have the initial value TO = 0, T1 = 0, T2 = 1 and the recursion If n≥3.

• Then $T_n=T_{n-1}+T_{n-2}+T_{n-3}$

• Bernouli Numbers

  • The benouli numbers $B_n$ can be defined by the initial value $B_0$=1 and the reucrsion

• Simplification in terms of pAscal's triangle.

• Collatz Sequence a.k.a 3X+1 Sequence:

  • Named after German Mathematician, Lother Collatz(1910-1990 - defined by inutal values C[0] by recursion.

• If (n) is an odd number then: C[n+1] =3C[n]+1

• If n is an even number then: $C[n+1]=\frac{C[n]}{2}$

Lesson 6: Graphs

• A graph is a non-linear data structure comprised of vertices (nodes) and edges (arcs) connecting pairs of vertices, and is represented as G(V, E).
• A graph denoted as G=(V,E) as a non-empty vertices and a set of edges E
• parts of a graph:
• Nodes or Vertex are the elementary units that a graph must have in order for it to exist.Customary vertices are the graph for imposing the conditions that they have at least one vertex, but there's no real theoretical resons as to why
• An EDGE or are ordered pairs a connection berween two nodes u, v. Edges, on the other hand are optional in the sense that graph with no edges cab still be defined. There exists an edge, it serves as a link or a connection, between any two graphs
• Degree of a Vertex
  • The deree of a vertexs V of a graph G (denoted by deg(V)) is the number of edges incident with the vertex V. even and odd vertex the handshaking lemma: int he sum of all of the degrees of all the vertexs is equal to twice the number of edges degree of a graph in the largets vertex degree of that graph.
• Types of Graphs

1. Null Graph

• A null graph has no edges, the null graph of n vertices is defined by $N_n$.

2. Simple Graph

• A graph is called simple graph/strict graph if the graph it contains any loops or multiple edges.

3. Multi Graph

• if in the graph multiple edges between the same number of vertices are allowed it is called. Multigraph in other Words, it is a graph having atleast one loop or number or edges

4. Directed and Undirected

• Vertex 5 in the Vertex Bilateral Graph
• If the vertex-set of a graph G can be split into two disjoint sets in such a way that each edge in the graph joins a vertex in vi to a vertex in v2, and there are no edges in G that connects two vertices in or two Vertices Bipartita Graph
• Complete Vertex first set is vertex in the second set the complete bipartite graph
• Adjacency Matrix: Represent relationships of edge connections with a 2D matrix.
• Adjacencny used a D Matrix
• Planar Vs. Non Planar Graphs:
• A graph is called planar graph if it can be draen in a plane without any edges of crossed.
• Isomorphism: if tw graph G and G contain the same number are that are Vertex. if it maps Adjacetn
• Euclidean Linear: connection between graph is that is called called an Euelar if called Euler path start end the V. Euler linear called Vertex is are is if the other vertex Caylems Therm: and connected of the it it state if stated labeled 1,0,...
• *Homomorphism always Linear edges connections graph is that is.
• Trees
• A forest F is a graph wich as no as no cycles. A
• A Tree
• if connected and has any cycle connected
• Drawing certain type of graph
• The euclidean Liner
• the n-cibe
• to draw a the n-cibe

Lesson 7: Propositional Logic

• Propositional Logic: concerned with statements to which the truth values, "true" and "false", can be assigned.
• Purpose to analyze these statements either individually or in a composite manner.
• A proposition consists of propositionals
• we denote the prepositional variables by CAPITAL letters (A,B,etc
• OR( V)
• the Or operations are a is a in A
• NOT "MAn IS MOrat returns truth value;TRUE" Truth Table
• *Negatiion( -
• Truth Table for NOT Connectives * Connect.

Truth Tables

• AND( Λ) Operations A and B (written Truth Table , is "Contradictions"Truth Table is ∧ Truth Table
• Contradiction statement Truth
• Truth Table of Implication Converse -True or Fase
• Truth Table for Fase is called by to
• *Implication -Truth Table is - True Equivilences -Truth Table for -True -True
• *Conradiction
• Converse if statment -* is " and statment is true

INVERSE, CONVERSE, CONTRA-POSITIVE

• Conditional Statment
• Hypothis is P Is denote as P > Q.
• Inverse: if do your homework the conradry Statement True Duability -Duality Statment and

NORMAL FORMS

CONJUNCITIVE

• Truth TAble
• and statments
• disyuntive

CONUUNCTIVE TABLE

TRUTH

• and statments
  TABLE TABLE

• This message shows the summary completed until Lesson 7.