Chapter 3

Question 1

Relation

Answer 1

A relation is a set of ordered pairs.

Question 2

Relation on, between sets

Answer 2

Let R be a relation and let A and B be sets. We say R is a relation on A provided R ⊆ A x A, and we say R is a relation from A to B provided R ⊆ A x B.

Question 3

Inverse relation

Answer 3

Let R be a relation. The inverse of R, denoted R^-1, is the relation formed by reversing the order of all the ordered pairs in R.

Question 4

Proposition 14.6 (proved)

Answer 4

Let R be a relation. Then (R^-1)^-1 = R.

Question 5

Properties of relations, Let R be a relation defined on a set A.

Answer 5

A relation R is Reflexive if xRx
A relation R is Symmetric if xRy implies yRx
A relation R is Transitive if xRy and yRz implies xRz
A relation R is Irreflexive if xRy implies x≠y
A relation R is Antisymmetric if xRy and yRx implies x=y

Question 6

Equivalence relation

Answer 6

Let R be a relation on a set A. We say R is an equivalence relation provided it is reflexive, symmetric, and transitive.

Question 7

Congruence modulo n

Answer 7

Let n be a positive integer. We say that integers x and y are congruent modulo n, and we write x ≣ y (mod n) provided n | (x-y). In other words, x ≣ y (mod n) if and only if x and y differ by a multiple of n.

Question 8

Theorem 15.5

Answer 8

Let n be a positive integer. The is-congruent-to-mod-n relation is an equivalence relation on the set of integers.

Question 9

Equivalence class

Answer 9

Let R be an equivalence relation on a set A and let a ∈ A. The equivalence class of a, denoted [a], is the set of all elements of A related (by R) to a; that is, [a] = {x ∈ A: x R a}

Question 10

Proposition 15.9 (proven)

Answer 10

Let R be an equivalence relation on a set A and let a ∈ A. Then a ∈ [a].

Question 11

Proposition 15.10 (proven)

Answer 11

Let R be an equivalence relation on a set A and let a, b ∈ A. Then a R b if and only if [a] = [b].

Question 12

Proposition 15.11 (proven)

Answer 12

Let R be an equivalence relation on a set A and let a, x, y ∈ A. If x, y ∈ [a], then x R y.

Question 13

Proposition 15.12 (proven)

Answer 13

Let R be an equivalence relation on A and suppose [a] ∩ [b] ≠ ∅. Then [a] = [b] .

Question 14

Corollary 15.13

Answer 14

Let R be an equivalence relation on a set A. The equivalence classes of R are nonempty, pairwise disjoint subsets of A whose union is A.

Question 15

Partition

Answer 15

Let A be a set. A partition of (or on) A is a set of nonempty, pairwise disjoint sets whose union is A. There are four key points in this definition, and we shall examine them closely in an example. The four points are
1. A partition is a set of sets; each member of a partition is a subset of A. The members of the partition are called parts.
2. The parts of a partition are nonempty. The empty set is never a part of a partition.
3. The parts of a partition are pairwise disjoint. No two parts of a partition may have an
element in common.
4. The union of the parts is the original set.

Question 16

Proposition 16.3

Answer 16

Let A be a set and let 𝒫 be a partition on A. The relation ≡𝒫 is an equivalence relation on A.

Question 17

Proposition 16.4

Answer 17

Let 𝒫 be a partition on a set A and let ≡𝒫 be the is-in-the-same-part-as relation. The equivalence classes of ≡𝒫 are exactly the parts of 𝒫.

Question 18

Counting equivalence classes

Answer 18

Let R be an equivalence relation on a finite set A. If all the equivalence classes of R have the same size, m, then the number of equivalence classes is |A| / m.

Question 19

Binomial coefficient

Answer 19

Let n, k ∈ ℕ. The symbol (n//k) denotes the number of k-element subsets of an n-element set.

Question 20

Most of chapter 17’s propositions, definitions, and proofs could not be displayed here

Answer 20

So go read the book