Home » Posts tagged 'set theory'

Tag Archives: set theory

A Trip To Mathematics: Part II Set(Basics)

Friday, November 4th, 2011 05:55 / 3 Comments

Introduction

In English dictionary, the word Set has various meanings. It is often said to be the word with maximum meanings (synonyms). But out of all, we should consider only one meaning: ”collection of objects” — a phrase that provides you enough clarity about what Set is all about. But It is not the exact mathematical definition of Set . The theory of Set as a mathematical discipline rose up with George Cantor, German mathematician. It is said that Cantor was working on some problems in Trigonometric series and series of real numbers, which accidently led him to recognise the importance of some distinct collections and intervals. And he started developing Set Theory. Well, we are not here to discuss the history of sets; but Mathematical importance.

Cantor defined the set as a ‘plurality concieved as a unity’ (many in one; in other words, mentally putting together a number of things and assigning them into one box).
Mathematically, a Set $S$ is ‘any collection’ of definite, distinguishable objects of our universe, concieved as a whole. The objects (or things) are called the elements or members of the set $S$ . Some sets which are often termed in real life are, words like ”bunch”, ”herd”, ”flock” etc. The set is a different entity from any of its members.
For example, a flock of birds (set) is not just only a single bird (member of the set). ‘Flock’ is just a concept with no material existence but ‘Bird’ or ‘birds’ are real.

Representing sets

Sets are represented in two main ways:
1. Standard Method: In this method we use to write all elements of a set in a curly bracket ( { } ).
For example:
Flock of Birds := {Bird-1, Bird-2, …, Bird-100,…}
or, $F:= \{B_1, B_2, \ldots, B_{100}, \ldots \}$ is a set.
Here I have used first capital letter of each term to notate the example mathematically. We read this set as, A set F is defined by a collection of objects $B_1, B_2, \ldots$ etc.
2. Characteristic Method: In this method, we write a representative element and define that by a characteristic property. A characteristic property of a set is a property which is satisfied by each member of that set and by nothing else.
For example, above set of Flock of birds can also be written as:
$\mathrm{ F := \{ B : B \ is \ a \ bird \} }$
which has the same meaning at a wider extent. We read it as: ”A set F is defined by element B such that B is a bird.”

Standard Sets

Some standard sets in Mathematics are:

Set of Natural Numbers: It includes of the numbers, which we can count, viz. $\mathrm{ \{0,1,2,3,4,5,6,7, \ldots \}}$ . The set of natural numbers is denoted by $\mathbb{N}$ .

Set of Integers: Integers includes of negatives of natural numbers and natural numbers itself. It is denoted by $\mathbb{Z}$ . $-5, -4, 1, 2, 0$ …all are integers. The rigorous definition of integers be discussed in fourth part of the series.

Set of Rational Numbers: Rational numbers are numbers which might be represented as $\frac{p}{q}$ , where p and q both are integers and relatively prime to each other and q not being zero. The set of rational numbers is represented by $\mathbb{Q}$ and may include elements like $\frac{2}{3}, \frac{-5}{7}, 8$ . The characteristic notation of the set of rational numbers is $\mathbb{Q} := \{ \dfrac{p}{q};/ p,q \in \mathbb{Z}, \ (p,q) \equiv 1 \ q \ne 0 \}$ . The rigorous dicussion about rational numbers will be provided in fourth part of the series.

Empty Set: It is possible to conceive a set with no elements at all. Such a set is variously known as an empty set or a void set or a vacuous set or a null set.
An example of emptyset is the set $\{\mathrm{x:\ x \ is \ an \ integer \ and \ x^2=2} \}$ , since there exists no integer which square is 2 —the set is empty. The unique empty set is denoted by $\emptyset$ .
Unit Set: A set with only one element is called the unit set. {x} is a unit set.

Universal Set: A set which contains every possible element in the universe, is a universal set. It is denoted by $U$ .

Two Sets

Let $A$ and $B$ be two sets. We say that $A$ is a subset of $B$ (or $B$ is superset of $A$ or $A$ is contained in $B$ or $B$ contains $A$ ) if every element of $A$ is also an element of set $B$ . In this case we write, $A \subseteq B$ or $B \supseteq A$ respectively, having the same meaning .
Two sets are equal to each other if and only if each is a subset of the other. Subset word might be understood using ‘sub-collection’ or ‘subfamily’ as its synonyms.
Operations on Sets:
As Addition, Subtraction, Multiplication and Division are the most common mathematical operations between numbers; Union, Intersection, Complement, Symmetric difference, Cartesian Products are the same between sets.

UNION OF SETS

If A and B are two sets, then their union (or join) is the set, defined by another set $S \cup T$ such that it consists of elements from either A or B or both. If we write the sets A and B using Characteristic Method as,

$\mathrm{A:= \{x : x \ is \ an \ element \ of \ set \ A\}}$ .
and, $\mathrm{B:=\{x : x \ is \ an \ element \ of \ set \ B\}}$
then the union set of A and B is defined by set J such that

$\mathrm{J := \{x: x \ is \ an \ element \ of \ set \ A \ or \ set \ B \ or \ both \}}$ .

For practical example, let we have two sets:
$A:= \{1,2,3,r,t,y\}$ and $B:=\{3,6,9,r,y,g,k\}$ be any two sets; then their union is $A \cup B :=\{ 1,2,3,6,9,r,t,y,g,k \}$ .
Note that it behaves like writting all the elements of each set, just caring that you are not allowed to write one element twice.

Here is a short video explaining Unions of Sets:

INTERSECTION OF SETS

Intersection or meet of two sets A and B is similarly defined by ‘and’ connective. The set {x: x is an element of A and x is an element of B} or briefly $\mathrm { \{ x: x \in A \wedge x \in B \}}$ . It is denoted by $A \cap B$ or by $A \cdot B$ or by $AB$ .
For example, and by definition, if A and B be two sets defined as,
$A:=\{1,2,3,r,t,y\}$
$B:=\{3,6,9,r,g,k\}$
then their intersection set, defined by $A \cap B:= \{3,r\}$ .

In simple words, the set formed with all common elements of two or more sets is called the intersection set of those sets.
Here is a video explaining the intersection of sets:

If, again, A and B are two sets, we say that A is disjoint from B or B is disjoint from A or both A and B are mutually disjoint, if they have no common elements. Mathematically, two sets A and B are said to be disjoint iff $A \cap B := \emptyset$ .
If two sets are not disjoint, they are said to intersect each other.

PARTITION OF A SET

A partition set of a set X is a disjoint collection of non-empty and distinct subsets of X such that each member of X is a member of exactly one member (subset) of the collection.
For example, if $\{q,w,e,r,t,y,u\}$ is a set of keyboard letters, then $\{ \{q,w,e\}, \{r\}, \{t,y\},\{u\}\}$ is a partition of the set and each element of the set belongs to exactly one member (subset) of partition set. Note that there are many partition sets possible for a set. For example, $\{\{q,w\}, \{e,r\},\{t,y,u\}\}$ is also a partition set of set $\{q,w,e,r,t,y,u\}$ .
A Video on Partition of set:

COMPLEMENT SET OF A SET

The complement set $A^c$ of a set $A$ is a collection of objects which do not belong to $A$ . Mathematically, $A^c := \{x: x \notin A \}$ .

The relative complement of set $A$ with respect to another set $X$ is $X \cap A^c$ ; i.e., intersection of set $X$ and the complement set of $A$ . This is usually shortened by $X-A$ , read X minus A. Thus, $X-A := {x : x \in X \wedge x \notin A}$ , that is, the set of members of $X$ which are not members of $A$ .

The complement set is considered as a relatative complement set with respect to (w.r.t) the universal set, and is called the Absolute Complement Set.

A Video on Complement of A Set:

SYMMETRIC DIFFERENCE

The symmetric difference is another difference of sets $A$ and $B$ , symbolized $A \Delta B$ , is defined by the union of mutual complements of sets $A$ and $B$ , i.e., $A \Delta B := (A -B) \cup (B-A) = B \Delta A$ .

Theorems on Sets

$A \cup (B \cup C) = (A \cup B) \cup C$
$A \cap (B \cap C) = (A \cap B) \cap C$
$A \cup B= B \cup A$
$A \cap B= B \cap A$
$A \cup (B \cap C)= (A \cup B) \cap (A \cup C)$
$A \cap (B \cup C)= (A \cap B) \cup (A \cap C)$
$A \cup \emptyset= A$
$A \cap \emptyset= \emptyset$
$A \cup U=U$
$A \cap U=A$
$A \cup A^c=U$
$A \cap A^c=\emptyset$
If $\forall A \ , A \cup B=A$ $\Rightarrow B=\emptyset$
If $\forall A \ , A \cap B=A \Rightarrow B=U$
Self-dual Property: If $A \cup B =U$ and $A \cap B=\emptyset \ \Rightarrow B=A^c$
Self Dual: ${(A^c)}^c=A$
${\emptyset}^c=U$
$U^c= \emptyset$
Idempotent Law: $A \cup A=A$
Idempotent Law: $A \cap A =A$
Absorption Law: $A \cup (A \cap B) =A$
Absorption Law: $A \cap (A \cup B) =A$
de Morgen Law: ${(A \cup B)}^c =A^c \cap B^c$
de Morgen Law: ${(A \cap B)}^c =A^c \cup B^c$

Another Theorem

The following statements about set A and set B are equivalent to one another

$A \subseteq B$
$A \cap B=A$
$A \cup B =B$

I trust that we are familiar with the basic properties of complements, unions and intersections. We should now turn to another very important concept, that of a function. So how to define a function? Have we any hint that can lead us to define one of the most important terms in mathematics? We have notion of Sets. We will use it in an ordered manner, saying that an ordered pair.
First of all we need to explain the the notion of an ordered pair. If $x$ and $y$ are some objects, how should we define the ordered pair $(x,y)$ of those objects? By another set? Yes!! The ordered pair is also termed as an ordered set. We define ordered pair $(x,y)$ to be the set $\{\{x,y\},\{x\}\}$ . We can denote the ordered pair $(x,y)$ by too, if there is a desperate need to use the small bracket ‘( )’ elsewhere.
So, note that Ordered Pairs
$(x,y) := \{\{x,y\},\{x\}\}$
and $(y,x) :=\{\{y,x\},\{y\}\} =\{\{x,y\},\{y\}\}$ are not identical. Both are different sets.
You might think that if ordered pair can be defined with two objects, then why not with three or more objects. As we defined ordered pair (ordered double, as a term) $(x,y)$ , we can also define $(x,y,z)$ , an ordered triple. And similarly an ordered $n$ -tuple $(x_1, x_2, \ldots x_n)$ in general such that:
$(x,y):=\{\{x,y\},\{x\}\}$
$(x,y,z):=\{\{x,y,z\},\{x,y\},\{x\}\}$
$(x_1, x_2, x_3, \ldots x_n) := \{\{x_1, x_2, x_3, \ldots x_n\}, \{x_1, x_2, x_3, \ldots x_{n-1}\}, \ldots, \{x_1, x_2\}, \{x_1\}\}$ .
Another important topic, which is very important in process to define function (actually in process to define ordered pair) is Cartesian Product (say it, Product, simply) of two sets. Let $A$ and $B$ be two sets. Then their Product (I said, we’ll not use Cartesian anymore) is defined to be the (another) set of an ordered pair, $(a,b)$ , where $a$ and $b$ are the elements of set $A$ and set $B$ respectively. Mathematically; the product of two sets $A$ and $B$
$A \times B := \{(a,b) : a \in A, \ b \in B\}$ .
Note that $A \times B \ne B \times A$ .
The name as well as the notation is suggestive in that if $A$ has $m$ elements, $B$ has $n$ elements then $A \times B$ indeed has $mn$ elements.
We see that if we product two sets, we get an ordered pair of two objects (now we’ll say them, variables). Similarly if we product more than two sets we get ordered pair of same number of variables. For example:
$X \times Y := (x,y); x \in X, y \in Y$ .
$X \times Y \times Z :=(x,y,z); x \in X, y \in Y, z \in Z$ . etc.
The sets, which are being product are called the factor sets of the ordered pair obtained. When we form products, it is not necessary that the factor sets be distinct. The product of the same set $A$ taken $n$ times is called the $n$ -th power of $A$ and is denoted by $A^n$ . Thus, $A^2$ is $A \times A$ . $A^3$ is $A \times A \times A$ . And so on.

Now we are ready to define functions. The next part of this series will focus on functions.

Keep Reading and Commenting.

Quick Notes on Elementary Set Theory and Functions

Tuesday, August 30th, 2011 19:01 / Leave a Comment

Cantor’s Concept of a set

A set $S$ is any collection of definite, distinguishable objects of our intuition or of our intellect to be conceived as a whole. The objects are called the elements or members of set $S$
The intuitive principle of extension for sets

Two sets are equal if and only if (iff) they have the same members. i.e., $X=Y \, \Leftrightarrow \,\forall x \in X \text{and} \ x \in Y$ .
The intuitive principle of abstraction

A formula (syn: property) $P(x)$ defines a set $A$ by the convention that the members of $A$ are exactly those objects $a$ such that $P(a)$ is a true statement. $\Rightarrow a \in \{ x|P(x) \}$ .
Operations with/for sets
- Union (Sum or Join) $A \cup B= \{ x | x \in A \, \text{or} \, x \in B \}$
- Intersection (Product or Meet)
  $A \cap B= \{ x| x\in A \, \text{and} \, x\in B \}$
- Disjoint Sets $A$ and $B$ are disjoint sets iff $A \cap B=\emptyset : \text{an empty set}$ and they intersect iff $A \cap B \ne \emptyset$
- Partition of Sets A partition of a set $X$ is a disjoint collection
  $\mathfrak{X}$ of non-empty and distinct subsets of $X$ such that each member of $X$ is a member of some (and hence exactly one) member of $\mathfrak{X}$ .
  For example: $\{ \{a,b\} \, \{c \} \, \{d, e\} \}$ is a partition of $\{a,b,c,d,e\}$ .
- Absolute Complement of a set $A$ is usually represented by $\Bar{A} = U-A = \{ x | x \notin A \}$ where $U$ is universal set.
- Relative Complement of a set $A \, \text{relative to another set} \, X$ is given by $X-A=X\cap \Bar{A}=\{ x \in X | x \notin A\}$ .
Theorems on Sets
1. $A \cup (B \cup C) = (A \cup B) \cup C$
2. $A \cap (B \cap C) = (A \cap B) \cap C$
3. $A \cup B= B \cup A$
4. $A \cap B= B \cap A$
5. $A \cup (B \cap C)= (A \cup B) \cap (A \cup C)$
6. $A \cap (B \cup C)= (A \cap B) \cup (A \cap C)$
7. $A \cup \emptyset= A$
8. $A \cap \emptyset= \emptyset$
9. $A \cup U=U$
10. $A \cap U=A$
11. $A \cup \Bar{A}=U$
12. $A \cap \Bar{A}=\emptyset$
13. If $\forall A \ , A \cup B=A$ $\Rightarrow B=\emptyset$
14. If $\forall A \ , A \cap B=A \Rightarrow B=U$
15. Self-dual Property: If $A \cup B =U$ and $A \cap B=\emptyset \ \Rightarrow B=\Bar{A}$
16. Self Dual: $\Bar{\Bar{A}}=A$
17. $\overline{\emptyset}=U$
18. $\Bar{U}= \emptyset$
19. Idempotent Law: $A \cup A=A$
20. Idempotent Law: $A \cap A =A$
21. Absorption Law: $A \cup (A \cap B) =A$
22. Absorption Law: $A \cap (A \cup B) =A$
23. de Morgen Law: $\overline{A \cup B} =\Bar{A} \cap \Bar{B}$
24. de Morgen Law: $\overline{A \cap B} =\Bar{A} \cup \Bar{B}$
Another Theorem

The following statements about set A and set B are equivalent to one another
1. $A \subseteq B$
2. $A \cap B=A$
3. $A \cup B =B$
Functions

Function is a relation such that no two distinct members have the same first co-ordinate in its graph. $f$ is a function iff
1. The members of $f$ are ordered pairs.
2. If ordered pairs $(x, y)$ and $(x, z)$ are members of $f$ , then $y=z$
Other words used as synonyms for the word ‘function’ are ‘transformation’, ‘map’, ‘mapping’, ‘correspondence’ and ‘operator’.
Notations for functions

A function is usually defined as ordered-pairs, see above, and $\text{ordered pair } (x,y) \in \text{function } f$ so that $xfy$ is (was) a way to represent where $x$ is an argument of $f$ and $y$ is image (value) of $f$ .
Other popular notations for $(x,y)\in f$ are: $y : xf$ , $y=f(x)$ , $y=fx$ , $y=x^f$ .
Intuitive law of extension for Functions

Two sets $f$ and $g$ are equal iff they have the same members (here, Domain and Range) $\Rightarrow f=g \Leftrightarrow D_f=D_g \ \text{and } \ f(x)=g(x)$
Into Function

A function $f$ is into $Y$ iff the range of $f$ is a subset of $Y$ . i.e., $R_f \subset Y$
Onto Function

A function $f$ is onto $Y$ iff the range of $f$ is $Y$ . i.e., $R_f=Y$
Generally a mapping is represented by $f : X \rightarrow Y$ .
One-to-One function

A function is called one-to-one if it maps distinct elements onto distinct elements.
A function $f$ is one-to-one iff $x_1 \ne x_2 \Leftrightarrow f(x_1) \ne f(x_2)$ and $x_1 = x_2 \Leftrightarrow f(x_1)=f(x_2)$
Restriction of Function

If $f : X \rightarrow Y$ and if $A \subseteq X$ , then $f \cap (A \times Y)$ is a function on $A \ \text{into } \ Y$ , called the restriction of $f$ to $A$ and $f \cap (A \times Y)$ is usually abbrevated by $f|A$ .
Extension of function

The function $f$ is an extension of a function $g$ iff $g \subseteq f$ .