Editing Power set (section)

== Power object ==
{{unsourced|section|date=February 2025}}
A set can be regarded as an [[algebra (universal algebra)|algebra]] having no nontrivial operations or defining equations.  From this perspective, the concept of the power set of {{math|''X''}} as the set of all subsets of {{math|''X''}} generalizes naturally to the set to all subalgebras of an [[algebraic structure]] or algebra.

The power set of a set, when ordered by inclusion, is always a complete atomic Boolean algebra, and every complete atomic Boolean algebra arises as the [[lattice (order)|lattice]] of all subsets of some set. The generalization to arbitrary algebras is that the set of subalgebras of an algebra, again ordered by inclusion, is always an [[algebraic lattice]], and every algebraic lattice arises as the lattice of subalgebras of some algebra.<ref>{{cite journal
 | last1 = Birkhoff
 | first1 = Garrett
 | last2 = Frink
 | first2 = Orrin, Jr.
 | title = Representations of Lattices by Sets
 | journal = Transactions of the American Mathematical Society
 | volume = 64
 | issue = 2
 | pages = 299–316
 | year = 1948
 | doi = 10.1090/S0002-9947-1948-0027263-2
 | url = https://www.ams.org/journals/tran/1948-064-02/S0002-9947-1948-0027263-2/S0002-9947-1948-0027263-2.pdf
}}
</ref> So in that regard, subalgebras behave analogously to subsets.

However, there are two important properties of subsets that do not carry over to subalgebras in general.  First, although the subsets of a set form a set (as well as a lattice), in some classes it may not be possible to organize the subalgebras of an algebra as itself an algebra in that class, although they can always be organized as a lattice.  Secondly, whereas the subsets of a set are in bijection with the functions from that set to the set {{math|1={{mset|0, 1}} = 2}}, there is no guarantee that a class of algebras contains an algebra that can play the role of {{math|2}} in this way.

Certain classes of algebras enjoy both of these properties.  The first property is more common; the case of having both is relatively rare.  One class that does have both is that of [[multigraph]]s.  Given two multigraphs {{math|''G''}} and {{math|''H''}}, a [[homomorphism]] {{math|''h'' : ''G'' → ''H''}} consists of two functions, one mapping vertices to vertices and the other mapping edges to edges.  The set {{math|''H''<sup>''G''</sup>}} of homomorphisms from {{math|''G''}} to {{math|''H''}} can then be organized as the graph whose vertices and edges are respectively the vertex and edge functions appearing in that set.  Furthermore, the subgraphs of a multigraph {{math|''G''}} are in bijection with the graph homomorphisms from {{math|''G''}} to the multigraph {{math|Ω}} definable as the [[complete graph|complete directed graph]] on two vertices (hence four edges, namely two self-loops and two more edges forming a cycle) augmented with a fifth edge, namely a second self-loop at one of the vertices.  We can therefore organize the subgraphs of {{math|''G''}} as the multigraph {{math|Ω<sup>''G''</sup>}}, called the '''power object''' of {{math|''G''}}.

What is special about a multigraph as an algebra is that its operations are unary.  A multigraph has two sorts of elements forming a set {{math|''V''}} of vertices and {{math|''E''}} of edges, and has two unary operations {{math|''s'', ''t'' : ''E'' → ''V''}} giving the source (start) and target (end) vertices of each edge.  An algebra all of whose operations are unary is called a [[presheaf]].  Every class of presheaves contains a presheaf {{math|Ω}} that plays the role for subalgebras that {{math|2}} plays for subsets.  Such a class is a special case of the more general notion of elementary [[topos]] as a [[category (mathematics)|category]] that is [[closed category|closed]] (and moreover [[cartesian closed category|cartesian closed]]) and has an object {{math|Ω}}, called a [[subobject classifier]].  Although the term "power object" is sometimes used synonymously with [[exponential object]] {{math|{{itco|''Y''}}<sup>''X''</sup>}}, in topos theory {{math|''Y''}} is required to be {{math|Ω}}.