<< Chapter < Page Chapter >> Page >

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. A B ¯ = A ¯ B ¯ size 12{ {overline {A union B}} = {overline {A}} intersection {overline {B}} } {} )

A - (B ∩ C) = (A - B) ∪ (A - C) (cf. A B ¯ = A ¯ B ¯ size 12{ {overline {A intersection B}} = {overline {A}} union {overline {B}} } {} )

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

12. B = A ¯ size 12{B= {overline {A}} } {} if and only if A ∪ B = U and A ∩ B = ∅

13. A ¯ ¯ = A size 12{ {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 →.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Discrete structures. OpenStax CNX. Jan 23, 2008 Download for free at http://cnx.org/content/col10513/1.1
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Discrete structures' conversation and receive update notifications?

Ask