17 Feb

What They Don’t Teach You About Sets 2

Posted by hishamuddinz in Uncategorized.

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:

11 Feb

What They Don’t Teach You About Sets 1

Posted by hishamuddinz in Uncategorized.

Resurrected this blog (again) for posting my postgraduate lectures/talks here. Here are the notes from LuFTER 1/2011 February 9, 2011. The Lunchtime Foundational Theory Expositions and Ruminations will consists of mainly lectures to my postgraduate students and occasionally research seminars, proposals etc.

The present ongoing lectures are meant to introduce mathematical structures in theoretical physics with perhaps Nirmala Prakash’s book as a guide of topics to be covered (but not necessarily adhering to it). The book itself is skewed towards topics for string theory but we will also cover other topics. The first topic will be on set theory. The mischievous title of the lecture is taking cue from Devlin’s book entitled “The Joy of Sets”, which is referenced.

Relationships and Sets

In most (conventional) physics, often use very rich mathematical structures (e.g. differential geometry) from the outset, which assume many things. Advances in foundational theories (e.g. quantum gravity) tend to relook at the usage basis of these structures and either generalize them or opt for primitive structures. So, what would be considered the most primitive structure? Set theory seems to fit the role with its common usage as a mathematical language. However, usually physicists are only exposed to very elementary ideas of set theory and perhaps not see its full power often only found in more advanced mathematics course. We hope to remedy this a little. In fact the deeper usage of set theory is really the following:

  • understanding the infinite
  • foundational subject matter of mathematics
  • common mode of reasoning

So what is a set? Its fundamental idea is simply the ability to regard a collection of objects as a single entity (the set). This sounds circular. In fact, in set theory, the undefinables are really the notion of a set and the relation “is an element of”. We introduce notation:

  • “x \in X” which means “x is an element of X“;
  • “x \notin X” which means “x is not an element of X“.

In forming sets, one can either

  • enumerate the elements or members of the set e.g. X = \{ x_1 , x_2 , \cdots , x_n , \cdots \}; or
  • describe by using some property P e.g. X = \{ x : P(x) \}, which is the set of all x for which P(x) holds. Example: \mathbb{C} = \{ z : z \textrm{ is a complex number} \}.

Using normal sentences to describe a set may not be best. Better, use logical statements. For this, we introduce the logical notations:

  • \Rightarrow means “implies”;
  • \Longleftrightarrow means “if and only if”;
  • \neg means “not”;
  • \wedge means “and”;
  • \vee means “or”;
  • \forall means “for all”;
  • \exists means “there exists”.

With these, one can start building logical statements for the set building. Some examples logical statement are given below (which also shows that some logical operations can be “derived” from others.

Example 1: P \Longleftrightarrow Q is the same as (P\Rightarrow Q) \land (Q\Rightarrow P)
One can build the truth table to show this is true.

\begin{array}{c|c|c} P\Rightarrow Q & Q\Rightarrow P & (P\Rightarrow Q)\land(q\Rightarrow Q)\\ \hline \textrm{False} & \textrm{False} & \textrm{False}\\ \textrm{False} & \textrm{True} & \textrm{False}\\ \textrm{True} & \textrm{False} & \textrm{False}\\ \textrm{True} & \textrm{True} & \textrm{True}\end{array}

Note that we could have build the truth table out of atomic statements instead of compound ones but we leave this for the reader to elaborate.

Exercise 1: Show that P\Rightarrow Q is the same as (\neg P)\vee Q.

Example 2: P\vee Q is the same as \neg((\neg P)\land(\neg Q)).
Now we build the truth table from the atomic statements for illustration.

\begin{array}{c|c|c|c|c|c} P & Q & \neg P & \neg Q & (\neg P)\land(\neg Q) & \neg((\neg P)\land(\neg Q))\\ \hline \textrm{False} & \textrm{False} & \textrm{True} & \textrm{True} & \textrm{True} & \textrm{False}\\ \textrm{False} & \textrm{True} & \textrm{True} & \textrm{False} & \textrm{False} & \textrm{True}\\ \textrm{True} & \textrm{False} & \textrm{False} & \textrm{True} & \textrm{False} & \textrm{True}\\ \textrm{True} & \textrm{True} & \textrm{False} & \textrm{False} & \textrm{False} & \textrm{True}\end{array}

This example is illustrative of the fact that one does not need all the logical operations; here, the “or” operation has been replaced by a combination of a “not” and an “and”. It is in fact well known that the “nand” gate (combining “not” and “and”) is a universal gate for classical computations.

In handling or consructing sets abstractly, it is important to ponder on Quine’s dictum “No entity without identity”. How would one know that two so-called abstract entities (sets) are not one and the same? Here, we state the following axiom of extensionality telling us when two sets X and Y are the same:

X=Y \iff \forall x (x\in X) \Longleftrightarrow (x\in Y) .

Thus, for example \{a,b,c\} = \{c,a,b\}. In this regard, there is one important set that we need to construct, namely the empty set \emptyset or \{\}. It can be defined as

\emptyset = \{ x: x \neq x \} .

Note from this definition, in principle we could have started with x coming from different sets, say X giving \emptyset_X and \chi giving \emptyset_\chi. But by virtue of axiom of extensionality, the empty set is unique, being the set with no elements (Exercise 2: Prove this).

Exercise 3: Using results of exercise 1, prove the statement x\in\emptyset \Rightarrow P(x) is true for all x.

An easy way to define more sets is to consider another set relation, namely subsets. We define Y is a subset of X, written as Y\subseteq X, if and only if every element of Y is an element of X i.e.

Y\subseteq X\Longleftrightarrow\forall x((x\in Y)\Rightarrow(x\in X)) .

Note that in this case X is also called superset of Y i.e. X\supseteq Y. In both these relations, it is possible that X=Y. But if you would like to consider otherwise i.e. considering Y is a proper subset of X, then we write Y\subset X where

Y\subset X\Longleftrightarrow(Y\subseteq X)\land(Y\neq X) .

Another important set concept is the idea of a power set \mathcal{P}(X) of the set X, which is the set of all subsets of X i.e.

\mathcal{P}(X) = \{ Y :Y\subseteq X\} .

We will illustrate the idea of power sets in a minute but before that one introduces another set relation namely the cardinality. Cardinality is a measure of the “size’ of the set particularly by looking into the “number” of its elements. We denote the cardinality of a set X by \sharp(X) or \textrm{card}(X).

Example 3: Consider the set X=\{\Diamond\}. Its cardinality is \sharp(X)=1. The power set of X is \mathcal{P}(X)=\{\emptyset,\{\Diamond\}\} and hence \sharp\mathcal{P}(X)=2. One could proceed further to find the power set of \mathcal{P}(X) itself:

\mathcal{P}(\mathcal{P}(X))=\{\emptyset,\{\emptyset\},\{\Diamond\},\{\emptyset,\{\Diamond\}\}\} ;

with \sharp\mathcal{P}(\mathcal{P}(X))=4. In fact, one can iterate this n times and find \sharp\mathcal{P}^{(n)}(X) = 2^n. It is interesting to note that the empty set played a role in increasing the cardinality of the nested power sets. We will later show that one can do better than this to build up what we know as numbers.

To end this part, I add a cautionary note that not all collections of objects can form a set. Consider the Russell set:

R=\{x:x\notin x\} .

Let’s ask: does R satisfies the property given? If yes, then R\notin R but then by the set definition R\in R – giving a contradiction. Suppose the answer is no then, which means R\in R. However the set definition implies R\notin R – again, a contradiction. This is essentially known as the Russell’s paradox. It’s resolution? Perhaps, it is too much to impose R to be a set, but R is said to be a class (will not elaborate here). Essentially the idea is to differentiate the use of a symbol and the meaning of the symbol. Alternatively, one could axiomatize set theory using Zermelo-Fraenkel axioms, which is beyond the scope of the lecture.

References

I list here some of my reading materials without attempting to show where I have used them. Go read them, if you have interest.

Follow

Get every new post delivered to your Inbox.