Options

Lecture 24 - Chapter 2: Pricing Resources

Today's lecture will be very short, consisting solely of some puzzles about prices.

We often compare resources by comparing their prices. So, we have some set of things \(X\) and a function \(f: X \to \mathbb{R}\) that assigns to each thing a price. Given two things in the set \(X\) we can then say which costs more... and this puts a preorder on the set \(X\). Here's the math behind this:

Puzzle 75. Suppose \( (Y, \le_Y) \) is a preorder, \(X\) is a set and \(f : X \to Y\) is any function. Define a relation \(\le_X\) on \(X\) by

$$ x \le_X x' \textrm{ if and only if } f(x) \le_Y f(x') .$$ Show that \( (X, \le_X ) \) is a preorder.

Sometimes this trick gives a poset, sometimes not:

Puzzle 76. Now suppose \( (Y, \le_Y) \) is a poset. Under what conditions on \(f\) can we conclude that \( (X, \le_X ) \) defined as above is a poset?

We often have a way of combining things: for example, at a store, if you can buy milk and you can buy eggs, you can buy milk and eggs. Sometimes this makes our set of things into a monoidal preorder:

Puzzle 77. Now suppose that \( (Y, \le_Y, \otimes_Y, 1_Y) \) is a monoidal preorder, and \( (X,\otimes_X,1_X ) \) is a monoid. Define \(\le_X\) as above. Under what conditions on \(f\) can we conclude that \( (X,\le_X\otimes_X,1_X) \) is a monoidal preorder?

We will come back to these issues in a bit more depth when we discuss Section 2.2.5 of the book.

To read other lectures go here.

Comments

  • 1.

    Maybe with the lack of a lecture today, people will post in the discussion groups. Maybe I'm being too optimistic.

    Anyway, Puzzle 75 feels very weird, since \( X \) could be a completely disjoint set.

    Comment Source:Maybe with the lack of a lecture today, people will post in the discussion groups. Maybe I'm being too optimistic. Anyway, Puzzle 75 feels very weird, since \\( X \\) could be a completely disjoint set.
  • 2.
    edited May 15

    Puzzle 75 is about things like this "a dozen eggs costs more than a stick of butter". We have a set \(\mathbb{R}\) whose elements are amounts of money, ordered in the usual way. We have a set \(X\) whose elements are things you can buy in the grocery store. And we have a function \(f: X \to \mathbb{R}\) mapping each thing you can buy in the grocery store to its price. Say

    $$ f(\text{a dozen eggs}) = 3.50 $$ and

    $$ f(\text{a stick of butter}) = 0.75 $$ Then we say

    $$ \text{a stick of butter} \le_X \text{a dozen eggs} $$ because

    $$ 0.75 \le_{\mathbb{R}} 3.50 .$$ This is just a way of saying that a stick of butter is cheaper than a dozen eggs. It makes perfect sense. Please, someone do these puzzles!

    By the way, Brandon passed his thesis defense, and all my students are happy. =D> =D> =D> =D> =D> =D>

    Comment Source:Puzzle 75 is about things like this "a dozen eggs costs more than a stick of butter". We have a set \\(\mathbb{R}\\) whose elements are _amounts of money_, ordered in the usual way. We have a set \\(X\\) whose elements are _things you can buy in the grocery store_. And we have a function \\(f: X \to \mathbb{R}\\) mapping each thing you can buy in the grocery store to its price. Say \[ f(\text{a dozen eggs}) = 3.50 \] and \[ f(\text{a stick of butter}) = 0.75 \] Then we say \[ \text{a stick of butter} \le_X \text{a dozen eggs} \] because \[ 0.75 \le_{\mathbb{R}} 3.50 .\] This is just a way of saying that a stick of butter is cheaper than a dozen eggs. It makes perfect sense. Please, someone do these puzzles! By the way, Brandon passed his thesis defense, and all my students are happy. =D> =D> =D> =D> =D> =D>
  • 3.

    Your commodity pricing example gives me a hunch, can I prove Puzzle 75 by pullback? That is to say, pullback the \( \le_Y \) along \( f \) to induce a relationship \( \le_X \) on the set \( X \).

    Comment Source:Your commodity pricing example gives me a hunch, can I prove Puzzle 75 by pullback? That is to say, pullback the \\( \le_Y \\) along \\( f \\) to induce a relationship \\( \le_X \\) on the set \\( X \\).
  • 4.
    edited May 16

    Marius worked on these these Puzzles in Lecture 23. Here is his comment. I thought I would copy them here so we can all talk in one place!

    Puzzle 75.

    Suppose \( (Y, \le_Y) \) is a preorder, \(X\) is a set and \(f : X \to Y\) is any function. Define a relation \(\le_X\) on \(X\) by

    $$ x \le_X x' \textrm{ if and only if } f(x) \le_Y f(x') .$$ Show that \( (X, \le_X ) \) is a preorder.

    Our relation turns \( f \) into a monotone map. For all \( x \in X \) we have \( f(x) \le_Y f(x)\) and thus \( x \le_X x\) satisfying reflexivity. Similarly, for all \( x,y,z \in X \), \( f(x) \le_Y f(y)\) and \( f(y) \le_Y f(z)\) implies \( f(x) \le_Y f(z)\) and thus \( x \le_X y\) and \( y \le_X z\) implies \( x \le_X z\) satisfying transitivity. This gives us a preorder on X.

    Puzzle 76.

    Now suppose \( (Y, \le_Y) \) is a poset. Under what conditions on \(f\) can we conclude that \( (X, \le_X ) \) defined as above is a poset?

    Since we don't want to induce any equivalent elements in \(X\), \( f \) must be injective.

    Puzzle 77.

    Now suppose that \( (Y, \le_Y, \otimes_Y, 1_Y) \) is a monoidal preorder, and \( (X,\otimes_X,1_X ) \) is a monoid. Define \(\le_X\) as above. Under what conditions on \(f\) can we conclude that \( (X,\le_X\otimes_X,1_X) \) is a monoidal preorder?

    We need to assure that our induced preorder structure is compatible with our monoidal structure. To this end we require our monotone map \( f \) to be a monoidal monotone for which \( 1_Y \le_Y f(1_X) \) and \( f(x) \otimes_Y f(y) \le_Y f(x \otimes_X y) \)

    Regarding Puzzle 71, does this mean we simply need to find injective monoidal monotones to other commutative monoidal posets (e.g \( (\mathbb{R}, \le, +, 0 )\)) or do we need stricter requirements to preserve the commutative sturcture (e.g \( 1_Y = f(1_X) \) and \( f(x) \otimes_Y f(y) = f(x \otimes_X y) \))?

    I'm off to bed, so maybe someone else can continue my thought process...

    Comment Source:Marius worked on these these Puzzles in Lecture 23. <a href = "https://forum.azimuthproject.org/discussion/comment/18135/#Comment_18135× ">Here is his comment.</a> I thought I would copy them here so we can all talk in one place! >**Puzzle 75.** >>Suppose \\( (Y, \le_Y) \\) is a preorder, \\(X\\) is a set and \\(f : X \to Y\\) is any function. Define a relation \\(\le_X\\) on \\(X\\) by >>\[ x \le_X x' \textrm{ if and only if } f(x) \le_Y f(x') .\] >>Show that \\( (X, \le_X ) \\) is a preorder. >Our relation turns \\( f \\) into a *monotone map*. For all \\( x \in X \\) we have \\( f(x) \le_Y f(x)\\) and thus \\( x \le_X x\\) satisfying reflexivity. Similarly, for all \\( x,y,z \in X \\), \\( f(x) \le_Y f(y)\\) and \\( f(y) \le_Y f(z)\\) implies \\( f(x) \le_Y f(z)\\) and thus \\( x \le_X y\\) and \\( y \le_X z\\) implies \\( x \le_X z\\) satisfying transitivity. This gives us a preorder on X. >**Puzzle 76.** >>Now suppose \\( (Y, \le_Y) \\) is a poset. Under what conditions on \\(f\\) can we conclude that \\( (X, \le_X ) \\) defined as above is a poset? >Since we don't want to induce any equivalent elements in \\(X\\), \\( f \\) must be injective. >**Puzzle 77.** >>Now suppose that \\( (Y, \le_Y, \otimes_Y, 1_Y) \\) is a monoidal preorder, and \\( (X,\otimes_X,1_X ) \\) is a monoid. Define \\(\le_X\\) as above. Under what conditions on \\(f\\) can we conclude that \\( (X,\le_X\otimes_X,1_X) \\) is a monoidal preorder? >We need to assure that our induced preorder structure is compatible with our monoidal structure. To this end we require our *monotone map* \\( f \\) to be a *monoidal monotone* for which \\( 1_Y \le_Y f(1_X) \\) and \\( f(x) \otimes_Y f(y) \le_Y f(x \otimes_X y) \\) >Regarding Puzzle 71, does this mean we simply need to find injective *monoidal monotones* to other commutative monoidal posets (e.g \\( (\mathbb{R}, \le, +, 0 )\\)) or do we need stricter requirements to preserve the commutative sturcture (e.g \\( 1_Y = f(1_X) \\) and \\( f(x) \otimes_Y f(y) = f(x \otimes_X y) \\))? > I'm off to bed, so maybe someone else can continue my thought process...
  • 5.

    Puzzle 76. I agree with Marius that \(f\) must be injective. In fact I think this is a necessary and sufficient condition! But before the proof, a small example.

    In John's example where \(X\) is a set of groceries and \(f\) maps groceries to their cost, $$\text{grocery 1} \leq \text{grocery 2}$$ iff the cost of grocery 1 is less than or equal to the cost of grocery 2. If \(f\) is not injective then there exist two different groceries (let's say apples and oranges) with the same cost (let's say $1). Since in the world of cost $1 \(\leq\) $1 by reflexivity, in the world of groceries we have apples \(\leq\) oranges and oranges \(\leq \) apples. This means that apples and oranges are equivalent (which makes sense because they are equivalent in terms of cost). But of course apples \(\neq \) oranges. So the groceries with the relation induced by \(f\) does not form a poset!

    This argument works in general to show that if \(f\) induces a poset relation \( (X, \leq_X) \), then \(f\) is injective.

    Proof by contradiction: Suppose that \(f\) is not injective. Then there exists \(x,x' \in X\) such that \(f(x) = f(x')\) where \(x \neq x'\). By reflexivity \[ f(x) \leq_Y f(x') \text{ and } f(x') \leq_Y f(x).\] By definition of \( \leq_X \), this means that $$x \leq_X x' \text{ and } x' \leq_X x.$$ Since \( x \neq x' \), this means that \( (X, \leq_X) \) is not a poset.

    The converse is also true: If \(f\) is injective, then it induces a poset relation \( (X, \leq_X) \).

    Proof: Suppose that $$x \leq_X x' \text{ and } x' \leq_X x.$$ Then by the definition of \(\leq_X\) \[f(x) \leq_Y f(x') \text{ and } f(x') \leq_Y f(x).\] Since \( (Y, \leq_Y) \) is a poset, this implies that \(f(x) = f(x')\). And since \(f\) is injective, this means that \(x = x'\).

    Comment Source:**Puzzle 76.** I agree with Marius that \\(f\\) must be injective. In fact I think this is a necessary and sufficient condition! But before the proof, a small example. In John's example where \\(X\\) is a set of groceries and \\(f\\) maps groceries to their cost, $$\text{grocery 1} \leq \text{grocery 2}$$ iff the cost of grocery 1 is less than or equal to the cost of grocery 2. If \\(f\\) is not injective then there exist two different groceries (let's say apples and oranges) with the same cost (let's say \$1). Since in the world of cost \$1 \\(\leq\\) \$1 by reflexivity, in the world of groceries we have apples \\(\leq\\) oranges and oranges \\(\leq \\) apples. This means that apples and oranges are equivalent (which makes sense because they are equivalent in terms of cost). But of course apples \\(\neq \\) oranges. So the groceries with the relation induced by \\(f\\) does not form a poset! This argument works in general to show that if \\(f\\) induces a poset relation \\( (X, \leq_X) \\), then \\(f\\) is injective. *Proof by contradiction:* Suppose that \\(f\\) is not injective. Then there exists \\(x,x' \in X\\) such that \\(f(x) = f(x')\\) where \\(x \neq x'\\). By reflexivity \\[ f(x) \leq_Y f(x') \text{ and } f(x') \leq_Y f(x).\\] By definition of \\( \leq_X \\), this means that $$x \leq_X x' \text{ and } x' \leq_X x.$$ Since \\( x \neq x' \\), this means that \\( (X, \leq_X) \\) is not a poset. The converse is also true: If \\(f\\) is injective, then it induces a poset relation \\( (X, \leq_X) \\). *Proof:* Suppose that $$x \leq_X x' \text{ and } x' \leq_X x.$$ Then by the definition of \\(\leq_X\\) \\[f(x) \leq_Y f(x') \text{ and } f(x') \leq_Y f(x).\\] Since \\( (Y, \leq_Y) \\) is a poset, this implies that \\(f(x) = f(x')\\). And since \\(f\\) is injective, this means that \\(x = x'\\).
  • 6.
    edited May 16

    Puzzle 77

    Claim If \( f(x) \otimes_Y f(x') = f( x \otimes_X x')\) then the relation \(\leq_X\) induced by \(f\) makes \( (X, \otimes_X, 1_X, \leq_X) \) a monoidal preorder.

    (In the second example below I show that this is actually too strong of a condition on \(f\) but it's a starting place! )

    Proof: Suppose that \(x \leq_X x'\) and \(y \leq_X y' \). Then \(f(x) \leq_Y f(x')\) and \(f(y) \leq_Y f(y' )\). Since \((Y, \otimes_Y, 1_Y, \leq_Y)\) is a monoidal preorder this means that \[f(x) \otimes_Y f(y) \leq_Y f(x') \otimes_Y f(y'). \] \(f\) exactly preserves the tensor structure so, \[f(x \otimes_X y) \leq_Y f(x' \otimes_X y') \] which implies that \(x \otimes_X y \leq_X x' \otimes_X y'\) by the definition of \( \leq_X\).

    Example I started thinking about some examples inspired by John's grocery example and the H20 example from Lecture 22 .

    Let \(X\) represent collections of groceries that can be bought at the "Eggs and Milk" store. Since the "Eggs and Milk" store only sells eggs and milk, every element of \(X\) can be represented by a pair \((a,b) \in \mathbb N^2\) where \(a\) is the number of eggs bought and \(b\) is the number of milks bought. \(X\) can be turned into a monoid by defining \[(a,b) \otimes_X (c,d) = (a + c, b + d) \] and where \(1_X = (0,0) \). Suppose that eggs cost $1 and milk costs $2. This means we should define a cost map \(f: X \to \mathbb R\) by (f ((a,b)) = a + 2b\). \(f\) preserves the \(\otimes\) structure because \[f((a,b)) \otimes_{\mathbb R} f((c,d)) = (a + 2b) + (c + 2d) = (a + c) + 2(b + d) = f((a+c, b + d)) = f((a,b) \otimes_X (c,d)).\] Another way of saying this is "The cost of buying two sets of groceries separately is the same as the cost of buying them together". This means that we have turned the groceries into a monoidal preorder!

    Example

    Suppose that the "Eggs and Milk" store now charges $0.10 for a bag with each purchase. This means that the cost function now looks like \[g((a,b)) = a + 2b + 0.10\] \(g\) doesn't exactly preserve the \(\otimes\) structure because now the bag charge means that: "the cost of buying two sets of groceries separately is more than the cost of buying them together". In math words, \[g((a,b)) \otimes g((c,d)) \geq g((a \otimes c, b \otimes d)) .\] I was interested that this is the opposite condition from what Marius proposed.

    My next question was whether \(g\) induced a monoidal preorder on the groceries anyway. It does, essentially because the bag charges cancel out. Here is the math: Suppose that \[(a,b) \leq (c,d) \text{ and }(a',b') \leq (c',d')\] Therefore \[g(a,b) \leq g(c,d) \text{ and }g(a',b') \leq g(c',d')\] \[ \implies a+ 2b + 0.10 \leq c + 2d + 0.10 \text{ and }a' + 2b' + 0.10 \leq c' + 2d' + 0.10\] \[ \implies a+ 2b \leq c + 2d \text{ and }a' + 2b' \leq c' + 2d'\] \[ \implies (a + a') + 2(b + b') \leq (c + c') + 2(d + d') \] \[ \implies (a + a') + 2(b + b') + 0.10 \leq (c + c') + 2(d + d') + 0.10 \] \[ \implies g((a,b) \otimes (a', b')) \leq g((c,d) \otimes (c',d')) \] \[ \implies (a,b) \otimes (a', b') \leq (c,d) \otimes (c',d') \]

    This lead me to a new claim...

    New Claim If \( f(x) \otimes_Y f(x') \geq f( x \otimes_X x')\) then the relation \(\leq_X\) induced by \(f\) makes \( (X, \otimes_X, 1_X, \leq_X) \) a monoidal preorder.

    But I have yet to prove it! I'm also wondering about Marius's suggestion that \( f\) should satisfy

    \(1_Y\leq_Y f(1_X)\)

    This is true in both my examples, since buying zero items costs more than or equal to $0.

    Phew that was a lot! Interested to hear what others think!

    Comment Source:**Puzzle 77** **Claim** If \\( f(x) \otimes_Y f(x') = f( x \otimes_X x')\\) then the relation \\(\leq_X\\) induced by \\(f\\) makes \\( (X, \otimes_X, 1_X, \leq_X) \\) a monoidal preorder. (In the second example below I show that this is actually too strong of a condition on \\(f\\) but it's a starting place! ) *Proof:* Suppose that \\(x \leq_X x'\\) and \\(y \leq_X y' \\). Then \\(f(x) \leq_Y f(x')\\) and \\(f(y) \leq_Y f(y' )\\). Since \\((Y, \otimes_Y, 1_Y, \leq_Y)\\) is a monoidal preorder this means that \\[f(x) \otimes_Y f(y) \leq_Y f(x') \otimes_Y f(y'). \\] \\(f\\) exactly preserves the tensor structure so, \\[f(x \otimes_X y) \leq_Y f(x' \otimes_X y') \\] which implies that \\(x \otimes_X y \leq_X x' \otimes_X y'\\) by the definition of \\( \leq_X\\). **Example** I started thinking about some examples inspired by John's grocery example and the H20 example from <a href = "https://forum.azimuthproject.org/discussion/2084/lecture-22-chapter-2-symmetric-monoidal-preorders#latest"> Lecture 22 </a>. Let \\(X\\) represent collections of groceries that can be bought at the "Eggs and Milk" store. Since the "Eggs and Milk" store only sells eggs and milk, every element of \\(X\\) can be represented by a pair \\((a,b) \in \mathbb N^2\\) where \\(a\\) is the number of eggs bought and \\(b\\) is the number of milks bought. \\(X\\) can be turned into a monoid by defining \\[(a,b) \otimes_X (c,d) = (a + c, b + d) \\] and where \\(1_X = (0,0) \\). Suppose that eggs cost \$1 and milk costs \$2. This means we should define a cost map \\(f: X \to \mathbb R\\) by \(f ((a,b)) = a + 2b\\). \\(f\\) preserves the \\(\otimes\\) structure because \\[f((a,b)) \otimes_{\mathbb R} f((c,d)) = (a + 2b) + (c + 2d) = (a + c) + 2(b + d) = f((a+c, b + d)) = f((a,b) \otimes_X (c,d)).\\] Another way of saying this is "The cost of buying two sets of groceries separately is the same as the cost of buying them together". This means that we have turned the groceries into a monoidal preorder! **Example** Suppose that the "Eggs and Milk" store now charges \$0.10 for a bag with each purchase. This means that the cost function now looks like \\[g((a,b)) = a + 2b + 0.10\\] \\(g\\) doesn't exactly preserve the \\(\otimes\\) structure because now the bag charge means that: "the cost of buying two sets of groceries separately is *more* than the cost of buying them together". In math words, \\[g((a,b)) \otimes g((c,d)) \geq g((a \otimes c, b \otimes d)) .\\] I was interested that this is the opposite condition from what Marius proposed. My next question was whether \\(g\\) induced a monoidal preorder on the groceries anyway. It does, essentially because the bag charges cancel out. Here is the math: Suppose that \\[(a,b) \leq (c,d) \text{ and }(a',b') \leq (c',d')\\] Therefore \\[g(a,b) \leq g(c,d) \text{ and }g(a',b') \leq g(c',d')\\] \\[ \implies a+ 2b + 0.10 \leq c + 2d + 0.10 \text{ and }a' + 2b' + 0.10 \leq c' + 2d' + 0.10\\] \\[ \implies a+ 2b \leq c + 2d \text{ and }a' + 2b' \leq c' + 2d'\\] \\[ \implies (a + a') + 2(b + b') \leq (c + c') + 2(d + d') \\] \\[ \implies (a + a') + 2(b + b') + 0.10 \leq (c + c') + 2(d + d') + 0.10 \\] \\[ \implies g((a,b) \otimes (a', b')) \leq g((c,d) \otimes (c',d')) \\] \\[ \implies (a,b) \otimes (a', b') \leq (c,d) \otimes (c',d') \\] This lead me to a new claim... **New Claim** If \\( f(x) \otimes_Y f(x') \geq f( x \otimes_X x')\\) then the relation \\(\leq_X\\) induced by \\(f\\) makes \\( (X, \otimes_X, 1_X, \leq_X) \\) a monoidal preorder. But I have yet to prove it! I'm also wondering about Marius's suggestion that \\( f\\) should satisfy > \\(1_Y\leq_Y f(1_X)\\) This is true in both my examples, since buying zero items costs more than or equal to \$0. Phew that was a lot! Interested to hear what others think!
  • 7.
    edited May 16

    Thanks Sophie for re-posting my comment in the right place and for your nice proof that \(f\) must be injective! Regarding:

    I was interested that this is the opposite condition from what Marius proposed.

    I just took the definition for a monoidal monotone from 7 sketches p.46 without thinking it through all that much. Given your example in comment 6, I see that in our interpretation of grocery shopping and resource theories your condition seems to make more sense. Batching processes usually results in lower costs and/or more products. My condition could also be the case in grocery shopping, however.

    Example Consider that you have a bunch of coupons for the grocery store giving you a flat 0.50$ discount. However, you may only use one coupon per visit to the store. This means that "the cost of buying two sets of groceries separately is less than the cost of buying them together".

    I think we need to also reverse the inequality in the second condition if we stick to your condition. It might be instructive to consider monoidal monotone maps between monoidal preorders with different units to think about this. For example \(f: (\mathbb{N},\le, +, 0) \hookrightarrow (\mathbb{N},\le, *, 1) \) or \(g: (\mathbb{N},\le, *, 1) \hookrightarrow (\mathbb{N},\le, +, 0) \), where \(f \) and \(g \) are the inclusions.

    For \(f\) it is the case that \( f(x) \otimes_Y f(y) \ge_Y f(x \otimes_X y) \) and \( 1_Y \ge_Y f(1_X)\). For \(g\) it is the case that \( g(x) \otimes_Y g(y) \le_Y g(x \otimes_X y) \) and \( 1_Y \le_Y g(1_X)\).

    So based on this one example it seems that either condition works as long as one is consistent. This means that for \( 1_Y = f(1_X)\) we could use either inequality.

    Edit: Just realized we probably only need one version of the conditions since we can formally take the function to the opposite preorder to get the other.

    Comment Source:Thanks Sophie for re-posting my comment in the right place and for your nice proof that \\(f\\) must be injective! Regarding: > I was interested that this is the opposite condition from what Marius proposed. I just took the definition for a monoidal monotone from 7 sketches p.46 without thinking it through all that much. Given your example in comment 6, I see that in our interpretation of grocery shopping and resource theories your condition seems to make more sense. Batching processes usually results in lower costs and/or more products. My condition could also be the case in grocery shopping, however. **Example** Consider that you have a bunch of coupons for the grocery store giving you a flat 0.50$ discount. However, you may only use one coupon per visit to the store. This means that "the cost of buying two sets of groceries separately is *less* than the cost of buying them together". I think we need to also reverse the inequality in the second condition if we stick to your condition. It might be instructive to consider monoidal monotone maps between monoidal preorders with different units to think about this. For example \\(f: (\mathbb{N},\le, +, 0) \hookrightarrow (\mathbb{N},\le, *, 1) \\) or \\(g: (\mathbb{N},\le, *, 1) \hookrightarrow (\mathbb{N},\le, +, 0) \\), where \\(f \\) and \\(g \\) are the inclusions. For \\(f\\) it is the case that \\( f(x) \otimes_Y f(y) \ge_Y f(x \otimes_X y) \\) and \\( 1_Y \ge_Y f(1_X)\\). For \\(g\\) it is the case that \\( g(x) \otimes_Y g(y) \le_Y g(x \otimes_X y) \\) and \\( 1_Y \le_Y g(1_X)\\). So based on this one example it seems that either condition works as long as one is consistent. This means that for \\( 1_Y = f(1_X)\\) we could use either inequality. *Edit:* Just realized we probably only need one version of the conditions since we can formally take the function to the opposite preorder to get the other.
  • 8.

    @Marius, Sophie: that's very interesting!

    It may be worth pointing out that your result

    Claim If \( f(x) \otimes_Y f(x') = f( x \otimes_X x')\) then the relation \(\leq_X\) induced by \(f\) makes \( (X, \otimes_X, 1_X, \leq_X) \) a monoidal preorder.

    generalizes Matthew's proposed solution to Puzzle 71, which turns the complex numbers into a commutative monoidal preorder. Do you see how?

    Comment Source:@Marius, Sophie: that's very interesting! It may be worth pointing out that your result > **Claim** If \\( f(x) \otimes_Y f(x') = f( x \otimes_X x')\\) then the relation \\(\leq_X\\) induced by \\(f\\) makes \\( (X, \otimes_X, 1_X, \leq_X) \\) a monoidal preorder. generalizes [Matthew's proposed solution to Puzzle 71](https://forum.azimuthproject.org/discussion/comment/18065/#Comment_18065×), which turns the complex numbers into a commutative monoidal preorder. Do you see how?
  • 9.
    edited May 16

    If you mean:

    $$x \preceq_p y \iff p \cdot x \leq p \cdot y$$

    then \(f(x) = p \cdot x \) and we see that \( f(x) \otimes_Y f(x') = p \cdot x + p \cdot x' = p \cdot (x+x') = f( x \otimes_Y x')\) since multiplication distributes over addition.

    Comment Source:If you mean: > $$x \preceq_p y \iff p \cdot x \leq p \cdot y$$ then \\(f(x) = p \cdot x \\) and we see that \\( f(x) \otimes_Y f(x') = p \cdot x + p \cdot x' = p \cdot (x+x') = f( x \otimes_Y x')\\) since multiplication distributes over addition.
  • 10.
    edited May 16

    Regarding this puzzle:

    Puzzle 76. Now suppose \( (Y, \le_Y) \) is a poset. Under what conditions on \(f\) can we conclude that \( (X, \le_X ) \) defined as above is a poset?

    Sophie wrote:

    Puzzle 76. I agree with Marius that \(f\) must be injective. In fact I think this is a necessary and sufficient condition!

    That's right! But you don't need me to tell you this, since you proved it, so you know it's right.

    (Of course sometimes we screw up when proving things, but writing down a proof and carefully checking the logic can reduce the chance of error quite dramatically.)

    Comment Source:Regarding this puzzle: > **Puzzle 76.** Now suppose \\( (Y, \le_Y) \\) is a poset. Under what conditions on \\(f\\) can we conclude that \\( (X, \le_X ) \\) defined as above is a poset? Sophie wrote: > **Puzzle 76**. I agree with Marius that \\(f\\) must be injective. In fact I think this is a necessary and sufficient condition! That's right! But you don't need me to tell you this, since you proved it, so you _know_ it's right. (Of course sometimes we screw up when proving things, but writing down a proof and carefully checking the logic can reduce the chance of error quite dramatically.)
  • 11.
    edited May 16

    And regarding this one:

    Puzzle 77. Now suppose that \( (Y, \le_Y, \otimes_Y, 1_Y) \) is a monoidal preorder, and \( (X,\otimes_X,1_X ) \) is a monoid. Define \(\le_X\) as above. Under what conditions on \(f\) can we conclude that \( (X,\le_X\otimes_X,1_X) \) is a monoidal preorder?

    Sophie wrote:

    Claim If \( f(x) \otimes_Y f(x') = f( x \otimes_X x')\) then the relation \(\leq_X\) induced by \(f\) makes \( (X, \otimes_X, 1_X, \leq_X) \) a monoidal preorder.

    Yes, that's right! So this is a sufficient condition, and this is the answer I had in mind.

    You suggest that a weaker condition may be enough:

    $$ f( x \otimes_X x') \le f(x) \otimes_Y f(x') \qquad \star $$ for all \(x,x' \in X\).

    Let's see. To prove \(\leq_X\) is a monoidal preorder, we need to prove

    $$ x_1 \le_X x_1' \textrm{ and } x_2 \le_X x_2' \textrm{ imply } x_1 \otimes_X x_2 \le_X x_1' \otimes_X x_2' $$ for all \(x_1,x_1',x_2,x_2' \in X\). In other words, we need

    $$ f(x_1) \le_Y f(x_1') \textrm{ and } f(x_2) \le_Y f(x_2') \textrm{ imply } f(x_1 \otimes_X x_2) \le_Y f(x_1' \otimes_X x_2') . $$ On the other hand, since \( (Y, \le_Y, \otimes_Y, 1_Y) \) is a monoidal preorder, we know that

    $$ f(x_1) \le_Y f(x_1') \textrm{ and } f(x_2) \le_Y f(x_2') \textrm{ imply } f(x_1)\otimes_Y f(x_2) \le_Y f(x_1') \otimes_Y f(x_2') . $$ If we assume condition \(\star\), we also know

    $$ f(x_1 \otimes_X x_2) \le_Y f(x_1)\otimes_Y f(x_2) . $$ Combining this with what we know, we get

    $$ f(x_1) \le_Y f(x_1') \textrm{ and } f(x_2) \le_Y f(x_2') \textrm{ imply } f(x_1 \otimes_X x_2) \le_Y f(x_1') \otimes_Y f(x_2') . $$ But this does not yet get us what we need! Remember, we need

    $$ f(x_1) \le_Y f(x_1') \textrm{ and } f(x_2) \le_Y f(x_2') \textrm{ imply } f(x_1 \otimes_X x_2) \le_Y f(x_1' \otimes_X x_2') . $$ The obvious way to get this is to also assume

    $$ f(x) \otimes_Y f(x') \le f(x \otimes_X x') \qquad \star\star $$ for all \(x,x' \in X\). But \(\star\) together with \(\star\star\) is just your earlier condition

    $$ f(x) \otimes_Y f(x') = f(x \otimes_X x') $$ I don't see how either \(\star\) or \(\star\star\) is enough for this problem. I don't think either one by itself will do the job.

    Comment Source:And regarding this one: > **Puzzle 77.** Now suppose that \\( (Y, \le_Y, \otimes_Y, 1_Y) \\) is a monoidal preorder, and \\( (X,\otimes_X,1_X ) \\) is a monoid. Define \\(\le_X\\) as above. Under what conditions on \\(f\\) can we conclude that \\( (X,\le_X\otimes_X,1_X) \\) is a monoidal preorder? Sophie wrote: > **Claim** If \\( f(x) \otimes_Y f(x') = f( x \otimes_X x')\\) then the relation \\(\leq_X\\) induced by \\(f\\) makes \\( (X, \otimes_X, 1_X, \leq_X) \\) a monoidal preorder. Yes, that's right! So this is a sufficient condition, and this is the answer I had in mind. You suggest that a weaker condition may be enough: \[ f( x \otimes_X x') \le f(x) \otimes_Y f(x') \qquad \star \] for all \\(x,x' \in X\\). Let's see. To prove \\(\leq_X\\) is a monoidal preorder, we need to prove \[ x_1 \le_X x_1' \textrm{ and } x_2 \le_X x_2' \textrm{ imply } x_1 \otimes_X x_2 \le_X x_1' \otimes_X x_2' \] for all \\(x_1,x_1',x_2,x_2' \in X\\). In other words, we need \[ f(x_1) \le_Y f(x_1') \textrm{ and } f(x_2) \le_Y f(x_2') \textrm{ imply } f(x_1 \otimes_X x_2) \le_Y f(x_1' \otimes_X x_2') . \] On the other hand, since \\( (Y, \le_Y, \otimes_Y, 1_Y) \\) is a monoidal preorder, we know that \[ f(x_1) \le_Y f(x_1') \textrm{ and } f(x_2) \le_Y f(x_2') \textrm{ imply } f(x_1)\otimes_Y f(x_2) \le_Y f(x_1') \otimes_Y f(x_2') . \] If we assume condition \\(\star\\), we also know \[ f(x_1 \otimes_X x_2) \le_Y f(x_1)\otimes_Y f(x_2) . \] Combining this with what we know, we get \[ f(x_1) \le_Y f(x_1') \textrm{ and } f(x_2) \le_Y f(x_2') \textrm{ imply } f(x_1 \otimes_X x_2) \le_Y f(x_1') \otimes_Y f(x_2') . \] But this does not yet get us what we need! Remember, we need \[ f(x_1) \le_Y f(x_1') \textrm{ and } f(x_2) \le_Y f(x_2') \textrm{ imply } f(x_1 \otimes_X x_2) \le_Y f(x_1' \otimes_X x_2') . \] The obvious way to get this is to also assume \[ f(x) \otimes_Y f(x') \le f(x \otimes_X x') \qquad \star\star \] for all \\(x,x' \in X\\). But \\(\star\\) together with \\(\star\star\\) is just your earlier condition \[ f(x) \otimes_Y f(x') = f(x \otimes_X x') \] I don't see how either \\(\star\\) or \\(\star\star\\) is enough for this problem. I don't think either one by itself will do the job.
  • 12.
    edited May 16

    Sophie wrote:

    I'm also wondering about Marius's suggestion that \( f\) should satisfy \(1_Y\leq_Y f(1_X)\)

    I don't think this condition plays any role in Puzzle 77. There's an interesting asymmetry in the definition of "monoidal preorder": the operation \(\otimes\) needs to get along with relation \(\le\), but the unit \(1\) does not.

    Later we will meet various kinds of maps between monoidal preorders: see Section 2.2.5. These should remind you of Puzzle 77, and they involve conditions on the unit. They are definitely relevant to your "pricing of groceries" examples... but nonetheless, I don't think any conditions on the unit are relevant to Puzzle 77.

    I could be wrong.

    Comment Source:Sophie wrote: > I'm also wondering about Marius's suggestion that \\( f\\) should satisfy > \\(1_Y\leq_Y f(1_X)\\) I don't think this condition plays any role in Puzzle 77. There's an interesting asymmetry in the definition of "monoidal preorder": the operation \\(\otimes\\) needs to get along with relation \\(\le\\), but the unit \\(1\\) does not. Later we will meet various kinds of _maps_ between monoidal preorders: see Section 2.2.5. These should remind you of Puzzle 77, and they involve conditions on the unit. They are definitely relevant to your "pricing of groceries" examples... but nonetheless, I don't think any conditions on the unit are relevant to Puzzle 77. I could be wrong.
  • 13.

    I've decided to make these puzzles into a mini-lecture, just because they fit pretty well into the overall flow of what we're doing: learning about monoidal preorder and their role in economics.

    Comment Source:I've decided to make these puzzles into a mini-lecture, just because they fit pretty well into the overall flow of what we're doing: learning about monoidal preorder and their role in economics.
  • 14.

    Thanks Marius, Tobias, and John for the responses! I had a lot of fun working on these problems.

    Marius, I really like the example of getting a discount instead of a bag charge! Your comment about opposite categories also made me think that given a function \(f: X \to Y\) we can define a relation on \(X\) in an opposite way by \[x \leq_X x' \iff f(x) \geq_Y f(x').\]

    I also wanted to check my thinking about Puzzle 77 again.

    I showed that the property \(f(x) \otimes_Y f(x') = f(x \otimes_X x') \) is sufficient for making \( (X, \leq_X, \otimes_X, 1_x) \) a monoidal pre-order. But the examples of a bag cost and coupon discount that Marius and I suggested, show that this is not a necessary condition, since in both of those cases we only have \(f(x) \otimes_Y f(x') \leq f(x \otimes_X x') \) and \(f(x) \otimes_Y f(x') \geq f(x \otimes_X x') \) respectively. So as of yet, we don't have a nice necessary and sufficient condition on \(f\) for making \( (X, \leq_X, \otimes_X, 1_x) \) a monoidal pre-order. Is that correct?

    Comment Source:Thanks Marius, Tobias, and John for the responses! I had a lot of fun working on these problems. Marius, I really like the example of getting a discount instead of a bag charge! Your comment about opposite categories also made me think that given a function \\(f: X \to Y\\) we can define a relation on \\(X\\) in an opposite way by \\[x \leq_X x' \iff f(x) \geq_Y f(x').\\] I also wanted to check my thinking about Puzzle 77 again. I showed that the property \\(f(x) \otimes_Y f(x') = f(x \otimes_X x') \\) is sufficient for making \\( (X, \leq_X, \otimes_X, 1_x) \\) a monoidal pre-order. But the examples of a bag cost and coupon discount that Marius and I suggested, show that this is not a necessary condition, since in both of those cases we only have \\(f(x) \otimes_Y f(x') \leq f(x \otimes_X x') \\) and \\(f(x) \otimes_Y f(x') \geq f(x \otimes_X x') \\) respectively. So as of yet, we don't have a nice necessary <b>and</b> sufficient condition on \\(f\\) for making \\( (X, \leq_X, \otimes_X, 1_x) \\) a monoidal pre-order. Is that correct?
  • 15.
    edited May 17

    Sophie: I haven't carefully checked those bag cost and coupon discount examples, so I can't promise that \(f(x) \otimes_Y f(x') = f(x \otimes_X x') \) is not necessary. But I'm willing to believe you.

    Re-examining what I wrote, it seems that a necessary and sufficient condition is

    $$ f(x_1)\otimes_Y f(x_2) \le_Y f(x_1') \otimes_Y f(x_2') \textrm{ implies } f(x_1 \otimes_X x_2) \le_Y f(x_1' \otimes_X x_2') .$$ It's late, so I'll have to check this when I'm more awake. Does this condition hold in your examples?

    Comment Source:Sophie: I haven't carefully checked those bag cost and coupon discount examples, so I can't promise that \\(f(x) \otimes_Y f(x') = f(x \otimes_X x') \\) is not necessary. But I'm willing to believe you. Re-examining what I wrote, it seems that a necessary and sufficient condition is \[ f(x_1)\otimes_Y f(x_2) \le_Y f(x_1') \otimes_Y f(x_2') \textrm{ implies } f(x_1 \otimes_X x_2) \le_Y f(x_1' \otimes_X x_2') .\] It's late, so I'll have to check this when I'm more awake. Does this condition hold in your examples?
  • 16.

    John: Yes your condition hold for both the bag cost and coupon examples. Also I can see how it slides right into the proof I gave in Comment 6. I wrote,

    \[f(x) \otimes_Y f(y) \leq_Y f(x') \otimes_Y f(y'). \] \(f\) exactly preserves the tensor structure so, \[f(x \otimes_X y) \leq_Y f(x' \otimes_X y') \]

    Just replace "\(f\) exactly preserves the tensor structure" with "by hypothesis"!

    Comment Source:John: Yes your condition hold for both the bag cost and coupon examples. Also I can see how it slides right into the proof I gave in Comment 6. I wrote, > \\[f(x) \otimes_Y f(y) \leq_Y f(x') \otimes_Y f(y'). \\] \\(f\\) exactly preserves the tensor structure so, \\[f(x \otimes_X y) \leq_Y f(x' \otimes_X y') \\] Just replace "\\(f\\) exactly preserves the tensor structure" with "by hypothesis"!
  • 17.

    Great, so this rather complicated condition is exactly the necessary and sufficient one!

    By the way, there's more about grocery store prices in Lecture 27. I hadn't realized until teaching this course how much category theory, or at least poset theory, is lurking in the humble corner grocery store.

    Comment Source:Great, so this rather complicated condition is exactly the necessary and sufficient one! By the way, there's more about grocery store prices in [Lecture 27](https://forum.azimuthproject.org/discussion/2098/lecture-27-chapter-2-adjoints-of-monoidal-monotones/p1). I hadn't realized until teaching this course how much category theory, or at least poset theory, is lurking in the humble corner grocery store.
  • 18.
    edited May 21

    You can also solve these sorts of problems with 'calculus of variations' so you have a a budget, some choices about how to allocate it if you are shopping, and a budget constraint . Usually written as a Lagrangian. The more complex cases basically involve tensor products. Category theory I think includes calculus of variations (or multiobjective optimization) as a special case. But it's a different more general dialect.

    Comment Source:You can also solve these sorts of problems with 'calculus of variations' so you have a a budget, some choices about how to allocate it if you are shopping, and a budget constraint . Usually written as a Lagrangian. The more complex cases basically involve tensor products. Category theory I think includes calculus of variations (or multiobjective optimization) as a special case. But it's a different more general dialect.
  • 19.
    edited June 22

    Is the condition: $$ f(x_1)\otimes_Y f(x_2) \le_Y f(x_1') \otimes_Y f(x_2') \textrm{ implies } f(x_1 \otimes_X x_2) \le_Y f(x_1' \otimes_X x_2') $$ really necessary? I'm having a hard time trying to prove it. What I mean in detail is: Assuming that \( (X,\le_X,\otimes_X,1_X) \) is a monoidal preorder, prove that the condition must hold.

    Comment Source:Is the condition: \[ f(x_1)\otimes_Y f(x_2) \le_Y f(x_1') \otimes_Y f(x_2') \textrm{ implies } f(x_1 \otimes_X x_2) \le_Y f(x_1' \otimes_X x_2') \] really necessary? I'm having a hard time trying to prove it. What I mean in detail is: Assuming that \\( (X,\le_X,\otimes_X,1_X) \\) is a monoidal preorder, prove that the condition must hold.
Sign In or Register to comment.