0.4 Discrete structures set theory  (Page 5/6)

As you can see in these examples, in general, A ×B ≠B ×A unless A = ∅, B = ∅ or A = B.

Note that A × ∅= ∅ × A = ∅ because there is no element in ∅ to form ordered pairs with elements of A.

The concept of Cartesian product can be extended to that of more than two sets. First we are going to define the concept of ordered n-tuple .

Definition (ordered n-tuple): An ordered n-tuple is a set of n objects with an order associated with them (rigorous definition to be filled in). If n objects are represented by x1, x2, ..., xn, then we write the ordered n-tuple as<x1, x2, ..., xn>.

Definition (Cartesian product): Let A1, ..., An be n sets. Then the set of all ordered n-tuples<x1, ..., xn>, where xi∈Ai for all i, 1 ≤ i ≤ n , is called the Cartesian product of A1, ..., An, and is denoted by A1 ×... ×An .

Example 3:

Let A = {1, 2}, B = {a, b} and C = {5, 6}. Then A ×B ×C = {<1, a, 5>,<1, a, 6>,<1, b, 5>,<1, b, 6>,<2, a, 5>,<2, a, 6>,<2, b, 5>,<2, b, 6>}.

Definition (equality of n-tuples): Two ordered n-tuples<x1, ..., xn>and<y1, ..., yn>are equal if and only if xi = yi for all i, 1 ≤i ≤n.

For example the ordered 3-tuple<1, 2, 3>is not equal to the ordered n-tuple<2, 3, 1>.

Properties of set operation

Basic properties of set operations are discussed here. 1 - 6 directly correspond to identities and implications of propositional logic, and 7 - 11 also follow immediately from them as illustrated below.

1. A ∪ ∅ = A

A ∩ U = A

------- Identity Laws

2. A ∪ U = U

A ∩ ∅ = ∅

------- Domination Laws

3. A ∪ A = A

A ∩ A = A

------- Idempotent Laws

4. A ∪ B = B ∪ A

A ∩ B = B ∩A

------- Commutative Laws

5. (A ∪ B) ∪ C = A ∪ (B ∪ C)

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

------- Associative Laws

6. A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

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

------- Distributive Laws

7. If A⊆B and C⊆D, then A ∪ C ⊆ B ∪ D, and A ∩ C ⊆ B ∩ D

8. If A⊆B, then A ∪ B = B and A ∩ B = A

9. A ∪ (B - A) = A ∪ B

10. A ∩ (B - A) = ∅

11. A - (B ∪ C) = (A – B) ∩ (A - C) (cf. $\overline{A\cup B}=\overline{A}\cap \overline{B}$ )

A - (B ∩ C) = (A - B) ∪ (A - C) (cf. $\overline{A\cap B}=\overline{A}\cup \overline{B}$ )

------- De Morgan's Laws

12. $B=\overline{A}$ if and only if A ∪ B = U and A ∩ B = ∅

13. $\overline{\overline{A}}=A$

Additional properties:

14. A ⊆A ∪B

15. A∩B ⊆A

The properties 1~6, and 11 can be proven using equivalences of propositional logic. The others can also be proven similarly by going to logic, though they can be proven also using some of these properties (after those properties are proven, needless to say). Let us prove some of these properties.

Proof for 4: A ∪ B = B ∪ A

We are going to prove this by showing that every element that is in A∪B is also in B∪A and vice versa.

Consider an arbitrary element x. Then by the definition of set union x ∈ A ∪ B ⇔ x ∈A ∨ x ∈ B

⇔ x ∈A ∨ x ∈ B by the commutativity of ∨

⇔ x ∈ B ∪ A by the definition of set union.

Hence by Universal Generalization, every element is in A ∪B is also in B ∪A.

Hence A ∪ B = B ∪ A.

Note here the correspondence of the commutativity of ∪ and that of ∨. This correspondence holds not just for the commutativity but also for others.

Furthermore a similar correspondence exists between ∩ and ⋀, and between ⊆ and →.