University Discrete Mathematics — Sets, Functions and Relations Worksheet

13 of the 14 questions

Each question targets one named concept from the sheet. Read them here, or print the PDF — it has working space under each one. 13 of the 14 questions are printed below. The other 1 is built on a diagram or a table of values that does not translate to the page, so it is in the free PDF — marked below where it would have come.

1. Q1Set Notation, Subsets and Power Sets

   Throughout, $\mathbb{N}=\{0,1,2,\dots \}$. List the elements of each set and give its cardinality.

   1. $A=\{n\in \mathbb{Z}\mid n^2\le 7\}$
   2. $B=\{3k-1\mid k\in \mathbb{N},k<4\}$
   3. $C=\{x\in \mathbb{Q}\mid x^2=2\}$ (you may use the fact that $\sqrt{2}$ is irrational)
   4. Write the set $D=\{\dots ,-7,-2,3,8,13,\dots \}$ in set-builder notation.
2. Q2Set Notation, Subsets and Power Sets

   Let $A=\{p,q,r\}$, where $p$, $q$ and $r$ are three different letters (none of them is itself a set), and recall that the power set $𝒫(A)$ is the set of all subsets of $A$.

   1. List the elements of $𝒫(A)$ and give $|𝒫(A)|$.
   2. Decide whether each statement is true or false, with a one-line reason.\\ (i)~$\varnothing \in 𝒫(A)$ (ii)~$\{p\}\in A$ (iii)~$\{p\}\subseteq A$ (iv)~$\{\{p\},\{q,r\}\}\subseteq 𝒫(A)$\\ (v)~$\{p,\{q\}\}\subseteq 𝒫(A)$ (vi)~$A\in 𝒫(A)$
3. Q3Set Operations and Venn Diagrams

   Let the universe be $U=\{1,2,\dots ,12\}$ and let $A=\{n\in U\mid n\text{ is even}\}$, $B=\{n\in U\mid n\text{ is a multiple of }3\}$ and $C=\{n\in U\mid n\le 4\}$. List the elements of each set.

   1. $A\cap B$
   2. $B\cup C$
   3. $A⧵B$
   4. $\overline{A\cup B}$ (the complement is taken in $U$)
   5. $(A\cap C)\times (B\cap C)$
   6. Write the set of elements of $U$ that lie in exactly one of $A$ and $B$ using only $A$, $B$, $\cup$, $\cap$ and $⧵$, then list it.
4. Q4Proving Set Identities

   Use a membership table (one row for each of the eight patterns of membership in $A$, $B$ and $C$) to decide whether each of the following holds for all sets $A$, $B$ and $C$. Where one fails, name a row that shows it.

   1. $A⧵(B\cap C)=(A⧵B)\cup (A⧵C)$
   2. $(A\cup B)⧵C=A\cup (B⧵C)$
5. Q5Proving Set Identities

   Using the standard set laws, and naming the law at each step (De Morgan, distributive, complement, identity, and so on), simplify $$\overline{A\cup B}\cup (\bar{A}\cap B),$$ where complements are taken in a universe $U$.

6. Q6Injective, Surjective and Bijective Functions

   A function $f:X\to Y$ is injective (one-to-one) when different inputs always give different outputs, surjective (onto) when every element of $Y$ is an output, and bijective when it is both. Classify each function as bijective, injective only, surjective only, or neither.

   1. $f:\{1,2,3,4\}\to \{w,x,y,z\}$ with $f(1)=x$, $f(2)=z$, $f(3)=w$, $f(4)=y$
   2. $g:\{1,2,3,4\}\to \{w,x,y\}$ with $g(1)=w$, $g(2)=y$, $g(3)=x$, $g(4)=y$
   3. $h:\{1,2,3\}\to \{w,x,y,z\}$ with $h(1)=z$, $h(2)=x$, $h(3)=w$
   4. Explain why no function from a $4$-element set to a $3$-element set can be injective.
7. Q7Injective, Surjective and Bijective Functions

   Decide whether each function is injective and whether it is surjective. Justify each “yes” in general and each “no” with specific elements. Here $\mathbb{N}=\{0,1,2,\dots \}$.

   1. $f:\mathbb{Z}\to \mathbb{Z}$, $f(n)=3n+1$
   2. $g:\mathbb{Z}\to \mathbb{N}$, $g(n)=|n|$
   3. $h:\mathbb{Z}\times \mathbb{Z}\to \mathbb{Z}$, $h(m,n)=2m+3n$
8. Q8Composition and Inverse Functions

   This question is built around a diagram or a table of values. Open it in the PDF.

9. Q9Relations and Their Properties

   A relation $R$ on a set $X$ is reflexive if $(x,x)\in R$ for every $x\in X$; symmetric if $(a,b)\in R$ implies $(b,a)\in R$; antisymmetric if $(a,b)\in R$ and $(b,a)\in R$ imply $a=b$; and transitive if $(a,b)\in R$ and $(b,c)\in R$ imply $(a,c)\in R$. On $X=\{1,2,3,4\}$ let $$R=\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(2,3)\}.$$ Decide which of the four properties $R$ has. For each one it lacks, name the pairs that show it.

10. Q10Relations and Their Properties

    For each relation on $\mathbb{Z}$, decide whether it is reflexive, symmetric, antisymmetric and transitive. Justify each “yes” in general and each “no” with specific integers.

    1. $aRb$ if and only if $a\le b+1$
    2. $aSb$ if and only if $ab>0$
11. Q11Equivalence Relations and Partitions

    On the set $X=\{-3,-2,-1,0,1,2,3\}$ define $aRb$ if and only if $a^2=b^2$.

    1. Explain briefly why $R$ is an equivalence relation.
    2. List its equivalence classes and say how many there are.
12. Q12Equivalence Relations and Partitions
    1. The collection $\{\{1,4\},\{2\},\{3,5,6\}\}$ is a partition of $\{1,2,3,4,5,6\}$. List the ordered pairs of the equivalence relation whose classes are these blocks, and give the number of pairs.
    2. Explain why neither $\{\{1,2\},\{2,3\},\{4,5,6\}\}$ nor $\{\{1,2\},\{4\},\{5,6\}\}$ is a partition of $\{1,2,3,4,5,6\}$.
13. Q13Partial Orders and Hasse Diagrams

    On $S=\{2,3,4,6,8,9,12\}$ write $a\mid b$ when $b$ is an integer multiple of $a$. The relation $\mid$ is a partial order on $S$.

    1. List the pairs $a\mid b$ with $a\ne b$ for which no $c\in S$ other than $a$ and $b$ satisfies $a\mid c$ and $c\mid b$, and draw the Hasse diagram.
    2. Give the minimal and the maximal elements, and say whether $S$ has a least or a greatest element.
    3. Give two elements that are incomparable.
14. Q14Synthesis — drawing on several topics in this unit

    Let $X=\{1,2,\dots ,8\}$ and define $f:X\to \{0,1,2\}$ by $f(n)=\lfloor n/3\rfloor$, the greatest integer less than or equal to $n/3$. Define a relation $R$ on $X$ by $aRb$ if and only if $f(a)=f(b)$.

    1. Is $f$ injective? Is it surjective?
    2. List the equivalence classes of $R$.
    3. How many ordered pairs does $R$ contain?
    4. List the set $\{n\in X\mid f(n)\ge 1\}$.

The 10 challenge problems for this topic are a separate, paid sheet and are not reproduced here.

How to do every concept on this sheet

This is the part worksheet sites usually leave out. Below is the actual reasoning behind each group of questions — not a full solution set, the decisions that get you to one. Read it before you start, or after you get stuck.

Describing a set, and reading the description back

A set is determined by its elements and by nothing else: no order, no repetition. Half the work in Q1 is translating between the two ways of writing one down — a list inside braces, and a rule of the form {x ∈ (some known set) | (a condition on x)}. Translating a rule into a list means testing candidates one at a time; translating a list into a rule means finding the pattern and naming the set the elements are drawn from.

Q1(b) is the other shape of rule: the element is given as an expression in a parameter, and the condition constrains the parameter rather than the element. Run k through every value the condition allows — with ℕ starting at 0, as the question states — and evaluate. Q1(c) is a rule that may be satisfied by nothing at all; the question hands you the fact about √2 that settles it, and your job is to say in a line why that fact decides membership. A set with no elements is a legitimate answer, written ∅, and its cardinality is a number like any other.

Membership, subsets and power sets

∈ and ⊆ are different relations between different kinds of object, and Q2 is built to catch the confusion between them. x ∈ A says x is one of the things A contains. B ⊆ A says every element of B is also an element of A — a statement about two sets. The power set 𝒫(A) is the set whose elements are the subsets of A, so its elements are themselves sets, and that is where the two symbols start trading places.

For Q2(a), build 𝒫(A) systematically rather than by inspiration: the empty set, then every one-element subset, then every two-element subset, then A itself. Listing by size is what stops a subset going missing. Each element of A is either in a given subset or out of it, independently of the others, so an n-element set has 2ⁿ subsets — use that as the check on the length of your list, not as a substitute for writing it.

Two facts worth stating before you start, because several parts turn on them: ∅ is a subset of every set, and each set counts as one of its own subsets.

The operations, in a fixed universe

Q3 fixes a universe U and three subsets of it described by rules, and asks for lists. Convert each of A, B and C to a list first, once, and then every part is bookkeeping on those three lists rather than a fresh reading of the rules.

Q3(a), (b) and (c) are those first three readings in turn, and (c) is the one to slow down on — a difference is not symmetric, so A − B and B − A are different questions. Q3(d) takes a complement of a compound set: build the union first, then keep everything of U that is not in it. Working the complement in your head over a union is where De Morgan's law would be needed, and the safer route with a listed universe is to build inside out.

Q3(f) asks for something in words — the elements in exactly one of A and B — and demands an expression built only from A, B, ∪, ∩ and difference. "Exactly one" is "in at least one, but not in both", and it is also "in A but not B, or in B but not A". Either reading turns into a formula with the symbols allowed; write the formula, then list the set it produces and check the list against your reading of the phrase. A Venn diagram with the wanted regions shaded is the fastest way to see that the two readings shade the same regions.

Proving an identity with a membership table

Q4 asks whether two expressions agree for all sets A, B and C, which is a different question from whether they agree on one example. A membership table settles it exhaustively. Each of the eight rows is one pattern of "in or out" for the three sets — this is the truth table of Propositional and Predicate Logic with 1 read as "is an element" — and each column is built from the columns before it by one operation.

Proving an identity with the set laws

Q5 forbids the table and asks for a chain of named steps. Each line is one expression, and between two lines you name the single law that got you there: De Morgan, distributive, complement, identity, domination, absorption, commutative, associative, double complement.

The expression in Q5 opens with a complement over a union, so the first move is the one law that can get inside it. After that, look at what the two halves of the expression have in common: a distributive law run backwards factors a shared set out of a union of two intersections, and once a set stands beside its own complement, the complement and identity laws collapse it. Work in small steps and never merge two laws into one line — the mark is for the chain, and a line without a named law is a line that has not been justified.

Injective, surjective and bijective

Q6 states the three definitions for you and gives three functions between small listed sets, each by its values. Test them on the picture: draw an arrow from each element of the domain to its value. Injective means no element of the codomain receives two arrows; surjective means every element of the codomain receives at least one. Bijective is both, and "neither" is one of the four labels on offer, so do not force a function into a class.

Q6(d) asks for a general argument rather than an example: why no function from a 4-element set to a 3-element set can be injective. Count arrows against targets — four arrows leaving, three possible destinations — and say what must therefore happen to at least one destination. Writing that sentence properly is the whole question; an example of one such function proves nothing about all of them.

Q7 moves to infinite domains, where arrows are no longer available and the definitions must be used directly. The asymmetry of the work is the thing to internalise, and the question states it: a "yes" is justified in general, a "no" with specific elements.

Step 3 is where Q7(a) has to be read carefully: solving gives a formula for x, and the question is whether that formula always lands back inside ℤ. Q7(b) has ℕ as its codomain, so the reachable targets and the two-sided domain are what the two tests turn on. In Q7(c) the domain is a set of pairs, so an input is (m, n) and two inputs being equal means both coordinates agreeing — which makes the injectivity test a question about whether one equation in two unknowns pins both of them down.

Composition and inverses

Q8 gives f and g on a four-element set as a table of values. Composition is evaluation twice, and the order is the trap: (g ∘ f)(x) means apply f first, then g. Build each composite as a new row of the table, one input at a time, reading f's row and then looking that value up in g's row.

Q8(a) asks both composites and whether they are equal, which is a question about the whole tables: equal means agreeing at every one of the four inputs, so one disagreement settles it and should be pointed at explicitly. Q8(b) asks for the table of the inverse of f. An inverse exists exactly when a function is bijective, and for a function given by a table you obtain it by reversing every arrow: the row of f read backwards. Check it by composing — an inverse composed with its function must send every input to itself.

The four properties of a relation

Q9 states the four definitions and gives a relation on a four-element set as an explicit list of ordered pairs. Work property by property, and let the definition dictate what you look for.

Q10 asks the same four questions about two relations on ℤ, defined by conditions rather than listed, so each "yes" is a short proof from the condition and each "no" is specific integers. For the first, a ≤ b + 1, write out what the condition says with the same variable in both slots to test reflexivity, and swap the roles of a and b to test symmetry; transitivity means chaining two inequalities and asking whether what you get is still of the required form — and the constant is what makes that interesting. For the second, ab > 0, the sign rules do the work, and the value 0 is the element to keep an eye on throughout, since it is the one integer whose product with anything is not positive.

Equivalence relations and partitions

An equivalence relation is one that is reflexive, symmetric and transitive at once, and its classes carve the set into blocks. Q11 defines a relation on a small listed set by a² = b², and Q11(a) asks only for a brief reason that it is an equivalence relation — so give the three conditions in three lines, each following from a property of equality itself, rather than checking pairs.

Q11(b) asks for the classes. Build them by sweeping the set: take the first element, collect everything related to it, strike all of those off, take the first element left, and repeat until nothing is left. That procedure guarantees what the theory promises — the classes are disjoint and together they cover X — and the count of classes falls out of the list.

Partial orders and Hasse diagrams

A partial order is reflexive, antisymmetric and transitive. Q13 hands you the fact that divisibility is a partial order on the given set of integers, so nothing has to be proved and everything has to be read off. Write a | b for "b is an integer multiple of a", and start by listing every such pair on the set — that list is the raw material for all three parts.

Q13(b) asks for minimal and maximal elements and then for a least and a greatest — four terms and two distinctions. Minimal means nothing in the set is strictly below it, and there may be several; least means it sits below everything, and there is at most one. On the diagram, minimal elements are the ones with no line going down, and a least element would have to be a single element from which every other element can be reached going up. Q13(c) asks for two incomparable elements: a pair with neither dividing the other, which on the diagram is a pair joined by no upward path in either direction. Incomparable pairs are what makes the order partial.

The synthesis question

Q14 runs the whole set through one construction: a function f on an eight-element set given by a floor expression, and the relation "f takes the same value". Compute the table of f first — all eight values, written out — and everything else is read from that table.

Q14(a) is Q6 and Q7 again, now on a listed domain: scan the table for a repeated value, and compare the values that occur against the codomain the question names. Q14(b) is Q11(b): the classes are the groups of inputs sharing a value, so the table sorted by value is the list of classes. Q14(c) is Q12(a)'s sum of squares applied to those class sizes — a relation of this form is automatically an equivalence relation, because equality of values is reflexive, symmetric and transitive, which is worth saying in a line before counting. Q14(d) is a set-builder question in the style of Q1: test each of the eight inputs against the stated condition on f and list the survivors.

Preview all 8 pages

Click any page to open the full PDF.

Getting the most out of it

Write the definition before you use it

Injective, surjective, reflexive, antisymmetric, transitive, partition: each is a quantified sentence, and the sentence tells you what a proof and what a disproof must look like. Copy it at the top of your work and let the quantifier decide whether you owe a general argument or a single example.

Draw the small cases

Arrow pictures for functions, Venn diagrams for operations, a grid of ordered pairs for a relation, an upward diagram for an order. On the finite sets this set works with, the picture is complete information, and it makes a missing pair or an unreached element visible in a second.

One example proves nothing about all sets

Testing a proposed identity on three particular sets and finding it holds is not a proof — it is one row of a membership table. Either fill in all eight rows or argue with named laws. The only thing a single example can settle is a failure.

Separate ∈ from ⊆ every time you write one

Before writing either symbol, say what kind of object sits on each side. Most lost marks in this set are an element treated as a set or a set treated as an element, and once power sets are in play both sides can be sets without the statement being true.

Check your work against its own count

A power set has 2ⁿ elements, a product of two sets has the product of their cardinalities, and the classes of an equivalence relation must add up to the whole set. Each of these is a one-line arithmetic check on a list you have just written, and each catches a dropped item.

Common questions