BQN

Product

The cartesian product of sets A and B is the set of all pairs of elements {A\times B = \{(a, b)\mid a\in A, b\in B\}}.

A relation is a subset of a cartesian product R\subseteq A\times B. We write aRb for (a, b)\in R where a\in A, b\in B. A right coset of R is {aR = \{b\in B\mid aRb\}\subseteq B}, a\in A, and a left coset is {Rb = \{a\in A\mid aRb\}\subseteq A}, b\in B.

A function is a relation where every right coset contains exactly one element. We write R\colon A\to B and R(a) = b where b\in B is the unique element of aR. A partial function is a relation where every right coset contains at most one element. A partial function can be extended to a function using a unique symbol \bot and defining R(a) = \bot if aR is empty.

The composition of relations R\subseteq A\times B and S\subseteq B\times C is the relation {SR = \{(a,c)\mid aRb\text{ and }bRc\text{ for some }b\in B\}\subseteq A\times C}.

Exercise. Show a(SR)c if and only if aR\cap Sc\not\emptyset.

A relational database is a collection of relations. The join (on B) of relations R\subseteq A\times B and S\subseteq B\times C is the relation {SR = \{(a,b,c)\mid aRb\text{ and }bRc\text{ for some }b\in B\}\subseteq A\times C}.

Exercise. If f\colon A\to B and g\colon B\to C are functions show a(gf)c if and only if c = g(f(a), a\in A, c\in C.

The transpose of R\subset A\times B is {R^* = \{(b,a)\mid a\in A, b\in B\}\subseteq B\times A}.

Exercise. Show bR^* = Rb and R^*a = aR for a\in A and b\in B.

A relation R\subseteq A\times A is reflexive if aRa, symmetric if aRb implies bRa, antisymmetric if aRb and bRa imply a = b, and transitive if aRb and bRc imply aRc, a,b,c\in A.

The identity relation is I_A = \{(a,a)\mid a\in A\}.

Exercise. Show R is reflexive if and only if I_A\subseteq R.

Exercise. Show R is symmetric if and only if R^* = R.

Exercise. Show R is symmetric implies I_A\subseteq R.

Exercise. Show R is antisymmetric if and only if I_A\subseteq R\cap R^*.

Exercise. Show R is transitive if and only if R^2 = RR\subseteq R.

I_A\subseteq R\cap R^*_.

For f\in A^B define \pi_b f = f(b), b\in B. If f_b\colon C\to A, b\in B, define g\colon C\to A^B by g(c)b = f_b(c).

If f\colon (A\times B)\to C then f,\colon A\to(B\to C) by (f,a)b = f(a,b), a\in A, b\in B.

If f\colon A\times B^I\to C^I then f,\colon A\to(B^I\to C^I) since (f,a)b\colon I\to C.

If S is a set define S^* = \sqcup_{n\in\bm{N}}S^n.

If \langle M,m,e\rangle is a monoid with binary operation m\colon M^2\to M and identity e\in M define \begin{aligned} m^0\colon M^0\to M &\text{ by } m(\emptyset) = e \\ m^1\colon M^1\to M &\text{ by } m^1(a) = a, a\in A \\ m^n\colon M^n\cong M\times M^{n-1}\to M &\text{ by } m^n(a,b) = m(a, m(b)), a\in M, b\in M^{n-1}\\ \end{aligned}

This defines m^*\colon M^*\to M by m^*|_{M^n} = m^n.