pathterminuspages/math/aboutcontactabout me

2.Relations on Sets



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.


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.


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.

CommentsGuest Name:Comment: