# 2.Relations on Sets

## 20.01.2021

### Contents/Index

1. Introduction to Sets
@2. Relations on Sets

We here list different relations on sets. A relation is an operator that returns true or false. For example $2 = 3$ returns false, whereas $2 \leq 3$ returns true.

## Equality

Two sets, $A$ and $B$, are equal if every element in one set is present in the other. Formally we can state this as $$x \in A \Rightarrow x \in B \land x \in B \Rightarrow x \in A$$ Or equivalently $$x \in A \iff x \in B$$ We write this as $$A = B$$ With this statement we can prove that the empty set is unique. Let $\emptyset_1,\emptyset_2$ be empty sets. Now $$x \in \emptyset_1$$ is false, hence $$x \in \emptyset_1 \Rightarrow x \in \emptyset_2$$ is trivially true. This goes vice versa.

## Subset

We say that $A$ is a subset of $B$ if every element in $A$ is in $B$. Formally $$x \in A \Rightarrow x \in B$$ We write this as $$A \subseteq B$$ Sometime we want to know that $A$ is a proper subset of $B$. That is though $A \subseteq B$, we have elements in $B$ that are not in $A$. We write this as $$A \subset B$$ However this is a stronger statement, we have that $$A \subset B \Rightarrow A \subseteq B$$ So often only the $\subseteq$ relation is used. Note that we have $$A = B \Rightarrow A \subseteq B \land B \subseteq A$$ So any set has itself as subset. We also have that any set has $\emptyset$ as a subset. Given a finite set, $A$, with size $n = |A|$, we have a total of $2^n$ subsets. This can be seen as constructing a mask on top of a set. Say we have $$A = \{a,b,c\}$$ one possible mask is given as $$m_1 = \{0,1,1\}$$ where $1$ means that we have the element, and $0$ means that we don't. So applying this mask to $A$ we obtain $$m_1(A) = \{b,c\}$$ We have $2^n$ possible masks. We have the following properties for the subset (non proper) relation:

• Reflexive: We have that a set a subset of itself.
• Anti-symmetrical: We have that $A \subseteq B \land B \subseteq A$ implies that $A = B$.
• Transitive: Given $A \subseteq B$ and $B \subseteq C$, we have that $A \subseteq C$. This is shown straight forward, let $x \in A$ by which follows that $x \in B$ by which follows that $x \in C$.

Such a relation is called a partial order.