#### Howdy, Stranger!

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

Options

# Exercise 102 - Chapter 1

edited June 2018

Choose sets X and Y with between two and four elements each, and choose a function $$f: X \rightarrow Y$$.

1. Choose two different subsets $$B_1 , B_2 \subseteq Y$$ and find $$f^{−1}(B_1)$$ and $$f^{-1}(B_2)$$.
2. Choose two different subsets $$A_1 , A_2 \subseteq X$$ and find $$f_!( A_1 )$$ and $$f_! (A_2)$$.
3. With the same $$A_1 , A_2 \subseteq X$$, find $$f_* (A_1)$$ and $$f_* (A_2 )$$.

Example 1.101.

Let $$f : X \rightarrow Y$$ be a function between sets. We can imagine X as a set of balls, $$Y$$ as a set of buckets, and $$f$$ as putting each ball in a bucket. Then we have the monotone map $$f^*: \mathbb{P} Y \rightarrow \mathbb{P} X$$ that category theorists call “pullback along f ”. This map takes a subset $$B \subseteq Y$$ to its preimage $$f^{−1} B \subseteq X:$$ that is, it takes a collection $$B$$ of buckets, and tells you all the balls that lie in them. This operation is monotonic (more buckets means more balls) and it has both a left and a right adjoint. The left adjoint $$f_! (A)$$ is given by the direct image: it maps a subset $$A \subseteq X$$ to

$$f_{!} (A) := \{ y \in Y | \exists a \in A \text{ such that } f(a) = y \}$$ This map hence takes a set $$A$$ of balls, and tells you all the buckets that contain at least one of these balls. The right adjoint $$f_*$$ maps a subset $$A \subseteq X$$ to

$$f_* (A) := \{ y \in Y | \forall a \text{ such that } f(a) = y \text{ we have } a \in A \}$$

• Options
1.
edited April 2018

I tried 3 different examples and instead of just choosing 2 subsets as the exercise asked for, I solved it for every subset since 2 and 3 element power sets aren't too big to draw out.

I've been struggling with this all week and still can't seem to figure this one out. I think I am having a problem getting my head around the logical expressions in the definitions of $$f_!$$ and $$f_*$$. So instead I just used the definitions of left and right adjoints got the answers above. Not sure if this is correct but they preserve order and seem to obey all the definitions of an adjoint. But what doesn't make sense for me is the intuitive explanations of these functions given in by Spivak and Fong.

[Left Adjoint] hence takes a set A of balls, and tells you all the buckets that contain at least one of these balls.

[Right Adjoint] takes a set A of balls, and tells you all the buckets that only contain balls from A.

Seems to me these intuitive explanations should be the other way around. The left adjoint seems to tell you the bucket that contains only the balls in A and right adjoint seems to tell you the buckets that contain at least one of the balls in A. Tell you the truth they both sound like they are saying the same thing to me...

What am I doing wrong here?

Comment Source:I tried 3 different examples and instead of just choosing 2 subsets as the exercise asked for, I solved it for every subset since 2 and 3 element power sets aren't too big to draw out. ![2-3 Pullback ver1](http://aether.co.kr/wp-content/uploads/2-3-pullback-f1.jpg) ![2-3 Pullback ver2](http://aether.co.kr/wp-content/uploads/2-3-pullback-f2.jpg) ![3-2 Pullback](http://aether.co.kr/wp-content/uploads/3-2-pullback-f1.jpg) I've been struggling with this all week and still can't seem to figure this one out. I think I am having a problem getting my head around the logical expressions in the definitions of \$$f_!\$$ and \$$f_*\$$. So instead I just used the definitions of left and right adjoints got the answers above. Not sure if this is correct but they preserve order and seem to obey all the definitions of an adjoint. But what doesn't make sense for me is the intuitive explanations of these functions given in by Spivak and Fong. >[Left Adjoint] hence takes a set A of balls, and tells you all the buckets that contain at least one of these balls. >[Right Adjoint] takes a set A of balls, and tells you all the buckets that only contain balls from A. Seems to me these intuitive explanations should be the other way around. The left adjoint seems to tell you the bucket that contains only the balls in A and right adjoint seems to tell you the buckets that contain at least one of the balls in A. Tell you the truth they both sound like they are saying the same thing to me... What am I doing wrong here? 
• Options
2.

@MichaelHong : I am not sure whether this helps you, but I think the description of the right adjoint you cited is slightly incomplete (this is related to the confusion I had when we first defined $$f_{\ast}$$ ): $$f_{\ast}(A)$$ does not just give you "all the buckets that only contain balls from A", but also all the buckets that never get any ball from $$X$$.

The description of the left adjoint seems right to me - and it definitely does not say the same thing as the one for the right adjoint:

1) it includes buckets (i.e., points of $$Y$$ ) that receive balls from both $$A$$ and $$X-A$$ and which would thus be excluded from $$f_{\ast}(A)$$ (this bites only if $$f$$ is not injective);

2) conversely, according to my description, $$f_{\ast}(A)$$ includes buckets outside the range of $$f$$ which are instead excluded by $$f_{!}$$ (this bites only if $$f$$ is not surjective).

3) If $$f$$ is both injective and surjective, then the two adjoints coincide with the inverse $$f^{-1}$$ of $$f$$.

Comment Source:@MichaelHong : I am not sure whether this helps you, but I think the description of the right adjoint you cited is slightly incomplete (this is related to the confusion I had when we first defined \$$f_{\ast}\$$ ): \$$f_{\ast}(A)\$$ does not just give you "all the buckets that only contain balls from A", but also all the buckets that never get any ball from \$$X\$$. The description of the left adjoint seems right to me - and it definitely does not say the same thing as the one for the right adjoint: 1) it includes buckets (i.e., points of \$$Y\$$ ) that receive balls from both \$$A\$$ and \$$X-A\$$ and which would thus be excluded from \$$f_{\ast}(A)\$$ (this bites only if \$$f\$$ is not injective); 2) conversely, according to my description, \$$f_{\ast}(A)\$$ includes buckets outside the range of \$$f\$$ which are instead excluded by \$$f_{!}\$$ (this bites only if \$$f\$$ is not surjective). 3) If \$$f\$$ is both injective and surjective, then the two adjoints coincide with the inverse \$$f^{-1}\$$ of \$$f\$$.
• Options
3.

@MichaelHong: What do you use to draw your diagrams? They're staggeringly beautiful.

Comment Source:@MichaelHong: What do you use to draw your diagrams? They're staggeringly beautiful.
• Options
4.
edited April 2018

Valter wrote:

$$f_*(A)$$ does not just give you "all the buckets that only contain balls from A", but also all the buckets that never get any ball from $$X$$.

This is a nice example of how ordinary language treats "all" in a different way than mathematics. Suppose I'm unmarried and I say "all my wives are millionaires". Is this true?

A mathematician would say yes, it's true. It's "vacuously true". In mathematics, "All my wives are millionaires" is equivalent to "I have no wife that is not a millionaire". Go through my wives and check this. Yes it's true, because there are no wives to check!

$$f_*(A)$$ gives you the buckets all of whose balls are from $$A$$. If a bucket has no balls in it, it's vacuously true that all the balls in this bucket are from $$A$$.

Comment Source:Valter wrote: > \$$f_*(A)\$$ does not just give you "all the buckets that only contain balls from A", but also all the buckets that never get any ball from \$$X\$$. This is a nice example of how ordinary language treats "all" in a different way than mathematics. Suppose I'm unmarried and I say "all my wives are millionaires". Is this true? A mathematician would say yes, it's true. It's "vacuously true". In mathematics, "All my wives are millionaires" is equivalent to "I have no wife that is not a millionaire". Go through my wives and check this. Yes it's true, because there are no wives to check! \$$f_*(A)\$$ gives you the buckets all of whose balls are from \$$A\$$. If a bucket has no balls in it, it's vacuously true that all the balls in this bucket are from \$$A\$$.
• Options
5.
edited April 2018

Michael Hong wrote:

The left adjoint seems to tell you the buckets that contains only the balls in A and right adjoint seems to tell you the buckets that contain at least one of the balls in A. Tell you the truth they both sound like they are saying the same thing to me...

The left adjoint $$f_{!} (A)$$ is the set of buckets such that some ball in that bucket comes from $$A$$.

The right adjoint $$f_{\ast}(A)$$ is the set of buckets such that all balls in that bucket come from $$A$$.

These are quite different. For example, suppose a bucket has two balls in it: one from $$A$$ and one not from $$A$$. Then this bucket is in $$f_{!}(A)$$ but not in $$f_{\ast}(A)$$. Some ball in that bucket is from $$A$$, but not all.

Or suppose a bucket has no balls in it. Then this bucket is in $$f_{\ast}(A)$$ but not in $$f_{!}(A)$$. All balls in that bucket are from $$A$$, but not some. If this seems surprising, read my previous comment. Since there are no balls in this bucket, it's vacuously true that all balls in this bucket come from $$A$$.

If you give me a specific example where you seem to be getting a different answer, we can talk about it. Your pictures are actually pictures of many choices of $$A$$ - too much to talk about.

Comment Source:Michael Hong wrote: > The left adjoint seems to tell you the buckets that contains only the balls in A and right adjoint seems to tell you the buckets that contain at least one of the balls in A. Tell you the truth they both sound like they are saying the same thing to me... The left adjoint \$$f_{!} (A) \$$ is the set of buckets such that _some_ ball in that bucket comes from \$$A\$$. The right adjoint \$$f_{\ast}(A) \$$ is the set of buckets such that _all_ balls in that bucket come from \$$A\$$. These are quite different. For example, suppose a bucket has two balls in it: one from \$$A\$$ and one not from \$$A\$$. Then this bucket is in \$$f_{!}(A)\$$ but not in \$$f_{\ast}(A)\$$. _Some_ ball in that bucket is from \$$A\$$, but not _all_. Or suppose a bucket has no balls in it. Then this bucket is in \$$f_{\ast}(A)\$$ but not in \$$f_{!}(A)\$$. _All_ balls in that bucket are from \$$A\$$, but not _some_. If this seems surprising, read my previous comment. Since there are no balls in this bucket, it's *vacuously* true that all balls in this bucket come from \$$A\$$. If you give me a specific example where you seem to be getting a different answer, we can talk about it. Your pictures are actually pictures of many choices of \$$A\$$ - too much to talk about. 
• Options
6.
edited April 2018

@Valter

$$f_{\ast}(A)$$ does not just give you "all the buckets that only contain balls from A", but also all the buckets that never get any ball from $$X$$.

Yes that's what I thought after I drew the diagrams! The word "all" was getting to me because by my mortal logic where all excludes the vacuous truth that John talks about in the comments below, this would lead to left and right adjoints being the same map for all of the examples above but it isn't.

Comment Source:@Valter >\$$f_{\ast}(A)\$$ does not just give you "all the buckets that only contain balls from A", but also all the buckets that never get any ball from \$$X\$$. Yes that's what I thought after I drew the diagrams! The word "all" was getting to me because by my mortal logic where all excludes the vacuous truth that John talks about in the comments below, this would lead to left and right adjoints being the same map for all of the examples above but it isn't. 
• Options
7.

@Daniel

Thank! I use Illustrator CS6 for my diagrams.

Comment Source:@Daniel Thank! I use Illustrator CS6 for my diagrams. 
• Options
8.
edited April 2018

@John

$$f_*(A)$$ gives you the buckets all of whose balls are from $$A$$. If a bucket has no balls in it, it's vacuously true that all the balls in this bucket are from $$A$$.

Thanks! This pretty much cleared up all confusion I was having for a week. Basically its like elementary school field day. Everyone ($$all$$) gets an award for participation!

These are quite different. For example, suppose a bucket has two balls in it: one from $$A$$ and one not from $$A$$. Then this bucket is in $$f_{*}(A)$$ but not in $$f_{!}(A)$$. _Some_ ball in that bucket is from $$A$$, but not _all_.

Or suppose a bucket has no balls in it. Then this bucket is in $$f_{!}(A)$$ but not in $$f_{\ast}(A)$$. All balls in that bucket are from $$A$$, but not some. If this seems surprising, read my previous comment. Since there are no balls in this bucket, it's vacuously true that all balls in this bucket come from $$A$$.

I think you switched $$f_!$$ and $$f_*$$ here?

Comment Source:@John >\$$f_*(A)\$$ gives you the buckets all of whose balls are from \$$A\$$. If a bucket has no balls in it, it's vacuously true that all the balls in this bucket are from \$$A\$$. Thanks! This pretty much cleared up all confusion I was having for a week. Basically its like elementary school field day. Everyone (\$$all\$$) gets an award for participation! >These are quite different. For example, suppose a bucket has two balls in it: one from \$$A\$$ and one not from \$$A\$$. Then this bucket is in \$$f_{*}(A)\$$ but not in \$$f_{!}(A)\$$. _Some_ ball in that bucket is from \$$A\$$, but not _all_. >Or suppose a bucket has no balls in it. Then this bucket is in \$$f_{!}(A)\$$ but not in \$$f_{\ast}(A)\$$. _All_ balls in that bucket are from \$$A\$$, but not _some_. If this seems surprising, read my previous comment. Since there are no balls in this bucket, it's *vacuously* true that all balls in this bucket come from \$$A\$$. I think you switched \$$f_!\$$ and \$$f_*\$$ here? 
• Options
9.
edited April 2018

Michael Hong wrote:

I think you switched $$f_!$$ and $$f_*$$ here?

Yes. I always get everything backwards.

I could say I was just testing you, but that would be a lie. I'll fix comment #5 so other people don't get confused.

Comment Source:Michael Hong wrote: > I think you switched \$$f_!\$$ and \$$f_*\$$ here? Yes. I always get everything backwards.<img src = "http://math.ucr.edu/home/baez/emoticons/sm_upset.gif"> I could say I was just testing you, but that would be a lie. I'll fix comment #5 so other people don't get confused.
• Options
10.
edited April 2018

By the way, Michael Hong, until quite recently a lot of logicians believed this axiom:

$$\forall x \, P(x) \implies \exists x \, P(x)$$ This says

If every $$x$$ has property $$P$$ then some $$x$$ has property $$P$$.

But we know realizes this axiom is bad because it fails in the cases where the set of $$x$$'s is empty! This is the tricky case that was confusing you. If I'm a bachelor, everyone who is my wife is a millionaire does not imply there exists a wife of mine who is a millionaire.

So, you're not the only one who was confused by this. It turns out that dropping the above axiom, which allows the empty set of $$x$$'s to work just as well as any other set, is crucial to making the rules of logic work smoothly.

Comment Source:By the way, Michael Hong, until quite recently a lot of logicians believed this axiom: $\forall x \, P(x) \implies \exists x \, P(x)$ This says <center> If every \$$x\$$ has property \$$P\$$ then some \$$x\$$ has property \$$P\$$. </center> But we know realizes this axiom is bad because it fails in the cases where the set of \$$x\$$'s is empty! This is the tricky case that was confusing you. If I'm a bachelor, _everyone who is my wife is a millionaire_ does not imply _there exists a wife of mine who is a millionaire_. So, you're not the only one who was confused by this. It turns out that dropping the above axiom, which allows the empty set of \$$x\$$'s to work just as well as any other set, is crucial to making the rules of logic work smoothly.
• Options
11.

@John

Ahh that makes sense. Its kind of like the discovery of zero but for logic. The empty set from A gets counted as a set just like zero gets counted like a number.

This is quite mind blowing because the consequences are freedom of imagination LOL. You can say anything about something that doesn't exist and it could be true but you can't say it exists just cause it could be true since it is just dreamt up.

Comment Source:@John Ahh that makes sense. Its kind of like the discovery of zero but for logic. The empty set from A gets counted as a set just like zero gets counted like a number. This is quite mind blowing because the consequences are freedom of imagination LOL. You can say anything about something that doesn't exist and it could be true but you can't say it exists just cause it could be true since it is just dreamt up. 
• Options
12.
edited April 2018

Michael wrote:

It's kind of like the discovery of zero but for logic.

Exactly! The analogy goes quite deep. I don't want to go to far into it right now, but the fact that "for all $$x \in S$$, $$P(x)$$ is true" is automatically true when $$S$$ is empty is analogous to the fact that the product of a collection of numbers is automatically equal to $$1$$ when that collection is empty. You may not have thought much about what happens when you multiply an empty collection of numbers, but you know examples, like

$$3^0 = 1$$ which means that if you multiply no 3's at all, you get 1.

Comment Source:Michael wrote: > It's kind of like the discovery of zero but for logic. Exactly! The analogy goes quite deep. I don't want to go to far into it right now, but the fact that "for all \$$x \in S\$$, \$$P(x)\$$ is true" is automatically true when \$$S\$$ is empty is analogous to the fact that the product of a collection of numbers is automatically equal to \$$1\$$ when that collection is empty. You may not have thought much about what happens when you multiply an empty collection of numbers, but you know examples, like $$3^0 = 1$$ which means that if you multiply no 3's at all, you get 1.
• Options
13.

@John

the product of a collection of numbers is automatically equal to 1 when that collection is empty.

I think we can all meditate on this infinitely LOL.

Comment Source:@John > the product of a collection of numbers is automatically equal to 1 when that collection is empty. I think we can all meditate on this infinitely LOL.