\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage[all]{xy} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics,amsmath,amssymb} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{latexsym} \usepackage{epsf} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.5in} \setlength{\textheight}{8.9in} \newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{defin}[theorem]{Definition} \newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}} \newtheorem{examp}[theorem]{Example} \newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}} \newtheorem{rema}[theorem]{Remark} \newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}} \begin{center} \vskip 1cm{\LARGE\bf Binary Relations on the Power Set \\ \vskip .1in of an $n$-Element Set } \vskip 1cm \large Ross La Haye \\ 955 Coppens Road \\ Green Bay, WI 54303 \\ USA \\ \href{mailto:rlahaye@new.rr.com}{\tt rlahaye@new.rr.com} \end{center} \vskip .1in \begin{abstract} We define six binary relations on the power set of an $n$-element set and describe their basic structure and interrelationships. An auxiliary relation is noted that will assist in determining the cardinalities of each. We also indicate an eighth relation that may be of interest. We conclude the second section by computing several quantities related to walks in the graph of the sixth relation. In the third section we turn our attention to the basic structure and cardinalities of the auxiliary relation noted in section two and several additional relations. We also compute seven sums associated with these relations and indicate connections four relations have with Wieder's \textit{conjoint} and \textit{disjoint} $k$-\textit{combinations}. \end{abstract} \section{Introduction} %\addcontentsline{toc}{section}{Introduction} Combinatorial interest has generally focused on the enumeration of various \emph{types} of relations or associated structures such as topologies and graphs. In this paper we will be interested in the generally more tractable problem of defining and enumerating several binary relations on the power set of an $n$-element set and computing various quantities associated with them. We will conclude by indicating connections four relations have with Wieder's \textit{conjoint} and \textit{disjoint} $k$-\textit{combinations}. The motivation here is to suggest some ways in which sets of $k$-subsets of some set may be studied under the rubric of asymmetric $k$-ary relations on the same. To the author's knowledge, the results of this paper or related results do not appear in the existing literature, except when so noted. \section{The six initial relations} \label{sec:1} \subsection{Definitions and structure} \label{sec:1.1} Let $P(A)$ be the power set of an $n$-element set $A$\footnote{For convenience we may assume that $A=\left\{1,2,3,\ldots,n\right\}$.}. Then $B= P(A)\times P(A)$ is just the Cartesian product of $P(A)$ with itself and the following binary relations on $P(A)$ are, of course, just subsets of $B$: \begin{itemize} \item[] $R_{0} = \left\{(x,y):x,y\in P(A), x \subseteq y \vee y \subseteq x\right\}$, \item[] $R_{1} = \left\{(x,y):x,y\in P(A), x \subset y \vee y \subset x\right\}$, \item[] $R_{2} = \left\{(x,y):x,y\in P(A), x \prec y \vee y \prec x\right\}$, \item[] $R_{3} = \left\{(x,y):x,y\in P(A), x \subseteq y\right\}$, \item[] $R_{4} = \left\{(x,y):x,y\in P(A), x \subset y\right\}$, and \item[] $R_{5} = \left\{(x,y):x,y\in P(A), x \prec y\right\}$. \end{itemize} Note that $x\prec y$ denotes that $x\subset y$ and $|y|-|x|=1$ \cite{Davey}. As $R_{3}$ has been defined to be a \textit{partial order} relation on $P(A)$, this just means that $R_{5}$ is the corresponding \textit{covering} relation \cite{Davey}. $R_{4}$ is the corresponding \textit{strict order} \cite{Davey}. Also, observe that $B$ is a reflexive, symmetric, and transitive relation on $P(A)$ and so is an \textit{equivalence} relation on the same. \begin{table}[ht] \centering \begin{tabular}[b]{lcccccc} \hline & $R_{0}$ & $R_{1}$ & $R_{2}$ & $R_{3}$ & $R_{4}$ & $R_{5}$\\ \hline reflexive & yes & no & no & yes & no & no\\ irreflexive & no & yes & yes & no & yes & yes \\ symmetric & yes & yes & yes & no & no & no \\ asymmetric & no & no & no & no & yes & yes \\ antisymmetric & no & no & no & yes & yes & yes \\ transitive & no & no & no & yes & yes & no \\ intransitive & no & no & yes & no & no & yes \\ \hline \end{tabular} \caption{Basic properties of $R_{0}$ -- $R_{5}$} \label{tab:Table1} \end{table} Tables \ref{tab:Table1}, \ref{tab:Table2}, and \ref{tab:Table3} list some basic information with regard to $R_{0}$ -- $R_{5}$. While entries $=, \subseteq$, and $\supseteq$ in Table \ref{tab:Table3} are easily enough understood, we explain an entry of $\cap$ as follows. Given a row relation $R_{r}$ and a column relation $R_{c}$ in Table \ref{tab:Table3}, an entry of $\cap$ indicates that, while $R_{r} \not\subseteq R_{c}$ and $R_{c} \not\subseteq R_{r}$, we still have that $R_{r} \cap R_{c} \neq \emptyset$. \begin{table}[ht] \centering \begin{tabular}[b]{lcccccc} \hline & $R_{0}$ & $R_{1}$ & $R_{2}$ & $R_{3}$ & $R_{4}$ & $R_{5}$ \\ \hline reflexive closure & & $R_{0}$ & & & $R_{3}$ & \\ reflexive reduction & $R_{1}$ & & & $R_{4}$ & & \\ symmetric closure & & & & $R_{0}$ & $R_{1}$ & $R_{2}$ \\ symmetric reduction & $R_{3}$ & $R_{4}$ & $R_{5}$ & & & \\ transitive closure & & & $R_{1}$ & & & $R_{4}$ \\ transitive reduction & & $R_{2}$ & & & $R_{5}$ & \\ \hline \end{tabular} \caption{Closures and reductions of $R_{0}$ -- $R_{5}$} \label{tab:Table2} \end{table} \begin{table}[ht] \centering \begin{tabular}[b]{lcccccc} \hline & $R_{0}$ & $R_{1}$ & $R_{2}$ & $R_{3}$ & $R_{4}$ & $R_{5}$ \\ \hline $R_{0}$ & = & $\supseteq$ & $\supseteq$ & $\supseteq$ & $\supseteq$ & $\supseteq$ \\ $R_{1}$ & $\subseteq$ & = & $\supseteq$ & $\cap$ & $\supseteq$ & $\supseteq$ \\ $R_{2}$ & $\subseteq$ & $\subseteq$ & = & $\cap$ & $\cap$ & $\supseteq$ \\ $R_{3}$ & $\subseteq$ & $\cap$ & $\cap$ & = & $\supseteq$ & $\supseteq$ \\ $R_{4}$ & $\subseteq$ & $\subseteq$ & $\cap$ & $\subseteq$ & = & $\supseteq$ \\ $R_{5}$ & $\subseteq$ & $\subseteq$ & $\subseteq$ & $\subseteq$ & $\subseteq$ & = \\ \hline \end{tabular} \caption{Inclusion and intersection relationships, $R_{0}$ -- $R_{5}$} \label{tab:Table3} \end{table} \vspace{8pt} \noindent\textbf{Examples}. With $A=\left\{1,2\right\}$, $P(A)=\left\{\emptyset,\left\{1\right\},\left\{2\right\},\left\{1,2\right\}\right\}$, and \begin{itemize} \item[] $R_{4} = \left\{(\emptyset,\left\{1\right\}),(\emptyset,\left\{2\right\}),(\emptyset,\left\{1,2\right\}),(\left\{1\right\},\left\{1,2\right\}),(\left\{2\right\},\left\{1,2\right\})\right\}$, \item[] $R_{5} = \left\{(\emptyset,\left\{1\right\}),(\emptyset,\left\{2\right\}),(\left\{1\right\},\left\{1,2\right\}),(\left\{2\right\},\left\{1,2\right\})\right\}$. \end{itemize} \vspace{8pt} \noindent Define the partial order relation \begin{itemize} \item[] $E=\left\{(p,q):p,q\in \left\{R_{0},R_{1},\ldots ,R_{5}\right\}, p\subseteq q\right\}$ \end{itemize} so that $G$ may be defined to be the (directed) graph of the covering relation corresponding to $E$. Then most of the information in Tables \ref{tab:Table1}, \ref{tab:Table2}, and \ref{tab:Table3} is illustrated in Figure \ref{fig:Figure1}. Observe that we have labelled the edges of $G$ in the diagram to indicate the closure and reduction relationships that obtain between the vertices of this graph, i.e., $R_{0},R_{1}$ etc. For example, an edge labelled \textit{s} and directed from vertex $u$ to vertex $v$ indicates that $u$ is the symmetric reduction of $v$ (and $v$ the symmetric closure of $u$); we can also deduce from this that $v$ is a symmetric relation. Similar observations hold for the other two edge labels. Finally, note that if a walk exists from $u$ to $v$, then $u\subseteq v$. However, if there is neither a walk from $u$ to $v$ nor a walk from $v$ to $u$, then, while $u \not\subseteq v$ and $v \not\subseteq u$, it is still the case that $u \cap v \neq \emptyset$. \begin{figure}[htbp] \centering $\xymatrix{& R_{0} \\ R_{3}\ar[ur]^s & & R_{1}\ar[ul]^r \\ & R_{4}\ar[ul]^r \ar[ur]^s & & R_{2}\ar[ul]^t \\ & & R_{5} \ar[ul]^t \ar[ur]^s}$ \caption{Hasse diagram of $G$} \label{fig:Figure1} \end{figure} \subsection{The cardinalities of $R_{0}$ -- $R_{5}$} In determining the cardinalities of $R_{0}$ -- $R_{5}$ it will be useful to recall \cite{Benjamin} that \begin{equation} \label{eq:Eq1} |P(A)| = 2^n. \end{equation} To see this, consider that in enumerating a subset of $A$, i.e., an element of $P(A)$, we decide on a case by case basis which elements of $A$ to include in the subset. As there are 2 outcomes possible for each of the elements of $A$ -- include in the subset or exclude from the subset -- and $n$ elements of $A$, there are $2^n$ subsets of $A$ altogether. Now recall that the $(x,y)\in R_{3}$ are such that $x\subseteq y$. It is not hard to see that enumerating each subset of each subset of $A$ will enumerate the elements of $R_{3}$. We may do so by deciding on a case by case basis which elements of $A$ to \begin{enumerate} \item include in both $x$ and $y$, \item exclude from both $x$ and $y$, or \item exclude from $x$ and include in $y$. \end{enumerate} As there are 3 outcomes possible for each of the $n$ elements of $A$, we see that \begin{equation} \label{eq:Eq2} |R_{3}| = 3^n. \end{equation} The cardinalities of $R_{0}$, $R_{1}$, and $R_{4}$ are determined as follows. Let $R^{-1}_{i}$ denote the \textit{inverse} relation of $R_{i}$ \cite{Rosen}. Then, define \begin{itemize} \item[] $R_{11}=\left\{(x,y):x,y\in P(A), x=y\right\}=\left\{(x,x):x\in P(A)\right\}$. \end{itemize} It should be clear that $R_{11}\subset R_{3}$. Moreover, it is obvious that \begin{equation} |R_{11}| = 2^n. \label{eq:Eq3} \end{equation} It then follows that \begin{equation} |R_{0}| = 2\cdot 3^n - 2^n, \label{eq:Eq4} \end{equation} as, by definition, $R_{0}=R_{3}\cup R^{-1}_{3}$, and $R_{11}$ should only be counted once in this union. Similarly, we see that \begin{equation} |R_{4}| = 3^n - 2^n, \label{eq:Eq5} \end{equation} as, by definition, $R_{4}=R_{3}\setminus R_{11}$. Furthermore, \begin{equation} |R_{1}| = 2\cdot(3^n - 2^n), \label{eq:Eq6} \end{equation} as, by definition, $R_{1}=R_{4}\cup R^{-1}_{4}$. Recall that for each $(x,y)\in R_{5}$, $x\subset y$ and $|y|-|x| = 1$. This suggests the following enumeration of this relation. First, select 1 of the $n$ elements of $A$ to add to $x$ (to get $y$). $x$ is then constructed from the remaining elements of $A$, and this can be done in $2^{n-1}$ ways. As $y$ is now completely determined, we have that \begin{equation} |R_{5}| = n\cdot 2^{n-1}. \label{eq:Eq7} \end{equation} It is then easy to see that \begin{equation} |R_{2}| = n\cdot 2^n, \label{eq:Eq8} \end{equation} as, by definition, $R_{2}=R_{5}\cup R^{-1}_{5}$. \vspace{8pt} \noindent Before concluding here we note one additional relation that may be of interest: \begin{itemize} \item[] $R_{6} = R_{4}\setminus R_{5}$. \end{itemize} $R_{6}$ is an irreflexive, asymmetric, antisymmetric, and transitive relation and so a strict order. We also note that this relation is a proper subset of $R_{0}$, $R_{1}$, $R_{3}$, and $R_{4}$. Finally, that \begin{equation} |R_{6}| = 3^n - 2^n - n\cdot 2^{n-1} \label{eq:Eq9} \end{equation} is easily deduced from Eqns.\ \eqref{eq:Eq5} and \eqref{eq:Eq7}. \begin{table}[ht] \centering \begin{tabular}[b]{ccccc} \hline Relation & Cardinality & Sequence & Sequence & Sequence \\ \hline $R_{0}$ & $2\cdot 3^n - 2^n$ & \seqnum{A027649}$(n)$ & \seqnum{A090888}$(n,3)$ & \\ $R_{1}$ & $2\cdot(3^n - 2^n)$ & \seqnum{A056182}$(n)$ & & \\ $R_{2}$ & $n\cdot 2^n$ & \seqnum{A036289}$(n)$ & & \\ $R_{3}$ & $3^n$ & \seqnum{A000244}$(n)$ & \seqnum{A090888}$(n,2)$ & \seqnum{A112626}$(n,0)$ \\ $R_{4}$ & $3^n - 2^n$ & \seqnum{A001047}$(n)$ & \seqnum{A090888}$(n,1)$ & \seqnum{A112626}$(n,1)$ \\ $R_{5}$ & $n\cdot 2^{n-1}$ & \seqnum{A001787}$(n)$ & \seqnum{A090802}$(n,1)$ & \\ $R_{6}$ & $3^n - 2^n - n\cdot 2^{n-1}$ & \seqnum{A066810}$(n)$ & & \seqnum{A112626}$(n,2)$ \\ \hline \end{tabular} \caption{The cardinalities of $R_{0}$ -- $R_{6}$} \label{tab:Table4} \end{table} \vspace{8pt} Table \ref{tab:Table4} lists the cardinalities of $R_{0}$ -- $R_{6}$ with references to the corresponding integer sequences in Sloane's {\it Encyclopedia} \cite{Sloane}. \subsection{Walks and lengths of walks in the graph of $R_{5}$} \label{sec:1.3} Let $H$ be the (directed) graph of $R_{5}$ and recall that $P(A)$ is the power set of an $n$-element set $A$. Also, let $C(n,k)$ denote the \textit{binomial coefficient}, i.e., the number of ways to select $k$ elements from an $n$-element set. We begin by counting the number of $k$-length walks $w(n,k)$ in $H$ \cite{Rosen}. As the vertices of $H$ are just elements of $P(A)$, a little thought shows that a $k$-length walk in $H$ begins at some $x\in P(A)$ and adds $k$ elements of $A$ not in $x$ to $x$, where the order of addition is important. We may enumerate such a walk by first selecting the $k$ elements to add to $x$. There are $C(n,k)$ ways to do this. This then leaves $2^{n-k}$ ways to construct $x$. Once constructed, we then just need to decide which of the $k!$ ways we will add the $k$ selected elements in. Hence \begin{equation} w(n,k)=k!\cdot C(n,k)\cdot 2^{n-k}. \label{eq:Eq10} \end{equation} The total number of walks $W(n)$ in $H$ is then just given by \begin{equation} W(n)=\sum_{0\leq k\leq n}w(n,k)=\sum_{0\leq k\leq n}k!\cdot C(n,k)\cdot 2^{n-k}. \label{eq:Eq11} \end{equation} \begin{figure}[h] \centering $\xymatrix{& \left\{1,2,3\right\} \\ \left\{1,2\right\}\ar[ur] & \left\{1,3\right\} \ar[u] & \left\{2,3\right\}\ar[ul] \\ \left\{1\right\}\ar[u] \ar[ur] & \left\{2\right\} \ar[ul] \ar[ur] & \left\{3\right\}\ar[ul] \ar[u] \\ & \emptyset \ar[ul] \ar[u] \ar[ur]}$ \caption{Hasse diagram of $H$ with $A=\left\{1,2,3\right\}$} \label{fig:Figure2} \end{figure} Now let $l(n,k)$ denote the total length of all $k$-length walks in $H$. It is not hard to see that \begin{equation} l(n,k)=\frac{k}{k!}\cdot w(n,k) = k\cdot C(n,k)\cdot 2^{n-k} \label{eq:Eq12} \end{equation} as in computing $l(n,k)$ we are interested in determining only \emph{that} in fact a $k$-length walk exists in $H$ and accounting for the length of this walk, and this is easily accomplished by dividing $w(n,k)$ by $k!$ and then, of course, just multiplying the result by $k$. The total length of all walks $L(n)$ in $H$ is then just given by \begin{equation} L(n)=\sum_{0\leq k\leq n}l(n,k)=\sum_{0\leq k\leq n}k\cdot C(n,k)\cdot 2^{n-k}. \label{eq:Eq13} \end{equation} $w(n,k)$ is given by \seqnum{A090802}$(n,k)$ in Sloane's {\it Encyclopedia} \cite{Sloane}, while $W(n)$ is given by \seqnum{A010842}$(n)$. There is no sequence listed that gives $l(n,k)$. However, $L(n)$ is given by \seqnum{A027471}$(n+1)$. \vspace{8pt} We conclude this section by observing that the number of 1-length walks in $H$ is just $1!\cdot C(n,1)\cdot 2^{n-1} = n\cdot 2^{n-1}$. It should be clear that the enumeration of these walks is fundamentally equivalent to the enumeration of $R_{5}$ given above \eqref{eq:Eq7}. \section{The additional relations} \label{sec:2} \subsection{Definitions and structure} \label{sec:2.1} As before, let $P(A)$ be the power set of an $n$-element set $A$. Here we will be chiefly interested in five pairwise disjoint relations on $P(A)$ whose union we define to be $R_{35}$. It should be clear that the cardinality of $R_{35}$ is easily computed as the sum of the cardinalities of these five relations. Moreover, we will be able to easily define and determine the cardinalities of the $2^5 - 7=25$ remaining possible unions of the relations (the empty union is excluded, of course). So we define \begin{itemize} \item[] $R_{7} = \left\{(x,y):x,y\in P(A),x\subset y\wedge x\cap y = \emptyset\right\}$, and \item[] $R_{10} = \left\{(x,y):x,y\in P(A),x\subset y\wedge x\cap y\neq\emptyset\right\}$, \end{itemize} and recall that \begin{itemize} \item[] $R_{11} = \left\{(x,y):x,y\in P(A),x=y\right\}$. \end{itemize} Then we let $R_{8}$ be an asymmetric binary relation on $P(A)$ whose $(x,y)$ are such that $x\not\subseteq y$ and $y\not\subseteq x$ and $x\cap y=\emptyset$. Similarly, we define $R_{9}$ be an asymmetric binary relation on $P(A)$ whose $(x,y)$ are such that $x\not\subseteq y$ and $y\not\subseteq x$ and $x\cap y\neq\emptyset$. It should be clear that $R_{7}$ and $R_{10}$ are also asymmetric relations. We also observe that $R_{7}$ - $R_{10}$ are irreflexive and vacuously antisymmetric, while $R_{11}$ is reflexive, vacuously symmetric, and antisymmetric. $R_{35}$ is a reflexive, antisymmetric, and transitive relation, and so a partial order. Let $Q$ be the \textit{quotient set} \cite{Schechter} $B/\equiv$, i.e., an equivalence relation on $B$, where \begin{align*} (a,b)\equiv (c,d) \Leftrightarrow (a=d)\wedge (b=c) \end{align*} for all $(a,b),(c,d)\in B$. Then $R_{35}$ may also be thought of as a set of equivalence class representatives of $Q$. Furthermore, we note that \begin{itemize} \item[] $R_{3} = R_{7}\cup R_{10}\cup R_{11}$, and \item[] $R_{4} = R_{7}\cup R_{10}$. \end{itemize} \vspace{8pt} \noindent\textbf{Examples}. With $A=\left\{1,2\right\}$, $P(A)=\left\{\emptyset,\left\{1\right\},\left\{2\right\},\left\{1,2\right\}\right\}$, and \begin{itemize} \item[] $R_{7} = \left\{(\emptyset,\left\{1\right\}),(\emptyset,\left\{2\right\}),(\emptyset,\left\{1,2\right\})\right\}$, \item[] $R_{8} =$ either $\left\{(\left\{1\right\},\left\{2\right\})\right\}$ or $\left\{(\left\{2\right\},\left\{1\right\})\right\}$, \item[] $R_{9} = \emptyset$, \item[] $R_{10} = \left\{(\left\{1\right\},\left\{1,2\right\}),(\left\{2\right\},\left\{1,2\right\})\right\}$, \item[] $R_{11} = \left\{(\emptyset,\emptyset),(\left\{1\right\},\left\{1\right\}),(\left\{2\right\},\left\{2\right\}),(\left\{1,2\right\},\left\{1,2\right\})\right\}$. \end{itemize} \subsection{The cardinalities of $R_{7}$ -- $R_{11}$ and their possible unions} \label{sec:2.2} The \textit{Stirling numbers of the second kind} $S(n,k)$ count the number of ways to partition an $n$-element set into $k$ non-empty subsets, or, \textit{parts}. They satisfy the recurrence \begin{equation} S(n+1,k+1)=S(n,k)+(k+1)\cdot S(n,k+1). \label{eq:Eq14} \end{equation} It is also the case that \begin{equation} S(n,1)=S(n,n)=1 \label{eq:Eq15}, \end{equation} as there is clearly just 1 way to partition an $n$-element set into either 1 part or $n$ parts. We assume $S(i,j)=0$ when $i