MA2011 Discrete maths

Graded problem sheet 3

General Instructions

This assessment should be submitted online, via LearnJCU, before 5pm on Thursday 28 March.

See LearnJCU for submission information and general instructions.

There is a choice of questions so follow the instructions given carefully

There are a total of 50 (+10 bonus) marks available for this assignment.

Part I  Complete both questions.

(A total of 14 marks are available for Part I)

Part II  Complete at least four questions from this section.

(Up to 36 marks are available for Part II)

Part III  Complete as many questions as you can.

(A maximum of 12 marks + 10 bonus marks are available for Part III.)

All questions are adapted from Tutorial sheets 5 and 6.  A few have been rearranged and some have been modified to make them clearer or simpler, but there are no new questions.

You may discuss this assessment  as much as you wish, but everyone must submit their own, individual and original work for grading.

You may hand write or type your work.  You are strongly encouraged to use LaTeX for typed work.  Please note that formatting errors can  (and do) occur with MS Word.  You may adapt the .tex file of this question sheet for your work.  Post your questions in the Padlet if you would like help with particular aspects of LaTex code.

• You are expected to show all necessary working.  No marks are awarded for answers without justification or explanation, even if they are correct.

• I may ask you for more explanation of your submitted answers.  This is first and foremost to support you in developing your learning.

• Make sure you set out your answers clearly and methodically.  While marks are not awarded for neatness, you may be penalised for poorly written or extremely untidy work.

Part I

Complete both questions. There are 14 marks available for this part of the assessment.

Questions

1. Total:  8 marks

(a)  How many elements does A × B have if jAj = 3 and j Bj = 4?                                 (1 mark)

(b)  Let A = ∅, B = {∅}, C = {∅ , {∅}}.

Write out the following sets in list form.

i.  B × C

ii.  A × B × C

(2 marks)

(c)  (from Rosen, Section 2.3, exercise 6)

Find the domain and range of the function that assigns to each positive integer its largest decimal digit (e.g the largest decimal digit of 1142 is 4).          (2 marks)

(d)  Let A = {1, 2, 3, 4}, and let R ≤ A × A be the relation on A given by R = {(1, 1), (2, 2), (1, 2), (4, 1)}

i.  Represent R as a binary matrix and as a digraph (directed graph).

ii.  Let Q be the relation on A given by Q = {(1, 4), (2, 1), (3, 3), (4, 4)}.  Describe R ∩ Q.

(2+1 marks)

2. Total:  6 marks

Let A = {1, 2, 3, 4} and B = {a, b, c} and let f : A → B be the function defined by

f(1) = a,  f(2) = f(4) = c,  f(3) = b

(a)  Is f surjective? Is f injective? Explain your answer.  (Hint: a diagram can be useful.)           (2 marks)

(b)  Show that the subsets fa   := {x : f(x) = a}, fb   := {x : f(x) = b}, fc   := {x : f(x) = c} describe a partition of A.                               (2 marks)

(c)  Give the equivalence relation on A whose equivalence classes are described by the partition in part (b).         (2 marks)

Part II

Complete at least four questions. You may complete more if you wish.

Questions

1. Total:  6 marks

Recall that the power set P (A) of a set A is the set of all subsets of A.

(a)  Let A = {2, 3, 4} and B = {2, 4, 6}.  Write out A ∩ B , P (A ∩ B), and P (A) ∩ P (B).

What do you notice?                                                                                                        (2 marks)

(b)  Prove or disprove that, for all sets A and B , P (A ∪ B) = P (A) ∪ P (B).            (4 marks)

2. Total:  6 marks

Using the definition of subset inclusion,  prove that  (or explain why),  for all sets  A and B , P (A ∩ B) = P (A) ∩ P (B).

(Hint: You can either do this directly, using the laws of set theory, or you can show that P (A ∩ B) ≤ P (A) ∩ P (B) and P (A) ∩ P (B) ≤ P (A ∩ B))                                             (6 marks)

3. Total:  6 marks

(a)  Let f : {1, 2, 3} → {a, b, c} be the function given by f(1) = b, f(2) = a, f(3) = c.

i.  Explain why f is a bijection and describe its inverse .                                   (2 marks)

ii.  Describe a bijection {a, b, c} → {1, 2, 3} that is not inverse to f.                    (1 mark)

(b)  For this part, answer either (i) or (ii) (or use (i) to help you answer (ii)).

Note that (i) is worth fewer marks than (ii).

i.  Let A = {a, b, c}.  Describe all functions from the set {1} to A. What do you notice? (2 marks)

ii.  Let A be a finite set.  How many functions are there  {1} → A?  Can you describe a relationship between the set of functions {1} → A and A itself?

(Hint: can you describe a bijection between A and the set of functions {1} → A?)

(3 marks)

4. Total: 6 marks

(a) Describe finite sets A and B and

i. a function f : A → B that is neither surjective nor injective.

ii. a function g : A → B that is surjective but not injective.

(Hint: It suffices, to draw digraphs with labelled vertices.)

(3 marks)

(b) Explain why, if A and B are finite sets, and jAj = j Bj, then a function f : A  → B  is injective if and only if it is surjective (and hence bijective).

(Hint: use a cardinality argument.)                                                        (3 marks)

5. Total: 6 marks

(a) (Gerstner, 4.1 Ex 11)

Think of a set A and a relation R on A that is reflexive and symmetric but not transitive. (Hint: A digraph suflces. Start small and add nodes and edges until you get the desired properties.)                                                                                      (2 marks)

(b) Check whether the following relations on N are reflexive, symmetric, or transitive:

i. R ≤ N × N given by (x, y) ∈ R if and only if xy is even.

ii. R ≤ N × N given by (x, y) ∈ R if and only if xy is odd.

(2+2 marks)

6. Total: 6 marks

(a) (Gerstner, 4.1 Ex 11)

Think of a set A  and a relation R  on A that is reflexive but neither symmetric nor transitive.

(Hint: A digraph suffices. Start small and add nodes and edges until you get the desired properties.)           (2 marks)

(b) Let A = {1, 2, 3, 4}.

i. What is the smallest reflexive relation on A? Show that this relation is also symmetric and transitive, hence an equivalence relation. (Hint: Draw a digraph)

ii. Show that the empty relation ∅ ≤ A × A is symmetric and transitive but not reflexive.

(2+2 marks)

Instructions:  Complete as many questions as you can.

The exercises in this section explore the relationship between relations R ≤ A × A on a set A, and functions F : A → P (A) from A to its power set.  They use the following constructions:

Construction I. Every relation R on a set A describes a function FR : A → P (A)

Let A be a set and R ≤ A × A a relation on A.

Define the function FR : A → P (A) by

FR (x) = {a ∈ A : (x, a) ∈ R} ≤ A for all x ∈ A.                                      (1)

(Note: If R is an equivalence relation, then FR (x) = [x] is the equivalence class of x under R.)

Example: Let A = {h, a, p, y} be the set of characters in the string ‘happy’, and R ≤ A × A be the relation whose elements are pairs (x,y) such that y immediately follows x in the string ‘happy’. So

R = {(h, a), (a, p), (p, p), (p, y)}.

Then FR (h) = {a},  FR (a) = {p},  FR (p) = {p, y},  FR (y) = ∅.

Construction II. Conversely, any function F: A → P (A) describes a relation RF on A

Let F : A → P (A) be a function.  Then

RF  = {(x, a): x ∈ A and a ∈ F (x)}                          (2)

Example: As  before,  let  A  =  {h, a, p, y} and  let  F  :  A  → P (A)  be  the  function  given  by F (h) = {a}, F (a) = {p}, F (p) = {p, y} and F (y) = ∅, then

RF  = {(h, a), (a, p), (p, p), (p, y)}

is the relation whose elements are pairs (x,y) such that y immediately follows x in the string ‘happy’.

• These exercises are more straightforward than they look.   It’s just about applying familiar definitions in unfamiliar contexts.

• The important thing to remember is that the collections of functions and relations between sets are, themselves, sets. Hence we can define functions and relations between them!

• See how far you get!

1. Total:  4 marks

(a)     i.  Let A = {0, 1} and R ≤ A × A be the relation R = {(0, 0), (0, 1), (1, 1)}.

Let FR  be as in equation (1) above. Describe the subset FR (0) of A.

ii.  Let A =  {a, b, c, d} and R =  ∅ ≤ A × A be the empty relation.   Let FR  be as in equation (1) above. Describe FR (a).

(1+1 marks)

(b)  Describe the relation RF  on A (as in equation (2) above) when

i.  A =  {1, 2, 3} and F : A → P (A) is given by F (1)  =  {1, 2}, F (2)  =  {2, 3}, F (3)  = {3, 1}

ii.  A = {1, 2, 3} and F : A → P (A) is given by F (1) = {1}, F (2) = {2, 3}, F (3) = ∅

(1+1 marks)

2. Total:  8 marks

Let Rel(A) be the set of relations on a set A and let Fun(A, P (A)) be the set of functions from A to its power set.

(a)  Describe Rel(A) and Fun(A, P (A)) when A = {1, 2}.

(Note:  If you get tired of listing all the elements, then you may choose another method. Indicate that you understand that you know how to construct them and how many there should be.)                                                (2 marks)

(b)  Let A be finite with jAj = n.

i.  By definition, Rel(A) is just the power set of A × A.  Use this fact to find  jRel(A)j in terms of n.

ii.  For finite sets X and Y , there are  jY j jXj  functions from X to Y.  So  j Fun(X, Y)j = jY j jXj .  Use this to find j Fun(A, P (A))j in terms of n.

iii.  Conclude that, if jAj = n < ∞ then jRel(A)j = j Fun(A, P (A))j .

(2+2+2 marks)

All marks for the remaining questions are bonus, and will be added to your graded problem sheet total. See how much you can answer.

3. Total:  10 bonus marks

(a)  Show that, for all sets A, the function Φ : Rel(A) → Fun(A, P (A)) given by Φ(R) = FR is injective (one-one).                                        (6 marks)

(b)  Try either of the following:

i.  Show that, for finite sets A, the function Φ : Rel(A) → Fun(A, P (A)) given by

Φ(R) = FR  is surjective and hence a bijection.  (Hint:  Use part (a) and question 2.)        (3 marks)

ii.  Show that, for all sets A, the function Φ : Rel(A) → Fun(A, P (A)) given by Φ(R) = FR  is surjective and hence a bijection.                                                   (4 marks)

(c)  (For fun.)  Show that Ψ : Fun(A, P (A)) → Rel(A), Ψ(F) = RF  is inverse to Φ .

(0 marks. Huge satisfaction.)