This homework is due by the end of the day on Fri, Feb 16.
Sample answers in purple.
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?
Concatenation is an operation on Q but not on S ("a" ⁀ "a" ∉ S). The algebra consisting of Q and concatenation is a monoid, with ɛ being its identity. Identity elements are always their own inverse, but in this algebra no other elements have inverses.
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.
{0,1,2,3}, and that the algebra consisting of that domain and operation forms a group.{1,2,3,4,5,6}, and that the algebra consisting of that domain and operation forms a group.{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.
Here is a table of addition mod 4 on the specified domain:
| + | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 1 | 2 | 3 |
| 1 | 1 | 2 | 3 | 0 |
| 2 | 2 | 3 | 0 | 1 |
| 3 | 3 | 0 | 1 | 2 |
The result of each addition mod 4 can be verified by inspecting the table to always also be a member of the domain. The resulting algebra has 0 as an identity, and 1 and 3 have each other as inverses, and 2 has itself as an inverse.
Here is a table of multiplication mod 7 on the specified domain:
| * | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 4 | 5 | 6 |
| 2 | 2 | 4 | 6 | 1 | 3 | 5 |
| 3 | 3 | 6 | 2 | 5 | 1 | 4 |
| 4 | 4 | 1 | 5 | 2 | 6 | 3 |
| 5 | 5 | 3 | 1 | 6 | 4 | 2 |
| 6 | 6 | 5 | 4 | 3 | 2 | 1 |
The result of each multiplication mod 7 can be verified by inspecting the table to always also be a member of the domain. The resulting algebra has 1 as an identity, and 2 and 4 have each other as inverses, and 3 and 5 have each other as inverses, and 6 has itself as an inverse.
Here is a table of multiplication mod 11 on the specified domain:
| * | 1 | 3 | 4 | 5 | 9 |
|---|---|---|---|---|---|
| 1 | 1 | 3 | 4 | 5 | 9 |
| 3 | 3 | 9 | 1 | 4 | 5 |
| 4 | 4 | 1 | 5 | 9 | 3 |
| 5 | 5 | 4 | 9 | 3 | 1 |
| 9 | 9 | 5 | 3 | 1 | 4 |
The result of each multiplication mod 11 can be verified by inspecting the table to always also be a member of the domain. The resulting algebra has 1 as an identity, and 3 and 4 have each other as inverses, and 5 and 9 have each other as inverses.
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 (Α – Β) ∪ (Β – Α).
Β, ∪ and ∩ and – are operators on 𝟚Β. Why does that entail that ⊖ is also an operator on 𝟚Β?Α ⊖ Β to prove that ⊖ is commutative. You can help yourself to the fact that ∪ is commutative.If ∪ is an operator, then for any Α, Β in the domain 𝟚Β, Α ∪ Β will also be in the domain.
If ∩ is an operator, then for any Α, Β in the domain, Α ∩ Β will also be in the domain.
If – is an operator, then for any Γ, Δ in the domain, Γ – Δ will also be in the domain. (We’re interested in the case where Γ = Α ∪ Β and Δ = Α ∩ Β.)
Thus for any Α, Β in the domain, (Α ∪ Β) – (Α ∩ Β) will also be in the domain.
By the second formulation, Α ⊖ Β is (Α – Β) ∪ (Β – Α). By the same formulation, Β ⊖ Α is (Β – Α) ∪ (Α – Β). Since ∪ is commutative, these are equivalent.
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 Α.(Α ⊖ Β) ⊖ Γ 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 …⊖ is associative.Complete the argument by filling in the … You can help yourself to the fact you proved in Problem 47b.
… because it will consist of those elements that (i) are in (Β ⊖ Γ) but not Α, or (ii) in Α but not (Β ⊖ Γ). Case (i) can be rephrased as “the element is in exactly one of Β and Γ, and not in Α. Case (ii) subdivides into (iia) the element is in Α but in neither of Β or Γ; or (iib) the element is in Α and in both of Β and Γ. Cases (i) and (iia) can be combines as “the element is in exactly one of Β, Γ, and Α.” Case (iib) 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 Α.
(a) Does the ⊖ operation have an identity? (b) Does every element of 𝟚Β have an inverse for the operation ⊖? What is it?
Yes, symmetric difference has ∅ as an identity. And every element has itself as an inverse.
Given the facts shown in problems 47–49, what category does the algebra consisting of the domain 𝟚Β and the ⊖ operation belong to?
Since it’s an associative operation on this domain, with an identity and every element has an inverse, this algebra is a group. (It also has more specific properties, for example because as you showed in 47b, this operation is commutative.)
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?
Since it’s an associative operation on this domain, with the identity ΙΒ, it’s at least a monoid. Since Ψ consists of all and only bijections on Β, each element f of Ψ will have an inverse function f⁻¹ that’s also ∈ Ψ. And f ∘ f⁻¹ will = f⁻¹ ∘ f will = ΙΒ. So this algebra is additionally a group.
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.)
● 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.● operation form a group.
A move can be understood as a function from squares to squares, and we already know that function composition is associative.
Here is a table of composed moves (with this domain the results are commutative):
| ● | stay | vertical | horizontal | diagonal |
|---|---|---|---|---|
| stay | stay | vertical | horizontal | diagonal |
| vertical | vertical | stay | diagonal | horizontal |
| horizontal | horizontal | diagonal | stay | vertical |
| diagonal | diagonal | horizontal | vertical | stay |
The result of each composition can be verified by inspecting the table to always also be a member of the domain. The resulting algebra has stay as an identity, and each move is its own inverse.
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 φ ∧ ¬(φ ∧ ψ).
We proved in the earlier problems that the algebra is a commutative group wrt ⊖. For it to be a ring, we need the further claim that the ⊙ is associative (we can take this as already established wrt ∩) and that the operations interacrt in the correct way, namely that:
x ∩ (y ⊖ z) = (x ∩ y) ⊖ (x ∩ z)
(y ⊖ z) ∩ x = (y ∩ x) ⊖ (z ∩ x)It suffices to prove one of these, because we know that ∩ and ⊖ are both commutative. Let’s prove the first.
We know from the definition of ∩ that something is in x ∩ (y ⊖ z) iff it’s in both of those sets, and we know from our earlier work with ⊖ that something is in y ⊖ z iff it’s in y but not in z, or in z but not in y. Putting these together, something is in x ∩ (y ⊖ z) iff either (i) it’s in x and (in y and not in z), or (ii) it’s in x and (in z and not in y). Because of the associativity and commutativity of “and”, this is the same as: either (iii) it’s in y and (in x and not in z), or (iv) it’s in z and (in x and not in y). Relying on the logical equivalence given in the hint, (iii) is equivalent to (v) it’s in y and (in x and not (in x and in z)), and (iv) is equivalent to (vi) it’s in z and (in x and not (in x and in y)). Again relying on the associativity and commutativty of “and”, (v) is equivalent to (vii) it’s (in x and in y) and not (in x and in z), and (vi) is equivalent to (viii) it’s (in x and in z) and not (in x and in y). By the definitions of ∩ and – and ∪, the disjunction of (vii) and (viii) is (ix) it’s in ((x ∩ y) – (x ∩ z)) ∪ ((x ∩ z) – (x ∩ y)), which from what we know about ⊖ is the rhs of the equation we’re trying to prove.
So the first algebra is a ring. Its ⊙ operation is ∩ which we know does commute. That operation does have an identity, namely the set Β such that the algebera’s universe is 𝟚Β.
If we replaced ⊖ with ∪, the resulting algebra would not (in general) be a group, because most elements would not have inverses. The identity element for ∪ would be ∅, but for most Δs (specifically, Δs that aren’t empty), there’s no Γ such that Δ ∪ Γ = ∅.
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?
Let the domain of our 4-element lattice be {⊥, x, y, ⊤}. At least one of x or y must be mapped to the same element that ⊥ is mapped to; otherwise you won’t be able to get the result that f(x ∧ y) = f(x) ∧ f(y). If you want the homomorphism to be surjective, then map ⊤ to the greatest element of the 3-element total order, one of x or y to the middle element, and the other of x or y, plus ⊥, to the least element of the 3-element order.
For non-surjective homomorphisms, you might collapse more of these together, for example, by mapping all three of x, y, and ⊥ to the same element; or mapping ⊤ and x to one element, and y and ⊥ to a lesser element; or even mapping all of the elements of the lattice to a single element in the 3-element order.
The mapping will be a join-homomorphism only when x ∨ y, that is ⊤, is mapped the greater element of what x and y are each mapped to. The surjective homomorphism, and the first of the non-surjective homomorphisms mentioned, do not satisfy this constraint.
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.
Our group is addition mod 6 on the domain {0,1,2,3,4,5}. The identity element 1 in the first group has to map to the identity element 0 in the second group. 6 in the first group is its own inverse (6 ⋅ 6 mod 7 = 1); this element maps to 3 in the second group which will also be its own inverse (3 + 3 mod 6 = 0). For the remaining elements, there is some latitude. Note that 3 and 5 are inverses in the first group; as are 2 and 4. In the second group, 1 and 5 are inverses, as are 2 and 4. One option that works is to map 3 to 1 and each of 5, 2 and 4 to themself. Another option that works is to map 3 to 5, 5 to 1, 2 to 4, and 4 to 2.