It looks like you're new here. If you want to get involved, click one of these buttons!
Products in preorders.
Given a set \(X\), a binary operation on \(X\) is a function \(*: X \times X \rightarrow X\) -- that is, a way of taking two elements of \(X\) and returning a third. This question explores how the product unifies many seemingly quite different binary operations commonly used in math.
(a) Consider the category where the objects are natural numbers and where there is a unique morphism from \(m\) to \(n\) if \(m\) divides \(n\). Given two numbers, for example 42 and 27, what is their product? What is the name of this binary operation?
(b) Consider the category where the objects are subsets of the set \(\lbrace a,b,c,d \rbrace\), and where there is a unique morphism from \(X\) to \(Y\) if \(X\) is a subset of \(Y\). Given two subsets, for example \(\lbrace a,b,c \rbrace\) and \(\lbrace b,c,d \rbrace\), what is their product? What is the name of this binary operation?
(c) Consider the category where the objects are True and False, and where there is a unique morphism from \(a\) to \(b\) if \(a\) implies \(b\). Given two objects, for example True and False, what is their product? What is the name of this binary operation?
Comments
a) Since \( m \rightarrow n \) implies that m divides n, then the product \( x \times y \) should contain one morphism \( x \times y \rightarrow x \) and one \( x \times y \rightarrow y \). So basically, we want \( x \times y \) such as it divides both \( x \) and \( y \). And that's the greatest common divisor of those two numbers: 3
b) Similarly, we want the product to be both a subset of \( {a,b,c} \) and \( {b,c,d} \). And that is the intersection: \( {b, c} \)
c) In this one we have that \( a \times b \rightarrow a \) and \( a \times b \rightarrow b ||) should be a tautology. So this should be the
andoperator and the value isFalseIn any case, we can test (not prove) all of those with this Haskell code:
https://gist.github.com/folivetti/e0ded9e8469388b6d00676d394a92c0d
a) Since \\( m \rightarrow n \\) implies that m divides n, then the product \\( x \times y \\) should contain one morphism \\( x \times y \rightarrow x \\) and one \\( x \times y \rightarrow y \\). So basically, we want \\( x \times y \\) such as it divides both \\( x \\) and \\( y \\). And that's the greatest common divisor of those two numbers: 3 b) Similarly, we want the product to be both a subset of \\( \{a,b,c\} \\) and \\( \{b,c,d\} \\). And that is the intersection: \\( \{b, c\} \\) c) In this one we have that \\( a \times b \rightarrow a \\) and \\( a \times b \rightarrow b ||) should be a tautology. So this should be the `and` operator and the value is `False` In any case, we can test (not prove) all of those with this Haskell code: https://gist.github.com/folivetti/e0ded9e8469388b6d00676d394a92c0d@FabricioOlivetti Thanks for your contributions to the forum!
Could you elaborate with some type of explanation and/or proofs? (As formal or as informal as you like.) To me the most interesting part of the exercises is the concepts that they illustrate. Supplying a proof calls for digging into the concepts. In the best case, such material could lead to further questions, new and different examples, and discussion generally.
The forum is a bit like a fledgling plant with a finicky appetite. We do our best...
@FabricioOlivetti Thanks for your contributions to the forum! Could you elaborate with some type of explanation and/or proofs? (As formal or as informal as you like.) To me the most interesting part of the exercises is the concepts that they illustrate. Supplying a proof calls for digging into the concepts. In the best case, such material could lead to further questions, new and different examples, and discussion generally. The forum is a bit like a fledgling plant with a finicky appetite. We do our best...By extension, this is an open invitation to anyone who wants to try their hand at explaining, or proving, any of the answers to the exercises which have been supplied so far. It could even be interesting to have multiple proofs of the same result, if they put different spins on the concepts.
By extension, this is an open invitation to anyone who wants to try their hand at explaining, or proving, any of the answers to the exercises which have been supplied so far. It could even be interesting to have multiple proofs of the same result, if they put different spins on the concepts.@DavidTanzer of course :) I just edited the answer! I don't have a strong mathematical background so I'll keep it informal!
If you notice any other unexplained answer from me just ping me, I'll do my best to answer quickly!
@DavidTanzer of course :) I just edited the answer! I don't have a strong mathematical background so I'll keep it informal! If you notice any other unexplained answer from me just ping me, I'll do my best to answer quickly!Hi @FabricioOlivetti, thanks for adding the clarifications.
I'm also interested to add to it a formal proof. That's going to have to begin by restating the general definition of what it means to be a product in a category, and then moving on to show why the gcd satisfies that definition. I don't have much time for this in the short term. But if anyone wants to start giving it a shot now, that would be great...
Hi @FabricioOlivetti, thanks for adding the clarifications. I'm also interested to add to it a formal proof. That's going to have to begin by restating the general definition of what it means to be a product in a category, and then moving on to show why the gcd satisfies that definition. I don't have much time for this in the short term. But if anyone wants to start giving it a shot now, that would be great...Ok, here I'll give it a go.
Given two objects A, B in a category, a product of A and B consists of another object, call it \(A \times B\), along with two morphisms \(\pi_1: A \times B \rightarrow A\), and \(\pi_2: A \times B \rightarrow B\), which satisfies a certain universal property in the category.
But before talking about the universal property, let's instantiate this first part of the definition to the category at hand.
Here, object A = m, and object B = n.
We have to now posit what the object \(A \times B\) is, and provide the two morphisms \(\pi_1: A \times B \rightarrow A\) and \(\pi_2: A \times B \rightarrow B\).
@FabricioOlivetti posited that \(A \times B\) is the greatest common divisor of m and n, gcd(m,n). Indeed it is, as we are now proving.
Claim: \(A \times B = m \times n = gcd(m,n)\)
(Note, don't be thrown off by the odd appearance of the above equation. Here the symbol \(\times\) is being used in a generic categorical sense, which in the case is being used to describe an operation that is not multiplication.)
Now we must produce \(\pi_1: m \times n \rightarrow m\) and \(\pi_2: m \times n \rightarrow n\).
But because this category is "thin," which means that there is at most one arrow between any two objects, there could only be one possible choice for \(pi_1\) and \(\pi_2\). Let's start with \(\pi_1: gcd(m,n) \rightarrow m\). Does any such arrow exist going from gcd(m,n) to m? Well yes, because gcd(m,n) divides m! So that is what \(\pi_1\) is. Similarly, \(\pi_2\) is the unique arrow going from gcd(m,n) to n.
Ok, here I'll give it a go. > (a) Consider the category where the objects are natural numbers and where there is a unique morphism from m to n if m divides n. Given two numbers, for example 42 and 27, what is their product? What is the name of this binary operation? Given two objects A, B in a category, a product of A and B consists of another object, call it \\(A \times B\\), along with two morphisms \\(\pi_1: A \times B \rightarrow A\\), and \\(\pi_2: A \times B \rightarrow B\\), which satisfies a certain universal property in the category. But before talking about the universal property, let's instantiate this first part of the definition to the category at hand. Here, object A = m, and object B = n. We have to now posit what the object \\(A \times B\\) is, and provide the two morphisms \\(\pi_1: A \times B \rightarrow A\\) and \\(\pi_2: A \times B \rightarrow B\\). @FabricioOlivetti posited that \\(A \times B\\) is the greatest common divisor of m and n, gcd(m,n). Indeed it is, as we are now proving. Claim: \\(A \times B = m \times n = gcd(m,n)\\) (Note, don't be thrown off by the odd appearance of the above equation. Here the symbol \\(\times\\) is being used in a generic categorical sense, which in the case is being used to describe an operation that is not multiplication.) Now we must produce \\(\pi_1: m \times n \rightarrow m\\) and \\(\pi_2: m \times n \rightarrow n\\). But because this category is "thin," which means that there is at most one arrow between any two objects, there could only be one possible choice for \\(pi_1\\) and \\(\pi_2\\). Let's start with \\(\pi_1: gcd(m,n) \rightarrow m\\). Does any such arrow exist going from gcd(m,n) to m? Well yes, because gcd(m,n) divides m! So that is what \\(\pi_1\\) is. Similarly, \\(\pi_2\\) is the unique arrow going from gcd(m,n) to n.What remains to be shown now is that gcd(m,n) satisfies the universal property. First we'll restate the universal property for a general category, and then instantiate it to the integer category to prove that gcd(m,n) satisfies it.
But here's a motivating hint for the universal property, and why it is needed. In the above construction that I gave, I proved the existence of the projection morphisms \(\pi_1\) and \(\pi_2\). But note that that argument only depended upon the fact that gcd(m,n) was a common divisor of m and n. I didn't invoke the fact that gcd(m,n) is the greatest common divisor of m and n. That greatest property is exactly what is needed to prove that gcd(m,n) satisfies the universal property.
What remains to be shown now is that gcd(m,n) satisfies the universal property. First we'll restate the universal property for a general category, and then instantiate it to the integer category to prove that gcd(m,n) satisfies it. But here's a motivating hint for the universal property, and why it is needed. In the above construction that I gave, I proved the existence of the projection morphisms \\(\pi_1\\) and \\(\pi_2\\). But note that that argument only depended upon the fact that gcd(m,n) was a common divisor of m and n. I didn't invoke the fact that gcd(m,n) is the _greatest_ common divisor of m and n. That _greatest_ property is exactly what is needed to prove that gcd(m,n) satisfies the universal property.Back to the general level now. Here is the universal property that the posited product object \(A \times B\) must satisfy:
For all other objects \(C\) and with arrows \(\tau_1: C \rightarrow A\) and \(\tau_2: C \rightarrow B\), there exists a unique arrow \(h: C \rightarrow A \times B\) such that \(\tau_1\) and \(\tau_2\) factor through \(h\):
\[\tau_1 = h \triangleright \pi_1\]
\[\tau_2 = h \triangleright \pi_2\]
Note: I am introducing a nonstandard notion here \(x \triangleright y\) to mean \(x;y\) = x-then-y = \(y \circ x\) = y-after-x. The triangle reads nicely to show that the output of morphism x gets fed into the input of morphism y. It's a left-to-right pipeline of morphisms.
Back to the general level now. Here is the universal property that the posited product object \\(A \times B\\) must satisfy: For all other objects \\(C\\) and with arrows \\(\tau_1: C \rightarrow A\\) and \\(\tau_2: C \rightarrow B\\), there exists a _unique_ arrow \\(h: C \rightarrow A \times B\\) such that \\(\tau_1\\) and \\(\tau_2\\) factor through \\(h\\): \\[\tau_1 = h \triangleright \pi_1\\] \\[\tau_2 = h \triangleright \pi_2\\] Note: I am introducing a nonstandard notion here \\(x \triangleright y\\) to mean \\(x;y\\) = x-then-y = \\(y \circ x\\) = y-after-x. The triangle reads nicely to show that the output of morphism x gets fed into the input of morphism y. It's a left-to-right pipeline of morphisms.Now let's instantiate back to our integer category, and show that \(A \times B = gcd(m,n)\) satisfies this universal property.
Now let's instantiate back to our integer category, and show that \\(A \times B = gcd(m,n)\\) satisfies this universal property.So suppose we are given some other integer \(c\), and arrows \(\tau_1: c \rightarrow m\) , \(\tau_2: c \rightarrow n\).
That means that \(c\) divides \(m\) and \(c\) divides \(n\), which is to say that \(c\) is a common divisor of \(m\) and \(n\).
Moreover, gcd(m,n) is the greatest common divisor of \(m\) and \(n\), which means that c divides gcd(m,n).
So there is an arrow \(h: c \rightarrow gcd(m,n)\).
Recall that the universal property required the existence of precisely such an arrow \(h\). Check!
So suppose we are given some other integer \\(c\\), and arrows \\(\tau_1: c \rightarrow m\\) , \\(\tau_2: c \rightarrow n\\). That means that \\(c\\) divides \\(m\\) and \\(c\\) divides \\(n\\), which is to say that \\(c\\) is a common divisor of \\(m\\) and \\(n\\). Moreover, gcd(m,n) is the _greatest_ common divisor of \\(m\\) and \\(n\\), which means that c divides gcd(m,n). So there is an arrow \\(h: c \rightarrow gcd(m,n)\\). Recall that the universal property required the existence of precisely such an arrow \\(h\\). Check!thanks @DavidTanzer that was very informative :)
thanks @DavidTanzer that was very informative :)@FabricioOlivetti, sure thing! It was a good exercise to spell everything out. As we see, there are a lot of implied details in the compact statements of category theory.
I need to do a couple more steps to complete the proof.
@FabricioOlivetti, sure thing! It was a good exercise to spell everything out. As we see, there are a lot of implied details in the compact statements of category theory. I need to do a couple more steps to complete the proof.Next we need to show that \(\tau_1\) and \(\tau_2\) factor through this \(h\):
\[\tau_1 = h \triangleright \pi_1\]
\[\tau_2 = h \triangleright \pi_2\]
Now since the category is thin, the above equations must be true. That's because all of the three arrows exist, and they form a well-typed commutative diagram, with domains and codomains of the arrows matching as expected. (Sorry I don't have the bandwidth to draw diagrams now.) Since in a thin category, there's at most one arrow between two objects, the left and right hand sides of these equations must be the same.
Next we need to show that \\(\tau_1\\) and \\(\tau_2\\) factor through this \\(h\\): \\[\tau_1 = h \triangleright \pi_1\\] \\[\tau_2 = h \triangleright \pi_2\\] Now since the category is thin, the above equations must be true. That's because all of the three arrows exist, and they form a well-typed commutative diagram, with domains and codomains of the arrows matching as expected. (Sorry I don't have the bandwidth to draw diagrams now.) Since in a thin category, there's at most one arrow between two objects, the left and right hand sides of these equations must be the same.Finally, we need to show that there is only one, unique such \(h\).
But that follows immediately from the fact that the category is thin.
That completes the proof.
Finally, we need to show that there is only one, unique such \\(h\\). But that follows immediately from the fact that the category is thin. That completes the proof.How about we now tackle the proof for part (b), taking my proof for (a) as a skeleton?
How about we now tackle the proof for part (b), taking my proof for (a) as a skeleton?(b) Consider the category where the objects are subsets of the set {a,b,c,d}, and where there is a unique morphism from X to Y if X is a subset of Y. Given two subsets, for example {a,b,c} and {b,c,d}, what is their product? What is the name of this binary operation?
@FabricioOlivetti claimed that in the category, the product is the intersection of two sets.
Note that this category is also thin: between sets A and B, there is either no morphism from A to B, if A is not a subset of B, or there is exactly one morphism from A to B, if A is a subset of B.
So a good deal of the structure of my proof for part (a) -- the parts that rely upon thinness -- should carry over.
It would seem kind of repetitive for me to crank out this proof now. Anyone up for getting the ball rolling here?
(b) Consider the category where the objects are subsets of the set {a,b,c,d}, and where there is a unique morphism from X to Y if X is a subset of Y. Given two subsets, for example {a,b,c} and {b,c,d}, what is their product? What is the name of this binary operation? @FabricioOlivetti claimed that in the category, the product is the intersection of two sets. Note that this category is also thin: between sets A and B, there is either no morphism from A to B, if A is not a subset of B, or there is exactly one morphism from A to B, if A is a subset of B. So a good deal of the structure of my proof for part (a) -- the parts that rely upon thinness -- should carry over. It would seem kind of repetitive for me to crank out this proof now. Anyone up for getting the ball rolling here?In
Control.Arrowin Haskell there's>>>, which is a left-to-right composition of morphisms. You can write this in \(\LaTeX\) as \(\ggg\) or\ggg.> Note: I am introducing a nonstandard notion here \\(x \triangleright y\\) to mean \\(x;y\\) = x-then-y = \\(y \circ x\\) = y-after-x. The triangle reads nicely to show that the output of morphism x gets fed into the input of morphism y. It's a left-to-right pipeline of morphisms. In `Control.Arrow` in Haskell there's `>>>`, which is a left-to-right composition of morphisms. You can write this in \\(\LaTeX\\) as \\(\ggg\\) or `\ggg`.