# Gracious Living

Sets
October 24, 2010, 17:31
Filed under: Math, Set Theory | Tags: , ,

This will probably be review for a lot of readers, but I just want to make sure we’re all on the same page before we really start.  These terms get used a lot a lot in higher math.  In the 1900’s, sets were seen by luminaries like Bertrand Russell as being the salvation of math, since you could describe basically any mathematical structure in terms of sets.  Nowadays, mathematicians tend to believe that the “guts” of math really aren’t that important, and category theory, which instead describes the relations between structures, has become more foundational.  By the way, category theory is just about the coolest possible thing, but its coolness only really becomes apparent once you have a bedrock of examples to work with.  I’ll start talking about it much later.  For now, let’s talk about sets.

A set is basically a collection of objects.  These objects can be anything, but generally we’ll be working with sets of math-related objects — points, numbers, or other sets.  Sets can also be finite or infinite.  The set of all natural numbers is an example of an infinite set.  We write sets with curly braces, and we treat them as having no structure whatsoever — in particular, we don’t worry about repetition or ordering of the elements.  The following are all equivalent ways of writing a set:

$\displaystyle\{3,1,3,5,5,7\}=\{1,3,5,7\}=\{x:x\text{ is an odd number between }1\text{ and }7\}=\{\text{odd numbers }x:1\le x\le 7\}$

An object in a set is called an element.  If $x$ is an element of the set $A$, we write $x\in A$ or $A\ni x$.  There’s a set with no elements, which we’ll call the empty set$\emptyset$.  If all the elements of $A$ are also in $B$, we say that $A$ is a subset of $B$ or that $B$ is a superset of $A$, and write $A\subset B,B\supset A$.  Note that this allows for the possibility $A=B$, so that $A\subset A$ (since any element of $A$ is also in $A$); but it is also true that $\emptyset\subset A$ (since there are no elements in $\emptyset$ that aren’t in $A$; this is called vacuous truth, make sure it makes sense to you).  If $A\subset B$ but $A\ne B$ and $A\ne\emptyset$, we say that $A$ is a proper subset of $B$ and write $A\subsetneq B$

Maybe we want a little more structure.  You’ve probably seen ordered pairs before; they’re written with parentheses and have the property that $(3,4)\ne(4,3)$ (while $\{3,4\}=\{4,3\}$.  An ordered $n$tuple is the same thing, but with $n$ coordinates instead of 2.  Again, $n$ can be infinite; $(1,2,3,\dotsc)$ is an example of an “$\omega$-tuple,” or just a sequence.  We’ll be talking about larger sizes of infinity where it’s no longer possible to even begin to write such a thing down.  But we can still imagine that one exists, with its essential property that the order of the coordinates matters.  We sometimes talk about an index set $I$ and write the tuple as $(a_i)_{i\in I}$.  Then if, say, $3.1\in I$, we can talk about $a_{3.1}$ as the “3.1th coordinate” of the $I$-tuple.

The following operations are defined for sets:

• The union of $A$ and $B$ is $A\cup B=\{x:x\in A\text{ or }x\in B\}$.
• The intersection of $A$ and $B$ is $A\cap B=\{x:x\in A\text{ and }x\in B\}$.
• The difference of $A$ and $B$ is $B-A=\{x:x\in B\text{ but not }A\}$.
• The product of $A$ and $B$ is $A\times B=\{(x,y):x\in A,y\in B\}$.  In other words, it’s the set of ordered pairs with the first coordinate in $A$ and the second in $B$.

There are a ton of set identities involving these operations, and you can prove basically all of them by Venn diagrams.  The product, as we defined it, isn’t associative, since $A\times(B\times C)=\{(a,(b,c))\},(A\times B)\times C=\{((a,b),c)\}$; but we can easily define it for any finite number of sets by

$\displaystyle A_1\times\dotsb\times A_n=\{(a_1,\dotsc,a_n):a_i\in A_i\}$.

In fact, we’ll end up needing these operations for infinite numbers of sets, and we can do this using index sets.  Let $\mathcal{A}$ be the set of sets $\{A_i\}$ where $i$ takes values in some index set $I$.  Then we define:

$\displaystyle\bigcup\mathcal{A}=\bigcup_{i\in I} A_i=\{a:a\in A_i\text{ for some }i\in I\}\\ \bigcap\mathcal{A}=\bigcap_{i\in I}A_i=\{a:a\in A_i\text{ for all }i\in I\}\\ \prod\mathcal{A}=\prod_{i\in I}A_i=\{(a_i)_{i\in I}:a_i\in A_i\}$

(The last symbol is a Greek capital “pi,” for “product.”  Some people just use a giant multiplication sign.)  Though index sets make this easier, we don’t really need them; we can define, say, $\bigcup\mathcal{A}$ for any set of sets $\mathcal{A}$ as the set of objects that are an element of some element of $\mathcal{A}$.

A final useful notion is the power set of a set $A$, which is just the set of all subsets of $A$.  We write this as $latex\mathcal{P}(A)$.  For example,

$\displaystyle \mathcal{P}(\{1,3,5\})=\{\emptyset,\{1\},\{3\},\{5\},\{1,3\},\{3,5\},\{1,5\},\{1,3,5\}\}.$

Clearly, $\bigcup\mathcal{P}(A)=A$ itself.

My cool example for today is the reason that set theory is nontrivial.  I said that sets could contain sets, right?  Logically, we might as well let them contain themselves, then.  If this is the case, we can define the Russell set $R=\{A:A\not\in A\}$, the set of all sets that don’t contain themselves.  Okay… so does the Russell set contain itself or not?  It can only contain itself if it doesn’t contain itself, but if it doesn’t contain itself, it must be in the Russell set.  This is a paradox, and so such a set can’t exist.  But this means we can’t just define a set as a “collection of objects” after all, at least not if we want sets to be considered “objects”.  The currently accepted solution is an axiom that prevents this problem; among other things, it stops us from having a “set of all sets,” or a set that contains itself, or an infinite chain of sets with more sets as elements.  Sometimes mathematicians find it useful to talk about a collection of all sets.  Typically we call this a “class” instead of a set, with the idea that classes can have elements but not be elements.

Oh, there are a few important examples of sets we’ll refer to again and again.  The natural numbers are $\mathbb{N}=\{1,2,\dotsc\}$ (with some authors including 0 as well).  The integers are $\mathbb{Z}=\{\dotsc,-2,-1,0,1,2,\dotsc\}$ (the Z stands for German “zahlen,” which means “to count”).  The rational numbers are just fractions: $\mathbb{Q}=\{a/b:a,b\in\mathbb{Z}\text{ and have no common factors}\}$.  The last part is more important than it looks: for example, Euclid’s proof that $\sqrt{2}$ is irrational relies on it.  The real numbers, $\mathbb{R}$, are the rational and irrational numbers, and we think of them as filling up a “number line.”  The question of “what are the reals” is important and I’ll get to formal definitions soon.  Finally, the complex numbers, $\mathbb{C}$, are numbers of the form $a+bi$ for $a,b\in\mathbb{R}$, where $i$ is formally defined as $\sqrt{-1}$.  As a set, this is just $\mathbb{R}\times\mathbb{R}$, but with the added ability to multiply and divide.  We can think of them as lying on a plane with the real numbers $a+0i$ on the horizontal axis and the imaginary numbers $0+bi$ on the vertical axis.

Thanks for reading!  If anything seems confusing or interesting, ask and I’ll discuss it further.  Soon, we’ll get to the good stuff.

[…] math we’ll be using is all founded in set theory.  Consider a set , whose elements we’ll call “points.”  A topology on is a set […]

Pingback by Topology | Gracious Living and the Two Meat Meal

[…] that we shouldn’t be using the standard “collection-of-things” visualization that sets were first introduced with.  Rather, the axioms will formally give us the idea that “piles-of-things” model so […]

[…] we’re going to do today is measure sets.  I said that sets have no structure back in the first couple of posts, but this isn’t entirely true.  Finite sets, for example, […]

[…]  Hilarious.  (A Boolean algebra is a mathematical structure that looks like the class of sets with the operations of union, intersection, and complementation.  Deductive logic itself basically […]

Pingback by It is 2011 now. « Gracious Living