Phil 455: Homework 4

This homework is due by the end of the day on Fri, Feb 16.

45. Consider the set of strings S {ɛ,"a","b"}, where ɛ is the empty string. Let Q be its closure under concatenation (⁀). Is concatenation an operation on S? Is it an operation on Q? Does the algebra consisting of Q and concatenation form a monoid? Do any members of that algebra have inverses?

46. This problem makes use of the function mod that you met in Problems 32 and 39. We’ll talk about “addition mod n,” which is the binary function from (x,y) to (x+y) mod n, and “multiplication mod n,” which is the binary function from (x,y) to (x⋅y) mod n. You can help yourself to the fact that each of these functions is commutative and associative.

    1. Show that addition mod 4 is an operation on the domain {0,1,2,3}, and that the algebra consisting of that domain and operation forms a group.
    2. Show that multiplication mod 7 is an operation on the domain {1,2,3,4,5,6}, and that the algebra consisting of that domain and operation forms a group.
    3. Show that multiplication mod 11 is an operation on the domain {1,3,4,5,9}, and that the algebra consisting of that domain and operation forms a group.

    In each case, to show that the algebra is a group, you’ll have to identify the identity element and the inverse relation.

47. In Problem 11 you met the “symmetric difference” operator on sets, which I’m symbolizing as ⊖. (It’s fine if you want to use (-) or xor to represent symmetric difference, rather than ⊖.)

    Α ⊖ Β was defined as (Α ∪ Β) – (Α ∩ Β), and you proved this was equivalent to (Α – Β) ∪ (Β – Α).

    1. In Problem 12, you argued that for any set Β, ∪ and ∩ and – are operators on 𝟚^Β. Why does that entail that ⊖ is also an operator on 𝟚^Β?
    2. Use the second fomulation of Α ⊖ Β to prove that ⊖ is commutative. You can help yourself to the fact that ∪ is commutative.

48. Here is the outline of an argument that ⊖ is associative.

    • Α ⊖ Β consists of those elements that are in exactly one of Α and Β: they’re in Α but not Β, or Β but not Α.
    • So (Α ⊖ Β) ⊖ Γ will consist of those elements that (i) are in Γ but not Α ⊖ Β, or (ii) in Α ⊖ Β but not Γ. Case (ii) can be rephrased as “the element is in exactly one of Α and Β, and not in Γ.” Case (i) subdivides into (ia) the element is in Γ but in neither of Α or Β; or (ib) the element is in Γ and in both of Α and Β. Cases (ii) and (ia) can be combined as “the element is in exactly one of Α, Β, and Γ.” Case (ib) can be rephrased as “the element is in all three of Α, Β, and Γ.” Hence, (Α ⊖ Β) ⊖ Γ consists of those elements that are either in exactly one, or in all three, of Α, Β, and Γ.
    • Α ⊖ (Β ⊖ Γ) also consists of those elements that are either in exactly one, or in all three, of Α, Β, and Γ; because …
    • Since these conditions are the same, ⊖ is associative.

    Complete the argument by filling in the … You can help yourself to the fact you proved in Problem 47b.

49. (a) Does the ⊖ operation have an identity? (b) Does every element of 𝟚^Β have an inverse for the operation ⊖? What is it?

50. Given the facts shown in problems 47–49, what category does the algebra consisting of the domain 𝟚^Β and the ⊖ operation belong to?

51. In Problem 13 you worked with a set Ψ of all bijections on another set Β. You argued that function composition (∘) is a non-commutative operation on Ψ. We also know that function composition is associative. Given what you established in Problems 14 and 15, what category does the algebra consisting of the domain Ψ and the ∘ operation belong to?

52. Consider the “checkerboard game” defined as follows. There’s a checkerboard with four squares, which I’ll name NW, NE, SE, and SW. A single checker is located on one of the squares. It can move either vertically (from NW to SW, or from SW to NW, and so on), or horizontally (from NW to NE, or from NE to NW, and so on), or diagonally (from NW to SE, or from SE to NW, and so on). Or it can stay in place. Consider the set consisting of these four moves {vertical,horizontal,diagonal,stay}. Consider the operation of performing two of these moves in sequence: vertical ● horizontal means first move horizontally then move vertically. (We order the moves in the same way we order functions when describing their composition.)

    1. Here is an argument that the ● operation is associative: a move can be understood as a f__ from s__s to s__s, and we already know that f__ c__ is associative. Fill in the blanks.
    2. Prove that the set of moves described together with the ● operation form a group.

53. Consider the algebra described in Problem 50 with symmetric difference ⊖ being the operation. Prove that if you use ⊖ in the ★ role, and ∩ in the ⊙ role, the resulting algebra is a ring. Does the ⊙ of this ring commute? Does it have an identity? What if we replaced ⊖ with the ∪ operation: would that be a ring?

    Hint: in answering this, you can help yourself to the logical equivalence between claims of the form φ ∧ ¬ψ and claims of the form φ ∧ ¬(φ ∧ ψ).

54. A meet homomorphism is a total function f between meet semilattices such that for all elements x, y of the first semilattice, the meet in the second semilattice of f(x) and f(y) is identical to f(x ∧ y) (where ∧ is the meet operation of the first semilattice). The notion of a join homomorphism is defined analogously.

    Specify (by drawing a diagram or otherwise) a meet homomorphism from a 4-element lattice to a 3-element total order. (It’s possible to solve this with a surjective homomorphism. Try to do so. If you can’t, then give a non-surjective homomorphism.)

    Does the function you provide also constitute a join homomorphism? Why or why not?

55. In Problem 46b above, you showed that multiplication mod 7 on the domain {1,2,3,4,5,6} constituted a group. Find a set of numbers that form a group with addition mod some n, where this group is isomorphic to the group from 46b. Specify the isomorphism.