The fractions \(\tfrac12\) , \(\tfrac24\) , and \(\tfrac{3}{6}\) are written with different pairs of integers, and everyone agrees that they are the same number. What, then, is the number? It cannot be the pair \((1,2)\) , because the pair \((2,4)\) has an equal claim. And when two fractions are added by the rule \(\tfrac ab+\tfrac cd=\tfrac{ad+bc}{bd}\) , why does the answer not depend on which of the many ways of writing each fraction was used?

The honest answer is that a rational number is not a pair of integers but a whole collection of pairs that have been declared equivalent, and that a rule stated in terms of pairs must be checked to give equivalent outputs on equivalent inputs. Saying this precisely takes three ideas: sets, which are collections; functions, which are rules assigning outputs to inputs; and relations, which record when one object stands in some connection to another. These three ideas are the vocabulary of all later mathematics. This chapter defines them, and it is also the first place where the proof forms of Chapter 1 are used on objects other than integers.

2.1 Sets and how to prove statements about them

A set is determined by its elements and by nothing else. Order and repetition in a listing are irrelevant: \(\{1,2,3\}\) , \(\{3,1,2\}\) , and \(\{1,1,2,3\}\) are one set. Sets may be elements of other sets, and then care is needed, since \(\{1\}\) and \(1\) are different objects: the first is a set with one element, the second is a number. The set \(\{\emptyset\}\) has one element and is not empty.

Sets are usually specified in set-builder notation: \(\{x\in U : P(x)\}\) is the set of those elements \(x\) of \(U\) for which the predicate \(P(x)\) is true. Thus \(\{n\in\mathbb Z : n=2k\text{ for some }k\in\mathbb Z\}\) is the set of even integers.

In symbols, \(A\subseteq B\) is the universal conditional \(\forall x\,(x\in A\to x\in B)\) . Two consequences follow from Chapter 1. First, \(\emptyset\subseteq B\) for every set \(B\) , vacuously: the hypothesis \(x\in\emptyset\) is never true. Second, the way to prove \(A\subseteq B\) is the way to prove any universal conditional: take an arbitrary element of \(A\) and show that it lies in \(B\) . To prove that two sets are equal, prove two inclusions. This method, called double inclusion, is the standard proof of a set equality.

2.2 Functions

The words “each” and “exactly one” are the content of the definition. “Each” says that \(f(a)\) is defined for every element of the domain; “exactly one” says that the output is unambiguous. A proposed rule that fails either requirement is not a function: “send a rational number to its numerator” is not a function on \(\mathbb Q\) until a way of writing each rational is fixed, because \(\tfrac12\) and \(\tfrac24\) are the same input with different numerators. A rule that passes the test is said to be well defined.

The codomain is part of the function. It is the set in which values are permitted to lie, and it need not be the set of values actually taken.

Each definition is a quantified statement, and its negation tells you how to refute it. A function fails to be injective if there exist two different inputs with the same output. It fails to be surjective if there exists an element of the codomain that is not an output. In terms of the equation \(f(x)=b\) with \(b\) given: injective means at most one solution for every \(b\) , surjective means at least one, and bijective means exactly one.

2.3 Comparing sizes with bijections

A shepherd who cannot count can still check that no sheep is missing, by dropping one pebble in a bag for each sheep that leaves in the morning and removing one for each that returns. Matching comes before counting, and for infinite sets it is the only notion of size available.

A bijection from \(\mathbb N\) to \(A\) is an infinite list \(a_0,a_1,a_2,\dots\) in which every element of \(A\) appears exactly once. Having the same cardinality behaves as one would hope: every set matches itself by the identity function, a bijection can be inverted by Theorem 2.9, and bijections compose by Theorem 2.8.

2.4 Relations and their properties

A function relates each input to one output. Many connections between objects are not of that kind: an integer has many divisors, a person has several friends or none.

A relation is nothing more than the set of pairs for which it holds. The relation “less than” on \(\{1,2,3\}\) is the set \(\{(1,2),(1,3),(2,3)\}\) . By Definition 2.4 a function is a relation with a special property. A relation on a finite set can be displayed as a grid with a filled cell for each pair, as in Figure 1.1, or as a diagram with an arrow from \(a\) to \(b\) for each pair \((a,b)\) .

Reflexivity makes a demand on every element. The other three are universal conditionals, so they make a demand only when their hypotheses are met and can hold vacuously. The following table records the properties of some familiar relations.

The relation \(<\) is antisymmetric because the hypothesis “\(a<b\) and \(b<a\) ” is never satisfied. “Differ by at most \(1\) ” is not transitive because \(1\) and \(2\) are related, \(2\) and \(3\) are related, and \(1\) and \(3\) are not.

2.5 Equivalence relations and partitions

An equivalence relation is a precise version of “the same in some respect”: the same parity, the same birthday, the same value as a fraction. A partition is a sorting of a set into labelled bins. The main theorem of this chapter says that these are two descriptions of one structure.

All three axioms were used in part (a): reflexivity to cover \(A\) , symmetry and transitivity to make overlapping classes equal. Drop any one and the classes need not form a partition.

2.6 Partial orders

Equivalence relations abstract sameness. The other great family of relations abstracts comparison.

The usual order \(\le\) on \(\mathbb Z\) is a total order. Inclusion \(\subseteq\) on \(\mathcal P(U)\) is a partial order that is not total once \(U\) has two elements: \(\{1\}\) and \(\{2\}\) are incomparable. Divisibility on \(\mathbb Z^{+}\) is a partial order: it is reflexive since \(a=a\cdot 1\) , transitive and antisymmetric by Exercise 1.11, and not total since neither of \(2\) and \(3\) divides the other. The word “partial” refers to the possibility of incomparable pairs.

Minimal means that nothing lies below. Least means lying below everything. The second is a far stronger condition, and the difference between them is exactly the difference between the two orders of quantifiers studied in Section 1.4.

A finite poset is drawn as a Hasse diagram: one point for each element, with \(b\) placed higher than \(a\) and joined to it by a line whenever \(b\) covers \(a\) . Lines implied by transitivity and the loops implied by reflexivity are omitted. Then \(a\preceq b\) holds exactly when one can travel from \(a\) to \(b\) along lines going upward.

Example 2.10: The divisors of sixty

Let \(D\) be the set of positive divisors of \(60\) , ordered by divisibility. Since \(60=2^{2}\cdot 3\cdot 5\) , the divisors are \(1,2,3,4,5,6,10,12,15,20,30,60\) , twelve in all. In this poset \(b\) covers \(a\) exactly when \(b/a\) is a prime, so the lines of the Hasse diagram correspond to multiplying by \(2\) , \(3\) , or \(5\) . There are \(20\) covering pairs.

The whole poset \(D\) has least element \(1\) , which divides everything, and greatest element \(60\) , which everything divides. The elements \(4\) and \(6\) are incomparable, as are \(12\) and \(15\) .

Now delete \(1\) and \(60\) and consider the ten remaining divisors. The minimal elements are \(2\) , \(3\) , and \(5\) : no other member of the set divides any of them. The maximal elements are \(12\) , \(20\) , and \(30\) . There is no least element, since a least element would have to divide \(2\) , \(3\) , and \(5\) ; and there is no greatest element. A poset can have several minimal elements, and then none of them is least.

Proposition 2.20 (a least element is the only minimal element). If a poset has a least element \(\ell\) , then \(\ell\) is minimal, and it is the only minimal element. In particular a poset has at most one least element.

Proof. Suppose \(x\preceq\ell\) for some \(x\) . Since \(\ell\) is least, \(\ell\preceq x\) , and antisymmetry gives \(x=\ell\) . So no \(x\) satisfies \(x\prec\ell\) , and \(\ell\) is minimal. Now let \(m\) be any minimal element. Since \(\ell\) is least, \(\ell\preceq m\) ; since \(m\) is minimal, \(\ell\prec m\) is impossible; so \(\ell=m\) . Finally, two least elements would both be minimal, hence both equal to \(\ell\) .

The three kinds of object in this chapter will reappear constantly. Congruence in Chapter 4 is an equivalence relation on \(\mathbb Z\) , and its classes are the objects of modular arithmetic. Counting in Chapter 5 is the construction of bijections. Connectedness in Chapter 6 is an equivalence relation on the vertices of a graph. Before any of that, one tool is still missing. Several arguments so far have ended with “and so on”, or with an appeal to the smallest element of a set of integers. The next chapter turns that appeal into a method of proof. A question to take along: a finite nonempty poset must have a minimal element, and the natural argument is to keep stepping downward until you cannot; what principle guarantees that the stepping stops?

Exercises

1. Let \(U=\{1,2,3,4,5,6\}\) , \(A=\{1,2,3\}\) , and \(B=\{2,3,4,5\}\) . List the elements of \(A\cup B\) , \(A\cap B\) , \(A\setminus B\) , \(B\setminus A\) , \(\overline{A\cup B}\) , and \(\mathcal P(\{1,2\})\) , and give the number of elements of \(A\times B\) and of \(\mathcal P(\mathcal P(\{1\}))\) .

   Answer

   \(A\cup B=\{1,2,3,4,5\}\) , \(A\cap B=\{2,3\}\) , \(A\setminus B=\{1\}\) , \(B\setminus A=\{4,5\}\) , \(\overline{A\cup B}=\{6\}\) , and \(\mathcal P(\{1,2\})=\{\emptyset,\{1\},\{2\},\{1,2\}\}\) . The product \(A\times B\) has \(3\cdot 4=12\) elements. Since \(\mathcal P(\{1\})=\{\emptyset,\{1\}\}\) has two elements, its power set has four.

2. Decide whether each statement is true or false, with a one-line reason: (a) \(\emptyset\in\emptyset\) ; (b) \(\emptyset\subseteq\emptyset\) ; (c) \(\{1\}\in\{1,\{1\}\}\) ; (d) \(\{1\}\subseteq\{1,\{1\}\}\) ; (e) \(\emptyset\in\mathcal P(A)\) for every set \(A\) ; (f) \(\{\emptyset\}\subseteq\mathcal P(A)\) for every set \(A\) .

   Answer

   (a) False: the empty set has no elements. (b) True: every set is a subset of itself. (c) True: \(\{1\}\) is one of the two listed elements. (d) True: the only element of \(\{1\}\) is \(1\) , which is an element of the larger set. (e) True: \(\emptyset\subseteq A\) . (f) True: the only element of \(\{\emptyset\}\) is \(\emptyset\) , which belongs to \(\mathcal P(A)\) by (e).

3. Prove by double inclusion that \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\) for all sets \(A\) , \(B\) , \(C\) , stating which logical equivalence from Theorem 1.4 each half of the argument relies on.

   Solution

   First inclusion. Let \(x\in A\cap(B\cup C)\) . Then \(x\in A\) , and \(x\in B\) or \(x\in C\) . If \(x\in B\) , then \(x\in A\cap B\) ; if \(x\in C\) , then \(x\in A\cap C\) . In either case \(x\in(A\cap B)\cup(A\cap C)\) .

   Second inclusion. Let \(x\in(A\cap B)\cup(A\cap C)\) . If \(x\in A\cap B\) , then \(x\in A\) and \(x\in B\) , so \(x\in B\cup C\) and hence \(x\in A\cap(B\cup C)\) . If \(x\in A\cap C\) , the same reasoning with \(C\) in place of \(B\) gives \(x\in A\cap(B\cup C)\) .

   Both halves rest on the first distributive law of Theorem 1.4(f), \(P\land(Q\lor R)\equiv(P\land Q)\lor(P\land R)\) , with \(P\) , \(Q\) , \(R\) standing for \(x\in A\) , \(x\in B\) , \(x\in C\) : the first half is its left-to-right direction and the second half its right-to-left direction. Each half is organized as a proof by cases because its hypothesis is a disjunction.

4. Prove that for all sets \(A\) and \(B\) the following three statements are equivalent: \(A\subseteq B\) ; \(A\cup B=B\) ; \(A\cap B=A\) .

   Hint

   Prove a cycle of three implications. From \(A\subseteq B\) to \(A\cup B=B\) : the inclusion \(B\subseteq A\cup B\) is automatic, and the other uses the hypothesis. From \(A\cup B=B\) to \(A\cap B=A\) : the inclusion \(A\cap B\subseteq A\) is automatic; for the other, an element of \(A\) lies in \(A\cup B\) . From \(A\cap B=A\) to \(A\subseteq B\) : an element of \(A\) lies in \(A\cap B\) .

5. Prove or disprove each statement about arbitrary sets \(A\) and \(B\) : (a) \(\mathcal P(A\cap B)=\mathcal P(A)\cap\mathcal P(B)\) ; (b) \(\mathcal P(A\cup B)=\mathcal P(A)\cup\mathcal P(B)\) .

   Solution

   (a) True. Let \(X\) be a set. Then \(X\in\mathcal P(A\cap B)\) means \(X\subseteq A\cap B\) . This holds exactly when every element of \(X\) is in \(A\) and in \(B\) , that is, exactly when \(X\subseteq A\) and \(X\subseteq B\) , which means \(X\in\mathcal P(A)\) and \(X\in\mathcal P(B)\) , that is, \(X\in\mathcal P(A)\cap\mathcal P(B)\) . The two power-set expressions have the same elements, so they are equal.

   (b) False. Take \(A=\{1\}\) and \(B=\{2\}\) . Then \(\{1,2\}\in\mathcal P(A\cup B)\) , but \(\{1,2\}\) is a subset of neither \(A\) nor \(B\) , so it is not in \(\mathcal P(A)\cup\mathcal P(B)\) . Here \(\mathcal P(A\cup B)\) has \(4\) elements and \(\mathcal P(A)\cup\mathcal P(B)=\{\emptyset,\{1\},\{2\}\}\) has \(3\) . The inclusion \(\mathcal P(A)\cup\mathcal P(B)\subseteq\mathcal P(A\cup B)\) does hold in general; a set contained in \(A\) or in \(B\) is contained in \(A\cup B\) .

6. Decide whether each function is injective and whether it is surjective, proving each answer: (a) \(f:\mathbb Z\to\mathbb Z\) , \(f(n)=3n-4\) ; (b) \(g:\mathbb R\to\mathbb R\) , \(g(x)=3x-4\) ; (c) \(h:\mathbb Z\times\mathbb Z\to\mathbb Z\) , \(h(m,n)=m+n\) ; (d) \(k:\mathbb N\to\mathbb N\) , \(k(n)=n^{2}\) .

   Solution

   (a) Injective: if \(3m-4=3n-4\) then \(3m=3n\) and \(m=n\) . Not surjective: \(f(n)=0\) would require \(3n=4\) , and no integer satisfies this, so \(0\) is not a value.

   (b) Bijective. The function \(x\mapsto(x+4)/3\) from \(\mathbb R\) to \(\mathbb R\) is an inverse, since \(3\cdot\frac{x+4}{3}-4=x\) and \(\frac{(3x-4)+4}{3}=x\) ; apply Theorem 2.9. The same formula as in (a) has become surjective because the domain now contains \(4/3\) .

   (c) Surjective: for any integer \(z\) , \(h(z,0)=z\) . Not injective: \(h(0,1)=h(1,0)=1\) and \((0,1)\ne(1,0)\) .

   (d) Injective: if \(m^{2}=n^{2}\) with \(m,n\ge 0\) then \((m-n)(m+n)=0\) , so \(m=n\) or \(m+n=0\) , and the latter forces \(m=n=0\) . Not surjective: \(2\) is not a value, because \(1^{2}<2<2^{2}\) and squares of natural numbers increase.

7. Let \(f:A\to B\) and \(g:B\to C\) . Prove Theorem 2.8(d): if \(g\circ f\) is surjective then \(g\) is surjective. Then give an example with small finite sets in which \(g\circ f\) is bijective although \(f\) is not surjective and \(g\) is not injective.

   Solution

   Let \(c\in C\) . Since \(g\circ f\) is surjective, there is \(a\in A\) with \(g(f(a))=c\) . Put \(b=f(a)\) ; then \(b\in B\) and \(g(b)=c\) . So every element of \(C\) is a value of \(g\) , and \(g\) is surjective.

   For the example take \(A=\{1\}\) , \(B=\{1,2\}\) , \(C=\{1\}\) , with \(f(1)=1\) and \(g(1)=g(2)=1\) . Then \(g\circ f\) sends \(1\) to \(1\) and is a bijection from \(A\) to \(C\) . But \(f\) is not surjective, since \(2\in B\) is not a value of \(f\) , and \(g\) is not injective, since \(g(1)=g(2)\) . Parts (c) and (d) of Theorem 2.8 say what can be recovered from the composition: injectivity of the first function applied and surjectivity of the last. This example shows nothing more can be.

8. Let \(f:\mathbb Z\to\mathbb Z\) be given by \(f(n)=n^{2}-n\) . Find the image \(f(\{-1,0,1,2\})\) and the preimages \(f^{-1}(\{0\})\) , \(f^{-1}(\{2\})\) , and \(f^{-1}(\{1\})\) , explaining the last answer with a parity argument.

   Answer

   \(f(-1)=2\) , \(f(0)=0\) , \(f(1)=0\) , \(f(2)=2\) , so the image is \(\{0,2\}\) . \(f^{-1}(\{0\})=\{0,1\}\) and \(f^{-1}(\{2\})=\{-1,2\}\) . \(f^{-1}(\{1\})=\emptyset\) , because \(n^{2}-n=n(n-1)\) is a product of two consecutive integers, one of which is even, so every value of \(f\) is even.

9. Let \(f:A\to B\) , let \(C,D\subseteq B\) , and let \(S,T\subseteq A\) . Prove that \(f^{-1}(C\cap D)=f^{-1}(C)\cap f^{-1}(D)\) , and prove that if \(f\) is injective then \(f(S\cap T)=f(S)\cap f(T)\) , pointing out the line where injectivity is used.

   Solution

   Preimages. For \(a\in A\) : \(a\in f^{-1}(C\cap D)\) if and only if \(f(a)\in C\cap D\) , if and only if \(f(a)\in C\) and \(f(a)\in D\) , if and only if \(a\in f^{-1}(C)\) and \(a\in f^{-1}(D)\) , if and only if \(a\in f^{-1}(C)\cap f^{-1}(D)\) . Each step is a definition, so the two sets have the same elements.

   Images. First, \(f(S\cap T)\subseteq f(S)\cap f(T)\) for every function: if \(y=f(a)\) with \(a\in S\cap T\) , then \(y\in f(S)\) because \(a\in S\) and \(y\in f(T)\) because \(a\in T\) . Conversely, suppose \(f\) is injective and let \(y\in f(S)\cap f(T)\) . Then \(y=f(s)\) for some \(s\in S\) and \(y=f(t)\) for some \(t\in T\) . Here injectivity is used: \(f(s)=f(t)\) gives \(s=t\) . So \(s\in S\cap T\) and \(y=f(s)\in f(S\cap T)\) . Without injectivity the elements \(s\) and \(t\) may differ, as in Example 2.4.

10. Assume that every positive integer can be written in exactly one way as \(2^{m}(2n+1)\) with \(m,n\in\mathbb N\) . Use this to show that \(F:\mathbb N\times\mathbb N\to\mathbb Z^{+}\) , \(F(m,n)=2^{m}(2n+1)\) , is a bijection, and conclude that \(\mathbb N\times\mathbb N\) is countable.

    Hint

    Surjectivity of \(F\) is the statement that every positive integer can be written in the form \(2^{m}(2n+1)\) ; injectivity is the statement that it can be so written in only one way. To finish, compose \(F\) with the bijection \(k\mapsto k-1\) from \(\mathbb Z^{+}\) to \(\mathbb N\) and use Theorem 2.8.

11. Let \(A=\{1,2,3,4,5\}\) and let \(f:A\to\mathcal P(A)\) have \(f(1)=\{2,3\}\) , \(f(2)=\{2,4\}\) , \(f(3)=\emptyset\) , \(f(4)=\{1,4,5\}\) , \(f(5)=\{1,2,3,4\}\) . Compute the diagonal set \(D\) of Theorem 2.11 and, for each \(a\in A\) , name an element that belongs to exactly one of \(D\) and \(f(a)\) .

    Answer

    \(D=\{1,3,5\}\) , since \(1\notin f(1)\) , \(2\in f(2)\) , \(3\notin f(3)\) , \(4\in f(4)\) , \(5\notin f(5)\) . For each \(a\) the element \(a\) itself belongs to exactly one of \(D\) and \(f(a)\) : \(1,3,5\) are in \(D\) and not in their images, while \(2\) and \(4\) are in their images and not in \(D\) .

12. A student writes: “The function \(f:\mathbb R\to\mathbb R\) , \(f(x)=x^{2}\) , is injective, because if \(a=b\) then \(a^{2}=b^{2}\) .” Explain what the student has actually proved, why it is not injectivity, and whether \(f\) is injective.

    Solution

    The student has proved the statement “if \(a=b\) then \(f(a)=f(b)\) ”. That statement holds for every function whatever; it says only that equal inputs give equal outputs. Injectivity is the converse statement, “if \(f(a)=f(b)\) then \(a=b\) ”, and proving a conditional does not prove its converse.

    The function is in fact not injective: \(f(-1)=1=f(1)\) and \(-1\ne 1\) . One counterexample settles it. The squaring function does become injective if the domain is restricted to the nonnegative reals, which again shows that the domain is part of the function.

13. For each relation on \(\mathbb Z\) decide whether it is reflexive, symmetric, antisymmetric, and transitive, giving a proof or a counterexample for each of the four properties: (a) \(a\mathrel R b\) if \(a+b\) is even; (b) \(a\mathrel R b\) if \(a+b\) is odd; (c) \(a\mathrel R b\) if \(ab\ge 0\) ; (d) \(a\mathrel R b\) if \(a\le b+1\) .

    Solution

    (a) Reflexive, since \(a+a=2a\) is even. Symmetric, since \(a+b=b+a\) . Transitive: if \(a+b\) and \(b+c\) are even then \(a+c=(a+b)+(b+c)-2b\) is even. Not antisymmetric: \(0\mathrel R 2\) and \(2\mathrel R 0\) with \(0\ne 2\) . It is the equivalence relation “same parity”.

    (b) Not reflexive, since \(a+a\) is even for every \(a\) . Symmetric. Not antisymmetric: \(0\mathrel R 1\) and \(1\mathrel R 0\) . Not transitive: \(0\mathrel R 1\) and \(1\mathrel R 2\) , but \(0+2\) is even.

    (c) Reflexive, since \(a^{2}\ge 0\) . Symmetric, since \(ab=ba\) . Not antisymmetric: \(1\mathrel R 2\) and \(2\mathrel R 1\) . Not transitive: \(1\mathrel R 0\) and \(0\mathrel R(-1)\) because both products are \(0\) , but \(1\cdot(-1)<0\) . Zero is related to everything, and that is what breaks transitivity.

    (d) Reflexive, since \(a\le a+1\) . Not symmetric: \(0\le 5+1\) holds and \(5\le 0+1\) fails. Not antisymmetric: \(0\le 1+1\) and \(1\le 0+1\) both hold with \(0\ne 1\) . Not transitive: \(2\le 1+1\) and \(1\le 0+1\) hold, and \(2\le 0+1\) fails.

14. Let \(f:A\to B\) be any function and define \(a\sim a'\) to mean \(f(a)=f(a')\) . Prove that \(\sim\) is an equivalence relation on \(A\) . Then list its classes when \(A=\{0,1,\dots,9\}\) and \(f(a)\) is the last decimal digit of \(a^{2}\) .

    Solution

    Reflexive: \(f(a)=f(a)\) for every \(a\in A\) . Symmetric: if \(f(a)=f(a')\) then \(f(a')=f(a)\) . Transitive: if \(f(a)=f(a')\) and \(f(a')=f(a'')\) then \(f(a)=f(a'')\) . All three properties are inherited from the corresponding properties of equality in \(B\) .

    For the example, the last digits of \(0^{2},1^{2},\dots,9^{2}\) are \(0,1,4,9,6,5,6,9,4,1\) . Grouping the inputs by output gives six classes:

    \[ \{0\},\quad\{5\},\quad\{1,9\},\quad\{2,8\},\quad\{3,7\},\quad\{4,6\}. \]

    The classes are the nonempty preimages \(f^{-1}(\{d\})\) . Every equivalence relation arises this way, from the function sending each element to its class, so “having the same value under some function” is a complete description of what equivalence relations are.

15. Let \(R\) and \(S\) be equivalence relations on a set \(A\) , regarded as subsets of \(A\times A\) . Prove that \(R\cap S\) is an equivalence relation, and show by an example on a three-element set that \(R\cup S\) need not be one.

    Solution

    Reflexive. For each \(a\in A\) , \((a,a)\in R\) and \((a,a)\in S\) because both are reflexive, so \((a,a)\in R\cap S\) . Symmetric. If \((a,b)\in R\cap S\) then \((b,a)\in R\) and \((b,a)\in S\) by symmetry of each, so \((b,a)\in R\cap S\) . Transitive. If \((a,b)\) and \((b,c)\) are in \(R\cap S\) , then \((a,c)\in R\) by transitivity of \(R\) and \((a,c)\in S\) by transitivity of \(S\) , so \((a,c)\in R\cap S\) .

    For the union, let \(A=\{1,2,3\}\) , let \(R\) be the equivalence relation with blocks \(\{1,2\}\) and \(\{3\}\) , and let \(S\) be the one with blocks \(\{1\}\) and \(\{2,3\}\) . Then \((1,2)\in R\) and \((2,3)\in S\) , so both pairs lie in \(R\cup S\) . But \((1,3)\) is in neither \(R\) nor \(S\) , because \(1\) and \(3\) lie in different blocks of both partitions. So \(R\cup S\) is not transitive.

16. List all partitions of \(\{1,2,3\}\) , and then count the equivalence relations on a five-element set by organizing the partitions according to their block sizes, as in Example 2.9.

    Answer

    The partitions of \(\{1,2,3\}\) are \(\{\{1,2,3\}\}\) , \(\{\{1,2\},\{3\}\}\) , \(\{\{1,3\},\{2\}\}\) , \(\{\{2,3\},\{1\}\}\) , and \(\{\{1\},\{2\},\{3\}\}\) : five in all. For a five-element set, by block sizes: \(5\) gives \(1\) ; \(4+1\) gives \(5\) ; \(3+2\) gives \(10\) ; \(3+1+1\) gives \(10\) ; \(2+2+1\) gives \(15\) ; \(2+1+1+1\) gives \(10\) ; \(1+1+1+1+1\) gives \(1\) . Total \(52\) .

17. Here is an argument that every symmetric and transitive relation \(R\) on a set \(A\) is reflexive: “Let \(a\in A\) . Take \(b\) with \(a\mathrel R b\) . By symmetry \(b\mathrel R a\) . By transitivity, from \(a\mathrel R b\) and \(b\mathrel R a\) we get \(a\mathrel R a\) .” Identify the unjustified step, give a counterexample to the claim, and state an extra hypothesis under which the argument becomes correct.

    Solution

    The unjustified step is “take \(b\) with \(a\mathrel R b\) ”. It asserts that such a \(b\) exists, and neither symmetry nor transitivity provides one: both are conditionals, which are silent about an element that is related to nothing.

    Counterexample: on \(A=\{1,2,3\}\) let \(R=\{(1,1),(1,2),(2,1),(2,2)\}\) . It is symmetric and transitive, and \((3,3)\notin R\) , so it is not reflexive. The element \(3\) is related to nothing, and for \(a=3\) the argument cannot start.

    The argument becomes correct under the extra hypothesis that every element of \(A\) is related to at least one element: \(\forall a\,\exists b\,(a\mathrel R b)\) . With that hypothesis the existential step is justified and the remaining two steps are valid as written.

18. For the relation of Example 2.8, show that addition is well defined: if \((a,b)\sim(a',b')\) then \((ad+bc,bd)\sim(a'd+b'c,b'd)\) for every \((c,d)\) . Explain in a sentence why this check, together with the symmetric one in the second argument, is exactly what is needed to add rational numbers.

    Hint

    The hypothesis is \(ab'=ba'\) . The goal, by the definition of \(\sim\) , is \((ad+bc)(b'd)=(bd)(a'd+b'c)\) . Expand both sides; each has two terms, one of which is \(bb'cd\) on both sides, and the other terms are \(ab'd^{2}\) and \(ba'd^{2}\) .

19. Draw the Hasse diagram of the positive divisors of \(36\) under divisibility. State how many covering pairs it has, and list all pairs of incomparable elements.

    Answer

    The divisors are \(1,2,3,4,6,9,12,18,36\) , in levels \(\{1\}\) , \(\{2,3\}\) , \(\{4,6,9\}\) , \(\{12,18\}\) , \(\{36\}\) . There are \(12\) covering pairs. The incomparable pairs are \(\{2,3\}\) , \(\{2,9\}\) , \(\{3,4\}\) , \(\{4,6\}\) , \(\{4,9\}\) , \(\{4,18\}\) , \(\{6,9\}\) , \(\{9,12\}\) , and \(\{12,18\}\) .

20. Consider \(\mathcal P(\{1,2,3\})\) ordered by inclusion. Draw its Hasse diagram, count the covering pairs, give a chain of four sets each properly contained in the next, and give three sets no two of which are comparable.

    Answer

    The diagram is a cube: \(\emptyset\) at the bottom, the three one-element sets, the three two-element sets, and \(\{1,2,3\}\) at the top, with \(12\) covering pairs. A chain: \(\emptyset\subset\{1\}\subset\{1,2\}\subset\{1,2,3\}\) . Three pairwise incomparable sets: \(\{1\}\) , \(\{2\}\) , \(\{3\}\) , or alternatively the three two-element sets.

21. Using Exercise 1.11, write out a complete proof that divisibility is a partial order on \(\mathbb Z^{+}\) . Then show that divisibility on \(\mathbb Z\) is not antisymmetric, and decide whether divisibility is a total order on \(\{1,2,4,8,16\}\) and on \(\{1,2,3,6\}\) .

    Solution

    Reflexive. For \(a\in\mathbb Z^{+}\) , \(a=a\cdot 1\) , so \(a\mid a\) . Antisymmetric. If \(a\mid b\) and \(b\mid a\) with \(a,b\) positive, then \(a=b\) by the second part of Exercise 1.11. Transitive. If \(a\mid b\) and \(b\mid c\) then \(a\mid c\) by the first part of Exercise 1.11. So divisibility is a partial order on \(\mathbb Z^{+}\) .

    On \(\mathbb Z\) antisymmetry fails: \(2\mid -2\) because \(-2=2\cdot(-1)\) , and \(-2\mid 2\) because \(2=(-2)\cdot(-1)\) , yet \(2\ne -2\) .

    On \(\{1,2,4,8,16\}\) divisibility is a total order: the elements are \(2^{0},\dots,2^{4}\) , and \(2^{i}\mid 2^{j}\) whenever \(i\le j\) , so any two are comparable. On \(\{1,2,3,6\}\) it is not total: neither of \(2\) and \(3\) divides the other.

22. Give an example of a poset that has exactly one minimal element and no least element, and explain why, by Proposition 2.20, the converse of that proposition is therefore false. Your example will need to be infinite; Chapter 3 explains why.

    Hint

    Start from the integers with their usual order, which have no minimal element at all, and adjoin one new element that is comparable only to itself. Check the three axioms for the enlarged relation, then ask which elements are minimal and whether any element lies below all the others.

23. Represent a relation on \([n]\) as an \(n\times n\) grid with a filled cell for each pair. Describe what reflexivity, symmetry, and antisymmetry look like in the grid, and use the description to count the reflexive relations, the symmetric relations, and the antisymmetric relations on \([3]\) .

    Solution

    Reflexive means that all \(n\) cells on the main diagonal are filled. The other \(n^{2}-n\) cells may be filled or not, independently, so there are \(2^{n^{2}-n}\) reflexive relations; for \(n=3\) this is \(2^{6}=64\) .

    Symmetric means that the picture is unchanged by reflection in the main diagonal: cell \((a,b)\) is filled exactly when cell \((b,a)\) is. Such a picture is determined by the cells on or above the diagonal, of which there are \(n(n+1)/2\) , so there are \(2^{n(n+1)/2}\) symmetric relations; for \(n=3\) this is again \(2^{6}=64\) .

    Antisymmetric means that no off-diagonal cell and its mirror image are both filled. The \(n\) diagonal cells are unrestricted, and each of the \(n(n-1)/2\) mirror pairs has three permitted states: neither filled, only the upper, only the lower. So there are \(2^{n}\cdot 3^{n(n-1)/2}\) antisymmetric relations; for \(n=3\) this is \(8\cdot 27=216\) .