> For the complete documentation index, see [llms.txt](https://mandober.gitbook.io/math-debrief/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mandober.gitbook.io/math-debrief/200-set-theory/topics/number-of-relations.md).

# 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$$