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