CS202 Study Guide

Unit 1: Sets, Set Relations, and Set Functions

1a. Define sets, operations on sets, and state important set properties

Why bother with a formal notation in any field of work?
In what way is a set different from a collection?
How does one use set-builder notation to translate equations into English to achieve general understanding?

German mathematician Georg Cantor (1845 - 1918) initiated set theory around 1870. He defined "set" as a collection of discrete distinguishable objects having a certain relationship. In some discussions, one states whether or not set members can be duplicated. In the course material, a "set" with repeating members is called a "collection". This distinction between sets and collections holds within computer languages. Since there are variations in definitions for different arenas, be careful to understand the difference within the current situation. Objects (elements, members) can be in more than one set at a time but they are entirely in a set or entirely not in a set.

As noted in the previous paragraph, formal definitions and notations are essential for communication. All parties have to agree on the meaning of words and symbols. Otherwise, confusion and non-understanding reign. Within discrete mathematics, set-builder notation is often used as a shorthand for describing a set's universe, the relationship between members of the set. For instance, Q = {a/b | a,b ∈ Z, b≠0} is a set-theory way of saying, "The membership of set Q is composed of elements that result from dividing a by b such that a and b are elements of set Z and b is not equal to zero".

Review Set Notation and Relations.

1b. Categorize sets into their various types (such as singleton, finite, infinite, equal, null, proper subset, and improper subset) and give a definition of each

What is the relationship between terminology and symbology?
What is the difference between null and empty?
In what way do a universal set and a superset differ?

As discussed earlier, a commonly understood terminology and notation (symbology) must exist for a topic to be discussed. Terminology typically refers to words in natural language, English in this case. "Notation" is short-hand produced by the use of "symbolism", special characters that represent words in natural language. Words, notation, and symbolism are all ways of representing concepts and ideas that enter the human mind. We can consider our thoughts and ideas without having any kind of means of expressing them. But, to communicate them to others, and to have some way of having them understood by others, we need some common way of expressing them. Thus we have terminology, notation, and symbolism.

Sometimes, there is not a one-to-one match between a given term and its notation. One-to-many is often seen. For instance, a null set is the same thing as an empty set. Such sets have various symbols, depending on the document ({ }, Ø, n(X) = 0, |A| = 0). Symbols can have different meanings, depending on the field of work at hand. For example, in other types of mathematics, |A| refers to the absolute value of A. In discrete mathematics, the topic we are studying, |A| refers to the number of elements in set A. The variations in terminology and symbols can lead to confusion so stay alert to the forms used.

Shades of meaning are also important. Definitions of terms and notations can appear to be the same at first but there is often a fine distinction. A good example is the universal set and superset. A superset contains all elements of a particular set but not just those elements. A universal set contains all elements and all sets under consideration. It is a set of all elements of all possible sets. The figure to the right illustrates this idea. Set F is the universal set. Set E is a superset.

Review Types of Sets.

1c. Describe set notation and how that notation is used to perform operations via symbol manipulation

Given a certain operation on a group of sets, how can that operation be represented diagrammatically?
Are there cases when an element cannot be a member of more than one set at a time? How so?
Are partial set memberships allowed? How so?

Operations, characterized as equations, are found in all areas of mathematics. Set theory is no different since it allows for operations to be performed on sets and set members. These operations are strictly defined since there must be a common definition for useful discussion between practitioners.

As noted earlier, an element can be fully a member of more than one set at a time. This is true if we stick solely within the framework of set theory. However, remember that we have to create solutions to situations we find in the real world. Semantics, the true meaning of words within the context of the situation, matter in that world. Take for instance the words YES and NO. In many situations, there is no MAYBE and the answer cannot be YES and NO at the same time. The set "answer" cannot contain the elements "yes" and "no" at the same time. For instance, we cannot take an action and not take that action at the same time. For set theory to have any meaning in the world outside pure mathematics, it has to be interpreted within the context of real-world situations. This provides a means of transitioning theory to reality.

There are many ways to express operations in set theory. We can use equations, generalizations, and Venn diagrams. Venn diagrams use oval shapes to depict set operations. Many people learn and understand better pictorially. Plus, pictures are an aid to understanding what equations, and especially generalizations, are saying. The same is true, for instance, with equations that deal with data that arrives over time. A graph of how the equation behaves each time unit goes a long way to assist in understanding what the equation represents, its behavior over time.

Review:

1d. Apply set definitions, operations, and properties to demonstrate set membership within a specific context

What are the symbols associated with various set operations and generalizations?
How does one apply Venn diagrams to illustrate the results of set operations?
What are important ways that set theory applies to real-life situations?

In other learning goals for this unit, we have seen how precise definitions of terms, symbols, operations, and generalizations make it possible for us to communicate on a given topic. This is also true with set theory. It is important to know the basic means of discussion. Definitions in common use for social conversation are woefully vague for this purpose.

Beyond precision in definition, there is understandability. If a long equation can be generalized into a shorter equation, that leads to better understanding. Another approach is to draw a picture, a Venn diagram in the case of set theory. Graphs of various kinds are often used in other fields of work. A picture that relates sets to the result of the operations between them can be very valuable for visualizing what equations are trying to convey.

If our learning is to have value, it has to make a positive difference in the real world. Knowing or developing theory, by itself, has little value unless it is applied to a worthwhile purpose. Here is an example: A great entrepreneurial opportunity is presented by the internet. One can easily set up a store that sells items, even if one never deals with the physical items themselves. (Beware. Running a store profitably is never easy. And, it is fraught with risk. Most stores fail.) Let's say the store carries electronic components, we could say that set S, the store, carries a finite number of components, {c₁, c₂, ..., c_n}. There may be several of each component available, {c_1|1, c_1|2, ... c_1|m}, if c₁ is used as an example. One thing that would help customers know what to buy for what purpose might be a series of well-documented kits, {k₁, k₂, ..., k₃}, that put various components together. Set theory can be used to bring that idea forward. We could think of a generalized set equation such as K₁ = {c_1|2, c_3|1, c_100|5}. This a short-hand way of saying Kit #1 is composed of: two units of Component #1, one unit of Component #3, and five units of Component #100. The Venn diagram to the right illustrates this idea. There is no reason software could not be written to create such diagrams from inventories and parts lists, where the size of the circles represents the number of components available. Links embedded in the image could lead to all manner of detail. To get the number of parts in a kit via this generalization:

$\mathrm{K}_{i \mid \mathrm{n}}=\sum_{a=1, b=1}^{p, y} \mathrm{C}_{\mathrm{a} \mid \mathrm{b}}$

where:

K_i|n refers to the number of parts (components) in kit I
p refers to the part number
y refers to the number of parts of that part number used in kit I

While this last equation may be too complex for the case at hand, it shows that complexity is available when needed.

Review:

Unit 1 Vocabulary

This vocabulary list includes terms you will need to know to successfully complete the final exam.

collection
elements
empty set
finite
formal definitions
formal notations
members
notation
null set
set
set-builder notation
superset
symbolism
terminology
universal set
Venn diagram