#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Options

# Question 2.5 - Products in preorders

edited January 19

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?

• Options
1.
edited January 23

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 Comment Source: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 • Options 2. edited January 23 @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... Comment Source:@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... • Options 3. edited January 23 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. Comment Source: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. • Options 4. @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! Comment Source:@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! • Options 5. edited January 25 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... Comment Source: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... • Options 6. edited June 14 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)$$

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.

Comment Source: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)\$$ 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. 
• Options
7.
edited January 27

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.

Comment Source: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. 
• Options
8.
edited January 27

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.

Comment Source: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. 
• Options
9.

Now let's instantiate back to our integer category, and show that $$A \times B = gcd(m,n)$$ satisfies this universal property.

Comment Source:Now let's instantiate back to our integer category, and show that \$$A \times B = gcd(m,n)\$$ satisfies this universal property.
• Options
10.
edited January 27

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!

Comment Source: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!
• Options
11.

thanks @DavidTanzer that was very informative :)

Comment Source:thanks @DavidTanzer that was very informative :)
• Options
12.

@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.

Comment Source:@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. 
• Options
13.

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.

Comment Source: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.
• Options
14.
edited January 27

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.

Comment Source: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.
• Options
15.

How about we now tackle the proof for part (b), taking my proof for (a) as a skeleton?

Comment Source:How about we now tackle the proof for part (b), taking my proof for (a) as a skeleton?
• Options
16.

(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?

Comment Source:(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? 
• Options
17.

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.

Comment Source:> 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.