Sets

There are a lot of things to talk about when it comes to sets.
Since it is assumed that you already know about things like union, intersection, etc., we're not going to go over set operations.

Some popular sets you might know are:

Look at this formula:

$A \subseteq B = \forall x [x \in A \implies x \in B]$

This is the subset notation ($\subseteq$), and the formula says that for all $x$, if $x$ in $A$, then $x$ in $B$. It also implies that both sets are equal.
When talking about a proper subset, the notation is $\subset$, for example $A \subset B$. That means $A$ is a proper subset of $B$, and they are not equal.

Why is $\varnothing$ is a subset of every set?

Well, think of this: $\varnothing \subseteq B$. That means $\forall x [x \in \varnothing \implies x \in B]$.
That is an implication. The first part of it is clearly false, there is nothing in an empty set, yet we say $x \in \varnothing$. Remember that in an implication, when the antecedent (the "if part") is false, no matter what follows, the whole statement is true. So, both the statements F $\implies$ T and F $\implies$ F are true. It doesn't matter if $x$ is in $B$ or not, since $x \in \varnothing$ is clearly false, the whole statement is true.

A power set is the set of all subsets of a set.

For example, if our set is $\{T, F\}$ then its power set is $\{\{T\}, \{F\}, \{T, F\}, \varnothing\}$.

Another example is $\mathbb{Z}^+ \in pow(\mathbb{Z})$. It says that the set of positive integers is in the power set of integers.

Difference is every element in set $A$ and not in set $B$:

The complement of a set is the set of all elements that are not in that set. It is denoted with an overline, like $\overline{B}$.

An example, if the domain we’re working with is the integers, then the complement of the nonnegative integers is the set of negative integers: $\overline{\mathbb{N}} = \mathbb{Z}^-$.

Finite Cardinality

When a set is finite, the number of elements it has is called its size, or cardinality, and it is denoted as $|A|$.

So, $|A|$ means the "number of elements in set $A$".

There are $2^n$ number of subsets of a set that has $n$ elements: $(|A| = n) \implies (|pow(A)| = 2^n)$

But, why is that?

Why is the size of a power set is $2^n$?

Alright, we are going to use a string representation for all possible subsets, where an element can be in it, or not.
We're going to put $0$ where the element exists in the set but not in the subset, and we're going to put $1$ where the element exists both in the set and the subset.

Let's say that our set $A$ is $\{a, b, c\}$.

We can say a subset could be the one where none of the elements exist — which is indeed the empty set, so we can represent it as $0, 0, 0$.

Another possibility is a subset where only $a$ exists — we will represent it as such: $1, 0, 0$. This is the subset $\{a\}$.

Going on like this, let's see all the possibilities:

This is indeed our power set, $pow(A)$ which is $\{\varnothing, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$.

The number of string representations (the number of $n$ bit strings) is the same as $2^n$, which is the size of our power set!

In our case, $n$ is $3$, so the size of our power set is $8$.

And, here are some set identities:

For a deep dive into an introduction to set theory, you can check out this wonderful book from Open Logic Project.

• previous
• next