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.