Phil 455: Homework 3 (on Relations)

Since this homework was posted late, it won’t be due until the end of the day (11:59 pm) on Friday.

1. Let Γ be {"a","b","c"} and Δ be {1,2}. How many different relations are there from Γ to Δ? How many of them are “functional”? In those cases, how many of the corresponding functions (the functions with the same graph) are surjective? How many are injective? Do any of the functional relations have inverses that are also functional?

2. Answer the same questions as in the previous problem, but with relations from Δ to Γ.

3. Unlike with functions, the composition of a relation and its inverse need not be an identity. Give an example that demonstrates this.

4. Let A be the set {1,2,3,4}. Determine the properties of each of the relations whose graphs are specified, and also each of their inverses.

    R1: { (1,1), (2,1), (3,4), (2,2), (3,3), (4,4), (4,1) }
    R2: { (3,4), (1,2), (1,4), (2,3), (2,4), (1,3) }
    R3: { (2,4), (3,1), (3,4), (2,2), (1,3), (4,3), (4,2) }
    R4: { (1,1), (2,4), (1,3), (2,2), (3,1), (4,4), (3,3), (4,2) }

   That is, for each relation you should say: (a) is it reflexive, irreflexive, or neither? (b) is it symmetric and/or anti-symmetric, asymmetric, or none of these? (c) is it transitive, intransitive, or neither? (d) is it a total/complete relation on A? (Clarification: by this, I mean is it weakly or strongly connected?)

5. Specify the equivalence relation on set A (from previous problem) that generates the following partition: { {1}, {2,3}, {4} }.

6. Where x ∈ ℕ, y ∈ ℕ and y > 0, say that x mod y is the remainder you get when dividing x by y. That is, it’s the r ∈ ℕ where r < y and ∃q ∈ ℕ (x = q⋆y + r). Some examples: 3 mod 5 = 3, 15 mod 5 = 0, 5 mod 3 = 2.

   Now let B be the set {2,3,5,6,10,15,30} and let R be the relation on B whose graph is {(y,x) | x mod y = 0}.

   1. List the elements of R and show that it is a non-strict partial order but not a total order.
   2. Identify any maximal, minimal, greatest, and/or least elements in this order.
   100. Do the same as (a) and (b) but for the set 𝟚^Γ, where Γ is {"a","b","c"}, and the relation is ⊆. (Recall that 𝟚^Γ means “the powerset of Γ.”)

7. For any n ∈ ℕ and n > 0, show that the relation whose graph is {(u,v) | u mod n = v mod n} is an equivalence relation, and that the partition it generates on ℕ has exactly n members.

8. Prove that the transitive closure of a relation R is transitive.