A relation $R\subseteq X\times Y$ between finite sets, its row fibres $R_x$ and its column fibres $R^y$

Let $X$ and $Y$ be finite sets (Finite, countably infinite, countable, uncountable, The cardinality $\mid A\mid$ of a finite set) and let $R\subseteq X\times Y$ be a relation between them. For $x\in X$ and $y\in Y$ set

$R_x:=\{y\in Y:(x,y)\in R\},R^y:=\{x\in X:(x,y)\in R\},$

the row fibre of $R$ at $x$ and the column fibre of $R$ at $y$.

(a) Everything here is finite. $X\times Y$ is finite (The product rule: $\mid A\times B\mid =\mid A\mid \mid B\mid$, and $\mid {\prod }_{i<m}{A}_i\mid ={\prod }_{i<m}\mid A_i\mid$, clause 1), so $R$ is finite as a subset of it, and $R_x\subseteq Y$ and $R^y\subseteq X$ are finite as subsets of finite sets (A subset of a finite set is finite, with $\mid B\mid \le \mid A\mid$, and equality holds if and only if $B=A$, clause 1). Hence $\mid R\mid$, $\mid R_x\mid$ and $\mid R^y\mid$ are all defined, and each is a natural number (The cardinality $\mid A\mid$ of a finite set).

(b) The fibres are the slices of $R$, up to a bijection. For $x\in X$,

$R\cap (\{x\}\times Y)=\{x\}\times R_x,$

since $(u,v)$ lies in the left-hand side exactly when $u=x$, $v\in Y$ and $(x,v)\in R$, that is exactly when $u=x$ and $v\in R_x$. The map $y\mapsto (x,y)$ is a bijection of $R_x$ onto $\{x\}\times R_x$, its two-sided inverse being the second-coordinate map (Injection, surjection, bijection), so $\mid \{x\}\times R_x\mid =\mid R_x\mid$ by the transport clause (c) of The cardinality $\mid A\mid$ of a finite set. Symmetrically $R\cap (X\times \{y\})=R^y\times \{y\}$ and $\mid R^y\times \{y\}\mid =\mid R^y\mid$.

(c) The slices partition $R$. The sets $\{x\}\times R_x$, for $x\in X$, are pairwise disjoint, because a point of $\{x\}\times R_x$ has first coordinate $x$; and their union is $R$, because every $(u,v)\in R$ has $u\in X$ and $v\in R_u$. Symmetrically the sets $R^y\times \{y\}$, for $y\in Y$, are pairwise disjoint with union $R$.

(d) Neighbours. When $X=Y$ and $R$ is symmetric ($(x,y)\in R$ implies $(y,x)\in R$) and irreflexive ($(x,x)\mathrm{\notin }R$ for every $x$), $R_x=R^x$ and this common set is called the set of neighbours of $x$; it is a subset of $X\setminus \{x\}$.

• A relation, not a matrix. The object counted here is a subset of a product of two finite sets. Nothing about arrays, entries or indices by position is used, and the two fibre families are the only structure the counting arguments need.

• No graph vocabulary. Clause (d) fixes the words symmetric, irreflexive and neighbour for a relation on a single finite set. Nothing among this page's declared prerequisites defines a graph, and none of the results stated with clause (d) needs one.

• Both fibre families are indexed by a finite set, which is what lets the cardinalities be summed at all: a sum over a finite index set is defined only when the index set is finite (The sum ${\sum }_{i\in S}{a}_i$ over a finite index set, and its product form).