Discrete Math › Section A · Introduction and preliminaries › Topic A.2
A tour of discrete structures
Every discrete problem is solved by modelling it with a few standard objects: sets, functions, sequences, relations and graphs. This tour introduces each one briefly, so you can recognise it when later topics study it in depth.
Structures are the tools
In the previous topic, What is discrete mathematics?, each puzzle was solved by choosing the right model: pairs of people, a list of row sizes, a network of villages. Those models are discrete structures, mathematical objects with fixed rules. A set ignores order; a sequence depends on it. A function must give exactly one output; a relation need not. Knowing the rules tells you which structure fits a problem.
Sets
A set is an unordered collection of distinct objects, called its elements. You can describe a set in words, list its elements in braces, as in \(\{2, 3, 5\}\), or use set-builder notation, as in \(\{x \in \mathbb{N} : x < 6\}\), read "the set of natural numbers x such that x is less than 6". The symbol \(\in\) means "is an element of". This course takes the natural numbers to be \(\mathbb{N} = \{0, 1, 2, 3, \dots\}\), as many discrete mathematics books do, though others start at 1. A set is fixed by its members alone, so \(\{1, 2, 3\}\), \(\{3, 1, 2\}\) and \(\{1, 2, 2, 3\}\) are the same set, with 3 elements.
Building and comparing sets
New sets are built from old ones. For \(A = \{1, 2, 3, 4\}\) and \(B = \{3, 4, 5\}\), the union \(A \cup B = \{1, 2, 3, 4, 5\}\) holds everything in either set, and the intersection \(A \cap B = \{3, 4\}\) holds what they share. A set \(C\) is a subset of \(A\), written \(C \subseteq A\), when every element of \(C\) is in \(A\), as with \(\{1, 4\} \subseteq A\). The number of elements is the cardinality, written \(|A| = 4\). A multiset is a related structure that allows repeats, such as the digits of 1012. The topic Sets and set operations develops all of this.
Functions
A function \(f: X \to Y\) assigns to each element of the domain \(X\) exactly one element of the codomain \(Y\). The output \(f(x)\) is the image of \(x\), and the set of all actual outputs is the range, which may be smaller than the codomain. A rule that gives some input no output, or two outputs, is not a function: "send x to a number whose square is x" gives the input 4 two outputs, 2 and −2. A function can also be seen as a set of ordered pairs, one pair (input, output) for each input.
Worked example: a set and a function
Let \(A = \{x \in \mathbb{N} : x^2 < 20\}\), and let \(f: A \to \mathbb{N}\) give the remainder when x is divided by 3. 1. List A: \(4^2 = 16 < 20\) but \(5^2 = 25\), so \(A = \{0, 1, 2, 3, 4\}\). 2. Compute the images: 0, 1, 2, 0, 1. 3. As ordered pairs, f is (0, 0), (1, 1), (2, 2), (3, 0), (4, 1). 4. The range is \(\{0, 1, 2\}\), much smaller than the codomain \(\mathbb{N}\). 5. Check that f is a function: every input has exactly one output. Repeated outputs are allowed; only an input with two outputs would break the rule.
Sequences
When order matters, use a sequence instead of a set. The ordered triple (1, 2, 3) differs from (3, 2, 1), and (2, 2) is a perfectly good ordered pair, while the sets \(\{1, 2, 3\}\) and \(\{3, 2, 1\}\) are equal. A finite sequence of n terms is also called an n-tuple. An infinite sequence \(a_0, a_1, a_2, \dots\) is really a function whose inputs are the positions 0, 1, 2, ... and whose outputs are the terms. The Fibonacci numbers 1, 1, 2, 3, 5, 8, 13, ... are a famous example: each term after the first two is the sum of the two before it.
Closed and recursive formulas
A sequence can be described in two ways. A closed formula gives each term directly from its position, as in \(a_n = 4n + 1\), which makes \(a_{10} = 41\) immediately. A recursive definition gives each term from earlier terms, together with an initial condition to start from, as in \(a_0 = 1\) and \(a_n = a_{n-1} + 4\). Both describe 1, 5, 9, 13, .... A recursive definition is often easier to find, but reaching a far-off term means computing every term before it.
Worked example: one sequence, two descriptions
A colony starts with 2 bacteria and triples every hour. Describe the counts and find the count after 5 hours. 1. List the first terms: 2, 6, 18, 54, .... 2. Recursive definition: \(a_0 = 2\) and \(a_n = 3a_{n-1}\) for \(n \ge 1\). 3. Closed formula: n triplings multiply the start by \(3^n\), so \(a_n = 2 \cdot 3^n\). 4. Recursively: 54, then 162, then \(a_5 = 486\). 5. From the closed formula: \(2 \cdot 3^5 = 2 \cdot 243 = 486\). 6. Check: the formula also gives \(a_3 = 2 \cdot 27 = 54\), matching the list.
Relations
A binary relation on a set is a collection of ordered pairs that records which elements are related. On \(\{1, 2, 3, 4\}\), the relation "a divides b" contains exactly 8 pairs: (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3) and (4, 4). Relations are classified by their properties. This one is reflexive, since every number divides itself. It is transitive: if a divides b and b divides c, then a divides c. It is not symmetric, since 1 divides 2 but 2 does not divide 1. The topic Relations and their properties studies these ideas, including equivalence relations.
Worked example: building a graph
A graph consists of vertices and edges; an edge is an unordered pair of distinct vertices. Take vertices 1, 2, 3, 4, 5, and join two numbers when their sum is prime. 1. Test every pair: the prime sums are 1 + 2 = 3, 1 + 4 = 5, 2 + 3 = 5, 2 + 5 = 7 and 3 + 4 = 7. 2. So the edges are {1, 2}, {1, 4}, {2, 3}, {2, 5} and {3, 4}. 3. The degree of a vertex is its number of edges: 1, 3, 4 have degree 2, vertex 2 has degree 3, vertex 5 has degree 1. 4. Check: the degrees add to 10, twice the 5 edges, since each edge has two ends.
Common mistakes to avoid
First, confusing the set \(\{1, 2\}\) with the ordered pair (1, 2): the set ignores order. Second, counting repeated elements, as if \(\{1, 2, 2\}\) had 3 elements; only a multiset keeps repeats. Third, calling the codomain the range: the range is only the outputs that actually occur. Fourth, rejecting a function because two inputs share an output; that is allowed, but one input with two outputs is not. Fifth, forgetting the initial condition of a recursive definition, without which no term can be computed.
Key takeaways
A set is an unordered collection of distinct elements, described in words, by a list or in set-builder notation, and built up with union and intersection. A function gives every input in its domain exactly one output in its codomain; its range is the set of actual outputs. A sequence is an ordered list, really a function on positions, given by a closed formula or a recursive definition with an initial condition. A relation is a collection of ordered pairs, classified by properties such as reflexive, symmetric and transitive. A graph has vertices joined by edges, each edge an unordered pair of distinct vertices.
Flashcards
Flashcard
A mathematical object used to model a problem
Test your understanding
Question 1 of 5
How many elements does the set {3, 1, 3, 2, 1} have?
Question 2 of 5
The function f: {1, 2, 3} → {1, 2, ..., 10} is given by f(x) = x + 4. What is its range?
Question 3 of 5
A sequence has a₀ = 5 and aₙ = aₙ₋₁ + 4 for n ≥ 1. What is a₃?
Question 4 of 5
Which rule is NOT a function from {1, 4, 9} to the integers?
Question 5 of 5
A graph has vertices 1, 2, 3, 4, and two vertices are joined when they differ by exactly 1. How many edges does it have?
