Is power set functor determined by its image on objects?On functors agreeing with the powerset functor on objects and not being isomorphic to itRel is a concrete category over Sets, but how to concretize that?Covariant Power set functorWhat are the group objects in the category of finite sets and bijections, and its functor category?Show that the graph $Gamma(f)$ of a function defines a functor from $mathbfSet$ to $mathbfRel$When is a functor uniquely determined by where it sends objects?Construction of Inverse Image FunctorOn functors agreeing with the powerset functor on objects and not being isomorphic to it
Are Generation Ships inherently implausible?
Did "2001: A Space Odyssey" make any reference to the names of companies, or show any evidence of the existence of advertisements?
Do insurance rates depend on credit scores?
Ball hits curve of same curvature
GVS similarity in cognate words other Germanic Languages
How to implement an integration filter on arrays?
Easiest way to modify LLC control?
Why is dwarfism considered an advantage for jobs in space?
Is there a material or method to allow "swimmable" coins?
Why is the processor instruction called "move", not "copy"?
Can any number of squares be a square?
Why choose the name "Morpheus" when it is the name of the Greek god of dreams
How many atoms in the hydrocarbon?
I wasted the 6 years of my life and I don't know what should I do and how will I survive?
Does the "stand your ground" law regarding shooting an intruder apply when the door of the dwelling was not locked?
What does exclamation mark mean before invoking a method in C# 8.0?
Is there any plausible in-between of Endotherms and Ectotherms?
Is it safe to drive from Prague to Salzburg during winter?
Did the Mueller report find that Trump committed any felonies?
Would italians refer to an American or foreign woman as Signora?
Film about the USA being run by fake videos of the president after his kidnapping
Integrate over a region
Turing award papers
Why does UNIX ed not have a prompt by default
Is power set functor determined by its image on objects?
On functors agreeing with the powerset functor on objects and not being isomorphic to itRel is a concrete category over Sets, but how to concretize that?Covariant Power set functorWhat are the group objects in the category of finite sets and bijections, and its functor category?Show that the graph $Gamma(f)$ of a function defines a functor from $mathbfSet$ to $mathbfRel$When is a functor uniquely determined by where it sends objects?Construction of Inverse Image FunctorOn functors agreeing with the powerset functor on objects and not being isomorphic to it
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty
margin-bottom:0;
.everyonelovesstackoverflowposition:absolute;height:1px;width:1px;opacity:0;top:0;left:0;pointer-events:none;
$begingroup$
Let $mathbfSet$ be a category of set, and $mathcalP:mathbfSet to mathbfSet$ be a power set functor defined as
$$
mathcalP(X) = 2^X = Usubseteq X
$$
and for any function $f:Xto Y$,
$$
mathcalP(f): mathcalP(X) to mathcalP(Y), quad mathcalP(f)(U) = f(U).
$$
It is not hard to show that this really defines a functor. My question is:
Let $mathcalF:mathbfSetto mathbfSet$ be a functor that satisfies $mathcalF(X) = mathcalP(X)$ for all set $X$. Does this imply that $mathcalF = mathcalP$? i.e. $mathcalF(f) =mathcalP(f)$ for all morphisms (functions) $f$?
I believe that this is true, but I have no idea about proof. This question is motivated from the functional programming, especially about list functor (in Haskell). This is the question that I posted on Haskell reddit. My strategy is that, if one can show that the above statement is true, then we can modify the proof to give an answer to the original question about list functor. Maybe one can try to show for the category of finite sets or countable sets.
category-theory programming functors
edited Sep 28 at 16:06
Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
asked Sep 28 at 7:06
Seewoo LeeSeewoo Lee
10.9k2 gold badges10 silver badges33 bronze badges
$endgroup$
add a comment
|
$begingroup$
Let $mathbfSet$ be a category of set, and $mathcalP:mathbfSet to mathbfSet$ be a power set functor defined as
$$
mathcalP(X) = 2^X = Usubseteq X
$$
and for any function $f:Xto Y$,
$$
mathcalP(f): mathcalP(X) to mathcalP(Y), quad mathcalP(f)(U) = f(U).
$$
It is not hard to show that this really defines a functor. My question is:
Let $mathcalF:mathbfSetto mathbfSet$ be a functor that satisfies $mathcalF(X) = mathcalP(X)$ for all set $X$. Does this imply that $mathcalF = mathcalP$? i.e. $mathcalF(f) =mathcalP(f)$ for all morphisms (functions) $f$?
I believe that this is true, but I have no idea about proof. This question is motivated from the functional programming, especially about list functor (in Haskell). This is the question that I posted on Haskell reddit. My strategy is that, if one can show that the above statement is true, then we can modify the proof to give an answer to the original question about list functor. Maybe one can try to show for the category of finite sets or countable sets.
category-theory programming functors
edited Sep 28 at 16:06
Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
asked Sep 28 at 7:06
Seewoo LeeSeewoo Lee
10.9k2 gold badges10 silver badges33 bronze badges
$endgroup$
1
$begingroup$
@QiaochuYuan Isn't it fail to satisfy $mathcalF(mathrmid_X) = mathrmid_mathcalF(X)$?
$endgroup$
– Seewoo Lee
Sep 28 at 7:17
$begingroup$
Oh, yes, you’re right.
$endgroup$
– Qiaochu Yuan
Sep 28 at 7:18
$begingroup$
For finite sets there is a counterexample not yet mentioned: let $f:Xrightarrow Y$ be a function; define $Ff:P(X) rightarrow P(Y)$ by $Ff(U) = text is odd$ - which basically arises from treating these powersets as groups under the symmetric difference. I don't think this can be extended to infinite sets, however.
$endgroup$
– Milo Brandt
Sep 28 at 22:34
$begingroup$
I made a separate post for my follow-up question on non-naturally-isomorphic functors: math.stackexchange.com/q/3374031/85341.
$endgroup$
– ComFreek
Sep 29 at 8:10
$begingroup$
@MiloBrandt Does your functor fulfill $Fid_X = id_FX$, though? If I am not mistaken, we have $Fid_X = X!$ (constant full subset $X$).
$endgroup$
– ComFreek
Sep 29 at 8:32
add a comment
|
$begingroup$
Let $mathbfSet$ be a category of set, and $mathcalP:mathbfSet to mathbfSet$ be a power set functor defined as
$$
mathcalP(X) = 2^X = Usubseteq X
$$
and for any function $f:Xto Y$,
$$
mathcalP(f): mathcalP(X) to mathcalP(Y), quad mathcalP(f)(U) = f(U).
$$
It is not hard to show that this really defines a functor. My question is:
Let $mathcalF:mathbfSetto mathbfSet$ be a functor that satisfies $mathcalF(X) = mathcalP(X)$ for all set $X$. Does this imply that $mathcalF = mathcalP$? i.e. $mathcalF(f) =mathcalP(f)$ for all morphisms (functions) $f$?
I believe that this is true, but I have no idea about proof. This question is motivated from the functional programming, especially about list functor (in Haskell). This is the question that I posted on Haskell reddit. My strategy is that, if one can show that the above statement is true, then we can modify the proof to give an answer to the original question about list functor. Maybe one can try to show for the category of finite sets or countable sets.
category-theory programming functors
edited Sep 28 at 16:06
Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
asked Sep 28 at 7:06
Seewoo LeeSeewoo Lee
10.9k2 gold badges10 silver badges33 bronze badges
$endgroup$
Let $mathbfSet$ be a category of set, and $mathcalP:mathbfSet to mathbfSet$ be a power set functor defined as
$$
mathcalP(X) = 2^X = Usubseteq X
$$
and for any function $f:Xto Y$,
$$
mathcalP(f): mathcalP(X) to mathcalP(Y), quad mathcalP(f)(U) = f(U).
$$
It is not hard to show that this really defines a functor. My question is:
Let $mathcalF:mathbfSetto mathbfSet$ be a functor that satisfies $mathcalF(X) = mathcalP(X)$ for all set $X$. Does this imply that $mathcalF = mathcalP$? i.e. $mathcalF(f) =mathcalP(f)$ for all morphisms (functions) $f$?
I believe that this is true, but I have no idea about proof. This question is motivated from the functional programming, especially about list functor (in Haskell). This is the question that I posted on Haskell reddit. My strategy is that, if one can show that the above statement is true, then we can modify the proof to give an answer to the original question about list functor. Maybe one can try to show for the category of finite sets or countable sets.
category-theory programming functors
category-theory programming functors
edited Sep 28 at 16:06
Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
asked Sep 28 at 7:06
Seewoo LeeSeewoo Lee
10.9k2 gold badges10 silver badges33 bronze badges
edited Sep 28 at 16:06
Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
asked Sep 28 at 7:06
Seewoo LeeSeewoo Lee
10.9k2 gold badges10 silver badges33 bronze badges
edited Sep 28 at 16:06
Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
edited Sep 28 at 16:06
Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
edited Sep 28 at 16:06
Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
18k5 gold badges26 silver badges46 bronze badges
asked Sep 28 at 7:06
Seewoo LeeSeewoo Lee
10.9k2 gold badges10 silver badges33 bronze badges
asked Sep 28 at 7:06
Seewoo LeeSeewoo Lee
10.9k2 gold badges10 silver badges33 bronze badges
asked Sep 28 at 7:06
Seewoo LeeSeewoo Lee
10.9k2 gold badges10 silver badges33 bronze badges
10.9k2 gold badges10 silver badges33 bronze badges
1
$begingroup$
@QiaochuYuan Isn't it fail to satisfy $mathcalF(mathrmid_X) = mathrmid_mathcalF(X)$?
$endgroup$
– Seewoo Lee
Sep 28 at 7:17
$begingroup$
Oh, yes, you’re right.
$endgroup$
– Qiaochu Yuan
Sep 28 at 7:18
$begingroup$
For finite sets there is a counterexample not yet mentioned: let $f:Xrightarrow Y$ be a function; define $Ff:P(X) rightarrow P(Y)$ by $Ff(U) = text is odd$ - which basically arises from treating these powersets as groups under the symmetric difference. I don't think this can be extended to infinite sets, however.
$endgroup$
– Milo Brandt
Sep 28 at 22:34
$begingroup$
I made a separate post for my follow-up question on non-naturally-isomorphic functors: math.stackexchange.com/q/3374031/85341.
$endgroup$
– ComFreek
Sep 29 at 8:10
$begingroup$
@MiloBrandt Does your functor fulfill $Fid_X = id_FX$, though? If I am not mistaken, we have $Fid_X = X!$ (constant full subset $X$).
$endgroup$
– ComFreek
Sep 29 at 8:32
add a comment
|
1
$begingroup$
@QiaochuYuan Isn't it fail to satisfy $mathcalF(mathrmid_X) = mathrmid_mathcalF(X)$?
$endgroup$
– Seewoo Lee
Sep 28 at 7:17
$begingroup$
Oh, yes, you’re right.
$endgroup$
– Qiaochu Yuan
Sep 28 at 7:18
$begingroup$
For finite sets there is a counterexample not yet mentioned: let $f:Xrightarrow Y$ be a function; define $Ff:P(X) rightarrow P(Y)$ by $Ff(U) = text is odd$ - which basically arises from treating these powersets as groups under the symmetric difference. I don't think this can be extended to infinite sets, however.
$endgroup$
– Milo Brandt
Sep 28 at 22:34
$begingroup$
I made a separate post for my follow-up question on non-naturally-isomorphic functors: math.stackexchange.com/q/3374031/85341.
$endgroup$
– ComFreek
Sep 29 at 8:10
$begingroup$
@MiloBrandt Does your functor fulfill $Fid_X = id_FX$, though? If I am not mistaken, we have $Fid_X = X!$ (constant full subset $X$).
$endgroup$
– ComFreek
Sep 29 at 8:32
1
1
$begingroup$
@QiaochuYuan Isn't it fail to satisfy $mathcalF(mathrmid_X) = mathrmid_mathcalF(X)$?
$endgroup$
– Seewoo Lee
Sep 28 at 7:17
$begingroup$
@QiaochuYuan Isn't it fail to satisfy $mathcalF(mathrmid_X) = mathrmid_mathcalF(X)$?
$endgroup$
– Seewoo Lee
Sep 28 at 7:17
$begingroup$
Oh, yes, you’re right.
$endgroup$
– Qiaochu Yuan
Sep 28 at 7:18
$begingroup$
Oh, yes, you’re right.
$endgroup$
– Qiaochu Yuan
Sep 28 at 7:18
$begingroup$
For finite sets there is a counterexample not yet mentioned: let $f:Xrightarrow Y$ be a function; define $Ff:P(X) rightarrow P(Y)$ by $Ff(U) = text is odd$ - which basically arises from treating these powersets as groups under the symmetric difference. I don't think this can be extended to infinite sets, however.
$endgroup$
– Milo Brandt
Sep 28 at 22:34
$begingroup$
For finite sets there is a counterexample not yet mentioned: let $f:Xrightarrow Y$ be a function; define $Ff:P(X) rightarrow P(Y)$ by $Ff(U) = text is odd$ - which basically arises from treating these powersets as groups under the symmetric difference. I don't think this can be extended to infinite sets, however.
$endgroup$
– Milo Brandt
Sep 28 at 22:34
$begingroup$
I made a separate post for my follow-up question on non-naturally-isomorphic functors: math.stackexchange.com/q/3374031/85341.
$endgroup$
– ComFreek
Sep 29 at 8:10
$begingroup$
I made a separate post for my follow-up question on non-naturally-isomorphic functors: math.stackexchange.com/q/3374031/85341.
$endgroup$
– ComFreek
Sep 29 at 8:10
$begingroup$
@MiloBrandt Does your functor fulfill $Fid_X = id_FX$, though? If I am not mistaken, we have $Fid_X = X!$ (constant full subset $X$).
$endgroup$
– ComFreek
Sep 29 at 8:32
$begingroup$
@MiloBrandt Does your functor fulfill $Fid_X = id_FX$, though? If I am not mistaken, we have $Fid_X = X!$ (constant full subset $X$).
$endgroup$
– ComFreek
Sep 29 at 8:32
add a comment
|
2 Answers
2
active
oldest
votes
$begingroup$
There exists at least one other endofunctor of $mathbfSet$ that sends every set to its powerset. This endofunctor sends a function $f:Xto Y$ to
$$widehatf :P(X)to P(Y):Umapsto widehatf(U)=yin Ymid f^-1(y)subset U$$
(where $f^-1$ is the inverse image).
One can check directly that $widehatfcirc g=widehatfcirc widehatg$ and $widehatid_X=id_P(X)$, or use the following fact (which explains the origin of that definition) : for every set $X$, the powerset $P(x)$ is a poset (ordered by inclusion), and for any given $f$, $P(f), f^-1$ and $widehatf$ are all monotone functions and we have two adjunctions $P(f)dashv f^-1dashv widehatf$. Then, for any $g$ we have a chain of adjunctions
$$P(fcirc g)dashv (fcirc g)^-1dashv widehatfcirc g$$
and since adjunctions can be composed, we also have
$$P(f)circ P( g)dashv g^-1 circ f^-1dashv widehatfcirc widehatg$$
Since $P$ is a functor, the first term of the two chains coincide. By uniqueness of adjoint functors the other terms also coincide, thus $widehatfcirc g=widehatfcirc widehatg$. You can use a similar argument for the identities.
answered Sep 28 at 7:53
Arnaud D.Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
$endgroup$
1
$begingroup$
Out of interest, do you know how many such functors there are up to natural isomorphism? The functors in the other answer are all nat. isomorphic to $mathcalP$. Yours isn't, I guess.
$endgroup$
– ComFreek
Sep 28 at 8:48
$begingroup$
@ComFreek That’s an interesting question...anyway thank you for a good counterexample!
$endgroup$
– Seewoo Lee
Sep 28 at 13:45
1
$begingroup$
This map is also known as $hat f(U) = Ysetminus f(Xsetminus U)$, which also clarifies why it's a functor - but it also shows that this functor is naturally isomorphic to the powerset functor!
$endgroup$
– Milo Brandt
Sep 28 at 22:49
add a comment
|
$begingroup$
Here's a class of counter-examples:
For each set $X$ choose a bijection $r_Xcolon mathcal P(X)tomathcal P(X)$. Now let your functor $mathcal F$ be defined on morphisms $fcolon Xto Y$ by
$$
mathcal F(f) = r_Ycirc mathcal P(f) circ r_X^-1.
$$
You can check that this is a functor and one non-trivial choice of $r_X$ would be taking complements, i.e. $r_X(U)=Xsetminus U$, then $mathcal Ff(U) = Ysetminus f(Xsetminus U)$.
answered Sep 28 at 8:20
ChristophChristoph
14.1k19 silver badges46 bronze badges
$endgroup$
2
$begingroup$
Indeed every such functor $mathcalF$ is naturally isomorphic to $mathcalP$: $$requireAMScd beginCD mathcalP(X) @>r_X>> mathcalP(X)\ @VmathcalPfVV @VVmathcalFf = r_y circ mathcalPf circ r_X^-1V \ mathcalP(Y) @>r_Y>> mathcalP(Y). endCD$$ Even more, every functor of this class is naturally isomorphic to every other functor of this class. (Note that $mathcalP$ is a special case for $forall X. r_X := id_X$.)
$endgroup$
– ComFreek
Sep 28 at 8:40
add a comment
|
Your Answer
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "69"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/4.0/"u003ecc by-sa 4.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3372859%2fis-power-set-functor-determined-by-its-image-on-objects%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
There exists at least one other endofunctor of $mathbfSet$ that sends every set to its powerset. This endofunctor sends a function $f:Xto Y$ to
$$widehatf :P(X)to P(Y):Umapsto widehatf(U)=yin Ymid f^-1(y)subset U$$
(where $f^-1$ is the inverse image).
One can check directly that $widehatfcirc g=widehatfcirc widehatg$ and $widehatid_X=id_P(X)$, or use the following fact (which explains the origin of that definition) : for every set $X$, the powerset $P(x)$ is a poset (ordered by inclusion), and for any given $f$, $P(f), f^-1$ and $widehatf$ are all monotone functions and we have two adjunctions $P(f)dashv f^-1dashv widehatf$. Then, for any $g$ we have a chain of adjunctions
$$P(fcirc g)dashv (fcirc g)^-1dashv widehatfcirc g$$
and since adjunctions can be composed, we also have
$$P(f)circ P( g)dashv g^-1 circ f^-1dashv widehatfcirc widehatg$$
Since $P$ is a functor, the first term of the two chains coincide. By uniqueness of adjoint functors the other terms also coincide, thus $widehatfcirc g=widehatfcirc widehatg$. You can use a similar argument for the identities.
answered Sep 28 at 7:53
Arnaud D.Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
$endgroup$
1
$begingroup$
Out of interest, do you know how many such functors there are up to natural isomorphism? The functors in the other answer are all nat. isomorphic to $mathcalP$. Yours isn't, I guess.
$endgroup$
– ComFreek
Sep 28 at 8:48
$begingroup$
@ComFreek That’s an interesting question...anyway thank you for a good counterexample!
$endgroup$
– Seewoo Lee
Sep 28 at 13:45
1
$begingroup$
This map is also known as $hat f(U) = Ysetminus f(Xsetminus U)$, which also clarifies why it's a functor - but it also shows that this functor is naturally isomorphic to the powerset functor!
$endgroup$
– Milo Brandt
Sep 28 at 22:49
add a comment
|
$begingroup$
There exists at least one other endofunctor of $mathbfSet$ that sends every set to its powerset. This endofunctor sends a function $f:Xto Y$ to
$$widehatf :P(X)to P(Y):Umapsto widehatf(U)=yin Ymid f^-1(y)subset U$$
(where $f^-1$ is the inverse image).
One can check directly that $widehatfcirc g=widehatfcirc widehatg$ and $widehatid_X=id_P(X)$, or use the following fact (which explains the origin of that definition) : for every set $X$, the powerset $P(x)$ is a poset (ordered by inclusion), and for any given $f$, $P(f), f^-1$ and $widehatf$ are all monotone functions and we have two adjunctions $P(f)dashv f^-1dashv widehatf$. Then, for any $g$ we have a chain of adjunctions
$$P(fcirc g)dashv (fcirc g)^-1dashv widehatfcirc g$$
and since adjunctions can be composed, we also have
$$P(f)circ P( g)dashv g^-1 circ f^-1dashv widehatfcirc widehatg$$
Since $P$ is a functor, the first term of the two chains coincide. By uniqueness of adjoint functors the other terms also coincide, thus $widehatfcirc g=widehatfcirc widehatg$. You can use a similar argument for the identities.
answered Sep 28 at 7:53
Arnaud D.Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
$endgroup$
1
$begingroup$
Out of interest, do you know how many such functors there are up to natural isomorphism? The functors in the other answer are all nat. isomorphic to $mathcalP$. Yours isn't, I guess.
$endgroup$
– ComFreek
Sep 28 at 8:48
$begingroup$
@ComFreek That’s an interesting question...anyway thank you for a good counterexample!
$endgroup$
– Seewoo Lee
Sep 28 at 13:45
1
$begingroup$
This map is also known as $hat f(U) = Ysetminus f(Xsetminus U)$, which also clarifies why it's a functor - but it also shows that this functor is naturally isomorphic to the powerset functor!
$endgroup$
– Milo Brandt
Sep 28 at 22:49
add a comment
|
$begingroup$
There exists at least one other endofunctor of $mathbfSet$ that sends every set to its powerset. This endofunctor sends a function $f:Xto Y$ to
$$widehatf :P(X)to P(Y):Umapsto widehatf(U)=yin Ymid f^-1(y)subset U$$
(where $f^-1$ is the inverse image).
One can check directly that $widehatfcirc g=widehatfcirc widehatg$ and $widehatid_X=id_P(X)$, or use the following fact (which explains the origin of that definition) : for every set $X$, the powerset $P(x)$ is a poset (ordered by inclusion), and for any given $f$, $P(f), f^-1$ and $widehatf$ are all monotone functions and we have two adjunctions $P(f)dashv f^-1dashv widehatf$. Then, for any $g$ we have a chain of adjunctions
$$P(fcirc g)dashv (fcirc g)^-1dashv widehatfcirc g$$
and since adjunctions can be composed, we also have
$$P(f)circ P( g)dashv g^-1 circ f^-1dashv widehatfcirc widehatg$$
Since $P$ is a functor, the first term of the two chains coincide. By uniqueness of adjoint functors the other terms also coincide, thus $widehatfcirc g=widehatfcirc widehatg$. You can use a similar argument for the identities.
answered Sep 28 at 7:53
Arnaud D.Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
$endgroup$
There exists at least one other endofunctor of $mathbfSet$ that sends every set to its powerset. This endofunctor sends a function $f:Xto Y$ to
$$widehatf :P(X)to P(Y):Umapsto widehatf(U)=yin Ymid f^-1(y)subset U$$
(where $f^-1$ is the inverse image).
One can check directly that $widehatfcirc g=widehatfcirc widehatg$ and $widehatid_X=id_P(X)$, or use the following fact (which explains the origin of that definition) : for every set $X$, the powerset $P(x)$ is a poset (ordered by inclusion), and for any given $f$, $P(f), f^-1$ and $widehatf$ are all monotone functions and we have two adjunctions $P(f)dashv f^-1dashv widehatf$. Then, for any $g$ we have a chain of adjunctions
$$P(fcirc g)dashv (fcirc g)^-1dashv widehatfcirc g$$
and since adjunctions can be composed, we also have
$$P(f)circ P( g)dashv g^-1 circ f^-1dashv widehatfcirc widehatg$$
Since $P$ is a functor, the first term of the two chains coincide. By uniqueness of adjoint functors the other terms also coincide, thus $widehatfcirc g=widehatfcirc widehatg$. You can use a similar argument for the identities.
answered Sep 28 at 7:53
Arnaud D.Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
answered Sep 28 at 7:53
Arnaud D.Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
answered Sep 28 at 7:53
Arnaud D.Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
answered Sep 28 at 7:53
Arnaud D.Arnaud D.
18k5 gold badges26 silver badges46 bronze badges
18k5 gold badges26 silver badges46 bronze badges
1
$begingroup$
Out of interest, do you know how many such functors there are up to natural isomorphism? The functors in the other answer are all nat. isomorphic to $mathcalP$. Yours isn't, I guess.
$endgroup$
– ComFreek
Sep 28 at 8:48
$begingroup$
@ComFreek That’s an interesting question...anyway thank you for a good counterexample!
$endgroup$
– Seewoo Lee
Sep 28 at 13:45
1
$begingroup$
This map is also known as $hat f(U) = Ysetminus f(Xsetminus U)$, which also clarifies why it's a functor - but it also shows that this functor is naturally isomorphic to the powerset functor!
$endgroup$
– Milo Brandt
Sep 28 at 22:49
add a comment
|
1
$begingroup$
Out of interest, do you know how many such functors there are up to natural isomorphism? The functors in the other answer are all nat. isomorphic to $mathcalP$. Yours isn't, I guess.
$endgroup$
– ComFreek
Sep 28 at 8:48
$begingroup$
@ComFreek That’s an interesting question...anyway thank you for a good counterexample!
$endgroup$
– Seewoo Lee
Sep 28 at 13:45
1
$begingroup$
This map is also known as $hat f(U) = Ysetminus f(Xsetminus U)$, which also clarifies why it's a functor - but it also shows that this functor is naturally isomorphic to the powerset functor!
$endgroup$
– Milo Brandt
Sep 28 at 22:49
1
1
$begingroup$
Out of interest, do you know how many such functors there are up to natural isomorphism? The functors in the other answer are all nat. isomorphic to $mathcalP$. Yours isn't, I guess.
$endgroup$
– ComFreek
Sep 28 at 8:48
$begingroup$
Out of interest, do you know how many such functors there are up to natural isomorphism? The functors in the other answer are all nat. isomorphic to $mathcalP$. Yours isn't, I guess.
$endgroup$
– ComFreek
Sep 28 at 8:48
$begingroup$
@ComFreek That’s an interesting question...anyway thank you for a good counterexample!
$endgroup$
– Seewoo Lee
Sep 28 at 13:45
$begingroup$
@ComFreek That’s an interesting question...anyway thank you for a good counterexample!
$endgroup$
– Seewoo Lee
Sep 28 at 13:45
1
1
$begingroup$
This map is also known as $hat f(U) = Ysetminus f(Xsetminus U)$, which also clarifies why it's a functor - but it also shows that this functor is naturally isomorphic to the powerset functor!
$endgroup$
– Milo Brandt
Sep 28 at 22:49
$begingroup$
This map is also known as $hat f(U) = Ysetminus f(Xsetminus U)$, which also clarifies why it's a functor - but it also shows that this functor is naturally isomorphic to the powerset functor!
$endgroup$
– Milo Brandt
Sep 28 at 22:49
add a comment
|
$begingroup$
Here's a class of counter-examples:
For each set $X$ choose a bijection $r_Xcolon mathcal P(X)tomathcal P(X)$. Now let your functor $mathcal F$ be defined on morphisms $fcolon Xto Y$ by
$$
mathcal F(f) = r_Ycirc mathcal P(f) circ r_X^-1.
$$
You can check that this is a functor and one non-trivial choice of $r_X$ would be taking complements, i.e. $r_X(U)=Xsetminus U$, then $mathcal Ff(U) = Ysetminus f(Xsetminus U)$.
answered Sep 28 at 8:20
ChristophChristoph
14.1k19 silver badges46 bronze badges
$endgroup$
2
$begingroup$
Indeed every such functor $mathcalF$ is naturally isomorphic to $mathcalP$: $$requireAMScd beginCD mathcalP(X) @>r_X>> mathcalP(X)\ @VmathcalPfVV @VVmathcalFf = r_y circ mathcalPf circ r_X^-1V \ mathcalP(Y) @>r_Y>> mathcalP(Y). endCD$$ Even more, every functor of this class is naturally isomorphic to every other functor of this class. (Note that $mathcalP$ is a special case for $forall X. r_X := id_X$.)
$endgroup$
– ComFreek
Sep 28 at 8:40
add a comment
|
$begingroup$
Here's a class of counter-examples:
For each set $X$ choose a bijection $r_Xcolon mathcal P(X)tomathcal P(X)$. Now let your functor $mathcal F$ be defined on morphisms $fcolon Xto Y$ by
$$
mathcal F(f) = r_Ycirc mathcal P(f) circ r_X^-1.
$$
You can check that this is a functor and one non-trivial choice of $r_X$ would be taking complements, i.e. $r_X(U)=Xsetminus U$, then $mathcal Ff(U) = Ysetminus f(Xsetminus U)$.
answered Sep 28 at 8:20
ChristophChristoph
14.1k19 silver badges46 bronze badges
$endgroup$
2
$begingroup$
Indeed every such functor $mathcalF$ is naturally isomorphic to $mathcalP$: $$requireAMScd beginCD mathcalP(X) @>r_X>> mathcalP(X)\ @VmathcalPfVV @VVmathcalFf = r_y circ mathcalPf circ r_X^-1V \ mathcalP(Y) @>r_Y>> mathcalP(Y). endCD$$ Even more, every functor of this class is naturally isomorphic to every other functor of this class. (Note that $mathcalP$ is a special case for $forall X. r_X := id_X$.)
$endgroup$
– ComFreek
Sep 28 at 8:40
add a comment
|
$begingroup$
Here's a class of counter-examples:
For each set $X$ choose a bijection $r_Xcolon mathcal P(X)tomathcal P(X)$. Now let your functor $mathcal F$ be defined on morphisms $fcolon Xto Y$ by
$$
mathcal F(f) = r_Ycirc mathcal P(f) circ r_X^-1.
$$
You can check that this is a functor and one non-trivial choice of $r_X$ would be taking complements, i.e. $r_X(U)=Xsetminus U$, then $mathcal Ff(U) = Ysetminus f(Xsetminus U)$.
answered Sep 28 at 8:20
ChristophChristoph
14.1k19 silver badges46 bronze badges
$endgroup$
Here's a class of counter-examples:
For each set $X$ choose a bijection $r_Xcolon mathcal P(X)tomathcal P(X)$. Now let your functor $mathcal F$ be defined on morphisms $fcolon Xto Y$ by
$$
mathcal F(f) = r_Ycirc mathcal P(f) circ r_X^-1.
$$
You can check that this is a functor and one non-trivial choice of $r_X$ would be taking complements, i.e. $r_X(U)=Xsetminus U$, then $mathcal Ff(U) = Ysetminus f(Xsetminus U)$.
answered Sep 28 at 8:20
ChristophChristoph
14.1k19 silver badges46 bronze badges
answered Sep 28 at 8:20
ChristophChristoph
14.1k19 silver badges46 bronze badges
answered Sep 28 at 8:20
ChristophChristoph
14.1k19 silver badges46 bronze badges
answered Sep 28 at 8:20
ChristophChristoph
14.1k19 silver badges46 bronze badges
14.1k19 silver badges46 bronze badges
2
$begingroup$
Indeed every such functor $mathcalF$ is naturally isomorphic to $mathcalP$: $$requireAMScd beginCD mathcalP(X) @>r_X>> mathcalP(X)\ @VmathcalPfVV @VVmathcalFf = r_y circ mathcalPf circ r_X^-1V \ mathcalP(Y) @>r_Y>> mathcalP(Y). endCD$$ Even more, every functor of this class is naturally isomorphic to every other functor of this class. (Note that $mathcalP$ is a special case for $forall X. r_X := id_X$.)
$endgroup$
– ComFreek
Sep 28 at 8:40
add a comment
|
2
$begingroup$
Indeed every such functor $mathcalF$ is naturally isomorphic to $mathcalP$: $$requireAMScd beginCD mathcalP(X) @>r_X>> mathcalP(X)\ @VmathcalPfVV @VVmathcalFf = r_y circ mathcalPf circ r_X^-1V \ mathcalP(Y) @>r_Y>> mathcalP(Y). endCD$$ Even more, every functor of this class is naturally isomorphic to every other functor of this class. (Note that $mathcalP$ is a special case for $forall X. r_X := id_X$.)
$endgroup$
– ComFreek
Sep 28 at 8:40
2
2
$begingroup$
Indeed every such functor $mathcalF$ is naturally isomorphic to $mathcalP$: $$requireAMScd beginCD mathcalP(X) @>r_X>> mathcalP(X)\ @VmathcalPfVV @VVmathcalFf = r_y circ mathcalPf circ r_X^-1V \ mathcalP(Y) @>r_Y>> mathcalP(Y). endCD$$ Even more, every functor of this class is naturally isomorphic to every other functor of this class. (Note that $mathcalP$ is a special case for $forall X. r_X := id_X$.)
$endgroup$
– ComFreek
Sep 28 at 8:40
$begingroup$
Indeed every such functor $mathcalF$ is naturally isomorphic to $mathcalP$: $$requireAMScd beginCD mathcalP(X) @>r_X>> mathcalP(X)\ @VmathcalPfVV @VVmathcalFf = r_y circ mathcalPf circ r_X^-1V \ mathcalP(Y) @>r_Y>> mathcalP(Y). endCD$$ Even more, every functor of this class is naturally isomorphic to every other functor of this class. (Note that $mathcalP$ is a special case for $forall X. r_X := id_X$.)
$endgroup$
– ComFreek
Sep 28 at 8:40
add a comment
|
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3372859%2fis-power-set-functor-determined-by-its-image-on-objects%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
1
$begingroup$
@QiaochuYuan Isn't it fail to satisfy $mathcalF(mathrmid_X) = mathrmid_mathcalF(X)$?
$endgroup$
– Seewoo Lee
Sep 28 at 7:17
$begingroup$
Oh, yes, you’re right.
$endgroup$
– Qiaochu Yuan
Sep 28 at 7:18
$begingroup$
For finite sets there is a counterexample not yet mentioned: let $f:Xrightarrow Y$ be a function; define $Ff:P(X) rightarrow P(Y)$ by $Ff(U) = text is odd$ - which basically arises from treating these powersets as groups under the symmetric difference. I don't think this can be extended to infinite sets, however.
$endgroup$
– Milo Brandt
Sep 28 at 22:34
$begingroup$
I made a separate post for my follow-up question on non-naturally-isomorphic functors: math.stackexchange.com/q/3374031/85341.
$endgroup$
– ComFreek
Sep 29 at 8:10
$begingroup$
@MiloBrandt Does your functor fulfill $Fid_X = id_FX$, though? If I am not mistaken, we have $Fid_X = X!$ (constant full subset $X$).
$endgroup$
– ComFreek
Sep 29 at 8:32