Introduction – Set Theory


Overview

In this article I’ll be going into some of the basics of Set Theory.  This is once again an article that will grow over time and become more and more mature as I have new things to add.  The goal is to understand the basics for now and to grow these basics into something more substantial.  Before I start with this article I would advise you to have a look at my article covering “Numerical Systems” and get to get to grip with the Laws of Numbers seeing that this and the other articles I’ll be doing will be building on the base that I’m trying to create.  Again, I have to state that these articles are more for my own use than for someone else’s, so if you’re not interested I’m sure there is something else on this site that might be of more interest to you. 

In this article I’ll be covering the following fundamentals:

  1. Symbols in Set Theory
  2. Definition
  3. Set Notation
  4. New Sets
    • Subset
    • Union
    • Intersection
    • Universal Set
    • Empty Set
    • Complement
    • Cartesian Product
    • Symmetric Difference
    • Disjoint Sets
    • Cardinality
    • Power Set
  5. Further Reading
  6. Summary

Symbols in Set Theory

When you start to work with Set Theory you’ll soon realize that it has a number of symbols which make writing things easier.  To cover this in some detail will take a lot of time, but for the purposes of this article I’ve decided to have a small glossary of symbols at the beginning so as to ensure that you can always come back easily. 

| = “such that”

= “as a member of” = “as an element of”

 = “not as a member of” = “not as an element of”

= “Union”

= “Intersection”

– = “Complement”

= {} = “Empty Set”

= “is a subset of”

= “is a superset of”

= “is a proper subset of”

= “is a proper superset of”

+ = “Symmetric Difference”

P = “Power Set”

N(A) = |A| = “Cardinality”

→ =

Definition

A set is a collection of distinct objects also known as elements or members.

Set Notation a.k.a Roster Method

List Notation

List notation is one of the simplest methods and it works very well with very small sets.  To explain this in the simplest manner, you should consider the following set:

A = {1, 2, 3, 4}

The above set is written using List Notation.  As you can see this is simply setting a variable “A” equal to the collection of objects which is “{1, 2, 3, 4}”.  As you can see it would be tedious to have to write down the entire set where “A” would be equal to the set of Integers (Z).

Set Builder Notation

Set Builder Notation caters for larger sets and can be built up by using some of the symbols that we covered in the section above as well as some of the Numerical symbols that we covered in the article “Numerical Systems”.  To demonstrate this simply you can have a look at the following:

Z+ = {x|x is a positive number}

If we break this down into segments you see that we’re stating the following:

“Z+ equals all x (variable) such that x is a positive number”

To translate this back into the symbols you should see that “|” is replaced with the words “such that” and x is the variable used to define all the numbers within the set.

New Sets

Subset

In Set Theory A is a subset of B if the members of A is contained in B.  This could also be written as A B.  If we take an example of something like this we could look at the following two sets:

A = {1, 2, 3}
B = {1, 2, 3, 4}

In this case you can see that all members of A can also be found in B, which makes A a subset of B.  Something to note here is that if we had the following:

A = {1, 2, 3}
B = {1, 2, 3}

In this scenario A would still be a subset of B seeing that all the members of A can also be found in B, at the same time B would also be a subset of A.  There is a concept of a “Proper Subset” which can be denoted as A B.  In the case of our first pair of sets this would be a correct statement to make, but in the case of our second pair of sets it would be incorrect.

Union:  ∪

Union is when you combine two sets into a third set which contains a distinct collection of all the members found in both sets.  Union can be denoted using the “” symbol and can be illustrated by the following example:

if A = {1, 2} and B = {0, 1} then A B = {0, 1, 2}

As you can see in this example we simply created a third set that contains the unique set of members of both set A and B.

Intersection:  ∩

Intersection is when you create a new set with the members that are shared between two sets.  This can be denoted by the following statement:

A B = {x|x A and x B}

To show this we can take the following scenario:

if A = {1, 2} and B = {0, 1} then A B = {1}

Universal Set:  U

To understand the Universal Set you have to understand that in some cases the sets we use could all be subsets of a sinle larger set, which is called a Universal Set.  For this discussion let’s look at the sets where:

A = {0, 1, 2} and B = {3, 4, 5} and C = {6, 7, 8}

In this case you could agree that the members of these sets all belong to a larger set of Natural Numbers (N) and can hence be written as: 

U = {N}

This can be denoted with:

U = {x|x is a Natural Number}

Empty Set:  ∅ or {}

An empty set is a set that contains no members at all and can be denote with either or {}.

Complement: –

If A is a subset of the Universal Set U, then the complement of A would be a set where the members would exist in U, but not to A.  This can be written as A’ and can be denoted as:

A’ = {x|x A}

To show this we can take the following scenario:

if U = {1, 2, 3, 4, 5, 6} and A = {1, 2} then A’ = {3, 4, 5, 6}

This can also be understood and explained in the terms of:

U – A = A’

In this case we use the “-“ symbol to denote that answer to A’ can be derived from the above formula.  So, if we take the terms above and show them as an example, then it might look as follows:

U – A = A’

{1, 2, 3, 4, 5, 6} – {1, 2} = {3, 4, 5, 6}

Cartesian Product:  X

The Cartesian Product of the two sets A and B is the direct product of the two sets A and B, written as A X B and can be denoted as:

A X B = {(A, B)|x A and x B}

To show this we can take the following scenario:

if A = {1, 2} and B = {3, 4} then A X B = {{1, 2}, {1, 4}, {2, 3}, {2, 4}}

Symmetric Difference: +

The Symmetric Difference between two sets A and B, written as A + B, is defined as the set of all members that belong to A or B but not both and can be denoted as:

{x|x A or x B, but not both}

To show this we can take the following scenario:

if U = {1, 2, 3, 4, 5, 6} and A = {1, 2} and B = {2, 3, 4, 5, 6} then A + B = {1, 3, 4, 5, 6}

Disjoint Sets

Sets are Disjoint when they share no common members.  We can denote this with the following:

A B = {}

To show this we can take the following scenario:

if A = {1, 2, 3} and B = {4, 5, 6} then A B = {}

Cardinality:  n(A)

The Cardinality of a set is the number of members in the set.  This can be denoted with:

n(A)

We can also use the notation of:

|A|

To show this we can take the following scenario:

if A = {1, 2, 3} and B = {5, 6} and C = {2, 4, 6, 8, 10} then n(A) = |A| = 3 and n(B) = |B| = 2 and n(C) = |C| = 5

Power Set

If we have a set A then the Power Set of set A would be the set that has all the subsets of set A as it’s members.  This can be denoted as:

P(A)

To show this we use the following scenario:

if A = {1, 2, 3} then P(A) = {{}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

As you can see in the above example, the Power Set of A would be all combinations of subsets that can be derived from set A.

Further Reading

Set Theory:  http://en.wikipedia.org/wiki/Set_theory

Sets:  http://en.wikipedia.org/wiki/Set_(mathematics)

Sub Set:  http://en.wikipedia.org/wiki/Subset

Empty Set:  http://en.wikipedia.org/wiki/Empty_set

Disjoint Set:  http://en.wikipedia.org/wiki/Disjoint_sets

Cardinality:  http://en.wikipedia.org/wiki/Cardinality

Complement:  http://en.wikipedia.org/wiki/Complement_(set_theory)

Cartesian Product:  http://en.wikipedia.org/wiki/Cartesian_product

Summary

As you can see there is a lot that I’ll be covering about Sets in future releases of this article.  This is by no means the completed document but this should give you a nice little introduction into Set Theory.  In subsequent releases of this article I’ll be building on the above to include concepts such as Venn Diagrams and I may even go into some of the different areas of study.  I’m covering these things, because I find it interesting and because this is the basis of so much we do in Computer Science and to top it all off.

  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: