0.4 Discrete structures set theory  (Page 4/6)

However, ∃x [x ∈ ∅ ⋀ x ∉ A] implies ∃x [x ∈ ∅]by formula 4 of the relationships between the connectives and quantifiers from predicate logic and "simplification" from the implications of propositional logic. But x ∉ ∅ for any x, which contradicts ∃x [x ∈ ∅]. Hence, ¬∀x [x ∈ ∅ → x ∈ A]can not be true. Hence, ∅ ⊆ A.

More Proofs

Theorem 3: A = B iff A⊆ B and B⊆ A

Proof: By the definition of A = B,

A = B ⇔∀x [x ∈ A ↔ x ∈ B]

⇔∀x [(x ∈ A → x ∈ B) ⋀ (x ∈ B → x ∈ A) ]

⇔∀x [x ∈ A → x ∈ B] ⋀ ∀x [ (x ∈ B → x ∈ A) ]

Since A⊆ B ⇔∀x [ (x ∈A → x ∈B) ], this means that A⊆ B and B⊆ A.

Hence, A = B iff A⊆ B and B⊆ A.

Theorem 4: A⊆B ⋀ B⊆C → A⊆ CProof: A⊆B ⋀ B⊆C

⇔∀x [x ∈ A → x ∈ B] ⋀ ∀x [ (x ∈ B → x ∈ C) ]

⇔∀x [(x ∈ A → x ∈ B) ⋀ (x ∈ B → x ∈ C) ]

Thus for an arbitrary x in the universe, Z, and x ∈ B → x ∈ C holds.Hence, by hypothetical syllogism x ∈ A → x ∈ C,Hence, A⊆ C.

Set operations

Set operations

Sets can be combined in a number of different ways to produce another set. Here four basic operations are introduced and their properties are discussed.

Definition (Union): The union of sets A and B, denoted by A ∪B, is the set defined as

A ∪B = {x | x ∈A ∨ x ∈B}

Example 1: If A = {1, 2, 3} and B = {4, 5}, then A ∪B = {1, 2, 3, 4, 5}.

Example 2: If A = {1, 2, 3} and B = {1, 2, 4, 5}, then A ∪B = {1, 2, 3, 4, 5}.

Note that elements are not repeated in a set.

Definition (Intersection): The intersection of sets A and B, denoted by A ∩B, is the set defined as

A ∩B = {x | x ∈A ⋀ x ∈B}

Example 3: If A = {1, 2, 3} and B = {1, 2, 4, 5}, then A ∩B = {1, 2}.

Example 4: If A = {1, 2, 3} and B = {4, 5}, then A ∩B = ∅.

Definition (Difference): The difference of sets A from B, denoted by A - B, is the set defined as

A - B = {x | x ∈A ⋀ x ∉ B}

Example 5: If A = {1, 2, 3} and B = {1, 2, 4, 5}, then A - B = {3}.

Example 6: If A = {1, 2, 3} and B = {4, 5}, then A - B = {1, 2, 3}.

Note that in general A - B≠ B - A

Definition (Complement): For a set A, the difference U - A, where U is the universe, is called the complement of A and it is denoted by $\overline{A}$ .

Thus $\overline{A}$ is the set of everything that is not in A.

The fourth set operation is the Cartesian product. We first define an ordered pair and Cartesian product of two sets using it. Then the Cartesian product of multiple sets is defined using the concept of n-tuple.

Definition (ordered pair):

An ordered pair is a pair of objects with an order associated with them. If objects are represented by x and y, then we write the ordered pair as<x, y>.

Two ordered pairs<a, b>and<c, d>are equal if and only if a = c and b = d. For example the ordered pair<1, 2>is not equal to the ordered pair<2, 1>.

Definition (Cartesian product):

The set of all ordered pairs<a, b>, where a is an element of A and b is an element of B, is called the Cartesian product of A and B and is denoted by A×B.

Example 1: Let A = {1, 2, 3} and B = {a, b}. Then A × B = {<1, a>,<1, b>,<2, a>,<2, b>,<3, a>,<3, b>}.

Example 2: For the same A and B as in Example 1,

B ×A = {<a, 1>,<a, 2>,<a, 3>,<b, 1>,<b, 2>,<b, 3>}.