Power set

Power set
The power set of some set S, denoted P(S), is the set of all subsets of S (including S itself and the empty set)

Example 1: Let A = { 1,2 3}

Power set of set A = P(A) = [{1},{2},{3},{1,2},{1,3},{2,3},{},A]

Example 2: P({0,1})={{},{0},{1},{0,1}}

Classes of sets: Collection of subset of a set with some properties
Example: Suppose A = { 1,2 3} , let X be the class of subsets of A which contain exactly two elements of A. Then

class X = [{1,2},{1,3},{2,3}]

Cardinality

The cardinality of a set S, denoted |S|, is simply the number of elements a set has. So
|{a,b,c,d}| = 4, and so on. The cardinality of a set need not be finite: some sets have infinite cardinality.

The cardinality of the power set
Theorem: If |A| = n then |P(A)| = 2n (Every set with n elements has 2n subsets)














The Cartesian product

The Cartesian Product of two sets is the set of all tuples made from elements of two sets. We write the Cartesian Product of two sets A and B as A × B. It is defined as:


It may be clearer to understand from examples;

Example: If A = {1, 2, 3} and B = {x, y} then
A . B = {(1, x), (1, y), (2, x), (2, y), (3, x), (3, y)}
B . A = {(x, 1), (x, 2), (x, 3), (y, 1), (y, 2), (y, 3)}

It is clear that, the cardinality of the Cartesian product of two sets A and B is:


A Cartesian Product of two sets A and B can be produced by making tuples of each element of A with each element of B; this can be visualized as a grid (which Cartesian implies) or table: if, e.g., A = { 0, 1 } and B = { 2, 3 }, the grid is


× A
0 1

B 2 (0,2) (1,2)
3 (0,3) (1,3)



Answers



Partitions of set:
Let S be any nonempty set. A partition ( ? ) of S is a subdivision of S into nonoverlapping, nonempty subsets. A partition of S is a collection {Ai} of non-empty subsets of S such that:
1) Ai ??, where i=1,2,3,……
2) The sets of {Ai } are mutually disjoint
or Ai ? Aj = ? where i ? j.
3) UAi = S, where A1 ? A2 ? .................. ? Ai = S
The partition of a set into five cells, A1, A2,A3,A4,A5, can be represented by Venn diagram

Example 1: let A = {1,2,3,n}
A1 = {1}, A2 = {3,n}, A3 = {2}
? = {A1, A2, A3} is a partition on A because it satisfy the three above conditions.

Example 2 : Consider the following collections of subsets of S = {1,2,3,4,5,6,7,8,9} (i) [{1,3,5},{2,6},{4,8,9}]
(ii) [{1,3,5},{2,4,6,8},{5,7,9}]
(iii) [{1,3,5},{2,4,6,8},{7,9}]
Then
(i) is not a partition of S since 7 in S does not belong to any of the subsets.
(ii) is not a partition of S since {1,3,5} and {5,7,9} are not disjoint.
(iii) is a partition of S.


FINITE SETS, COUNTING PRINCPLE:
A set is said to be finite if it contains exactly m distinct elements where m denotes some nonnegative integer. Otherwise, a set is said to be infinite. For example, the empty set ? and the set of letters of English alphabet are finite sets, whereas the set of even positive integers, {2,4,6,…..}, is infinite.
If a set A is finite, we let n(A) or #(A) denote the number of elements of A.
Example: If A ={1,2,a,w} then
n(A) = #(A) = |A| = 4
Lemma: If A and B are finite sets and disjoint Then A ? ? is finite set and:
n(A ? B) = n(A) + n(B)
Theorem (Inclusion–Exclusion Principle): Suppose A and B are finite sets. Then A ? B and A ? B are finite and

|A ? B| = |A| + |B| - | A ? B|

That is, we find the number of elements in A or B (or both) by first adding n(A) and n(B) (inclusion) and then subtracting n(A ? B) (exclusion) since its elements were counted twice.
We can apply this result to obtain a similar formula for three sets:

Corollary:
If A,B,C are finite sets then
|A ? B ? C | = |A| + |B| + |C| - | A ? B| - |A ? C| - |B ? C| + |A ? B ? C|

Example (1) :
A= {1,2,3}
B= {3,4}
C= {5,6}

A ? B ? C = {1,2,3,4,5,6}
|A ? B ? C| = 6

|A| =3 , |B| = 2 , |C| = 2
? ? B = {3} , | ? ? B | = 1
? ? C ? ? ? , | ? ? C | = 0
B ? C = { } , | ? ? C | = 0
? ? B ? C = { } , | ? ? B ? C | = 0

|A ? B ? C | = |A| + |B| + |C| - | A ? B| - |A ? C| - |B ? C| + |A ? B ? C|
|A ? B ? C | = 3 + 2 +2 -1 – 0 – 0 + 0 = 6

Example (2):
Suppose a list A contains the 30 students in a mathematics class, and a list B contains the 35 students in an English class, and suppose there are 20 names on both lists. Find the number of students:
(a) only on list A
(b) only on list B
(c) on list A ? B

Solution:
(a) List A has 30 names and 20 are on list B; hence 30 ? 20 = 10 names are only on list A.
(b) Similarly, 35 ? 20 = 15 are only on list B.
(c) We seek n(A ? B). By inclusion–exclusion,
n(A ? B) = n(A) + n(B) ? n(A ? B) = 30 + 35 ? 20 = 45.

Example (3):
Suppose that 100 of 120 computer science students at a college take at least one of languages: French, German, and Russian and:
65 study French (F). 45 study German (G). 42 study Russian (R).

20 study French & German F ? G. 25 study French & Russian F ? R. 15 study German & Russian G ? R.
Find the number of students who study:
1) All three languages ( F ? G ? R)
2) The number of students in each of the eight regions of the Venn diagram



Solution:
|F ? G ? R| = |F| + |G| + |R| - |F ? G| - |F ? R| - |G ? R| + |F ? G ? R| 100 = 65 + 45 + 42 - 20 - 25 - 15 + |F ? G ? R|
100 = 92 + |F ? G ? R|
?|F ? G ? R| = 8 students study the 3 languages
20 – 8 = 12 (F ? G) - R
25 – 8 = 17 (F ? R) - G
15 – 8 = 7 (G ? R) - F

65 – 12 – 8 – 17 = 28 students study French only
45 – 12 – 8 7 = 18 students study German only
42 – 17 – 8 7 = 10 students study Russian only
120 – 100 = 20 students do not study any language