Comprehensive Study Notes on Discrete Mathematics and Discrete Structures

Overview and Definition of Discrete Mathematics

• Definition and Etymology of Discrete:

  • Phonetic spelling and pronunciation: dis·crete / dis’krët.

  • Part of speech: Adjective.

  • Formal definition: Individually separate and distinct.

  • Direct synonyms: Separate, detached, distinct, abstract.

• The Concept of Mathematics:

  • Defining discrete mathematics is difficult primarily because defining mathematics itself is complex.

  • Mathematics is often defined as the study of numbers, functions, lines, triangles, parallelepipeds, vectors, and related concepts.

  • Alternatively, mathematics can be viewed as a collection of tools designed to solve problems involving numbers, functions, lines, and geometric shapes.

  • Discrete mathematics applies the definition of "discrete" (individually separate and distinct) to these mathematical concepts.

• Continuous vs. Discrete Mathematics:

  • In algebra or calculus, sets of numbers (such as the range of a function) are frequently represented as continuous intervals.

  • Continuous Example: The range of the squaring function $f(x) = x^2$ is the interval $[0, \infty)$, representing all real numbers greater than or equal to $0$.

  • Why the Interval is Not Discrete: The set $[0, \infty)$ is not discrete because its numbers are not separated from one another. Between any two distinct numbers in the set, there exist infinitely many other real numbers that are also contained in the set.

  • Discrete Example: Consider a function that outputs the exact number of children of each person reading this material.

  • Range of Discrete Function: The range is a discrete set such as $\{0, 1, 2, 3\}$, or possibly including $5$ or $6$. Nobody reading has $1.32419$ children.

  • Why the Set is Discrete: The output set is discrete because its elements are separate and isolated integers. The domain of inputs is also a discrete set because each input is an individual person.

Core Areas of Discrete Mathematics: Introductory Problems

• Investigative Activities in Discrete Mathematics:

  • Discrete structures are used to model real-world problems. Four foundational problems illustrate the core themes of the field:

• Problem 1: The Handshake Problem

  • Scenario: The most popular mathematician in the world hosts a party for all of his friends.

  • Setup: Exactly $10$ people attend the party. Everyone shakes hands with every other person (excluding themselves) exactly once.

  • Target Question: How many total handshakes take place?

• Problem 2: Hot Dog Eating Contest Warm-Up

  • Scenario: A warm-up event for Oscar's All-Star Hot Dog Eating Contest features $26$ contestants.

  • Individual Consumption Pattern:

  • $1\text{-st}$ contestant (Al) eats $1$ hot dog.

  • $2\text{-nd}$ contestant (Bob) eats $3$ hot dogs.

  • $3\text{-rd}$ contestant (Carl) eats $5$ hot dogs.

  • Each subsequent contestant eats $2$ more hot dogs than the contestant before them.

  • Target Questions: How many hot dogs did Zeno (the $26\text{th}$ and final contestant) eat? How many total hot dogs were eaten by all $26$ contestants combined?

• Problem 3: The Burial Chamber Chests

  • Scenario: After excavating for weeks, a burial chamber is discovered containing two large empty chests with carved English messages.

  • Scenario Rules:

  • Exactly one chest contains treasure, while the other chest is filled with deadly immortal scorpions.

  • For either chest, if the chest's carved message is true, then the chest contains treasure.

  • Dilemma: It is unknown whether either carved message is true or false.

  • Target Question: What logical approach determines which chest to open safely?

• Problem 4: Connecting Towns Without Intersections

  • Scenario: In ancient times, five small towns decide to build direct roads connecting every pair of towns.

  • Constraints:

  • Unlimited funds are available to build roads as long and winding as necessary.

  • Stop signs have not been invented, so no two roads are permitted to intersect.

  • Tunnels and bridges are strictly prohibited due to moral reasons.

  • Target Question: Is it possible for each of the $5$ towns to construct a road to each of the four other towns without creating any road intersections?

Analysis of Introductory Problems

• Structural Representations for Solutions:

  • Handshake Problem Analysis:

  • The attendees represent individual elements of a set.

  • A handshake requires a pair of two distinct people. The problem asks how many pairs can be formed from a $10\text{-element}$ set.

  • Three-Person Example: If $3$ people named $A$, $B$, and $C$ attend, the unique pairs are $\{A, B\}$, $\{A, C\}$, and $\{B, C\}$. Pairs such as $\{B, A\}$ represent the same physical handshake and are not listed separately.

  • Hot Dog Problem Analysis:

  • Hot dog consumption is modeled using sequences of integers (whole numbers).

  • First Sequence: The $n\text{-th}$ term represents the number of hot dogs eaten by the $n\text{-th}$ contestant.

  • Second Sequence: Represents the cumulative total of hot dogs eaten by the first $n$ contestants combined.

  • Solution Method: Determine the $26\text{-th}$ term in the cumulative sequence by analyzing sequence growth rates and interrelationships.

  • Scorpion Chests Logic Analysis:

  • Belongs to symbolic logic within discrete mathematics.

  • Statements have discrete truth values: strictly True or strictly False, with no intermediate possibilities.

  • Solution Method: Analyze statement structures and evaluate how the truth values of component parts interact to govern the truth value of the compound statement.

  • Towns and Roads Graph Analysis:

  • Modeled using a discrete structure called a graph (distinct from a continuous function graph).

  • A graph represents connections between set elements (towns connected by roads).

  • Towns represent vertices and roads represent edges. The problem asks if a graph with $5$ vertices and $10$ edges can be drawn without any edges intersecting.

• The Four Main Topics of Discrete Mathematics:

  • Combinatorics: The theory of how objects combine and the formal techniques used to count these combinations (illustrated by the Handshake problem).

  • Sequences: The study of ordered lists of numbers, rates of growth, and summation properties (illustrated by the Hot Dog problem).

  • Symbolic Logic: The study of truth values, logical operators, and deductive reasoning structures (illustrated by the Scorpion Chests problem).

  • Graph Theory: The study of networks composed of vertices and connecting edges (illustrated by the Towns and Roads problem).

  • Related Fields in Discrete Mathematics: Computer science, abstract algebra, number theory, game theory, probability (discrete variants), and geometry (discrete variants).

Discrete Structures Overview

• Definition and Role of Discrete Structures:

  • Discrete structures are fundamental mathematical objects used to represent components of real-world and theoretical problems.

  • The term "structure" highlights the presence of rigid constraints defining each object, analogous to physical structures like apartment buildings, airplane hangars, or suspension bridges.

  • Key Discrete Structures: Sets, functions, sequences, relations, and graphs.

• Problem-Solving Methodology:

  • Discrete mathematics focuses on a problem-solving approach: examining discrete questions, developing solution procedures, and proving answer correctness.

  • Educational Analogy: Studying mathematical tools without solving problems is like art students studying paintbrushes, easels, and paint chemistry without ever painting actual landscapes.

• Purpose of Reading Questions:

  • End-of-section reading questions promote reflection on material.

  • Formulating individual questions helps identify knowledge gaps and deepens conceptual understanding.

• Domino Set Problem (Investigate 0.2.1):

  • A double-six domino set consists of tiles containing pairs of numbers, each ranging from $0$ to $6$.

  • Key Questions: How many tiles are in a double-six domino set? How many dominoes are in a double-nine domino set? How many dominoes are in a double-$n$ domino set?

Sets

• Definition of a Set:

  • A set is an unordered collection of elements.

  • All of mathematics can be defined using set theory (including numbers themselves).

• Methods for Describing Sets:

  • Verbal Description: Specifying membership conditions in plain language (e.g., "Let $A$ be the set of all natural numbers less than $10$").

  • Roster Notation / Explicit Listing: Listing all elements explicitly inside curly braces, e.g., $A = \{0, 1, 2, 3, 4, 5, 6, 7, 8, 9\}$.

  • Set Comprehension / Set-Builder Notation: Expressing membership via formal logical conditions, e.g., $A = \{x \in \mathbb{N} : x < 10\}$.

  • Symbol Definitions:

    • $\mathbb{N}$ represents the set of natural numbers: $\mathbb{N} = \{0, 1, 2, 3, \dots\}$.

    • $\in$ means "is an element of".

    • : is read as "such that" and precedes the criteria defining membership.

• Principles of Set Membership and Equality:

  • A set is defined entirely by its membership; element order and duplicate entries do not alter the set.

  • Identical Set Descriptions: The following four descriptions define the exact same set:

  1. $\{1, 2, 3\}$

  2. $\{1, 1, 2, 2, 3, 3, 3\}$ (Contains exactly $3$ elements, not $7$)

  3. $\{3, 2, 1\}$ (Element order is irrelevant)

  4. $\{x \in \mathbb{N} : x \le 3 \text{ and } x \ge 1\}$

• Common Operations and Properties of Sets:

  • Set Construction: Creating new sets via union ($\cup$) and intersection ($\cap$).

  • Set Comparison: Evaluating subset relationships ($\subseteq$).

  • Cardinality: The measure of the number of elements contained in a set.

Functions

• Definitions and Terminology:

  • A function is a rule assigning each input exactly one output.

  • Image: The unique output assigned to a given input.

  • Domain: The set of all valid input values.

  • Codomain: The set of all allowable potential output values.

  • Range: The set of all actual outputs (the collection of all images of domain elements).

  • Notation: $f: A \rightarrow B$ specifies a function named $f$ mapping domain $A$ to codomain $B$.

• Defining Function Rules:

  • Functions can be specified using algebraic formulas (e.g., $f(x) = x^2$ maps inputs to their square), verbal descriptions, tables, or graphs.

  • Single Output Requirement: A valid function rule must assign precisely one output value for any valid input in the domain.

• Functions as Sets of Ordered Pairs:

  • The graph of a function is represented as a set of ordered pairs $(x, y)$.

  • Example 0.2.2: Consider the function $f: \{1, 2, 3\} \rightarrow \mathbb{N}$ defined by $f(x) = x^2$.

  • Evaluated Points: $(1, 1)$, $(2, 4)$, and $(3, 9)$.

  • Discrete Graphing: Points are drawn individually without connecting lines because the domain contains only three distinct elements.

  • Equivalence: The set of ordered pairs {!(1, 1), (2, 4), (3, 9)}  is identical to the function itself.

• Types of Function Formulas:

  • Closed Formula: Provides an explicit calculation rule based solely on the input value.

  • Example: $f(n) = 3n + 1$. To find $f(5)$, evaluate $3 \times 5 + 1 = 16$.

  • Recursive Definition: Computes function outputs based on previously calculated outputs of the same function.

  • Example: Recurrence $f(n) = f(n-1) + 3$ with initial condition f(1) = 4$.\n - Evaluation Process: To find f(5)$, calculate$f(2) = f(1) + 3 = 7$,$f(3) = f(2) + 3 = 10$,$f(4) = f(3) + 3 = 13$, and$f(5) = f(4) + 3 = 16$.

Sequences

• Definition and Properties of Sequences:

  • A sequence is an ordered collection of numbers.

  • Unlike sets, element ordering matters, and repeated values retain distinct positional entries.

  • Finite Sequences and Tuples: The finite sequence $(1, 2, 3)$ contains $3$ elements and is called an ordered triple. In general, an ordered collection of $n$ elements is called an $n\text{-tuple}$.

  • Difference Between Sequences and Sets: The sequence $(1, 2, 3) \neq (3, 2, 1)$, whereas the set \{1, 2, 3\} = \{3, 2, 1\}$.\n\n- Sequences as Counting Tools:\n - Generalizing counting questions yields sequences of answers.\n - Example: Asking "How many wheels do n$cars have?" yields the infinite sequence$4, 8, 12, 16, 20, \dots.\n\n- Formal Definition of Sequences as Functions:\n - A sequence is a function whose domain is the set of natural numbers \mathbb{N}$or a subset of consecutive natural numbers (e.g.,${1, 2, 3, \dots, n}), representing positions.\n - The codomain is a specified target set, and function outputs represent sequence terms.\n - Subscript Notation: Terms are denoted a_n$instead of standard function notation$a(n).\n - Full Sequence Notation: Denoted (a_n){n \in \mathbb{N}}$or$(a_n){n \ge 1}.\n - Example: Fibonacci sequence 1, 1, 2, 3, 5, 8, 13, \dots$. The$4\text{-th}$term is$a_4 = 3$(assuming$a_1 = 1 is the first term).\n\n- Tabular Representation of Sequences:\n - Sequences can be presented using two-row input-output tables mapping term positions to term values.\n - Example Table (Triangular Numbers):\n\n\n\n- Closed Formulas vs. Recursive Definitions for Sequences:\n - Closed Formula: Explicit rule for the n\text{-th}$term, e.g.,$a_n = \frac{n(n+1)}{2}.\n - Recursive Definition: Defines terms using preceding terms, e.g., Fibonacci recurrence a_n = a_{n-1} + a_{n-2}$with initial conditions$a_1 = 1$and$a_2 = 1.\n\n# Relations\n\n- Definition and Binary Relations:\n - A relation specifies a connection between mathematical objects.\n - Binary Relations: Relate pairs of elements.\n - Examples using numbers 2$and$6:\n - Less-than relation: 2 < 6.\n - Multiple-of relation: 6$is a multiple of$2.\n - Parity relation: 2$and$6 are both even.\n - Inequality relation: 2 eq 6$.

• Relations on Multi-Element Tuples:

  • Relations can involve more than two elements.

  • Example: The "Pythagorean triple" relation on three numbers $(a, b, c)$ holds precisely when $a^2 + b^2 = c^2$.

  • True statement: The triple $(3, 4, 5)$ belongs to the relation because $3^2 + 4^2 = 5^2$ ($9 + 16 = 25$).

  • False statement: The triple $(2, 3, 4)$ does not belong because 2^2 + 3^2 = 13 \neq 16 = 4^2$.\n\n- Formal Set-Theoretic Definition:\n - A relation is formally defined as a set of ordered pairs (or triples, n\text{-tuples}).\n - The "less-than" relation on real numbers is represented by the infinite set of ordered pairs \{\!(x, y) \in \mathbb{R}^2 : x < y\}\n.\n\n- Standard Properties of Relations:\n - Irreflexive: No element is related to itself. (Less-than is irreflexive because x < x$is false for all$x).\n - Antisymmetric: For distinct x$and$y$, if$x$is related to$y$, then$y$cannot be related to$x$. (Less-than is antisymmetric because$x < y$and$y < x cannot both be true).\n - Transitive: If x$is related to$y$and$y$is related to$z$, then$x$is related to$z$. (Less-than is transitive because$x < y$and$y < z$implies$x < z).\n - Equivalence Relation: A relation that is simultaneously reflexive (every element is related to itself), symmetric (if x$is related to$y$, then$y$is related to$x), and transitive.\n\n# Graphs\n\n- Set Construction and Visual Representation:\n - Example Set: V = {1, 2, 3, 4, 5, 6}.\n - Unordered pairs summing to 7$:${1, 6}$,${2, 5}$,${3, 4}.\n - Unordered pairs summing to an even number yield a distinct set of connections.\n - Graph Definition: A visual drawing of dots (vertices) and lines (edges) modeling relationships between set elements.\n\n- Formal Definition of Graphs:\n - A graph is a symmetric and irreflexive binary relation.\n - Symmetric: If vertex u$is related to vertex$v$, then$v$is related to$u.\n - Irreflexive: No vertex is related to itself.\n - Formally defined as a set of vertices V$together with a set of edges$E, where each edge is a two-element subset of vertices.\n\n- Real-World Applications of Graphs:\n - Social Networks: Students represented as vertices, mutual friendships represented as edges.\n - Geography: Countries represented as vertices, edges connecting countries that share a land border.\n - Airline Flight Networks: Airports represented as vertices (e.g., Denver, Newark, Paris); edges represent direct flights. Graph theory determines whether direct flights exist between Denver and Paris or require a layover in Newark.\n - Package Delivery Optimization: Amazon drivers delivering packages to 10$$ neighborhood houses use graph theory algorithms to determine optimal delivery routes.

Additional Discrete Structures

• Overview of Other Discrete Structures:

  • Multisets: Collections similar to sets that permit repeated element occurrences.

  • Finite Geometries and Designs: Structures occupying an intermediate position between graphs and traditional geometries.

  • Computer Science Data Structures: Data organization structures such as linked lists and red-black trees.

  • Abstract Algebra Structures: Algebraic systems built on underlying sets with operations, including groups, rings, matroids, partially ordered sets (POSets), and Boolean algebras.