Scribd
Upload
45 views5 pages

Chapter 3 Sets

These are my lecture notes on the discrete math chapter of sets. I'm still a little inexperienced in typing symboles but I tryed my best. Hope this helps.

Uploaded by

aly.darghouth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
45 views5 pages

Chapter 3 Sets

These are my lecture notes on the discrete math chapter of sets. I'm still a little inexperienced in typing symboles but I tryed my best. Hope this helps.

Uploaded by

aly.darghouth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 5

Discrete math: (01-02-2024)

Chapter 3: Sets
Def: A set is an un-ordered collection of items, called “elements”.

If x is an element of a set S, we write x ∈ S . (“x in S”.)

Examples: {“2”, “hello”, “&”} is a set.

 V = {“a”,”e”,”i”,”o”,”u”}. S = {1,2,3} ; A = {1,2,3,…,100} ; B = {2,4,6,8,…}


 N , R , Z ,Q are all sets.
 Set builder notation: { x ∈ D∨P (x) }
o Example: B = { x ∈ N ¿| x is even }
o [a,b] =

Def: Two sets A and B are equal iff:

∀x (x ∈ A ↔ x ∈ B).

Example: A = {1,2,3} ; B = {3,2,1} ; C = {1,1,1,2,3,3}. Notation: A = B.

A = B = C.

Def: A set A is a subset of a set B iff: Notation: A(att je≤trouve aprés ) B

∀x x ∈ A → x ∈ B.

Venn diagram:

Def: A is a proper subset of B iff:

1) A ⊂ B
A
A⊂B and
B
2) ∃ x s .t . x ∈ B^ x ∉ A

i.e. (that is) when A ⊂ B and A ≠ B .

Ex: Let A and B be two sets.

Write using formal logic symbols the negation of A ⊂ B.

 ¬ ( A ⊂ B ) ≡¬ ( ∀ x x ∈ A → x ∈ B ) .

≡∃ x ¬ ( x ∈ A → x ∈ B ) .

≡∃ x s . t . x ∈ A ^ x ∉ B .
Remark: A ⊂ B: ∀ x (x ∈ A → x ∈ B)

B⊂ A : ∀ x ∈ B→ x ∈ A

( A ⊂ B) ^ ( B⊂ A ) ≡ ∀ x x ∈ A ↔ x ∈ B≡ A=B .

This is can be used as a method to prove the equality between 2 sets.

Ex: Let S= { m∈ Z|∃k ∈ Z s .t .m=2 k }

and T ={ n ∈ Z|∃l∈ Z s . t . n=2 l−2 }

Show that S=T.

1) S ⊂ T ? :

Let x ∈ S .

So ∃ k ∈ Z s .t . x=2 k .

Let l=k +1.l ∈ Z∧x=2 k =2 (l−1 )=2 l−2

So ∃l ∈ Z s . t . x=2 l−2.

So x ∈ T .

Therefore S ⊂ T .

2) T ⊂ S ? :

Let x ∈ T

So ∃l ∈ Z s . t . x=2 l−2

Let k = l – 1

k ∈ Z∧x=2 ( l−1 )=2 k

So ∃ k ∈ Z s .t . x=2 k

So x ∈ S .

Therefore T ⊂ S .

Def: If a set S has exactly n elements, we say that S is finite, of cardinality n.

Notation:|S|=n.

Example: S = {2 , “hello”, “&” } is finite. |S|=3

{ x ∈ Z ∨−10 ≤ x ≤10 } is finite, of cardinal 21.

Def: A set that is not finite is said to be infinite.


Examples: N isinfinite .

{ x ∈ R∨−10 ≤ x ≤ 10} is infinite.

Let n ∈ N .

{all words of length N} n ∈ N .

S = { N , Z } is finite. |S| = 2.

True or false:

−1 ∈ S ;−1⊂ S ; N ⊂ S ; N ∈ S ; N ∈ S ; {−1 } ∈ S ; {−1 } ⊂ S ; S ⊂ S ; S ∈ S

Def: The empty set is the set with no elements. Notation:∅

Remark: Prove that: ∀ set S , ∅ ⊆ S .

Example: We want to show that ∀ x ( x ∈ ∅ → x ∈ S ) .

F ?

Def: Let S be a set . The Power set of Q, denoted P(s), is the set of subsets of S.

Example: S ={1,2,3}. P(s) = {∅ , { 1 } , { 2 } , { 3 } , {1 , 2 } , {2 , 3 } , {1 , 3 } , S }

Rk: ∀ set S , S ⊆ S .

Example: Give the power set of T ={ { a ,b } , ∅ } .

- D ( T )={ ∅ , { { a , b } , ∅ } , { ∅ , {a ,b } } , { { a , b } } , { ∅ } }.

True/False:

1. N ⊆ S F
2. N ∈ S T
3. N ∈ P( s) F
4. N ⊆ P ( s ) F
5. { N } ⊆ P ( s ) T
6. F
7. { 0 , 1 ,2 , … , 10 } ∈ P(s) F
8. { 0 , 1 ,2 , … , 10 } ⊆P (s ) F
2. Operations on sets:
Def: The Union of A and B, denoted A ∪ B ,is the set of all elements that are∈ A∨¿ B .

A ∪ B= { x ∈Ω| x ∈ A v x ∈ B }.

Venn diagram:

A B

Def: The intersection of A and B, denoted A ∩ B, is the set of all elements that are in A and in B.

A ∩ B= { x ∈ Ω| x ∈ A ^ x ∈ B }.

Example: A={ a , b } ; B= {b , c , d } : A ∩={b }

Venn Diagram:

A B

Def: The complement of A, denoted A , is the set for all elements that are not in

A={ x ∈ Ω| x ∉ A } .

Venn Diagram:

A A

Def: The difference


Ex: Let A and B be two sets. Prove or disprove A ∪ B= A ∪ B .

The statement is False.

Indeed, consider A =[0,2] with domain beinge R .

B=[0,1]

- A ∪ B=[ 0 , 2 ] ⇒ A ∪ B=¿

You might also like