What They Don’t Teach You About Sets 2

17 Feb

What They Don’t Teach You About Sets 2

Posted February 17, 2011 by hishamuddinz in Uncategorized. Leave a Comment

This is the second installment of notes of my lecture in LuFTER 1/2011. In the last post, we are limited to relationships on a given set. With so limited tools, we will not be able to do much apart from say, solving taxonomic problems. Here, we will now introduce more structures, namely operations on sets.

Set Operations

The two basic operations of set theory are the well-known set union and set intersection.

The union $X\cup Y$ of sets $X$ and $Y$ is the set of objects whose members are either members of $X$ or members of $Y$ i.e.

$X\cup Y=\{x:(x\in X)\lor(x\in Y)\}$ .

The set union obeys commutativity

$X\cup Y=Y\cup X$ ,

and associativity

$X\cup(Y\cup Z)=(X\cup Y)\cup Z$ .

The intersection $X\cap Y$ of sets $X$ and $Y$ is the set of objects whose members are members of both $X$ and $Y$ i.e.

$X\cap Y=\{x: (x\in X)\land(x\in Y)$ .

Similarly the set intersection also obeys commutativity and associativity:

$X\cap Y=Y\cap X$ ;

$X\cap(Y\cap Z)=(X\cap Y)\cap Z$ .

Exercise 1: Prove the commutativity and associativity laws for the set union and intersection.

At this juncture, one should probably have noticed the correspondence between set union and intersection with the logical or and logical and respectively. Later, we will see that these set operations do indeed give the algebra of Boolean logic. (Question: Which comes first?) It is also good to highlight one can extend both union and intersection to a family of sets $X_i$ where $i\in I$ for some labelling set $I$ ; namely $\bigcup_{i\in I} X_i$ and $\bigcap_{i\in I} X_i$ . You will probably see them in defining topological space.

One could go further to define the idea of set-theoretic difference $X-Y$ (perhaps as opposed to the union) as

$X-Y=\{x:(x\in X)\land(x\notin Y)$ .

Sometimes, it is also denoted as $X\backslash Y$ . An example is the set difference $\mathbb{R}-\mathbb{Q}$ between the set of real numbers $\mathbb{R}$ and the set of rational numbers $\mathbb{Q}$ ; the resultant set is the set $\mathbb{J}$ of irrational numbers.

Exercise 2: Prove $X-Y=X-(X\cap Y)$ .

Note that if $X\cap Y=\emptyset$ , then $X$ and $Y$ is said to be disjoint. Related to the set difference operation is the symmetric difference i.e.

$X\Delta Y=(X-Y)\cup(Y-X)$ ,

and this has “better” properties:

$X\Delta Y=Y\Delta X$ ;
$X\Delta Y=(X\cup Y)-(Y\cap X)$ ;
$(X\Delta Y)\Delta Z=X\Delta(Y\Delta Z)$ .

Often one build sets from one large set (the universe of discourse) and this large set, we called universal set $U$ . Within such set then, we can now define an operation called complement $X^c$ of the set $X\subset U$ :

$X^c=\{x:x\in U\land x\notin X\}$ .

This complement operation obeys the following:

$(X^c)^c=X$ ;
$\emptyset^c=U$ ;
$U^c=\emptyset$ ;
$X\cup X^c=U$ ;
$X\cap X^c=\emptyset$ .

The complement operation also obeys the deMorgan’s laws:

$(X\cup Y)^c=X^c\cap Y^c$ ;
$(X\cap Y)^c=X^c\cup Y^c$ .

One can see that the complement really acts like a NOT gate.

Exercise 3: Prove the properties of the complement operation including deMorgan’s laws.

To complete the logic operations analogy, one adds further the distributivity law whenever one mixes both the union and intersection operations together:

$X\cup(Y\cap Z)=(X\cup Y)\cap(X\cup Z)$ ;
$X\cap(Y\cup Z)=(X\cap Y)\cup(X\cap Z)$ .

Exercise 4: Prove the distributive laws.

Putting together all the operations together with the sets $X,Y,Z$ in $U$ , they form what is known as the Boolean algebra.

We end this part by giving an interesting example of constructing the “natural numbers” using set operations. We begin with the empty set $\emptyset$ , which we conveniently called it $0$ . Next, we define what we called as the successor set $S(n)=n\cup\{n\}$ giving the following sequence (with more relabelling):

$0:=\emptyset$ ;
$1:=S(0)=0\cup\{0\}=\emptyset\cup\{0\}=\{0\}$ ;
$2:=S(1)=1\cup\{1\}=\{0\}\cup\{1\}=\{0,1\}$ ;
$3:=S(2)=2\cup\{2\}=\{0,1\}\cup\{2\}=\{0,1,2\}$ ;
$\qquad\vdots$

The collection $\{0,1,2,3,\cdots\}$ forms the set $\omega$ of natural numbers, which can be shown to obey the Peano postulates:

$0\in\omega$ ;
$\forall n\in\omega\Rightarrow S(n)\in\omega$ ;
$\forall n,m\in\omega\ (n\neq m)\Rightarrow(S(n)\neq S(m))$ ;
$\forall X\subset\omega,\ ((0\in X)\land(\forall n\in X(S(n)\in X)))\Rightarrow X=\omega$ .

The set $\omega$ can then be identified with the natural numbers $\mathbb{N}=\{0,1,2,\cdots\}$ . One could easily see that for $m,n\in\omega$ , then $m\in n\Rightarrow m\subset n$ implying the orderedness of numbers, a property that we will touch upon later. In fact we could do more by defining addition and multiplication using set-theoretic relations and operations.

It is often remarked that this example is like creating something (numbers) out of nothing (the empty set). In some sense, it is but there is no need to philosophize it too much (and in no way it is like the creation operation!). It is simply an abstraction of the counting operation. An analogy can be made with by first peering into an empty box and later put the empty box in another box, and the latter box in one other box ad infinitum, very much like the Russian doll. If there is anything to philosophize on, is that numbers can be thought of as an abstract mental construct that we associate with counting – a fact that we often forget.

References

These are additional references since the first part:

Kenneth Kunen, “Set Theory: An Introduction to Independence Proofs“, (North-Holland, 1990)
Ian R. Porteous, “Topological Geometry“, (Cambridge Univ. Press, 1981)
Roger Godement, “Algebra“, (Hermann, 1968)

Like this:

Be the first to like this post.

M	T	W	T	F	S	S

	1	2	3	4	5	6
7	8	9	10	11	12	13
14	15	16	17	18	19	20
21	22	23	24	25	26	27
28

Ketchup Spills Catching up on matters of theoretical physics and other related spills

What They Don’t Teach You About Sets 2

Like this:

Leave a Reply Cancel reply

Meta

Blog Stats

Whence

Past Light Cone

Blogroll

Follow “Ketchup Spills”