Mathematics 243, section 3 – Algebraic Structures Problem Set 4 due: October 5, 2012

‘A’ Section

1. Consider the following relations defined on the set ℤ. In each case, say whether the relation is reflexive, symmetric, transitive. Justify your answers.

a. xRy if and only if (−1)^{x} = (−1)^{y}

b. xRy if and only if x · y ≥ 0

c. xRy if and only if |x − y| ≤ 2

d. xRy if and only if x has the same number of base 10 digits as y, ignoring signs of x, y.

e. xRy if and only if the sum of the base 10 digits of x is the same as the sum of the base 10 digits of y, ignoring signs of x, y.

2. Which of the relations in question 1 are equivalence relations? For those that are, say exactly which integers make up the equivalence class [11] using correct set notation.

3. Let R be the relation on ℤ defined by xRy if and only if 4x − 15y is a multiple of 11. Show that R is an equivalence relation and describe all of the equivalence classes for R.

4. Decide whether each of the following statements is true. For those that are true, give a short proof using the postulates for ℤ given in §2.1 of the text. For those that are false, give a counterexample.

a. If xy = xz for integers x, y, z, then y = z.

b. If x < y, then x^{2} < y^{2}.

c. If z − x < z − y, then y < x.

‘B’ Section

1. In class we showed that the distinct equivalence classes of an equivalence relation R on a set A give a partition of A. Conversely, suppose

A = ⋃_{λ∈L} A_{λ}

is a partition of A. Show that the relation R on A defined by:

aRa′ ⇔ a, a′ are both elements of the same subsetA_{λ}

is an equivalence relation on A.

2. In both parts of this problem, you will be working in ℤ, using the postulates from §2.1

a. Show that if x · y = 0, then x = 0 or y = 0. (Hint: Argue by contraposition. By the trichotomy postulate 4, if x ≠ 0, then x ∈ ℤ^{+} or −x ∈ ℤ^{+}, and the same is true for y.)

b. From part a, deduce the cancellation law in ℤ: If x · y = x · z and x ≠ 0, then y = z.

3. Prove by mathematical induction:

a. For all n ∈ ℤ^{+},

1^{2} + 2^{2} + ⋯ + n^{2} = \frac{n(n + 1)(2n + 1)}{6}.

b. For all n ∈ ℤ^{+},

\frac{1}{1 · 2} + \frac{1}{2 · 3} + ⋯ + \frac{1}{n(n + 1)} = \frac{n}{n + 1}

c. For all n ≥ 2, n^{3} > 1 + 2n.

d. If |A| = n, then |P(A)| = 2^{n}. (Suggestion: For the induction step, one proof comes like this. Let A = {a_{1}, …, a_{k}, a_{k+1}}. Every subset of A is of one of two types – the ones containing a_{k+1} and the ones not containing a_{k+1}. Count the number of subsets of each type by using the induction hypothesis.)

4. The binomial coefficients are the numbers

\binom{n}{k} = \frac{n!}{k!(n − k)!}

(where 0! = 1 by convention).

a. Show using the definition that for all k with 1 ≤ k ≤ n,

\binom{n}{k} + \binom{n}{k − 1} = \binom{n + 1}{k}

(this is often known as the Pascal’s triangle identity for binomial coefficients, because it is the fact underlying the way the coefficients can be computed from the Pascal’s triangle table).

b. (The Binomial Theorem) Show by induction that for all n ≥ 1 and all a, b ∈ ℝ

(a + b)^{n} = ∑_{ℓ=0}^{n} \binom{n}{ℓ}a^{ℓ}b^{n−ℓ}

(that is, for each ℓ, 0 ≤ ℓ ≤ n, the number \binom{n}{ℓ} is exactly the coefficient of the term a^{ℓ}b^{n−ℓ} appearing in the expansion of (a + b)^{n} – the lower index ℓ is the same as the exponent of a).