Intro to Set Theory

To start off, a set is collection of elements.

Additionally, there are two specific very important sets used in set theory:

• ξ: the universal set. It's the set of all things being selected from. For now we'll take the universal set to mean ℤ, or the set of all integers. All sets we'll use from here on are subsets of ξ. The term 'subset' will be explained later.

• ∅: the empty set. A set with no elements.

Let's define one set, called S, to be the set of all non-negative (integer) numbers below 5. Therefore, S={1,2,3,4}.

This method of listing the elements in S is fine when the amount of elements in a set is small, but with big or even infinite sets, it is more convenient (and easier to do maths with) when it is written using set-builder notation.

Set-builder notation is written in the form S={s:(P_)(s)}

S is the set called S.

{} are the set brackets. These enclose the elements inside the set. Typically curly brackets are used to represent sets.

s represents an element in S (or all elements depending on context).
This idea can be shown through the statement s∈S. ∈ is the 'element(s) of' symbol, showing s is an element of S. (The name s is arbitrary.)

Additionally, ∋ is the 'belongs to' symbol. It is the reverse of ∈. Therefore S∋s.

: is the 'such that' symbol. It qualifies or restricts the elements in a set to those that follow the condition that comes after it which is (P_)(s).

(P_)(s) is a property of s. It can be thought of as a condition that an element must pass to be a part of a set. Since the condition is 0<s<5, this means that s must be between 0 and 5 to be included in the set.

In this case, the statement is said as "S is the set of integers that are between 0 and 5 inclusive." (or more strictly, "S is the set of integers such that all elements in S are between 0 and 5 (inclusive).")

The size of sets are also important. This is determined by the number of elements in a set, known as its cardinality. Cardinality is denoted as |S| (or sometimes n(S)). Here |S|=4.

For this next example, let A be the positive multiples of 2, and B the positive multiples of 3.
A={2,4,6,8,10,12…}={a:2|a}
B={3,6,9,12,15…}={b:3|b}

To find the elements that are present in either set (e.g. here, all multiples of 2 or 3), we can use the union operator ∪. We write this as A∪B={2,3,4,6,8,9,10,12…}

To find the elements that are present in multiple sets (e.g. here, the multiples of both 2 and 3), we can use the intersection operator ∩. We write this as A∩B={6,12,18,24…}

Now, take C to be the set of prime numbers, and D the set of composite numbers. Therefore:
C={2,3,5,7,11,13,17…}
D={4,6,8,9,10,12,14…}

When intersecting C and D, C∩D=∅. They have no elements in common so their intersection is an empty set. C and D are said to be disjoint because they share no elements.

In this example (and every other one we'll use), C and D are both select elements from ξ, the universal set. C and D are said to be subsets of ξ and ξ is said to be a superset of C and D.

Different notation is used to describe this, but here we'll use ⊂ to denote a subset that is strictly not equal to its superset. (That is, there are some elements in ξ that aren't in C and the same can be said for D. This is written as C,D⊂ξ. (And vice versa – ξ⊃C,D.)

Another symbol, ⊆, can be used to show that a set is a subset or equal to another. e.g. E⊆F means that E (exclusively) contains some elements of F and it could even contain all of them.

Quantifiers are also used in set theory to convey how much or what type of thing we are considering.

An important quantifier is for all, written as ∀.

Consider the following sets: D from earlier, and G, the set of all positive multiples of 4.
D={4,6,8,9,10,12,14…}
G={4,8,12,16,20,24…}

Since all multiples of 4 (or any number) are composite, every element of G can be found in D. Using set notation, this is written as ∀g∈G,g∈D. This reads "for every element in G, that element is also in D." or more 'mathematically' said: "for all g in G, g is an element of D."

This is also how we define G as a subset of D; i.e. G⊆D because ∀g∈G,g∈D.

Another quantifier is ∃, called 'there exists'. It is usually followed by a 'such that' statement to qualify the elements which are 'existing'.

Let H be the set of all humans, and I be the set of all countries. It can be said that ∀h∈H,∃i∈I:h lives in i. ("For every human, there exists a country that they live in.") More concisely said, ∀h,∃i:h lives in i .

Let J be the set of all thumbprints. For every human, there exists a unique thumbprint for that human. Mathematically, 'there exists exactly one' is represented with the ∃! symbol. It can be said that ∀h,∃!j:j is the thumbprint of h.

Negating ∀ (for all) gives 'for not all', which is largely equivalent to 'there exists'. To illustrate this, take S from earlier. It can be said that ∀s∈S,(P_)(s)=TRUE or just ∀s∈S,(P_)(s) for short.

Negating that (with the ¬ symbol) gives ¬(∀s∈S,(P_)(s)).

Logically, negating the statement "all (P_)(s)=TRUE" results in "not all (P_)(s)=TRUE" or "there is at least one s such that (P_)(s) =FALSE". This is the same as saying "there exists an s such that ¬(P_)(s)=TRUE".

Therefore, ¬(∀s∈S,(P_)(s))≡∃s∈S:¬(P_)(s)
"Negating 'for all s in S, (P_)(s) is TRUE.' gives 'there exists an s in S such that (P_)(s) is not TRUE.' "

Another useful operation that can be done on sets is difference.

The difference of two sets is the elements of one set that aren't in another. For example, A-B={2,4,8,10,14,16.…}

Using set-builder notation, difference is defined as: A-B={x:x∈A,x∉B} ("A-B is equal to the set of elements such that all elements in A-B are elements of A and not elements of B.")

A set's opposite is its complement. This is every element in ξ that is not an element of that set. For example, if ξ was the set of all continents, the complement of Africa would be the set of every continent that isn't Africa.

The complement of a set (e.g. S) is typically denoted by (S^∁).

Additionally, because (S^∁) is essentially the difference between ξ and the set, (S^∁)=ξ-S.

A set's complement is also defined as the negation of its truth statement.
That is to say that since S={s:(P_)(s)} (where (P_)(s)=0<s<5,
(S^∁)={s:¬(P_)(s)} (meaning ¬(P_)(s)=s<0 or s>5.

Note that also, since there are no elements that are not in ξ, (ξ^∁)=∅

Similarly, since there are no elements in the empty set, every defined element must not be in it, meaning (∅^∁)=ξ.

Lastly, a symmetric difference can be applied to two sets. This is the elements which are in either set but not in both. (In computer science terms, if complement is NOT, and difference is AND NOT, symmetric difference is like XOR.)

Symmetric difference is written in various ways, such as A ⨁ B, A⊝B, A⊛B, and A△B. It is equivalent to (A∪B)-(A∩B).