Explain Set relations and operations in TOC

Subset

If A and B are sets, then A ⊂ B (A is a subset of B) if w ∈ A which implies that w ∈ B; that is every element of A is also an element of B.

Examples

• Let A = {ab, ba} and B = {ab, ba, aaa}. Then A ⊂ B, but B ⊄ A.

• Let A = {x, xx, xxx, . . .} and B = {∧, x, xx, xxx, . . .}. Then, A ⊂ B, but B ⊄ A.

• Let A = {ba, ab} and B = {aa, bb}. Then, A ⊄ B and B ⊄ A.

Definition

Let A and B be 2 sets. A = B if A ⊂ B and B ⊂ A.

Examples

• Let A = {ab, ba} and B = {ab, ba}. Then A ⊂ B and B ⊂ A, so A = B.

• Let A = {ab, ba} and B = {ab, ba, aaa}. Then A ⊂ B, but B ⊄ A, so A ⊄ B.

• Let A = {x, xx, xxx, . . .} and B = {xn| n ≥ 1}. Then A ⊂ B and B ⊂ A, so A = B.

Union

Given two sets of strings S and T, we can define S + T = {w : w ∈ S or w ∈ T} to be the union of S and T, that is S + T consists of all words either in S or in T (or in both).

Examples

Suppose S = {ac, bb} and T = {aa, bb, a}. Then S + T = {ac, bb, aa, a}.

Intersection

Given two sets S and T of strings, we can define S ∩ T = {w : w ∈ S and w ∈ T}, which is the intersection of S and T, that is S ∩ T consists of strings that are in both S and T.

Sets S and T are disjoint when S ∩ T = ∅.

Examples

• Let S = {ab, bb} and T = {aa, bb, a}. Then S ∩ T = {bb}.

• Let S = {ab, bb} and T = {ab, bb}. Then S ∩ T = {ab, bb}.

• Let S = {ab, bb} and T = {aa, ba, a}. Then S ∩ T = ∅

Difference

For any 2 sets S and T of strings, we can define S − T = {w : w ∈S, w ⊄ T}.

Examples

Let S = {a, b, bb, bbb} and T = {a, bb, bab}. Then S − T = {b, bbb}.

Let S = {ab, ba} and T = {ab, ba}. Then S − T = ∅.

Cartesian Product

The Cartesian product of two sets A and B is the set A × B = {(x, y) : x ∈ A, y ∈ B} of ordered pairs.

Examples

• If A = {ab, ba, bbb} and B = {bb, ba}, then

A × B = {(ab, bb), (ab, ba), (ba, bb), (ba, ba), (bbb, bb), (bbb, ba)}.

Note that (ab, ba) ∈ A × B.

And also, note that

B × A = {(bb, ab), (bb, ba), (bb, bbb), (ba, ab), (ba, ba), (ba, bbb)}.

and (bb, ba) ∈ B × A,

but (bb, ba) ⊄ A × B, so B × A ⊄ A × B.

We can define the Cartesian product for more than 2 sets.