# Number of relations

Let set A: $$A = \{\ \ 1, \ \ 2\ \ \}$$

Powerset of A: $$P(A) = \{\ \ \varnothing,\ \ \{1\},\ \ \{2\},\ \ \{1,2 \}\ \ \}$$

Cartesian product of the set $$A$$: $$A\times A = \{ \ \ (1,1),\ \ (1,2),\ \ (2,1),\ \ (2,2)\ \ \}$$

Enumerated powerset of the Cartesian product of the set $$A$$ i.e. $$\mathcal{P}(A\times A) = \mathcal{P}(A^2)$$ is given below. There are 16 elements in this powerset i.e. there are 16 possible relations:

* 1 possible way to choose no pairs (0-place): $$4\choose 0$$
* 4 possible ways to choose 1 pair (1-place): $$4\choose 1$$
* 6 possible ways to choose 2 pairs (2-place): $$4\choose 2$$
* 4 possible ways to choose 3 pairs (3-place): $$4\choose 3$$
* 1 possible way to choose all pairs (n-place): $$4\choose 4$$

The formula to choose k-places out of n elements:

$$
{n \choose k} = {\frac{n!}{k!(n-k)!}}
$$

Enumerated powerset of the Cartesian product of the set $$A$$:

$$
{\\
\mathcal{P}(\ \ \{\ \ (1,1),\ \ (1,2),\ \ (2,1),\ \ (2,2)\ \ \}\ \ ) = \\
\Huge\{\\
R_1:  \varnothing, \\
R_2:  \{(1,1)\},   \\
R_3:  \{(1,2)\},   \\
R_4:  \{(2,1)\},   \\
R_5:  \{(2,2)\},   \\
R_6:  \{(1,1), (1,2)\}, \\
R_7:  \{(1,1), (2,1)\}, \\
R_8:  \{(1,1), (2,2)\}, \\
R_9:  \{(1,2), (2,1)\}, \\
R_{10}:  \{(1,2), (2,2)\}, \\
R_{11}: \{(2,1), (2,2)\}, \\
R_{12}: \{(1,1), (1,2), (2,1)\}, \\
R_{13}: \{(1,1), (1,2), (2,2)\}, \\
R_{14}: \{(1,1), (2,1), (2,2)\}, \\
R_{15}: \{(1,2), (2,1), (2,2)\}, \\
R_{16}: \{(1,1), (1,2), (2,1), (2,2)\} \\
\Huge\}
\\}
$$

Relations:

* null (1): $$R_1$$
* identity (1): $$R_8$$
* universal (1): $$R_{16}$$
* reflaxive (4): $$R_1, R_8, R_{13}, R_{16}$$
* irreflexive (4): $$R_1, R_3, R_4, R_9$$
* symmetric (8): $$R_1, R_2, R_5, R_8, R_9, R_{12}, R_{15}, R_{16}$$
* anti-symmetric (12): $$R_1-R_8, R_{10}, R_{11}, R_{13}, R_{14}$$
* asymmetric (5): $$R_1-R_5$$
* transitive (13): only $$R_9$$ and $$R_{15}$$ are not transitive

Summary:

* The number of distinct binary relations on an n-element set is $$2^{(n^2)}$$
* The number of reflexive and irreflexive relations is the same.
* The number of strict partial orders (irreflexive transitive relations) is the same as that of partial orders.
* the number of equivalence relations is the number of partitions, which is the **Bell number**.

Ordered pair $$(1,2) = \{\{1\},\{1,2\}\}$$

Powerset of A: $$P(A)$$

$$= \{\varnothing, \{1\}, \{2\}, \{1,2\}\}$$

$$= \{\varnothing, \{1\}, \{2\}, \{1,2\}, \{2,1\}\}$$

$$= \{\varnothing, \{1\},\{1,2\}, \{2\},\{2,1\}\}$$

$$= \{\varnothing, (1,2), (2,1) \}$$

Ordered pair $$(x,y) = \{\{x\},\{x,y\}\}$$

if $$x=y$$ then $$(a,a)$$

$$=\{\{a\},\{a,a\}\}$$

$$=\{\{a\},\{a\}\}$$

$$=\{\{a\}\}$$

**Sets**

* A set is an unordered collection of distinct objects (that share some common property) considered as an object in its own right.
* defined intensionaly (semantically): "A set of odd positive ints"
* defined extensionaly (enumeration): $$\{a,b,c\}$$
* denoted with a capital letter: $$A=\{a,b,c\}$$, elements with lowercase
* If $$a$$ is an element of set $$B$$ then: $$a\in B$$, if not $$a\notin B$$
* Order or repetition unimportant: $$\{\{a\},b,\varnothing\}=\{b, \{a\},\{\},b,\varnothing,\{\}\}$$
* A set can contain other sets, $$x \in A, A \in \mathscr{M}$$, so $$x\in A$$ but $$x \notin \mathscr{M}$$.
* Two sets are equal if they contain the same elements.

**Types**

* An empty set contains no elements: $$\varnothing = \{\}$$
* A set, $$\{a,b\}$$, is distinguished from the ordered pair, $$(a,b)$$
* $$n$$-element set is different from ordered $$n$$-tuple: $$\{x_1, x_2,\dots,x_n\} \neq (x_1,\dots, x_n)$$
* Two ordered pairs are equal **iff**: $$(a,b) = (x,y) \iff a=x \land b = y$$
* The order of the elements or their repetition is of no consequence to sets, $$\{a,b,\{\}\}=\{b,\{\},b,\varnothing,a\}$$.
* $$\{\varnothing\}=\{\{\}\}$$

**Subset and powerset**

* if all elements of a set $$A$$ are also elements of a set $$B$$, then $$A$$ is a **subset** of $$B$$: $$A \subseteq B$$ and $$B$$ is a **superset** of $$A$$: $$B \supseteq A$$.
* a set $$B$$ is **equal** to $$A$$ if the two sets consist of exactly the same elements: $$A = B \iff A \subseteq B \land B \subseteq A$$.
* if $$A \subseteq B$$ but $$B \neq A$$ then $$A$$ is a **proper subset** of $$B$$: $$A \subset B$$.
* if a set $$P$$ contains all possible subsets of a set $$A$$, then $$P$$ is a **powerset** of $$A$$, denoted as $$P(A)$$.
* e.g. if $$A=\{a,b\}$$, then $$P=\{\{a\},\{b\},\{ab\},\{\varnothing\}\}$$
* here, the cardinality (number of elements) of $$P$$ is 4, denoted as $$|P|=4$$

Properties of sets: $$\forall A,B,C$$

* $$A \subseteq A$$ (reflexivity)
* $$A \subseteq B \land B \subseteq C \rightarrow A \subseteq C$$  (transitivity)
* $$A \subseteq B \land B \subseteq A \rightarrow A=B$$ (anti-symmetry, axiom of extensionality)
* $$\varnothing \subseteq A$$
* $$A\subseteq \varnothing \rightarrow A=\varnothing$$
