Computer Representation of Sets

Computer Representation of Sets

    Method for storing elements using an arbitrary ordering of the elements of the universal
    set.Specify an arbitrary ordering of the elements of U, for instance a1, a2, . . . , an. Represent a 
    subset A of U with the bit string of length n, where the ith bit in this string is 1 if ai belongs to A
    and is 0 if ai does not belong to A.

Example1: Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.

i)What bit strings represent the subset of all odd integers in U?

  The bit string that represents the set of odd integers in U, {1, 3, 5, 7, 9}, has a one bit in the

  first, third, fifth, seventh, and ninth positions. It is 10 1010 1010.

ii)What bit strings represent the subset of all even integers in U?

   The bit string that  represent the subset of  even integers in U,{2, 4, 6, 8, 10}.

   It is 01 0101 0101.

iii)What bit strings represent the subset of integers not exceeding 5 in U? 

    The set of all integers in U that do not exceed 5, {1, 2, 3, 4, 5}, is represented by the

    string 11 1110 0000.

To find the bit string for the complement of a set from the bit string for that set, change each 1 to 0 and each 0 to 1.

Example 2:The bit string for the set {1, 3, 5, 7, 9} (with universal set {1, 2, 3, 4,

5, 6, 7, 8, 9, 10}) is 10 1010 1010.

What is the bit string for the complement of this set?

The bit string for the complement of this set is obtained by replacing 0s with 1s.

This yields the string 01 0101 0101,which corresponds to the set {2, 4, 6, 8, 10}.

To obtain the bit string for the union and intersection of two sets we perform bitwise Boolean

operations on the bit strings representing the two sets.

Example 3:The bit strings for the sets {1, 2, 3, 4, 5} and {1, 3, 5, 7, 9} are 11 1110 0000 and 10 1010 1010.

The bit string for the union of these sets is 11 1110 0000 ∨ 10 1010 1010 = 11 1110 1010,

which corresponds to the set {1, 2, 3, 4, 5, 7, 9}.

If either of the bits in the ith position in the two strings is 1 (or both are 1),the bit in the ith position of the bit string of the union is 1. When both bits are 0, is 0. Hence, the bit string for union is the bitwise OR of the bit strings for the two sets.

The bit string for the intersection of these sets is

11 1110 0000 ∧ 10 1010 1010 = 10 1010 0000, which corresponds to the set {1, 3, 5}.

When the bits in the corresponding position in the two strings are both 1,the bit in the ith position of the bit string of the intersection is 1. When either of the two bits is 0 (or both are 0) ,is 0. Hence, the bit string for the intersection is the bitwise AND of the bit strings for the two sets.

Properties of Relations

• Reflexive
• Irreflexive
• Symmetric
• Antisymmetric
• Transitive

[1] Reflexive

     A reflexive relation is a binary relation on a set for which every element is related to itself.

Example

A={1,2,3}

R={(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)}

R is reflexive because they contains all pairs of the form (a,a), namely (1,1),(2,2)&(3,3)

       

[2] Irreflexive

     A irreflexive relation is a binary relation on a set for which is false for every element.

" a Î A,(a,a) Ï R

Example

These 4 irreflexive relations are :

1. Empty
2. {(1,2)}
3. {(2,1)}
4. {(1,2),(2,1)}

[3] Symmetric

     A symmetric relation is a binary relation on a set  A if  (a,b) Î R = (b,a) Î R  

R={(1,1),(1,2),(2,1),(2,2)}

R is symmetric because both (1,2) and (2,1) are in the relation.

[4] Antisymmetric

     A binary relation a on a set A is antisymmetric whenever (a, b) Î R and (b, a) Î R , then a=b

Example

R={(2, 1), (3, 1), (4, 1), (3, 2), (4, 2), (4, 3)}

R is antisymmetric because there is no pair of element a and b.

a ≠ b (a,b) & (b,a).

[5] Transitive

A binary relation a on a set A is transitive (a,b) Î R and (b,c) Î R = (a,c) Î R     

Example

A={1,2,3,4}

answer:

R={(1,1),(1,2),(2,2),(2,3),(1,3),(3,3)}

     

       

Generalised Union and Intersection


Generalised Union

• The union of a collection of set is a 
• set that contains those elements that are members of at 
• least one set in the collection
  
  
•      A ∪ (B ∪ C) = (A ∪ B) ∪ C

• 
  A = {0,2,4,6}, B = {0,1,3,5,7}, C = {0,1,2,3}
• 
  
  A ∪ B ∪ C = {0,1,2,3,4,5,6,7}

• 
  

Generalised Intersection

• The intersection of a collection of sets is a set that 
• contains those elements that are members all the sets in 
• the collection
• 
  

•     A ∩ (B ∩ C) = (A ∩ B) ∩ C

• A = {0,2,4,6}, B = {0,1,3,5,7}, C = {0,1,2,3}
• 
  
  A ∩ B ∩ C = {0}

Cartesian Product

 The direct product of two sets

Specifically, the Cartesian product of two sets X and Y denoted  X × Y, is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y

Example

A={abu,dol}

B={cow,goat,camel}

What is the cartesian product of A x B ?

  

       A x B ={(abu,cow),(abu,goat),(abu,camel),(dol,cow),(dol,goat),(dol,camel)}

Take note !!

      A x B  B x A

POWER SET

The power set of a set A is the set of all its subsets (including, of course, itself and the empty set). It is denoted by P(A).

Using set comprehension notation, P(A) can be defined as

P(A) = { Q | Q⊆A }

Example 4

Write down the power sets of A if:

(a) A = {1, 2, 3}

(b) A = {1, 2}

(c) A = {1}

(d) A = ø

Solution

(a) P(A) = { {1, 2, 3}, {2, 3}, {1, 3}, {1, 2}, {1}, {2}, {3}, ø }

(b) P(A) = { {1, 2}, {1}, {2}, ø }

(c) P(A) = { {1}, ø }

(d) P(A) = { ø }

SET OPERATION

·         Union

Definition (Union): The union of sets A and B, denoted by AB , is the set defined as :-
             AB = { x | xAxB }

Example 1: If A = {1, 2, 3} and B = {4, 5} ,  then AB = {1, 2, 3, 4, 5} .

Example 2: If A = {1, 2, 3} and B = {1, 2, 4, 5} ,  then AB = {1, 2, 3, 4, 5} .

Note that elements are not repeated in a set.

·         Intersection

Definition (Intersection): The intersection of sets A and B, denoted by AB , is the set defined as :-
             AB = { x | xAxB }

Example 3: If A = {1, 2, 3} and B = {1, 2, 4, 5} ,  then AB = {1, 2} .

Example 4: If A = {1, 2, 3} and B = {4, 5} ,  then AB = .

·         Disjoin Set  (Non-Overlapping Sets )

Two or more sets which have no elements in common. For example, the sets A = {a,b,c} and B = {d,e,f} are disjoint.

·         Set Difference

Definition (Difference): The difference of sets A from B , denoted by A- B , is the set defined as

             A- B = { x | xAxB }

Example 5: If A = {1, 2, 3} and B = {1, 2, 4, 5} ,  then A- B = {3} .
Example 6: If A = {1, 2, 3} and B = {4, 5} ,  then A- B = {1, 2, 3} .

Note that in general A- BB–A

·         Set Complimentary

The set of elements that are not in a set A is called the complement of A. It is written A′ (or sometimes A^C, or ).

Clearly, this is the set of elements that answer 'No' to the question Are you in A?.

For example, if U = N and A = {odd numbers}, then A′ = {even numbers}.

·         Characteristic of Set

Venn Diagram and Subsets

Venn Diagram

Venn diagram contains universal set U, which is all the object under consideration on a rectangle. It contains other geometrical figure to represent sets. Usually, Venn Diagram is used to show relationship between sets.

 

 

Subsets

It is used to encounter situation where the first element are same with the second element.  Subset also represents in terminology terms.

Sets of number & Set equality

Sets of number.

N  =  the set of natural numbers {0, 1,2,3,….}

Z  =  the set of integers {…,-2,-1,0,1,2,….}

Z+ = the set of positive integers {1,2,3,….}

Q  =  the set of rational numbers {p/q | p ∈ Z,q ∈ Z, and q = 0}

R  =  the set of real numbers {

R+ =  the set of positive real numbers

C  =  the set of complex numbers.

 

Set equality.

Definition =

Two sets are equal if and only if they have the same elements. Therefore, if A and B are sets,

then A and B are equal if and only if ∀x(x ∈ A ↔ x ∈ B).We write A = B if A and B are

equal sets.

Example =

The sets {4, 5, 6} and {6, 4, 1} are equal, because they have the same elements. The

order in which the elements of a set are listed does not matter. {1, 3, 3, 3, 5, 5, 5, 5} is the same as the

 set {1, 3, 5} because they have the same elements. Eventhough element of a set is listed more than

once ,it does not matter.

Set Membership
  definition - symbol ∈ means “is an element of”...
                     - statement x∈A means that x is an element of the set A.
                     - symbol ∉ means " not an element of "......
                     - the statement  x∉A means that x is not element of set A.
   example:-    
                  A = {♢,♡,♣,♠}, then ♡∈A but △∉A (where the symbol ∉ means “not an element of”).

Empty set (null set)

   definition  - is set with no element...

                        - symbol {} or ø..

   example:-

            A = {2, 6, 8} and B = {3, 5, 7}

            Let C represent the intersection of the sets A and B.
            C = {}, a null set, because there is no element common between the two sets.  

Way of listing the elements of Set

Way of listing the elements of Sets

i)ROSTER METHOD-list all the members or elements of a set

Example 1:The set V of unisza can be written as V = {u,n,i,s,z,a}

Example 2:The set O of even positive integers less than 10 can be expressed by O = {2,4,6,8}

Example 3:The set may consists of elements which have different types with each other, just like: {a, 1, Aiman,Malaysia}

Example 4: Let say there is a set with elements of numbers from 1 to 99. It would be irritating to list out all the elements in the set. Therefore, for a set with fixed pattern of elements, we can use the symbol “…” in the denotion of the set. For example, {1, 2, 3, . . . , 99}.

ii)SET BUILDER-state the properties of the elements. For example, the set O of all even positive integers less than 10 can be written as

O = {x | x is an even positive integer less than 10}

The bold part represents the set builder for the set. As stated in the set builder, x is an even positive integer less than 10. The elements which does not fulfill the properties are not considered as an element of set O. Therefore, the possible elements of set O is { 2, 4, 6, 8 }

The set Q⁺ of all positive rational numbers can be written as

Q⁺ = {x ∈ R | x =p/q , for every integers p and q}

Specify properties of Sets

Sets are inherently unordered:

• No matter what objects a, b, and c denote, fa, b, c g = fa, c, b g = fb, a, c g = fb, c, ag = fc, a, b g = fc, b, ag.

All elements are distinct (unequal); multiple listings make no difference.

• fa, a, b g = fa, b, b g = fa, b g = fa, a, a, a, b, b, b g.
• This set contains at most 2 elements.

Powerpoint slide