MorkaLork Development

Interesting stuff I've picked up over the years...

Set theory

2009-05-13 15:17:49 | 662 views | explanation math set theory

What this article is about and what it's not

This article won't go in to the depth of Set Theory, nor will it try to explain the intricacy of the Set concept or how to actually define the notation of set. It will however try to define the contents of a set and how it can be described.

Sources can be found at the end of the article.

What is a set?

A set is a collection of objects that relates to that set. These objects can be refered to as members or elements in a set. The members can have two relationships to a set, either they belong to it, or they don't.
The members can be values, names, objects or whatever entity that is appropriate in the context.
The set can be described as consisting of the members that belongs to it.

A member of a set has to be well defined to avoid paradoxes. There is an important difference between a set of numbers and a set of numbers ranging 1 to 5. In the first set, we have no clue what the set consists of more than that it contains numbers. The second set is still quite vague, but at least we know the range of numbers and can therefor accept that there is a more precise condition for what is a member and what is not.

Then there is also a need to define the members themselves. If we were to describe data values in a collection, such as 1, 1.2 and 2 then there is a big difference between not describing the data type and doing so.
If we were to use a data type without decimals (such as integer) then we would only have 1, 1 and 2, and that would mean we would only have two distinct members, since 1.2 automatically gets downsized to 1. However, if we use a data type that could use decimals (such as double) then we would have three values.

Short list of important rules:

Three ways of describing sets

1. By listing all its members (list notation)

This is a good way to define finit sets (and finit sets only). We use curly brackets to encapsulate the members, and comma(s) to separate them, like this:
{1, 2, 3}
{a, v, p}
{Google, Yahoo, Alta vista}

We can also use a three dot abbrevation to visualize a continuity, that is {1, 2, 3, ..., 10}, but when using this it must be clear what the three dots mean. In this case it obviously means that the collection holds all numbers between 1 and 10 with no decimals, it cannot mean that it holds 1, 2, 3, 4, 5, 5.5, 6, 7, 8, 9, 10, because that would be illogical and hard, if not impossible, to understand.

If a list contains the same member several times it still only counts one time. So {1, 2, 2, 3} is the same as {1, 2, 3}.
There is also no rule to say in what order the members should be placed, so {1, 2, 3} and {3, 1, 2} is the same.

2. Predication notation

This one is a bit trickier. There is a special way to specify a set that looks like this:

{x|x is a non-decimal number and x < 5}

This is read as follows: "the set of all x such that x is a non-decimal number and is less than 5"

Another example:

{x|x is a book by Stephen King}

This is read as follows: "the set of all x such that x is a book by Stephen King"

What the first example means is that we have a set of objects and what we know about these objects is that they are non-decimal numbers and that they have a value less than 5.
So this would be a valid list:
{1, 2, 3, 4}
Whereas this would not:
{1, 1.1, 2, 3}

The general way to write this is {x|P(x)} where the P is the predicate (such as 'is a non-decimal number').

3. Recursive rules

Example: the set E of even numbers greater than 3

Recursive definitition:
1. 4 ∈ E
2. if x ∈ E, then x + 2 ∈ E
3. nothing else belongs to E


The first rule shows us the basis. The lowest member, or value in this cause, is 4. This is known as the Basis Clause.
The second rule shows us a pattern, or rule, to follow in order to obtain correct members. This is known as the Inductive Clause.
The third rule stipulates that rule 1 and 2 must be followed in order to generate a proper set member. This is known as the Extramal Clause and is not always shown, but is good to point out in order to fully understand the rules.

Set identity

Before we get into this part, let's make a list of expressions to use and go back to during this part of the article.

iffShort for "If and only if"
↔Sign for "If and only if"
∅Empty/Null set
∈Belongs to
⊆Relationship between sets. A ⊆ B means A is a subset to B
⊇Relationship between sets. A ⊇ B means A is a superset to B
⊂Relationship between sets. A ⊂ B means A is a proper subset to B
⊃Relationship between sets. A ⊃ B means A is a proper superset to B
℘Relationship between sets. ℘A means that A is a powerset
≠Does not equal

Two sets can only be considered to be identical if they have the exact same members. This can be described in the following way:

A = B
iff(if and only if)
for every x, x ∈ A ↔ x ∈ B.

The above can be translated as follows:

A equals B if, and only if, for every x, x can be found in A if and only if x can be found in B.

This means that every member in A must exist in B, but not vice versa. This makes A a subset to B which can be written like this: A ⊆ B. This however is ambiguous since we cannot be sure if B might be holding only members that exist in A. To make this a proper subset we must then explicitly declare that while A holds only members that exist in B, A and B are still not the same, so we show it like this:

A ⊆ B and A ≠B

This means that A contains only members that exist in B, but A and B are not the same. This can thus be written like this:

A ⊂ B

This means that A contains only members existing in B and that A and B are not the same. An example could be that A contains {1, 2, 3} and that B contains {1, 2, 3, 4, 5}. In this case A contains only members that B has, but B has additional members that A doesn't have.
This can be displayed through a Euler diagram like this:


As we can see, all members, 1, 2, 3, 4, 5 is inside B, the big circle, and A contains only a part of B's members, 1, 2 and 3.

Let's show some more examples for A ⊂ B:

Example 1: {1, 2} ⊂ {3, 1, 4, 2, 5}
Example 2: {a} ⊂ {a, b, c}
Example 3: {a, b} ⊆ {a, b}
Example 4: {John, Lisa} ⊂ {Marcus, John, Basil, Lisa}

Example 1 shows us that the order of members plays no part in defining a set, its only important that they are contained within the set. And in example 1, we can see that the members of A (1 and 2) can all be found in B (3, 1, 4, 2, 5). Example 2 is similar whereas example 3 is different. As we can see in example 3, set A contains only members that exist in set B, but set B contains only members that exist in set A.

Note that an empty set is always a subset to any set that is not itself empty.

Note that instead of writing A ⊂ B (A is a subset to B) we can write B ⊃ A which means that B is a superset to A.

Example for B ⊃ A:

Example 1: {1, 2, 3} ⊃ {1, 2}
Example 2: {Copenhagen, Stockholm, Berlin, London} ⊃ {Berlin}

The powerset is a set that holds members that belongs to several sets. It's denoted with the ℘ sign.
An example might explain:

A = {1, 2, 3}
℘(A) = {∅, {1}, {1, 2}, {3}}

What it means is that A is a powerset to the subsets that only have members that exist in A.

That about does it in this short description of Set Theory math and it has not gone deep into any part really. It's meant to be a short explanatory guide if you just need to know something somewhat fast, so if you want more in-depth texts on this subjects, I refer you to the Source list.

Sources (Swedish)

Article comments

Feel free to comment this article using a facebook profile.

I'm using facebook accounts for identification since even akismet couldn't handle all the spam I receive every day.