Not signed in

Want to take part in these discussions? Sign in if you have an account, or apply for one below

• Username
• Password
• Remember me

• Sign in using OpenID
• Remember me

• Forgot your password?
• Apply for membership

2-category 2-category-theory abelian-categories adjoint algebra algebraic algebraic-geometry algebraic-topology analysis analytic-geometry arithmetic arithmetic-geometry book bundles calculus categorical categories category category-theory chern-weil-theory cohesion cohesive-homotopy-type-theory cohomology colimits combinatorics complex complex-geometry computable-mathematics computer-science constructive cosmology deformation-theory descent diagrams differential differential-cohomology differential-equations differential-geometry digraphs duality elliptic-cohomology enriched fibration foundation foundations functional-analysis functor gauge-theory gebra geometric-quantization geometry graph graphs gravity grothendieck group group-theory harmonic-analysis higher higher-algebra higher-category-theory higher-differential-geometry higher-geometry higher-lie-theory higher-topos-theory homological homological-algebra homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory k-theory lie-theory limits linear linear-algebra locale localization logic mathematics measure-theory modal modal-logic model model-category-theory monad monads monoidal monoidal-category-theory morphism motives motivic-cohomology nforum nlab noncommutative noncommutative-geometry number-theory of operads operator operator-algebra order-theory pages pasting philosophy physics pro-object probability probability-theory quantization quantum quantum-field quantum-field-theory quantum-mechanics quantum-physics quantum-theory question representation representation-theory riemannian-geometry scheme schemes set set-theory sheaf sheaves simplicial space spin-geometry stable-homotopy-theory stack string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory tqft type type-theory universal variational-calculus

1. • CommentRowNumber1.
   • CommentAuthorTodd_Trimble
   • CommentTimeMay 7th 2010
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItexOkay, let's continue here. Hopefully I've chosen the correct category for it (ha ha). Eric wrote: > So functions send elements of X to elements of Y, but not every element of Y gets something mapped to it and several elements of X can map to the same element of Y. Right. Exactly. And it's important to remember well-definedness, too, so there are no two elements of Y that an element of X can get mapped to. > The opposite function seems like it sends elements in Y to something like a "set of fibers", but that can't be quite right because that would be a map Y→P(X), i.e. the powerset of X. That's actually on the right track though! You've done a neat trick (used in topos theory all the time) of taking a relation between $Y$ and $X$ and turning it into a function, $Y \to P X$. And yes, given the original function $f: X \to Y$, what you've created is indeed the fiber map $Y \to P X$, taking $y \in Y$ to its preimage $f^{-1}(y) \in P X$. And, putting a piece of the puzzle together, notice the power set $P X$ is a finite Boolean algebra (I'm assuming we're working with finite sets $X$, $Y$). So maybe we're getting somewhere! > BUT... I think we have a map P(X)→X which just takes the union of elements in P(X). So I think f op:Y→X sends each element of Y to its preimage in P(X) and then takes the union of all preimages. Or something... It sounds like you were beginning to panic a little in the first sentence. $X$ is just a set right now; it has no extra structure. So there is no given map $P X \to X$ which would take a union. (And let's not try to do anything artificial like manufacture such a structure on $X$ out of thin air. Category theory is largely about doing everything naturally. Very Zen.) Let's see where we are. We have an assignment of showing that the opposite of the category of finite sets is equivalent to the category of finite Boolean algebras. The first step was to associate, to an arrow $f: X \to Y$, the opposite relation $f^{-1}$ (preimage), which is in the opposite direction. Then you had the bright idea of turning this into a concrete function $f^{-1}: Y \to P X$. And $P X$ is a Boolean algebra, so this may be encouraging. Some notes: the well-definedness of $f$ means exactly that no two fibers intersect: that if $y \neq y'$, then $f^{-1}(y) \cap f^{-1}(y') = \emptyset$. Since well-definedness is crucial to being a function, we should expect this intersection property observation also to play a crucial role in the story. Okay. You've also essentially observed that this $f^{-1}: Y \to P X$ hasn't quite landed us in the category of Boolean algebras; right now it's not a Boolean algebra map, and for that matter, $Y$ isn't even a Boolean algebra. What can we do about that? Is there any way of getting a Boolean algebra map out of this data? I don't mean putting a Boolean algebra structure on $Y$ exactly -- that would be artificial -- but getting a Boolean algebra out of $Y$ in some way, and getting a Boolean algebra homomorphism out of the situation. Do what comes naturally...

   Okay, let’s continue here. Hopefully I’ve chosen the correct category for it (ha ha).

   Eric wrote:

   So functions send elements of X to elements of Y, but not every element of Y gets something mapped to it and several elements of X can map to the same element of Y.

   Right. Exactly. And it’s important to remember well-definedness, too, so there are no two elements of Y that an element of X can get mapped to.

   The opposite function seems like it sends elements in Y to something like a “set of fibers”, but that can’t be quite right because that would be a map Y→P(X), i.e. the powerset of X.

   That’s actually on the right track though! You’ve done a neat trick (used in topos theory all the time) of taking a relation between $Y$ and $X$ and turning it into a function, $Y \to P X$. And yes, given the original function $f: X \to Y$, what you’ve created is indeed the fiber map $Y \to P X$, taking $y \in Y$ to its preimage $f^{-1}(y) \in P X$.

   And, putting a piece of the puzzle together, notice the power set $P X$ is a finite Boolean algebra (I’m assuming we’re working with finite sets $X$, $Y$). So maybe we’re getting somewhere!

   BUT… I think we have a map P(X)→X which just takes the union of elements in P(X). So I think f op:Y→X sends each element of Y to its preimage in P(X) and then takes the union of all preimages. Or something…

   It sounds like you were beginning to panic a little in the first sentence. $X$ is just a set right now; it has no extra structure. So there is no given map $P X \to X$ which would take a union. (And let’s not try to do anything artificial like manufacture such a structure on $X$ out of thin air. Category theory is largely about doing everything naturally. Very Zen.)

   Let’s see where we are. We have an assignment of showing that the opposite of the category of finite sets is equivalent to the category of finite Boolean algebras. The first step was to associate, to an arrow $f: X \to Y$, the opposite relation $f^{-1}$ (preimage), which is in the opposite direction. Then you had the bright idea of turning this into a concrete function $f^{-1}: Y \to P X$. And $P X$ is a Boolean algebra, so this may be encouraging.

   Some notes: the well-definedness of $f$ means exactly that no two fibers intersect: that if $y \neq y'$, then $f^{-1}(y) \cap f^{-1}(y') = \emptyset$. Since well-definedness is crucial to being a function, we should expect this intersection property observation also to play a crucial role in the story.

   Okay. You’ve also essentially observed that this $f^{-1}: Y \to P X$ hasn’t quite landed us in the category of Boolean algebras; right now it’s not a Boolean algebra map, and for that matter, $Y$ isn’t even a Boolean algebra. What can we do about that? Is there any way of getting a Boolean algebra map out of this data? I don’t mean putting a Boolean algebra structure on $Y$ exactly – that would be artificial – but getting a Boolean algebra out of $Y$ in some way, and getting a Boolean algebra homomorphism out of the situation.

   Do what comes naturally…

2. • CommentRowNumber2.
   • CommentAuthorEric
   • CommentTimeMay 8th 2010
   • PermaLink
   Author: Eric
   Format: MarkdownItexOn the train ride home last night, I was drawing a bunch of pictures trying to figure this out. I discovered some mistakes in the way I think about things. First, it was kind of fun showing that $$f^{-1}(y_i) \cap f^{-1}(y_j) = \delta_{i,j}(f^{-1}(y_i))$$ where $\delta_{i,i}$ is a magical function that makes the above statement correct (but I think you know what I mean) :) Next, I knew we were trying to get an algebra so I thought about "products" and my brain immediately started thinking about limits of discrete diagrams. But then that relation about the fibers being disjoint made me think the product I want might be intersection or something. Then I thought I remembered that intersection was a pullback so started drawing little squares. Then I also started trying to think in terms of elements, but that is a no no around here, so started thinking about [[generalized elements]]. Then I thought that FinSet had an [[initial object]] and a [[terminal object]] and started drawing more squares. THEN I realized that I didn't know what a Boolean algebra was :) I studied Boolean algebra many moons ago as an undergrad, but realized that maybe what I was familiar with, i.e. Boolean algebras with algebra in $\{0,1\}$, might be a subset of what you are talking about. THEN I realized that we don't want the collection of objects to form a Boolean algebra (that might be a Boolean algebroid or something). We want each object to BE a Boolean algebra :) So then I started thinking about endomorphisms on finite sets, which brings me to this moment :) So much for a train ride, eh? :) Now I'm thinking it would probably be helpful to focus on a single finite set $X$ and look at endomorphisms $f:X\to X$. In fact, it might even be good to start with endomorphisms on $X = \{0,1\}$. There are only two endomorphisms $I:X\to X$ and $S:X\to X$ with $S^2 = I$. I'm guessing the opposite of this category is related to the Boolean algebra I'm familiar with, but need to think about it. In this case, it seems that $I^{op} = I$ and $S^{op} = S$. Anyway, I thought it might be curious to see the twisted journey my thoughts took me on during the last train ride :)

   On the train ride home last night, I was drawing a bunch of pictures trying to figure this out. I discovered some mistakes in the way I think about things.

   First, it was kind of fun showing that

   $$f^{-1}(y_i) \cap f^{-1}(y_j) = \delta_{i,j}(f^{-1}(y_i))$$

   where $\delta_{i,i}$ is a magical function that makes the above statement correct (but I think you know what I mean) :)

   Next, I knew we were trying to get an algebra so I thought about “products” and my brain immediately started thinking about limits of discrete diagrams.

   But then that relation about the fibers being disjoint made me think the product I want might be intersection or something. Then I thought I remembered that intersection was a pullback so started drawing little squares. Then I also started trying to think in terms of elements, but that is a no no around here, so started thinking about generalized elements. Then I thought that FinSet had an initial object and a terminal object and started drawing more squares.

   THEN I realized that I didn’t know what a Boolean algebra was :) I studied Boolean algebra many moons ago as an undergrad, but realized that maybe what I was familiar with, i.e. Boolean algebras with algebra in $\{0,1\}$, might be a subset of what you are talking about.

   THEN I realized that we don’t want the collection of objects to form a Boolean algebra (that might be a Boolean algebroid or something). We want each object to BE a Boolean algebra :)

   So then I started thinking about endomorphisms on finite sets, which brings me to this moment :) So much for a train ride, eh? :)

   Now I’m thinking it would probably be helpful to focus on a single finite set $X$ and look at endomorphisms $f:X\to X$. In fact, it might even be good to start with endomorphisms on $X = \{0,1\}$.

   There are only two endomorphisms $I:X\to X$ and $S:X\to X$ with $S^2 = I$.

   I’m guessing the opposite of this category is related to the Boolean algebra I’m familiar with, but need to think about it. In this case, it seems that $I^{op} = I$ and $S^{op} = S$.

   Anyway, I thought it might be curious to see the twisted journey my thoughts took me on during the last train ride :)

3. • CommentRowNumber3.
   • CommentAuthorDavidRoberts
   • CommentTimeMay 8th 2010
   • PermaLink
   Author: DavidRoberts
   Format: MarkdownItex>There are only two endomorphisms... actually I and S are _automorphisms_. There are also the constant maps, sending both elements to 0 and 1 respectively, giving us 4 endomorphisms.

   There are only two endomorphisms…

   actually I and S are automorphisms. There are also the constant maps, sending both elements to 0 and 1 respectively, giving us 4 endomorphisms.

4. • CommentRowNumber4.
   • CommentAuthorEric
   • CommentTimeMay 8th 2010
   • PermaLink
   Author: Eric
   Format: MarkdownItexOh right. Thanks

   Oh right. Thanks

5. • CommentRowNumber5.
   • CommentAuthorTodd_Trimble
   • CommentTimeMay 8th 2010
   • (edited May 8th 2010)
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItex> Then I also started trying to think in terms of elements, but that is a no no around here That is a complete misconception! I think in terms of elements all the time: plain, vanilla elements. Sometimes I even have to think that way to get straightened out, this after years and years of thinking about category theory. (An example occurred very recently while writing an nLab page, but I can't recall what it was.) In doing battle with mathematics, use any and all conceptual tools that you find helpful. > THEN I realized that I didn't know what a Boolean algebra was :) I studied Boolean algebra many moons ago as an undergrad, but realized that maybe what I was familiar with, i.e. Boolean algebras with algebra in {0,1}, might be a subset of what you are talking about. Don't we have a page [[Boolean algebra]]? What happens when you click on that? You may find more information there than you really need, but probably you know that a Boolean algebra is supposed to be, by definition, a set/collection that comes equipped with operations $\vee$, $\wedge$, $\neg$, satisfying certain identities. And you know that $\{0, 1\}$ is an example of a Boolean algebra, and how the operations work in that case. That's a good start. You can manufacture more examples of Boolean algebras, starting from that one example, as follows. If $S$ is any set, then the set of all functions $f: S \to \{0, 1\}$ forms a Boolean algebra, by dint of the Boolean algebra structure that already exists on $\{0, 1\}$. For, if $f$ and $g$ are such functions, then define $f \vee g$ by the rule $(f \vee g)(s) = f(s) \vee g(s)$, where the right side is interpreted in the Boolean algebra $\{0, 1\}$. The other operations $\wedge$, $\neg$ on functions are defined similarly. The last thing you were talking about is an example, where $S = \{0, 1\}$, and you get the 4-element Boolean algebra of endofunctions on $\{0, 1\}$. (But I think thinking about general endofunctions on general $S$ is putting you off course with regard to this particular discussion.) By the way, in case you hadn't observed it already, the Boolean algebra of all functions $f: S \to \{0, 1\}$ is the same thing, i.e., is isomorphic to, the Boolean algebra $P(S)$ (the power set, equipped with the standard $\vee$, $\wedge$, $\neg$). Do you see why? What would the one-to-one correspondence be between $hom(S, \{0, 1\})$ and $P(S)$? Anyway, to get back to the discussion: you have in your hand a nice function $f^{-1}(-): Y \to P(X)$. We want to get a Boolean algebra map out of this situation; in particular, we need a Boolean algebra associated with the set $Y$ somehow. What would you try? Edit: just clicked on [[Boolean algebra]] myself. Pretty bare-bones; needs a lot of work.

   Then I also started trying to think in terms of elements, but that is a no no around here

   That is a complete misconception! I think in terms of elements all the time: plain, vanilla elements. Sometimes I even have to think that way to get straightened out, this after years and years of thinking about category theory. (An example occurred very recently while writing an nLab page, but I can’t recall what it was.)

   In doing battle with mathematics, use any and all conceptual tools that you find helpful.

   THEN I realized that I didn’t know what a Boolean algebra was :) I studied Boolean algebra many moons ago as an undergrad, but realized that maybe what I was familiar with, i.e. Boolean algebras with algebra in {0,1}, might be a subset of what you are talking about.

   Don’t we have a page Boolean algebra? What happens when you click on that?

   You may find more information there than you really need, but probably you know that a Boolean algebra is supposed to be, by definition, a set/collection that comes equipped with operations $\vee$, $\wedge$, $\neg$, satisfying certain identities. And you know that $\{0, 1\}$ is an example of a Boolean algebra, and how the operations work in that case. That’s a good start.

   You can manufacture more examples of Boolean algebras, starting from that one example, as follows. If $S$ is any set, then the set of all functions $f: S \to \{0, 1\}$ forms a Boolean algebra, by dint of the Boolean algebra structure that already exists on $\{0, 1\}$. For, if $f$ and $g$ are such functions, then define $f \vee g$ by the rule $(f \vee g)(s) = f(s) \vee g(s)$, where the right side is interpreted in the Boolean algebra $\{0, 1\}$. The other operations $\wedge$, $\neg$ on functions are defined similarly.

   The last thing you were talking about is an example, where $S = \{0, 1\}$, and you get the 4-element Boolean algebra of endofunctions on $\{0, 1\}$. (But I think thinking about general endofunctions on general $S$ is putting you off course with regard to this particular discussion.)

   By the way, in case you hadn’t observed it already, the Boolean algebra of all functions $f: S \to \{0, 1\}$ is the same thing, i.e., is isomorphic to, the Boolean algebra $P(S)$ (the power set, equipped with the standard $\vee$, $\wedge$, $\neg$). Do you see why? What would the one-to-one correspondence be between $hom(S, \{0, 1\})$ and $P(S)$?

   Anyway, to get back to the discussion: you have in your hand a nice function $f^{-1}(-): Y \to P(X)$. We want to get a Boolean algebra map out of this situation; in particular, we need a Boolean algebra associated with the set $Y$ somehow.

   What would you try?

   Edit: just clicked on Boolean algebra myself. Pretty bare-bones; needs a lot of work.

6. • CommentRowNumber6.
   • CommentAuthorEric
   • CommentTimeMay 8th 2010
   • PermaLink
   Author: Eric
   Format: MarkdownItex>Don't we have a page [[Boolean algebra]]? What happens when you click on that? Not much (as you later discovered) :) Of course I tried that, but as is often the case, it sent me on trail of definitions and I never did get what the point really was about. >You may find more information there than you really need, but probably you know that a Boolean algebra is supposed to be, by definition, a set/collection that comes equipped with operations $\vee$, $\wedge$, $\neg$, satisfying certain identities. And you know that $\{0, 1\}$ is an example of a Boolean algebra, and how the operations work in that case. That's a good start. My exposure to Boolean algebra was in the context of electrical engineering. There the operations were AND, OR, and NOT (all of which can be constructed from NAND gates). These operations correspond to hardware elements, i.e. AND gates, OR gates, and NOT gates. AND was written as multiplication, i.e. AB = 1 only if A = 1 and B = 1, and OR was written as "+" where 1+1 = 1. Given a Boolean function, $F:S\to\{0,1\}$, e.g. $$ F = A B\bar{C} + A C + \bar{B} C$$ we'd have to first "simplify" the expression using a [Karnaugh map](http://en.wikipedia.org/wiki/Karnaugh_map), then build a circuit using AND gates, OR gates, and NOT gates. It was actually a pretty fun class :) I wonder if it is of any significance to Boolean algebra that AND, OR, and NOT can all be constructed from [NAND](http://en.wikipedia.org/wiki/NAND_logic) (also by NOR). NAND (and independently NOR) are "universal". >By the way, in case you hadn't observed it already, the Boolean algebra of all functions $f: S \to \{0, 1\}$ is the same thing, i.e., is isomorphic to, the Boolean algebra $P(S)$ (the power set, equipped with the standard $\vee$, $\wedge$, $\neg$). Do you see why? No, I don't see why yet, but its getting late, so I'll have to sleep on it. I'd like to understand that though. >What would you try? I'm about to pass out, but will try to give this a go tomorrow. Since $P(X)$ is a Boolean algebra associated to $X$, then if we're looking for a Boolean algebra associated to $Y$, I can think of crazier things to consider the $P(Y)$ :)

   Don’t we have a page Boolean algebra? What happens when you click on that?

   Not much (as you later discovered) :) Of course I tried that, but as is often the case, it sent me on trail of definitions and I never did get what the point really was about.

   You may find more information there than you really need, but probably you know that a Boolean algebra is supposed to be, by definition, a set/collection that comes equipped with operations $\vee$, $\wedge$, $\neg$, satisfying certain identities. And you know that $\{0, 1\}$ is an example of a Boolean algebra, and how the operations work in that case. That’s a good start.

   My exposure to Boolean algebra was in the context of electrical engineering. There the operations were AND, OR, and NOT (all of which can be constructed from NAND gates). These operations correspond to hardware elements, i.e. AND gates, OR gates, and NOT gates. AND was written as multiplication, i.e. AB = 1 only if A = 1 and B = 1, and OR was written as “+” where 1+1 = 1. Given a Boolean function, $F:S\to\{0,1\}$, e.g.

   $$F = A B\bar{C} + A C + \bar{B} C$$

   we’d have to first “simplify” the expression using a Karnaugh map, then build a circuit using AND gates, OR gates, and NOT gates. It was actually a pretty fun class :)

   I wonder if it is of any significance to Boolean algebra that AND, OR, and NOT can all be constructed from NAND (also by NOR). NAND (and independently NOR) are “universal”.

   By the way, in case you hadn’t observed it already, the Boolean algebra of all functions $f: S \to \{0, 1\}$ is the same thing, i.e., is isomorphic to, the Boolean algebra $P(S)$ (the power set, equipped with the standard $\vee$, $\wedge$, $\neg$). Do you see why?

   No, I don’t see why yet, but its getting late, so I’ll have to sleep on it. I’d like to understand that though.

   What would you try?

   I’m about to pass out, but will try to give this a go tomorrow. Since $P(X)$ is a Boolean algebra associated to $X$, then if we’re looking for a Boolean algebra associated to $Y$, I can think of crazier things to consider the $P(Y)$ :)

7. • CommentRowNumber7.
   • CommentAuthorTodd_Trimble
   • CommentTimeMay 8th 2010
   • PermaLink
   Author: Todd_Trimble
   Format: MarkdownItex> I wonder if it is of any significance to Boolean algebra that AND, OR, and NOT can all be constructed from NAND (also by NOR). Yeah, I don't know how significant that is. Way back in the day (late 19th, early 20th century), there were oodles of axiom systems for Boolean algebras proposed by people like Schröder and Huntington, with people vying to get away with one operation and one axiom, that sort of thing. I guess more recently there was an outstanding case of one of these axiom systems being proved correct (sound and complete) with the help of an automated theorem prover where humans had failed (the Robbins conjecture or something like that). Anyway, NAND has a distinguished history which you (as an electrical engineer) obviously know about. (Minor rant: I don't like when people say that NAND is all you need. You need to assume nonemptiness as well (provided for by a constant like $\top$), else I wouldn't call it a Boolean algebra (-: .) Categorically, a Boolean algebra is the same thing as a cartesian monoidal *-autonomous category :-D, and I don't think NAND is a totally stupid thing to consider there, despite some derogatory things Mac Lane has written.

   I wonder if it is of any significance to Boolean algebra that AND, OR, and NOT can all be constructed from NAND (also by NOR).

   Yeah, I don’t know how significant that is. Way back in the day (late 19th, early 20th century), there were oodles of axiom systems for Boolean algebras proposed by people like Schröder and Huntington, with people vying to get away with one operation and one axiom, that sort of thing. I guess more recently there was an outstanding case of one of these axiom systems being proved correct (sound and complete) with the help of an automated theorem prover where humans had failed (the Robbins conjecture or something like that). Anyway, NAND has a distinguished history which you (as an electrical engineer) obviously know about.

   (Minor rant: I don’t like when people say that NAND is all you need. You need to assume nonemptiness as well (provided for by a constant like $\top$), else I wouldn’t call it a Boolean algebra (-: .)

   Categorically, a Boolean algebra is the same thing as a cartesian monoidal *-autonomous category :-D, and I don’t think NAND is a totally stupid thing to consider there, despite some derogatory things Mac Lane has written.