Home » Posts tagged 'Subset'

Tag Archives: Subset

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$ .

Dedekind’s Theory of Real Numbers

Friday, May 13th, 2011 07:38 / Leave a Comment

: Image via Wikipedia

Intro

Let $\mathbf{Q}$ be the set of rational numbers. It is well known that $\mathbf{Q}$ is an ordered field and also the set $\mathbf{Q}$ is equipped with a relation called “less than” which is an order relation. Between two rational numbers there exists infinite number of elements of $\mathbf{Q}$ . Thus the system of rational numbers seems to be dense and so apparently complete. But it is quite easy to show that there exist some numbers (?) (e.g., ${\sqrt{2}, \sqrt{3} \ldots}$ etc.) which are not rational. For example, let we have to prove that $\sqrt{2}$ is not a rational number or in other words, there exist no rational number whose square is 2. To do that if possible, purpose that $\sqrt{2}$ is a rational number. Then according to the definition of rational numbers $\sqrt{2}=\dfrac{p}{q}$ , where p & q are relatively prime integers. Hence, ${\left(\sqrt{2}\right)}^2=p^2/q^2$ or $p^2=2q^2$ . This implies that p is even. Let $p=2m$ , then $(2m)^2=2q^2$ or $q^2=2m^2$ . Thus $q$ is also even if 2 is rational. But since both are even, they are not relatively prime, which is a contradiction. Hence $\sqrt{2}$ is not a rational number and the proof is complete. Similarly we can prove that why other irrational numbers are not rational. From this proof, it is clear that the set $\mathbf{Q}$ is not complete and dense and that there are some gaps between the rational numbers in form of irrational numbers. This remark shows the necessity of forming a more comprehensive system of numbers other that the system of rational number. The elements of this extended set will be called a real number. The following three approaches have been made for defining a real number.

Dedekind’s Theory
Cantor’s Theory
Method of Decimal Representation

The method known as Dedekind’s Theory will be discussed in this not, which is due to R. Dedekind (1831-1916). To discuss this theory we need the following definitions:

Rational number A number which can be represented as $\dfrac{p}{q}$ where p is an integer and q is a non-zero integer i.e., $p \in \mathbf{Z}$ and $q \in \mathbf{Z} \setminus \{0\}$ and p and q are
relatively prime as their greatest common divisor is 1, i.e., $\left(p,q\right) =1$ .

Ordered Field: Here, $\mathbf{Q}$ is, an algebraic structure on which the operations of addition, subtraction, multiplication & division by a non-zero number can be carried out.

Least or Smallest Element: Let $A \subseteq Q$ and $a \in Q$ . Then $a$ is said to be a least element of $A$ if (i) $a \in A$ and (ii) $a \le x$ for every $x \in A$ .

Greatest or Largest Element: Let $A \subseteq Q$ and $b \in Q$ . Then $b$ is said to be a least element of $A$ if (i) $b \in A$ and (ii) $x \le b$ for every $x \in A$ .

Dedekind’s Section (Cut) of the Set of All the Rational Numbers

Since the set of rational numbers is an ordered field, we may consider the rational numbers to be arranged in order on straight line from left to right. Now if we cut this line by some point $P$ , then the set of rational numbers is divided into two classes $L$ and $U$ . The rational numbers on the left, i.e. the rational numbers less than the number corresponding to the point of cut $P$ are all in $L$ and the rational numbers on the right, i.e. The rational number greater than the point are all in $U$ . If the point $P$ is not a rational number then every rational number either belongs to $L$ or $U$ . But if $P$ is a rational number, then it may be considered as an element of $U$ .

Def.

Real Numbers:

Let $L \subset \mathbf{Q}$ satisfying the following conditions:

$L$ is non-empty proper subset of $\mathbf{Q}$ .

$a, b \in \mathbf{Q}$ , $a < b$ and $b \in L$ then this implies that $a \in L$ .

$L$ doesn’t have a greatest element.

Let $U=\mathbf{Q}-L$ . Then the ordered pair $< L,U >$ is called a section or a cut of the set of rational numbers. This section of the set of rational numbers is called a real number.

Notation: The set of real numbers $\alpha, \beta, \gamma, \ldots$ is denote by $\mathbf{R}$ .

Let $\alpha = \langle L,U \rangle$ then $L$ and $U$ are called Lower and Upper Class of $\alpha$ respectively. These classes will be denoted by $L(\alpha)$ and $U(\alpha)$ respectively.

(more…)

MY DIGITAL NOTEBOOK

Tag Archives: Subset

Quick Notes on Elementary Set Theory and Functions

Cantor’s Concept of a set

The intuitive principle of extension for sets

The intuitive principle of abstraction

Operations with/for sets

Theorems on Sets

Another Theorem

Functions

Notations for functions

Intuitive law of extension for Functions

Into Function

Onto Function

One-to-One function

Restriction of Function

Extension of function

Dedekind’s Theory of Real Numbers

Intro

Dedekind’s Section (Cut) of the Set of All the Rational Numbers

Real Numbers:

Follow “MY DIGITAL NOTEBOOK”

MY DIGITAL NOTEBOOK

Tag Archives: Subset

Quick Notes on Elementary Set Theory and Functions

Cantor’s Concept of a set

The intuitive principle of extension for sets

The intuitive principle of abstraction

Operations with/for sets

Theorems on Sets

Another Theorem

Functions

Notations for functions

Intuitive law of extension for Functions

Into Function

Onto Function

One-to-One function

Restriction of Function

Extension of function

Better You Share!

Like this:

Dedekind’s Theory of Real Numbers

Intro

Dedekind’s Section (Cut) of the Set of All the Rational Numbers

Real Numbers:

Better You Share!

Like this:

Follow “MY DIGITAL NOTEBOOK”