Maps?

[gnighm]

First time on Github, so apologies if I make mistakes on protocol:

I never studied beyond high school math(s), so I was a bit puzzled when I got to the term “Maps” in the section on Monoids. Even in your first example that used it, I understood most of it until you said f swap circle f swap = e.

For the same reasons, exercise 2.4 is also difficult to understand.

[hdgarrood]

Welcome! There's not really any protocol for this repo, don't worry :)

It didn't occur to me that people might find this confusing: mathematicians often refer to functions as "maps", and by the time I wrote this, I had heard people say it enough times that I didn't think anything of it. I guess it's probably fair to say that lots of programmers consider functions to be different kinds of things than the Map data structure; is that why you found it puzzling? I suspect it isn't a coincidence that these things share a name, though, since if you squint a bit, you can consider a Map a b to be essentially the same thing as a (partial) function a -> b:

mapToFunction :: forall a b. Partial => Map a b -> a -> b
mapToFunction m x = fromJust (Map.lookup x m)

Does that help clear things up at all? Also with respect to the f swap circle f swap = e example, can you expand a little on what lost you? E.g. is it that you don't follow what I'm trying to communicate there, or perhaps that you would have expected f swap circle f swap to equal something other than e?

[gnighm]

Thank you for your quick response! That makes sense that "maps" refer to functions. In the section I arrived at, I think one reason I became confused by the function in question is because it had the set X as both the input and output of the function. Perhaps I am overthinking it: Does that just mean for any any x put into the function, there is a corresponding x? If so...then, yes, that is relatively simple.

The other thing that threw me off is just the notion of a set of functions rather than a set of values. So I was confused about why the identity element e is a function in this case, whereas it was a value (such as 1, 0, or T) as in the examples given above. Now it makes sense that since the set in question is a set of functions, so the identity element must be a function as well. Here I have another question. After you designated set X as {A,B}, you then say "Then there are four functions from X to X: ...". This seems to check out just fine after working through it, but was I supposed to know that these four functions exist based on the givens?

As for my difficulty fswap∘fswap=e, I think this was because I wasn't thinking clearly that all of the elements here are functions. This makes more sense now.

I will let you know if I make it through the exercises in 2.4! Again, my math never went past high school calculus, and even my programming knowledge is nothing more than the most rudimentary C++. Your patience and desire to share mathematics is appreciated.

[hdgarrood]

Does that just mean for any any x put into the function, there is a corresponding x? If so...then, yes, that is relatively simple.

If I understand you correctly, yes. The important thing is that you put something in which is an element of the set X, and you get something out which is potentially different, but whatever it is, it is guaranteed to also be an element of X. This is what allows you to compose these functions: if the thing you got out wasn't an element of X, then the types wouldn't match up and you wouldn't be able to then put your output back into some other function from X to X.

Now it makes sense that since the set in question is a set of functions, so the identity element must be a function as well.

Yes, exactly! I'm pleased that you were able to see this without it being explicitly stated.

... was I supposed to know that these four functions exist based on the givens?

Not necessarily: my idea there was that any reader who either didn't know or didn't immediately recall the rule for working out how many functions there are from one set to another would be able to do what you've done here, i.e., work through it and hopefully get to a point where they see why there are no functions other than the ones I've listed. (Incidentally the more general rule is that if X has n elements and Y has m elements, then there are m^n distinct functions from X to Y, but you don't need to know this here.)

Your patience and desire to share mathematics is appreciated.

This is very nice to hear; you're welcome ❤️

[gnighm]

Here is my solution to Exercise 2.4.

To be done: Prove that (Maps(X,M),⋆) is monoid.

Closure. f(x) and g(x) are members of set M. Since (M,∗) is a monoid, then f(x)∗g(x) is always a member of that same set. Therefore, the star product of two functions from X to M is itself a function from X to M, so closure is satisfied.

Associativity.
f⋆g=x↦f(x)∗g(x)=x↦ g(x) ∗ f(x) = g⋆f
But x↦f(x)∗g(x)=x↦ g(x) ∗ f(x), since (M,∗) is monoid.
But g⋆f = x↦ g(x) ∗ f(x)
Therefore f⋆g=g⋆f

Identity.
The identity function e : X→M defined by e(x)=x for all x ∈ X is the identity element with respect to function composition, so identity is satisfied.

Since Maps(X,M) is a function, its identity element is also a function. So the identity element is a function such that
f⋆e = x↦f(x)∗e(x)=x↦ f(x)

That such a function exists follow from the fact that (M,∗) is monoid. Since f(x) and g(x) are members of set M, there must exist a g(x) for which x↦f(x)∗g(x)=x↦f(x). But e is defined as the function for which x↦f(x)∗e(x)=x↦ f(x).

Therefore (Maps(X,M),⋆) is monoid.

Let me know if that all works. I am also not sure exactly how to articulate the identity element (beyond what I said in proving there is identity), which is required by the Exercise.
Thank you!

[gnighm]

Reviewing the definition of associativity, it doesn't look like I quite addressed it, but the answer should come down to some form of "because (M,∗) is a monoid".

Also: I posted my comment before seeing your response. Thank you for affirming my thoughts my above! I don't know that I ever learned the rule for how many functions exist between two sets, so that's good to know too. (Thinking about for a moment just now, it makes sense... I'm so used to thinking of functions as continuous and you can't really put a number on that.)

[hdgarrood]

Reviewing the definition of associativity, it doesn't look like I quite addressed it, but the answer should come down to some form of "because (M,∗) is a monoid”.

This is correct: in fact what you’ve shown is that if (M,*) is commutative, then so is (Maps(X,M), ⋆). This is a useful theorem but it’s not the one we wanted! Also note that you can’t assume that x*y = y*x for all x,y in M, because this isn’t true for all monoids! One counterexample would be the list monoid, where the operation is concatenation and the identity element is the empty list.

[hdgarrood]

Oops, didn’t mean to close.

[hdgarrood]

Closure looks good, but identity isn’t quite there: if X and M are different sets, the function e(x)=x won’t be a function from X to M, but rather a function from X to X. (Hint: What could you do to make sure that e(x) is always an element of M?)

[gnighm]

It looks like I miscopied my answered for Identity. Omitting the first line, it seems that the rest of it holds. I’ll copy it here:

Since Maps(X,M) is a function, its identity element would also be a function. So the identity element would be a function such that
f⋆e = x↦f(x)∗e(x)=x↦ f(x)

That such a function exists follow from the fact that (M,∗) is monoid. Since f(x) and g(x) are members of set M, there must exist a g(x) for which x↦f(x)∗g(x)=x↦f(x). But e is defined as the function for which x↦f(x)∗e(x)=x↦ f(x).

Since g(x) is a member of set M, so is e(x).

[gnighm]

Update:
I just made it through the section on Groups. For some reason, I found it much easier! If I had never dabbled in Gauss’ Disquisitiones Arithmeticae, I think I would have found it overwhelming, but as it stands, I found it much easier than what I read in Gauss. The section that was the hardest was on the symmetric group, but after looking up permutations and symmetric groups, and also writing out S sub 3 and composing a number of them, it made send that the function in question is bijective. I didn’t come up with a proof for Exercise 3.5, but I was convinced of its truth once I understood what the terms meant. Looking forward to the next section!

Also: In the Groups section, you have more explanation of the Map and function terminology than in the Monoid section. Perhaps it would be better if it came earlier?

[hdgarrood]

You’re close, but not quite there.

That such a function exists follow from the fact that (M,∗) is monoid

This is true, but not very persuasive, since it doesn’t provide much detail. In this case it is possible to say what the identity element of Maps(X,M) is explicitly, rather than just arguing that it exists. You might find it useful to compare your answer with the solutions in the appendix, too.

[gnighm]

I hadn't noticed that appendix before—I think that would have cut down on a lot of the questions I asked here! The answer given there makes sense.

[hdgarrood]

Also: In the Groups section, you have more explanation of the Map and function terminology than in the Monoid section. Perhaps it would be better if it came earlier?

Thanks for the suggestion, I'll have a look at that when I get a chance.

Maybe I'll draw more attention to the appendix too :)

[gnighm]

I'm nearing the end of the integral domains section, and I was surprised the Exercise 6.4 had the word (hard) attached to it. It made sense that for any Zm to have a zero-divisor, you needed two elements of the set Zm to have a product equal to m. But only composite numbers are the product of two factors (that aren't 1). So then it is when m is prime that you have an integral domain. The appendix uses more technical language, but I think it comes to the same.

Also: I once spent a long evening with a Linear Algebra textbook, getting up to the chapter on eigenvectors/eigenvalues. Without that small background, I think all of the matrix math would have been a bit too much, so I was glad to see that you made suggestions for understanding matrix multiplication better. I didn't remember the phrase "linear mapping" from anywhere, so that took a little more effort to understand.