Not signed in (Sign In)

Not signed in

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

  • Sign in using OpenID

Site Tag Cloud

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 galois-theory 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 homology homotopy homotopy-theory homotopy-type-theory index-theory integration integration-theory itex 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 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 science set set-theory sheaf simplicial space spin-geometry stable-homotopy-theory string string-theory superalgebra supergeometry svg symplectic-geometry synthetic-differential-geometry terminology theory topology topos topos-theory type type-theory universal variational-calculus

Vanilla 1.1.10 is a product of Lussumo. More Information: Documentation, Community Support.

Welcome to nForum
If you want to take part in these discussions either sign in now (if you have an account), apply for one now (if you don't).
    • CommentRowNumber1.
    • CommentAuthorTodd_Trimble
    • CommentTimeMay 7th 2010

    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 YY and XX and turning it into a function, YPXY \to P X. And yes, given the original function f:XYf: X \to Y, what you’ve created is indeed the fiber map YPXY \to P X, taking yYy \in Y to its preimage f 1(y)PXf^{-1}(y) \in P X.

    And, putting a piece of the puzzle together, notice the power set PXP X is a finite Boolean algebra (I’m assuming we’re working with finite sets XX, YY). 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. XX is just a set right now; it has no extra structure. So there is no given map PXXP X \to X which would take a union. (And let’s not try to do anything artificial like manufacture such a structure on XX 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:XYf: X \to Y, the opposite relation f 1f^{-1} (preimage), which is in the opposite direction. Then you had the bright idea of turning this into a concrete function f 1:YPXf^{-1}: Y \to P X. And PXP X is a Boolean algebra, so this may be encouraging.

    Some notes: the well-definedness of ff means exactly that no two fibers intersect: that if yyy \neq y', then f 1(y)f 1(y)=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:YPXf^{-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, YY 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 YY exactly – that would be artificial – but getting a Boolean algebra out of YY in some way, and getting a Boolean algebra homomorphism out of the situation.

    Do what comes naturally…

    • CommentRowNumber2.
    • CommentAuthorEric
    • CommentTimeMay 8th 2010

    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)f 1(y j)=δ i,j(f 1(y i))f^{-1}(y_i) \cap f^{-1}(y_j) = \delta_{i,j}(f^{-1}(y_i))

    where δ i,i\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}\{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 XX and look at endomorphisms f:XXf:X\to X. In fact, it might even be good to start with endomorphisms on X={0,1}X = \{0,1\}.

    There are only two endomorphisms I:XXI:X\to X and S:XXS:X\to X with S 2=IS^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=II^{op} = I and S op=SS^{op} = S.

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

    • CommentRowNumber3.
    • CommentAuthorDavidRoberts
    • CommentTimeMay 8th 2010

    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.

    • CommentRowNumber4.
    • CommentAuthorEric
    • CommentTimeMay 8th 2010

    Oh right. Thanks

    • CommentRowNumber5.
    • CommentAuthorTodd_Trimble
    • CommentTimeMay 8th 2010
    • (edited May 8th 2010)

    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}\{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 SS is any set, then the set of all functions f:S{0,1}f: S \to \{0, 1\} forms a Boolean algebra, by dint of the Boolean algebra structure that already exists on {0,1}\{0, 1\}. For, if ff and gg are such functions, then define fgf \vee g by the rule (fg)(s)=f(s)g(s)(f \vee g)(s) = f(s) \vee g(s), where the right side is interpreted in the Boolean algebra {0,1}\{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}S = \{0, 1\}, and you get the 4-element Boolean algebra of endofunctions on {0,1}\{0, 1\}. (But I think thinking about general endofunctions on general SS 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{0,1}f: S \to \{0, 1\} is the same thing, i.e., is isomorphic to, the Boolean algebra P(S)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})hom(S, \{0, 1\}) and P(S)P(S)?

    Anyway, to get back to the discussion: you have in your hand a nice function f 1():YP(X)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 YY somehow.

    What would you try?

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

    • CommentRowNumber6.
    • CommentAuthorEric
    • CommentTimeMay 8th 2010

    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}\{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{0,1}F:S\to\{0,1\}, e.g.

    F=ABC¯+AC+B¯C 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{0,1}f: S \to \{0, 1\} is the same thing, i.e., is isomorphic to, the Boolean algebra P(S)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)P(X) is a Boolean algebra associated to XX, then if we’re looking for a Boolean algebra associated to YY, I can think of crazier things to consider the P(Y)P(Y) :)

    • CommentRowNumber7.
    • CommentAuthorTodd_Trimble
    • CommentTimeMay 8th 2010

    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.