{
"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"
]
},
"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"
]
},
"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"
]
},
"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"
]
},
"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"
]
},
"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"
]
},
"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"
]
},
"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"
]
},
"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"
]
},
"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"
]
},
"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"
]
},
"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"
]
},
"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.8.3"
},
"kernelspec": {
"name": "julia-1.8",
"display_name": "Julia 1.8.3",
"language": "julia"
}
},
"nbformat": 4
}