{ "cells": [ { "cell_type": "markdown", "source": [ "# Algebra of subgraphs" ], "metadata": {} }, { "outputs": [], "cell_type": "code", "source": [ "using Catlab.Graphs, Catlab.Graphics\n", "using Catlab.Theories, Catlab.CategoricalAlgebra" ], "metadata": {}, "execution_count": 1 }, { "cell_type": "markdown", "source": [ "A *subgraph* of a graph $G$ is a monomorphism $A \\rightarrowtail G$. Because\n", "the category of graphs is a presheaf topos, its subobjects have a rich\n", "algebraic structure, which we will explore in this vignette.\n", "\n", "Throughout the vignette, we will work with subgraphs of the following graph." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"dot\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"1\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"2\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"3\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"4\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"5\")), Catlab.Graphics.Graphviz.Node(\"n6\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"6\")), Catlab.Graphics.Graphviz.Node(\"n7\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"7\")), Catlab.Graphics.Graphviz.Node(\"n8\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"8\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"1\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"2\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"3\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"4\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n6\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"5\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"6\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n8\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"7\"))], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:rankdir => \"LR\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:height => \"0.05\", :margin => \"0\", :shape => \"circle\", :width => \"0.05\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:arrowsize => \"0.5\"))", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "1\n", "\n", "\n", "\n", "n2\n", "\n", "2\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "1\n", "\n", "\n", "\n", "n3\n", "\n", "3\n", "\n", "\n", "\n", "n2->n3\n", "\n", "\n", "2\n", "\n", "\n", "\n", "n4\n", "\n", "4\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "3\n", "\n", "\n", "\n", "n8\n", "\n", "8\n", "\n", "\n", "\n", "n3->n8\n", "\n", "\n", "7\n", "\n", "\n", "\n", "n4->n1\n", "\n", "\n", "4\n", "\n", "\n", "\n", "n5\n", "\n", "5\n", "\n", "\n", "\n", "n6\n", "\n", "6\n", "\n", "\n", "\n", "n5->n6\n", "\n", "\n", "5\n", "\n", "\n", "\n", "n7\n", "\n", "7\n", "\n", "\n", "\n", "n7->n7\n", "\n", "\n", "6\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 2 } ], "cell_type": "code", "source": [ "G = cycle_graph(Graph, 4) ⊕ path_graph(Graph, 2) ⊕ cycle_graph(Graph, 1)\n", "add_edge!(G, 3, add_vertex!(G))\n", "\n", "to_graphviz(G, node_labels=true, edge_labels=true)" ], "metadata": {}, "execution_count": 2 }, { "cell_type": "markdown", "source": [ "## Meet and join\n", "\n", "The basic operations of [meet](https://ncatlab.org/nlab/show/meet) or\n", "intersection ($\\wedge$), [join](https://ncatlab.org/nlab/show/join) or union\n", "($\\vee$), [top](https://ncatlab.org/nlab/show/top) or maximum ($\\top$),\n", "[bottom](https://ncatlab.org/nlab/show/bottom) or minimum ($\\bot$) are all\n", "computed pointwise: separately on vertices and edges.\n", "\n", "Consider the following two subgraphs." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"dot\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n6\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n7\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n8\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n6\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n8\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}())], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:rankdir => \"LR\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:height => \"0.05\", :margin => \"0\", :shape => \"point\", :width => \"0.05\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:arrowsize => \"0.5\"))", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "\n", "\n", "\n", "n2\n", "\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "\n", "\n", "\n", "n3\n", "\n", "\n", "\n", "\n", "n2->n3\n", "\n", "\n", "\n", "\n", "\n", "n4\n", "\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "\n", "\n", "\n", "n8\n", "\n", "\n", "\n", "\n", "n3->n8\n", "\n", "\n", "\n", "\n", "\n", "n4->n1\n", "\n", "\n", "\n", "\n", "\n", "n5\n", "\n", "\n", "\n", "\n", "n6\n", "\n", "\n", "\n", "\n", "n5->n6\n", "\n", "\n", "\n", "\n", "\n", "n7\n", "\n", "\n", "\n", "\n", "n7->n7\n", "\n", "\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 3 } ], "cell_type": "code", "source": [ "(A = Subobject(G, V=1:4, E=[1,2,4])) |> to_graphviz" ], "metadata": {}, "execution_count": 3 }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"dot\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n6\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n7\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n8\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n6\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n8\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\"))], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:rankdir => \"LR\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:height => \"0.05\", :margin => \"0\", :shape => \"point\", :width => \"0.05\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:arrowsize => \"0.5\"))", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "\n", "\n", "\n", "n2\n", "\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "\n", "\n", "\n", "n3\n", "\n", "\n", "\n", "\n", "n2->n3\n", "\n", "\n", "\n", "\n", "\n", "n4\n", "\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "\n", "\n", "\n", "n8\n", "\n", "\n", "\n", "\n", "n3->n8\n", "\n", "\n", "\n", "\n", "\n", "n4->n1\n", "\n", "\n", "\n", "\n", "\n", "n5\n", "\n", "\n", "\n", "\n", "n6\n", "\n", "\n", "\n", "\n", "n5->n6\n", "\n", "\n", "\n", "\n", "\n", "n7\n", "\n", "\n", "\n", "\n", "n7->n7\n", "\n", "\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 4 } ], "cell_type": "code", "source": [ "(B = Subobject(G, V=[2,3,4,7,8], E=[2,3,6,7])) |> to_graphviz" ], "metadata": {}, "execution_count": 4 }, { "cell_type": "markdown", "source": [ "The *join* is defined as left adjoint to the diagonal, making it the *least\n", "upper bound*:\n", "\n", "$$A \\vee B \\leq C \\qquad\\text{iff}\\qquad A \\leq C \\text{ and } B \\leq C.$$" ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"dot\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n6\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n7\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n8\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n6\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n8\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\"))], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:rankdir => \"LR\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:height => \"0.05\", :margin => \"0\", :shape => \"point\", :width => \"0.05\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:arrowsize => \"0.5\"))", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "\n", "\n", "\n", "n2\n", "\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "\n", "\n", "\n", "n3\n", "\n", "\n", "\n", "\n", "n2->n3\n", "\n", "\n", "\n", "\n", "\n", "n4\n", "\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "\n", "\n", "\n", "n8\n", "\n", "\n", "\n", "\n", "n3->n8\n", "\n", "\n", "\n", "\n", "\n", "n4->n1\n", "\n", "\n", "\n", "\n", "\n", "n5\n", "\n", "\n", "\n", "\n", "n6\n", "\n", "\n", "\n", "\n", "n5->n6\n", "\n", "\n", "\n", "\n", "\n", "n7\n", "\n", "\n", "\n", "\n", "n7->n7\n", "\n", "\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 5 } ], "cell_type": "code", "source": [ "A ∨ B |> to_graphviz" ], "metadata": {}, "execution_count": 5 }, { "cell_type": "markdown", "source": [ "Dually, the *meet* is defined as right adjoint to the diagonal, making it the\n", "*greatest lower bound*:\n", "\n", "$$C \\leq A \\text{ and } C \\leq B \\qquad\\text{iff}\\qquad C \\leq A \\wedge B.$$" ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"dot\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n6\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n7\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n8\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n6\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n8\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}())], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:rankdir => \"LR\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:height => \"0.05\", :margin => \"0\", :shape => \"point\", :width => \"0.05\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:arrowsize => \"0.5\"))", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "\n", "\n", "\n", "n2\n", "\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "\n", "\n", "\n", "n3\n", "\n", "\n", "\n", "\n", "n2->n3\n", "\n", "\n", "\n", "\n", "\n", "n4\n", "\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "\n", "\n", "\n", "n8\n", "\n", "\n", "\n", "\n", "n3->n8\n", "\n", "\n", "\n", "\n", "\n", "n4->n1\n", "\n", "\n", "\n", "\n", "\n", "n5\n", "\n", "\n", "\n", "\n", "n6\n", "\n", "\n", "\n", "\n", "n5->n6\n", "\n", "\n", "\n", "\n", "\n", "n7\n", "\n", "\n", "\n", "\n", "n7->n7\n", "\n", "\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 6 } ], "cell_type": "code", "source": [ "A ∧ B |> to_graphviz" ], "metadata": {}, "execution_count": 6 }, { "cell_type": "markdown", "source": [ "## Implication and negation\n", "\n", "The other operations, beginning with implication ($\\Rightarrow$) and negation\n", "($\\neg$) are more interesting because they do not have pointwise formulas.\n", "\n", "*Implication* is defined as the right adjoint to the meet:\n", "\n", "$$C \\wedge A \\leq B \\qquad\\text{iff}\\qquad C \\leq A \\Rightarrow B.$$" ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"dot\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n6\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n7\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n8\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n6\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n8\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\"))], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:rankdir => \"LR\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:height => \"0.05\", :margin => \"0\", :shape => \"point\", :width => \"0.05\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:arrowsize => \"0.5\"))", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "\n", "\n", "\n", "n2\n", "\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "\n", "\n", "\n", "n3\n", "\n", "\n", "\n", "\n", "n2->n3\n", "\n", "\n", "\n", "\n", "\n", "n4\n", "\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "\n", "\n", "\n", "n8\n", "\n", "\n", "\n", "\n", "n3->n8\n", "\n", "\n", "\n", "\n", "\n", "n4->n1\n", "\n", "\n", "\n", "\n", "\n", "n5\n", "\n", "\n", "\n", "\n", "n6\n", "\n", "\n", "\n", "\n", "n5->n6\n", "\n", "\n", "\n", "\n", "\n", "n7\n", "\n", "\n", "\n", "\n", "n7->n7\n", "\n", "\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 7 } ], "cell_type": "code", "source": [ "(A ⟹ B) |> to_graphviz" ], "metadata": {}, "execution_count": 7 }, { "cell_type": "markdown", "source": [ "*Negation* is defined by setting $B = \\bot$ in the above formula:\n", "\n", "$$C \\wedge A = \\bot \\qquad\\text{iff}\\qquad C \\leq \\neg A.$$" ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"dot\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n6\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n7\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n8\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n6\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n8\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}())], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:rankdir => \"LR\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:height => \"0.05\", :margin => \"0\", :shape => \"point\", :width => \"0.05\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:arrowsize => \"0.5\"))", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "\n", "\n", "\n", "n2\n", "\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "\n", "\n", "\n", "n3\n", "\n", "\n", "\n", "\n", "n2->n3\n", "\n", "\n", "\n", "\n", "\n", "n4\n", "\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "\n", "\n", "\n", "n8\n", "\n", "\n", "\n", "\n", "n3->n8\n", "\n", "\n", "\n", "\n", "\n", "n4->n1\n", "\n", "\n", "\n", "\n", "\n", "n5\n", "\n", "\n", "\n", "\n", "n6\n", "\n", "\n", "\n", "\n", "n5->n6\n", "\n", "\n", "\n", "\n", "\n", "n7\n", "\n", "\n", "\n", "\n", "n7->n7\n", "\n", "\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 8 } ], "cell_type": "code", "source": [ "¬A |> to_graphviz" ], "metadata": {}, "execution_count": 8 }, { "cell_type": "markdown", "source": [ "### Induced subgraph as a double negation\n", "\n", "The logic of subgraphs, and of subobjects in presheaf toposes generally, is\n", "not classical. Specifically, subobjects form a [Heyting\n", "algebra](https://ncatlab.org/nlab/show/Heyting+algebra) but not a [Boolean\n", "algebra](https://ncatlab.org/nlab/show/Boolean+algebra). This means that the\n", "law of excluded middle does not hold: in general, $\\neg \\neg A \\neq A$.\n", "\n", "Applying the double negation to a discrete subgraph gives the subgraph induced\n", "by those vertices." ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"dot\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n6\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n7\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n8\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n6\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n8\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}())], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:rankdir => \"LR\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:height => \"0.05\", :margin => \"0\", :shape => \"point\", :width => \"0.05\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:arrowsize => \"0.5\"))", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "\n", "\n", "\n", "n2\n", "\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "\n", "\n", "\n", "n3\n", "\n", "\n", "\n", "\n", "n2->n3\n", "\n", "\n", "\n", "\n", "\n", "n4\n", "\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "\n", "\n", "\n", "n8\n", "\n", "\n", "\n", "\n", "n3->n8\n", "\n", "\n", "\n", "\n", "\n", "n4->n1\n", "\n", "\n", "\n", "\n", "\n", "n5\n", "\n", "\n", "\n", "\n", "n6\n", "\n", "\n", "\n", "\n", "n5->n6\n", "\n", "\n", "\n", "\n", "\n", "n7\n", "\n", "\n", "\n", "\n", "n7->n7\n", "\n", "\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 9 } ], "cell_type": "code", "source": [ "(C = Subobject(G, V=1:4)) |> to_graphviz" ], "metadata": {}, "execution_count": 9 }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"dot\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n6\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n7\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n8\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n6\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n8\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}())], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:rankdir => \"LR\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:height => \"0.05\", :margin => \"0\", :shape => \"point\", :width => \"0.05\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:arrowsize => \"0.5\"))", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "\n", "\n", "\n", "n2\n", "\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "\n", "\n", "\n", "n3\n", "\n", "\n", "\n", "\n", "n2->n3\n", "\n", "\n", "\n", "\n", "\n", "n4\n", "\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "\n", "\n", "\n", "n8\n", "\n", "\n", "\n", "\n", "n3->n8\n", "\n", "\n", "\n", "\n", "\n", "n4->n1\n", "\n", "\n", "\n", "\n", "\n", "n5\n", "\n", "\n", "\n", "\n", "n6\n", "\n", "\n", "\n", "\n", "n5->n6\n", "\n", "\n", "\n", "\n", "\n", "n7\n", "\n", "\n", "\n", "\n", "n7->n7\n", "\n", "\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 10 } ], "cell_type": "code", "source": [ "¬(¬C) |> to_graphviz" ], "metadata": {}, "execution_count": 10 }, { "cell_type": "markdown", "source": [ "## Subtraction and non\n", "\n", "The subojects also form [co-Heyting\n", "algebra](https://ncatlab.org/nlab/show/co-Heyting+algebra) and hence a\n", "bi-Heyting algebra.\n", "\n", "*Subtraction* is defined dually to implication as the left adjoint to the\n", "join:\n", "\n", "$$A \\leq B \\vee C \\qquad\\text{iff}\\qquad A \\setminus B \\leq C.$$" ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"dot\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n6\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n7\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n8\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n6\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n8\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}())], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:rankdir => \"LR\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:height => \"0.05\", :margin => \"0\", :shape => \"point\", :width => \"0.05\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:arrowsize => \"0.5\"))", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "\n", "\n", "\n", "n2\n", "\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "\n", "\n", "\n", "n3\n", "\n", "\n", "\n", "\n", "n2->n3\n", "\n", "\n", "\n", "\n", "\n", "n4\n", "\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "\n", "\n", "\n", "n8\n", "\n", "\n", "\n", "\n", "n3->n8\n", "\n", "\n", "\n", "\n", "\n", "n4->n1\n", "\n", "\n", "\n", "\n", "\n", "n5\n", "\n", "\n", "\n", "\n", "n6\n", "\n", "\n", "\n", "\n", "n5->n6\n", "\n", "\n", "\n", "\n", "\n", "n7\n", "\n", "\n", "\n", "\n", "n7->n7\n", "\n", "\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 11 } ], "cell_type": "code", "source": [ "(A \\ B) |> to_graphviz" ], "metadata": {}, "execution_count": 11 }, { "cell_type": "markdown", "source": [ "*Non* is defined by setting $A = \\top$ in the above formula:\n", "\n", "$$\\top = B \\vee C \\qquad\\text{iff}\\qquad {\\sim} B \\leq C.$$" ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"dot\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n6\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n7\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n8\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n6\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n8\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\"))], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:rankdir => \"LR\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:height => \"0.05\", :margin => \"0\", :shape => \"point\", :width => \"0.05\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:arrowsize => \"0.5\"))", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "\n", "\n", "\n", "n2\n", "\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "\n", "\n", "\n", "n3\n", "\n", "\n", "\n", "\n", "n2->n3\n", "\n", "\n", "\n", "\n", "\n", "n4\n", "\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "\n", "\n", "\n", "n8\n", "\n", "\n", "\n", "\n", "n3->n8\n", "\n", "\n", "\n", "\n", "\n", "n4->n1\n", "\n", "\n", "\n", "\n", "\n", "n5\n", "\n", "\n", "\n", "\n", "n6\n", "\n", "\n", "\n", "\n", "n5->n6\n", "\n", "\n", "\n", "\n", "\n", "n7\n", "\n", "\n", "\n", "\n", "n7->n7\n", "\n", "\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 12 } ], "cell_type": "code", "source": [ "~A |> to_graphviz" ], "metadata": {}, "execution_count": 12 }, { "cell_type": "markdown", "source": [ "### Boundary via non\n", "\n", "A [*boundary*](https://ncatlab.org/nlab/show/co-Heyting+boundary) operator can\n", "be defined using the non operator:\n", "\n", "$$\\partial A := A \\wedge {\\sim} A.$$" ], "metadata": {} }, { "outputs": [ { "output_type": "execute_result", "data": { "text/plain": "Catlab.Graphics.Graphviz.Graph(\"G\", true, \"dot\", Catlab.Graphics.Graphviz.Statement[Catlab.Graphics.Graphviz.Node(\"n1\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n2\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n3\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n4\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:color => \"cornflowerblue\", :label => \"\")), Catlab.Graphics.Graphviz.Node(\"n5\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n6\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n7\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Node(\"n8\", OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:label => \"\")), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n2\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n4\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n1\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n5\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n6\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n7\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}()), Catlab.Graphics.Graphviz.Edge(Catlab.Graphics.Graphviz.NodeID[Catlab.Graphics.Graphviz.NodeID(\"n3\", \"\", \"\"), Catlab.Graphics.Graphviz.NodeID(\"n8\", \"\", \"\")], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}())], OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:rankdir => \"LR\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:height => \"0.05\", :margin => \"0\", :shape => \"point\", :width => \"0.05\"), OrderedCollections.OrderedDict{Symbol, Union{String, Catlab.Graphics.Graphviz.Html}}(:arrowsize => \"0.5\"))", "image/svg+xml": [ "\n", "\n", "\n", "\n", "\n", "\n", "G\n", "\n", "\n", "\n", "n1\n", "\n", "\n", "\n", "\n", "n2\n", "\n", "\n", "\n", "\n", "n1->n2\n", "\n", "\n", "\n", "\n", "\n", "n3\n", "\n", "\n", "\n", "\n", "n2->n3\n", "\n", "\n", "\n", "\n", "\n", "n4\n", "\n", "\n", "\n", "\n", "n3->n4\n", "\n", "\n", "\n", "\n", "\n", "n8\n", "\n", "\n", "\n", "\n", "n3->n8\n", "\n", "\n", "\n", "\n", "\n", "n4->n1\n", "\n", "\n", "\n", "\n", "\n", "n5\n", "\n", "\n", "\n", "\n", "n6\n", "\n", "\n", "\n", "\n", "n5->n6\n", "\n", "\n", "\n", "\n", "\n", "n7\n", "\n", "\n", "\n", "\n", "n7->n7\n", "\n", "\n", "\n", "\n", "\n" ] }, "metadata": {}, "execution_count": 13 } ], "cell_type": "code", "source": [ "(A ∧ ~A) |> to_graphviz" ], "metadata": {}, "execution_count": 13 } ], "nbformat_minor": 3, "metadata": { "language_info": { "file_extension": ".jl", "mimetype": "application/julia", "name": "julia", "version": "1.6.4" }, "kernelspec": { "name": "julia-1.6", "display_name": "Julia 1.6.4", "language": "julia" } }, "nbformat": 4 }