Subset Relation — Set Theory

This is a continuation of my previous post about Set Theory. If you have not read that yet, start there.

When one set contains all of the elements of another set (and may be more), second set is considered to be a subset of the first set. This definition allows, two equivalent sets to be subsets of each other.

  • A = {a} and B = {a, b} then A ⊆ B
  • A = {a, b} and B = {a, b} then A ⊆ B and B ⊆ A
  • odd_numbers ⊆ ℤ

Formal Notation

A ⊆ B ⇔ ∀x (x ∈ A ⇒ x ∈ B)

This reads as A is a subset of B if and only if B contains every element that is an element of A.

Proper Subsets

When one set contains all of the elements of another set and some more, then the second set is considered to be a proper subset of the first set.

  • A = {a} and B = {a, b} then A ⊂ B

Partial Ordering

Following three rules states that subset is a partial ordering.

Reflexivity

A ⊆ A

Given the formal notation for subset isA ⊆ B ⇔ ∀x (x ∈ A ⇒ x ∈ B) it is clear that every element present of set A is present in itself. Hence, it can be concluded that A is a subset of itself.

Antisymmetry

A ⊆ B ∧ B ⊆ A ⇒ A = B

Again, it is clear from the subset definition that if all elements of set A occurs in set B and vice versa, they must be equivalent.

Transitivity

A ⊆ B ∧ B ⊆ C ⇒ A ⊆ C

Lastly, it is trivial to prove that when set B contains all elements of set A and set C contains all elements of set B, set C in fact contains all the elements of set A.


Subset Characterisation

A ⊆ B ⇔ A ∩ B = A

It is trivial to see that A can be a subset of another set B, if and only if their intersection results in set A.

A ⊆ B ⇔ A ∪ B = B

Equally, it is obvious that the set A will only be a subset of B, if and only if their union results in set B.

In both case, the setA is wholly contained within the setB in a Venn diagram.


Originally published at medium.com on September 14, 2017.