## Tuesday, September 3, 2013

### Mathematics -- Part Two: Sets

In mathematics, a set is a collection of distinct objects, considered as an object in its own right. For example, the numbers 2, 4, and 6 are distinct objects when considered separately, but when they are considered collectively they form a single set of size three, written {2,4,6}.

Sets are one of the most fundamental concepts in mathematics. Developed at the end of the 19th century, set theory is now a ubiquitous part of mathematics, and can be used as a foundation from which nearly all of mathematics can be derived. Sets are what us older folks that went to school in the days of the one-room school house call “The New Math,” and often struggle helping our elementary school age children with the math because it isn’t how we were originally taught in our day and had these diagrams named after some Swede called "Venn." These days, elementary topics such as Venn diagrams are taught at a young age, while more advanced set concepts are taught as part of a university degree.

You can consider a set as a “bag” that objects are placed in. There is no order in a set (except in an “ordered set”) and the basic concept is membership. An object is either a member of a set or it is not. It’s like a club. (And I’m always reminded of the statement by Groucho Marx that he wouldn’t belong to any club that would allow him to join.) There can be sets within sets, just like a bag within a bag, the so-called subsets.

Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics. The language of set theory can be used in the definitions of nearly all mathematical objects.

There are several basic operations that can be performed on a set. Sets can be combined in a number of different ways to produce another set.

#### Set Union

One operation is called “Union.” In mathematical notation, The Union of sets A and B, denoted by AB, is the set defined as

AB = { x | x ∈ A ∨ x ∈ B }

Well, that is the new math indeed. Looks sort of like Greek. Recall from my first article that I said math was a universal language. Well this is actually a very precise mathematical statement using that universal language. You know that the symbol “∪” means “Union.” The vertical bar (“|”) means “such that” and the “V” looking character (“∨”) stands for the english word “or.” The funny looking “e” (“∈”) stands for membership and is read as “is in” or “is a member of.” So now we can translate that the “union of sets A and B equals all x (or members) such that x is in or is a member of set A or x is a member of set B.

It is much more clear if we use a diagram called a Venn diagram. Venn diagrams consist of circles that represent the set. It is sort of the “bag” that all the members are in. Inside a particular circle are all the member objects and outside are all the objects that are not a member. When showing sets, we assume some objects can be members of two or more sets. The set is shown inside a box called the "Universe," which contains all possible objects of the type being considered, such as all Integers or all numbers. For example, the number 12 is a member of the set of all even numbers and it is also a member of the set of all numbers that are multiples of three.

Here is a Venn diagram for two sets and the Union of those two sets is everything inside either the circle for set A or the circle for set B. The Union is sort of like adding the two sets, only remember a given object can only be a member of a given set “once.” That means the Union is all the members that are only in set A plus all the members that are only in set B plus all the members that are in both sets.

Here’s the diagram

My earlier example was mathematical and used numbers, but set theory is so basic and so powerful that objects can be anything from data records in a computer to human beings, animals, and plants. For example, the Union of the set of all members of the Kiwanis and the set of men in the city of Denver. It is both the powerful generality of sets combined with their very specific language and rules that makes them so useful and allows them to be used to construct the very foundation of arithmetic and all of mathematics. It is a modern answer to an age old problem of putting math on a very solid foundation.

As most people know, in the “old days,” houses were not necessarily built on good foundations. Some houses were built on wood that rotted or on soil that shifted. There were no building codes or modern engineering and some old buildings, like the Tower of Pisa, are now suffering from foundation failure. In the Nineteenth Century, set theory was invented to put all of math on a very good foundation. Consider set theory as the concrete footings of modern math.

This set of blog articles (yes, even articles can be in a set) is just intended to be an introduction to math, not an in depth explanation, so I’ll just cover a few more set operations. This will give you a feeling for what modern set theory is all about in case you didn’t go to a school that taught the “new math.”

#### Set Intersection

Besides Union, set theory defines an “Intersection.” The Intersection of sets A and B, denoted by AB, is the set defined as

AB = { x | x ∈ A ∧ x ∈ B }

Translating, Intersection of sets A and B equals all x (or members) such that x is in or is a member of set A AND x is a member of set B. (The symbol “∧” stands for “and.”) In other words, the Intersection includes all the objects that are members of both sets. Do you get a feeling that Union and Intersection are sort of like the left hand and right hand. They are closely related, not exactly inverses, but somehow they are “opposite” or “mirror images” of each other.

Here is the Venn diagram for Intersection.

#### Subset

I will cover one more set operation. That is the previously mentioned concept of “subset.” That is a set contained within a set. An example would be the set of all citizens of the United States. It contains a subset that is all the women who are citizens of the United States or all citizens of the United States that receive Social Security checks. The subset must be wholly contained within the outer set (called the "superset") to be a subset.

Here’s the Venn diagram.

So if set A is a subset of set B, then every member of set A is also a member of set B. It is logical to think of the subset as a smaller set, but it is possible that both sets are the same size. That is, they have the same number of members. Consider the set of all even numbers which is a subset of all numbers that are divisible by two. Actually, they are the same set. One is a subset of the other and vice-versa, which is the definition of set equality. Usually, though we consider subsets as “smaller” or less members than the superset. A subset that has less members than the superset is called a “proper” subset.

There’s a lot more set operations including set difference, complements, ordered pairs, cartesian products, n-tuples, and equality. All together it is a powerful notation and concepts for describing other mathematical concepts. That’s the point. Prove something with set theory and then you’ve proved it for other branches of math that can be “mapped” to set theory, and that’s about all of mathematics. It is simple enough to teach to elementary school kids and powerful enough to use in a graduate math course. Set theory can also be used to expand mathematics into other areas such as computer database operations and other Computer Science subjects or topics such as anthropology or botany or the theory of games. Sets, in a sense, are the most basic mathematics; even more basic than numbers.

#### Number Sets

The symbol for subset is “⊂,” although that is actually the symbol for proper subset or the so-called “strict” subset. In the first chapter of this Mathematics series I defined sets of numbers such as the Natural numbers, Integers, Reals, and Complex. We can now use set notation to indicate the relationships between these sets. I’ll use some special symbols for the numeric families.

Natural Numbers (counting numbers) = ℕ
Integer = ℤ
Rational = ℚ
Real = ℝ
Complex = ℂ
Universal Set (all possible values) = U (I couldn’t find the html symbol for “U.” It looks like the others above.)

ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ ⊂ ℂ ⊂ U

You can use set notation to define sets. For example:

ℝ = ℚ ∪ ℚ'

where " ' " represents not. That is, the Irrationals are the numbers that are not Rational. (Not exactly true since Complex numbers are also in the Universe. So it can depend on what you define as the Universe, but be careful of circular definitions … just like the caution in grammar. In this case we interpret ℚ' as "Irrational," that is all Real numbers that are not Rational.)

The better formed equation would be ℚ' = ℝ − ℚ. (You may have guessed that there is set "subtraction" and it removes members.)

You may be curious about how these labels were chosen. Obviously, we don't use "R" for Rational since it is used for "Real." You can consider "Q" as "quotient" because the Rational numbers are all formed as the quotient, or division, or fraction with two Integers. The Integers use "Z" from the German word for "number," "Zahlen." These symbols were developed in the '30s and are now accepted in mathematical notations. They started being used in scientific papers and then in text books and now they are the standard.

Of course, using "I" for Integers would be confused with Irrationals and even Imaginary numbers. Due to alphabetic confusion, in electronics engineering, where "I" is used for Current ("Intensity" of Current, "C" was already taken for "Capacitance" … I know … too complicated.) So, in EE you use j instead of i for √−1to keep from confusion with current.

Now let's talk about the two letter abbreviations for the states … just kidding.

Many mathematical concepts can be defined precisely using only set theoretic concepts. For example, mathematical structures as diverse as graphs, manifolds, rings, and vector spaces can all be defined as sets satisfying various (axiomatic) properties. Equivalence and order relations are ubiquitous in mathematics, and the theory of mathematical relations can be described in set theory.

Sets can be used as an abstraction of arithmetic. In reality, all of mathematics is a form of abstraction. Even the numbers are abstractions. What does it mean to talk about “seven”? What is 7? I can explain what seven dollars are, or seven cupcakes, but what is “seven”? It is an abstraction. It is a representation. And … we can use it for keeping track of our dollars and our cupcakes.

The next topic is “algebra.” That’s an abstraction of arithmetic. Instead of “7,” we will let “x” stand for the number of cupcakes. That’s next in Mathematics — Part Three: Algebra.