Hello there. This is the last part of a three part Introduction to Set Theory and Logic.
Part One of this introduction talked about definitions, notation with some examples. The number system was also covered.
In Part Two, Venn diagrams were used to help with understanding relations between sets.
Part Three will go into more detail about set operations and counting with sets.
It is assumed that the reader is familiar with set theory concepts from parts one and two.
- The Algebra of Sets
- The Dual Of A Set
- Finite Sets
- Counting Principles
- The Power Set
- Ordered Pairs
- Cartesian Products
The Algebra of Sets
We continue from part 2 where we learned unions, intersections, complements, subtraction of sets, and symmetric differences with the help of Venn diagrams.
Like in grade school, you learned about the rule of addition, subtraction, multiplication, division and so on. We do the same here with sets. Instead of me typing out the Laws of the Algebra of Sets, I will display an image.
The above image displays a nice organized list of the laws. However the choice of symbols is weird in my opinion. Instead of the ampersand & use like in for intersections. Instead of the plus sign + use as in for unions. The overbar such as for the complement of the set A is okay. You can use for complements as well.
The one law missing from the above is the involution law . This one is somewhat obvious though.
You could memorize these laws but it is not necessary (unless your math course wants you to). The one that is useful if you are in computer science and do computer programming is the DeMorgan’s laws.
The Dual Of A Set
In part two, we talked about complements of a set and how the complement of a set for example is all the elements not in . We have a reverse (opposite) operation concept for the set algebra symbols called the dual.
For example the dual of is .
We then look at finite sets.
A set is considered to be finite (or non-infinite) if it contains distinct (different) elements in the set where is a non-negative integer. A non finite set is an infinite set.
Suppose we have the set , the number of elements in set is denoted by . Try to not get confused with the absolute value of numbers and functions as we are dealing with sets.
In here, we deal with finite sets only and not with infinite sets as it is “infinitely” more abstract.
Now, we learn a new way of counting but through sets. The number of elements in a set is also called the cardinality of a set.
If the set is then we say that set has 3 elements denoted by
If the set is then we say that set has 4 elements denoted by
The intersection is then we say that set has 1 element denoted by
What if we want the number of elements in the union denoted by ?
We see that is Remember that sets do not have multiples of an element. The number of elements is not actually 3 from set A plus 4 from set B, it is actually 3 + 4 -1 (from the intersection) which equals 6. The minus is from .
We can generalize the above into a formula as follows for two sets.
As a reference, here is a Venn Diagram.
The three set case is a bit more involved. The formula is as follows
For probability and statistics students, there is a probability version of the counting principles. It is similar to the formulas above as it is based on set theory and Venn diagrams.
The Power Set
Recall that a subset is a set which contains some or all of the elements of a larger set. For example, the set is a (proper) subset of .
We now define the power set of set S denoted by . Given a given set , the power set is the class of all subsets of .
We can also find the number of elements in the power set of . If the set is finite then the power set is also finite. The number of elements in is . (2 to the power of the number of elements in set ).
That may sound confusing at first. It will be clarified with an example.
Suppose that the set is . The power set contains all the subsets of which would be
Remember that the empty set is a subset of a non-empty set. The set itself is also a subset of and it is thus a subset of .
The number of elements in this power set is .
An ordered pair is similar to a co-ordinate on the xy-plane. Here, the ordered denoted by (a, b) is defined as having a as the first element and b as the second element.
With sets order did not matter but with ordered pairs, order does matter . For example, the sets is the same as but . In general, unless .
The last topic of this three part series is the Cartesian product of two sets and . The Cartesian product of sets and is denoted by or “A cross B”. It is the set of all ordered pairs (a, b) such that and or .
If we have then that can be written as . If set or set (or both of them) is empty () then the Cartesian product is empty as well.
Remember that the real line is in one dimension. The two dimensional real space comes from .
Here is an example of how the Cartesian product operates.
Suppose we have the set and . What are , and ?
Think of the Cartesian products as all possible combinations between two sets.
We saw that and have 6 elements from and respectively. contained 4 elements ().
A generalized result can be defined here. If sets and are sets with a finite number of elements then .
This is the end of the three part series of An Introduction to Set Theory and Logic. I hope this series was useful or interesting to you. You may or may not absorb of all the material. However, you may realize that mathematics is more than numbers and calculus. There are so many branches of mathematics and a good portion of them do not have numbers.
Material is from old notes and from a coursepack book from my undergraduate university for the course Introduction to Mathematical Proofs.
The featured image is from https://upload.wikimedia.org/wikipedia/commons/thumb/4/4e/Cartesian_Product_qtl1.svg/220px-Cartesian_Product_qtl1.svg.png