SET

Before we get into the details of Theory of Computations. The set is an essential topic which is required to be reviewed. So, let's have a quick review of this topic.

What is a Set?

- Set is a group of elements, having a common characteristic or property.
- Example: A = {1,2,3,4,5}
- Another way to specify a set is to give the properties that characterize elements of the sets.
- Example: A = {x | x is a positive integer less than or equal to 5}

Set Terminology

1. Belongs To (∈)

- x ∈ A means that x is an element of A.
- Using this notation we can specify the set {0,1,2,3,4} call it Z by writing
                   Z = {x | x ∈ N | x <= 5}
   Where N = set of natural numbers.

2. Subset

- Let A and B be two sets. Then A is a subset of B if every element of A is an element of B.
- It is represented by A⊆ B.
- If A is a subset of B and B is a subset of A, then A = B. Also if a is a subset of B but is not equal to B then it is represented as A⊂ B.

3. Universal Set

- The set U of all the elements we might ever consider in the discourse is called the universal set.

4. Complement

- Let A be a set, then the complement of A is the set consisting of all elements of the universal set that are not in A.
                 A' = {x | x∈ U \land \!\, x ∉ A}
- It is denoted by A'.
- Example:
               If U is a set of natural numbers and A = {1,2,3}, then
                 A' = {x | x∈ U \land \!\, x > 3}

Set Operations

Different operations can be performed on sets;

1. Union:

- If A and B are two sets, then the union of A and B is the set that contains all the elements that are in A and B including the ones in both A and B.
- Union is denoted by A∪B.
- Example:
   If A = {1,2} and B = {3, 4, 5} then A∪B = {1, 2, 3, 4, 5}.

2. Difference

- If A and B are two sets, then the difference of A from B is the set that contains all the elements that are in A but not in B.
- The difference is denoted by A-B.
- Example:
  If A= {1, 2, 3} and B = {3, 4, 5} then A-B = {1,2} also B-A = {4,5}.
- It can be seen that A-B ≠ B-A.

3. Intersection

- If A and B are two sets, then the intersection of A and B is the set that contains all the elements that are in both A and B.
- The intersection is denoted by A∩B.
- Example:
  If A= {1, 2, 3} and B = {3, 4, 5} then A∩B = {3}.

Disjoint Sets

- A and B sets are said to be disjoint if they contain no common element, i.e. A∩B = ∅, where ∅ is an empty set.
- Example:
  Let A= {1, 2, 3} and B = {4,5,6,7} then A and B are disjoint sets as  A∩B = ∅.

Some Standard Identities of Sets

Let A, B, C represent arbitrary sets and ∅ be the empty set and U be the Universal set, then

1. Commutative Laws:

- A∪B = B∪A
- A∩B = B∩A

2. Associative Laws:

- A∪(B∪C) = (A∪B)∪C
- A∩(B∩C) = (A∩B)∩C

3. Distributive Laws:

- A∩(B∪C) = (A∩B)∪(A∩C)
- A∪(B∩C) = (A∪B)∩(A∪C)

4. Idempotent Laws:

- A∪A = A
- A∩A = A

5. Absorption Laws:

- A∪(A∩B) = A
- A∩(A∪B) =  A

6. De Morgan Laws:

- (A∪B)' = A' ∩ B'
- (A ∩ B)' = A' U B'

7. Laws involving Complements:

- (A')' = A
- A ∩ A' = ∅
- A ∪ A' = U

8. Laws involving empty set:

- A ∪ ∅ = Λ
- A ∩ ∅ = ∅

9. Laws involving Universal set:

- A ∪ U = U
- A ∩ U = A