"Sets, Relations and Functions" — Practice

Question 1

How many relations on a three-element set are reflexive? How many are symmetric? How many are both?

Accepted Answer

There are nine pairs in the Cartesian product, three on the diagonal and six off it. For reflexive relations the three diagonal pairs are forced in and the other six are free, giving 2 to the power 6, which is 64. For symmetric relations the three diagonal pairs are each free and the six off-diagonal pairs form three mirror couples that are wholly in or wholly out, giving 3 plus 3 free choices, so 2 to the power 6, which is 64 again. For relations that are both, the diagonal is forced and only the three couples remain free, giving 2 cubed, which is 8.

Question 2

Give a relation on {1,2,3} that is symmetric and transitive but not reflexive, and explain why the usual argument that symmetry plus transitivity forces reflexivity fails.

Accepted Answer

Take R = {(1,1),(1,2),(2,1),(2,2)}. It is symmetric, since each off-diagonal pair appears with its mirror. It is transitive, as can be checked on all chains within {1,2}. It is not reflexive, because (3,3) is absent. The usual argument runs that aRb gives bRa by symmetry and the two together give aRa by transitivity. That argument silently assumes some b exists with aRb. Here the element 3 is related to nothing at all, so the chain never begins and reflexivity at 3 is never forced.

Question 3

On the integers define aRb when a minus b is divisible by 7. Prove that R is an equivalence relation and state how many equivalence classes it has.

Accepted Answer

Reflexive: a minus a is 0, which is divisible by 7, so aRa always holds. Symmetric: if a minus b equals 7k then b minus a equals minus 7k, again a multiple of 7, so bRa holds. Transitive: if a minus b equals 7k and b minus c equals 7l, then adding gives a minus c equal to 7 times k plus l, so aRc holds. All three conditions hold, so R is an equivalence relation. Its classes collect integers sharing a remainder on division by 7, so there are exactly 7 classes, and they partition the integers.

Question 4

How many equivalence relations can be defined on a set of four elements, and what is the fastest way to obtain the answer?

Accepted Answer

There are 15. The fastest route is the correspondence between equivalence relations and partitions, which says that counting equivalence relations is the same as counting the ways to cut the set into non-overlapping blocks. For four elements the partitions are: one block of four, which is 1 way; a block of three with a singleton, which is 4 ways; two blocks of two, which is 3 ways; a block of two with two singletons, which is 6 ways; and four singletons, which is 1 way. The total is 1 plus 4 plus 3 plus 6 plus 1, which is 15.

Question 5

In a group of 100 students, 60 study Physics, 45 study Chemistry and 25 study both. How many study neither?

Accepted Answer

By inclusion-exclusion, the number studying at least one subject is 60 plus 45 minus 25, which is 80. The subtraction is needed because the 25 students taking both were counted once in each of the first two figures. Those studying neither subject are the remainder of the group, namely 100 minus 80, which is 20 students.

Question 6

A set A has 3 elements and a set B has 4 elements. Find the number of subsets of A, the number of relations from A to B, and the number of functions from A to B.

Accepted Answer

The number of subsets of A is 2 cubed, which is 8, since each of the 3 elements is independently in or out. The Cartesian product of A with B has 3 times 4, which is 12, ordered pairs, and a relation is any subset of it, so there are 2 to the power 12, which is 4096, relations. A function must send each of the 3 elements of A to exactly one of the 4 elements of B, and those choices are independent, so there are 4 cubed, which is 64, functions. Note that the exponent is the size of the domain in the last count.

Question 7

How many onto functions exist from a set of 4 elements to a set of 2 elements? Verify the inclusion-exclusion count by a direct argument.

Accepted Answer

By the formula the count is 2 to the fourth, minus 2 times 1 to the fourth, which is 16 minus 2, giving 14. A direct argument confirms it. There are 16 functions in total from a four-element set to a two-element set. A function fails to be onto exactly when it misses one of the two images, that is, when it sends everything to a single element. There are precisely 2 such constant functions. Removing them from the 16 leaves 14 onto functions.

Question 8

Find the domain of f(x) = the square root of (x minus 1) plus the square root of (5 minus x), and state its range.

Accepted Answer

Each square root requires a non-negative argument, so we need x at least 1 and x at most 5. Both conditions must hold at once, so the domain is the intersection, namely the closed interval from 1 to 5. Taking the union here would be wrong and would give an unbounded set. For the range, the function is 0 at neither endpoint but takes the value 2 at both x equal to 1 and x equal to 5, and it is largest at the midpoint x equal to 3, where it equals 2 times the square root of 2. So the range is the closed interval from 2 to 2 root 2.

Question 9

Let f(x) = 3x minus 2 and g(x) = x squared plus 1, both from the reals to the reals. Find f composed with g and g composed with f, and state whether either is one-one.

Accepted Answer

For f composed with g, apply g first: f(g(x)) equals 3 times (x squared plus 1) minus 2, which is 3x squared plus 1. For g composed with f, apply f first: g(f(x)) equals (3x minus 2) squared plus 1, which is 9x squared minus 12x plus 5. The two differ, confirming that composition is not commutative. Neither is one-one, since both are quadratic in x and therefore take equal values at pairs of distinct points. For instance the first takes the value 4 at both x equal to 1 and x equal to minus 1.

Question 10

Show that f from the reals to the reals given by f(x) = x cubed plus x is one-one and onto, without solving any cubic.

Accepted Answer

For injectivity, differentiate: the derivative is 3x squared plus 1, which is at least 1 and therefore strictly positive everywhere. A function with a strictly positive derivative is strictly increasing, and a strictly increasing function is one-one, since distinct inputs give distinct outputs. For surjectivity, note that the function is continuous, that it tends to plus infinity as x grows without bound and to minus infinity as x decreases without bound. By the intermediate value theorem it therefore attains every real value, so its range is all of the reals and it is onto. Being both, it is a bijection.

Question 11

If g composed with f is onto, must g be onto? Must f be? Justify with proof or counterexample.

Accepted Answer

The function g must be onto. Take any element c of the final codomain. Since the composite is onto, some a maps to c under it, meaning g of f of a equals c. Then the element f(a) is mapped by g to c, so c lies in the range of g, and since c was arbitrary, g is onto. The function f need not be onto. Let f send 1 to 1 from the set {1} into {1,2}, and let g send both 1 and 2 to the single element 1. The composite sends 1 to 1 and so is onto its codomain {1}, but f misses the element 2 entirely and is therefore not onto.

Question 12

Simplify the complement of (A union B) intersected with A, and state which laws you used.

Accepted Answer

By De Morgan's law, the complement of A union B equals the complement of A intersected with the complement of B. Intersecting that with A gives A intersected with the complement of A intersected with the complement of B. The associative law lets us group A with its own complement first, and that intersection is empty. Intersecting the empty set with anything leaves the empty set, so the whole expression is the empty set. The laws used are De Morgan's law, associativity of intersection and the complement law.

Practice — "Sets, Relations and Functions"

Sign in to save attempts to your dashboard and track your accuracy over time

Find a verified tutor

Join a live course

Browse coaching centres

About

Categories

Support

Documentation

Get Study Tips & Updates

Download Our App

Download for iOS

Download for Android

Popular Cities