Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: Boolean Algebra

Henry Story (Apr 28 2020 at 15:32):

Question: Where $\overline{A}$ and $\overline{B}$ are boolean algebras, are the atoms of $\overline{A}+\overline{B}$ the elements in $Set$ of $A \times B$ or $A + B$?

In the Category $Set$ we have types $A, B, C$. The category $Set^{op}$ is isomorphic I believe to the Category of Complete Atomic Boolean Algebras CABA. In order to distinguish types from $Set$ and those from CABA I'll use an overline to map types from $Set$ to CABA.

I have an answer on Math StackExchange which seems to indicate the that the atoms of $\overline{A}+\overline{B}$ are the elements of $A \times B$ ie, ordered pairs. But I can't work which category is being spoken of. It's a bit confusing because this would mean that in general $\overline{A}+\overline{B}$ would be much larger than $\overline{A} \times \overline{B}$. It is also a bit confusing because it one would need to work out how to do case analysis on $\overline{A} + \overline{B}$ if its atoms are pairs, and how to do projections on $\overline{A} \times \overline{B}$ if its atoms are elements from either elements from $A$ or $B$....

So if in $Set$ $A = \{a_1, a_2, a_3\}$ and $B = \{b_1, b_2, b_3\}$ then in CABA $\overline{A}$ will have the elements as $A$ as atoms and similarly for $B$. But what are the atoms of $\overline{A}+\overline{B}$ in CABA? Will it be {$\overleftarrow{a_1}, \overleftarrow{a_2}, \overleftarrow{a_3}, \overrightarrow{b_1} \overrightarrow{b_2}, \overrightarrow{b_3}$} (where I use the arrows to indicate right or left injections). Ie will it be the elements of $A+B$ in Set? But $A \times B$ in set corresponds in CABA $\overline{A \times B} = \overline{A} + \overline{B}$.

Pastel Raschke (Apr 28 2020 at 15:58):

(deleted)

Pastel Raschke (Apr 28 2020 at 16:02):

with LEM CABAs are powersets, though i think you know this

https://ncatlab.org/nlab/show/complete+Boolean+algebra#cabas
https://ncatlab.org/nlab/show/Set#OppositeCategory

A• + B• = (A × B)•, and this is bigger than A• × B• = (A + B)•. what you need to do is look at how products and coproducts are defined in BoolAlg.

https://ncatlab.org/nlab/show/BoolAlg

Pastel Raschke (Apr 28 2020 at 16:08):

er, CompAtomBoolAlg?

Pastel Raschke (Apr 28 2020 at 16:31):

complete boolean maps preserve all meets and joins, i'm not sure what conditions atomicity imposes.

i believe maps A• -> A• + B• send atoms a to any atom (a,_), and maps A• × B• -> A• send atoms injl(a) to a and injr(b) to... bottom, i guess? again, i'm not sure.

Henry Story (Apr 28 2020 at 18:02):

Pastel Raschke said:

i believe maps $\overline{A} \to \overline{A} + \overline{B}$ send atoms $a \in A$ to any atom $(a, x) \in(A,B)$, and maps $\overline{A} \times \overline{B} \to \overline{A}$ send atoms $injl(a) \in A+B$ to $a \in A$ and $injr(b)$ to... $\bot$, i guess? again, i'm not sure.

Yes, that seems to make sense.
It would be nice to find it explained more fully in a textbook or something. Usually a lot of time is taken to explain how disjunction/conjunction works within a boolean algebra, not between boolean algebras.

Reid Barton (Apr 28 2020 at 18:03):

The maps $\overline A \to \overline A + \overline B$ usually don't send atoms to atoms at all.

Henry Story (Apr 28 2020 at 18:16):

Just for context, this is what I had come up with for a diagram for the definition of ⋁ in a complement topos. Here both product and sum are isomorphic as they 2+2=2*2=4, but I still wanted to make sure I understand the difference. (explanation here)
Co-product-BA.jpg

Reid Barton (Apr 28 2020 at 18:30):

If I am understanding this diagram correctly, it looks right to me.

Henry Story (Apr 28 2020 at 18:34):

I still need to draw out the co-topos example diagram in CABA for $\land$ with the morphism $[ \langle \bot, id \rangle, \langle id, \bot \rangle ]: \mho + \mho \to \mho \times \mho$, which will require me to understand how products and coproduces interact in CABA.
product.jpg

Henry Story (Apr 28 2020 at 18:52):

(I should perhaps change all the 0s and 1s in the diagram so that ⋁ works more like or in logic, where here we are trying to falsify a statement.)

Henry Story (Apr 28 2020 at 18:54):

well actually I need to understand what $[\bot, \bot]: \mho + \mho \to 0$ means.
I filled the diagram in without taking that into account.

Henry Story (Apr 28 2020 at 20:33):

So it looks like I got it right intuitively, but this diagram shows how it ties in with the rules given by @Pastel Raschke . I started with the $[\bot, \bot]: \mho + \mho \to 0$. Then I found that the co-characteristic function from $\mho \to \mho + \mho$ takes $1$ to the highest point, where everything below it in blue is sent to $\bot$. $0$ sends everything above it to $\top$.
Since this is the dual of a topos, it tells us how to falsify the conjunction of which it is a dual: namely anywhere where we can falsify either disjuncts. The diagram should be a pushout
Co=Product.jpg

Pastel Raschke (Apr 28 2020 at 22:18):

@Reid Barton would the statement be correct if i had said the injections, corresponding to the projections of the product in Set?

Henry Story (Apr 29 2020 at 09:04):

I think I'll need to work my way up to what $[ \langle \bot, id \rangle, \langle id, \bot \rangle ]: \mho + \mho \to \mho \times \mho$ means in CABA from first principles.... It is too difficult otherwise. This will take some time, as I have to do some completely different stuff.

Henry Story (May 02 2020 at 07:29):

Anyone know of a good paper or resource that explains (co)products, (co)equalizers, pullbacks, pushouts, for Complete Atomic Boolean Algebras? (Something a little more general would do too, as long as I can apply it to CABAs).

sarahzrf (May 02 2020 at 07:40):

/me runs a paper on universal constructions in Set thru a mirror

Henry Story (May 02 2020 at 07:48):

sarahzrf said:

/me runs a paper on universal constructions in Set thru a mirror

That is very useful as a way of testing what one comes up with. But it is takes a lot of time :-/ CABA's explode in complexity very quickly. It also looks very different: I don't know what kind of mirror I'd need ;-)
(co)Product.jpg

Henry Story (May 02 2020 at 08:59):

I think I got the extra trick I was not using. Always look at a function $f: A \to B$ in Set then look at the inverse $f^{-1}: \mathscr{P}(B) \to \mathscr{P}(A)$ to check the construction in CABA.

Henry Story (May 03 2020 at 12:45):

The above trick helped me finish the complement topos diagram for conjunction in CABA. The thick solid red lines are the lines I calculated (a couple of different ways). Those allowed me to specify the orange lines. The thick orange lines are those that are active in the pushout. The arrow $(0,0) \mapsto \bot$ was the only way to get the other arrows to abide by the law of morphisms respecting limits. I added Injection from and projection to $\mho$ to help me work out what the elements of $\mho + \mho$ and $\mho \times \mho$ meant, so as to work out how the case analysis worked. :sweat:
It seems to show (as expected) that in order to defat a disjunction one needs to refute both sides.
Pushout diagram for conjunction in the complement topos of Boolean algebras