Difference between revisions of "ECE600 F13 set theory review mhossain" - Rhea

Revision as of 15:54, 30 September 2013

Definitions and Notation

Definition $ \qquad $ A set is a collection of objects called elements, numbers or points.

Notation $ \qquad $ $ \omega $∈$ A $ means $ \omega $ is an element of the set $ A $. $ \omega $∉$ A $ means $ \omega $ is not in the set $ A $.

There are two common ways to specify a set:

• Explicitly list all elements, e.g. $ \{1,2,3,4,5,6\} $
• Specify a rule for membership, e.g. $ A=\{\omega $∈$ Z:1 $ ≤ $ \omega $ ≤ $ 6\} $, i.e. the set of all integers between 1 and 6 inclusive. I prefer this notation for large or infinite sets.

Note that there is always a set that contains every possible element of interest. This set, along with some structure imposed upon the set, is called a space, denoted

Definition $ \qquad $ Let $ A $ and $ B $ be two sets. Then,

The proof that the second statement is equivalent is trivial and follows from the definition of the term subset, which is presented shortly.

If $ A $ and $ B $ are not equal, we write

Definition $ \qquad $ If $ \omega $∈$ A $ ⇒ $ \omega $∈$ B $, then $ A $ is said to be a subset of $ B $. if If $ B $ contains at least one element that is not in $ A $, then $ A $ is a proper subset of $ B $. We will simply call $ A $ a subset of $ B $ in either case, and write $ A $⊂$ B $.

Definition $ \qquad $ the set with not elements is called the empty set, or null set and is denoted Ø or {}.

Venn Diagrams

A Venn diagram is a graphical representation of sets. It can be useful to gain insight into a problem, but cannot be used as a proof.

Fig 1: An example of a Venn diagram

Set Operations

Definition $ \qquad $ The intersection of sets $ A $ and is defined as

Fig 2: A∩B is shown in green

Definition $ \qquad $ The union of sets $ A $ and is defined as

Fig 3: A∪B is shown in green

Definition $ \qquad $ The complement of a set $ A $, denoted $ A^c $, Ā, or A' is defined as

Fig 4: $ A^c $ is shown in green

Definition $ \qquad $ The set difference $ A-B $ or A\B is defined as

Note that

Fig 5: $ A-B $ is shown in green

Definition $ \qquad $ Sets $ A $ and $ B $ are disjoint if $ A $ and $ B $ have not elements in common ie

In figure 1, A and C are disjoint. B and C are also disjoint.

Algebra of Sets

1. Union is commutative ⇔ A ∪ B = B ∪ A (proof)
2. Intersection is commutative ⇔ A ∩ B = B ∩ A (proof)
3. Union is associative ⇔ A ∪ (B ∪ C) = (A ∪ B) ∪ C (proof)
4. Intersection is associative ⇔ A ∩ (B ∩ C) = (A ∩ B) ∩ C (the proof is similar to the one for the associative property of the union)
5. Intersection is distributive over union ⇔ A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C) (proof)
6. Union is distributive over intersection ⇔ A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C) (proof)
7. (A')' = A (proof)
8. De Morgan's Law: (A ∩ B)' = A' ∪ B' (proof)
9. De Morgan's Law: (A ∪ B)' = A' ∩ B' (proof)
10. S' = Ø, where S is the sample space (proof)
11. A ∩ S = A (proof)
12. A ∩ Ø = Ø (proof)
13. A ∪ S = S (proof)
14. A ∪ Ø = A (proof)
15. A ∪ A' = S (proof)
16. A ∩ A' = Ø (proof)

A Note on Sets of Different Sizes

We can categorize the sets we encounter three ways:

• A set $ A $ is finite if it contains an finite number of elements, i.e. the number of elements in the set is some natural number $ n $. Then we can list the elements in $ A $; e.g. $ A = \{x_1,...,x_n\} $.

• A set is countable if its elements can be put into a one-to-one correspondence (a bijection) with the integers. In this course when, we say countable, we mean countably infinite. We may write $ A=\{x_1,x_2,...\} $. The set of rationals is a countable set.

• A set is uncountable if it is not finite or countable. A set that is uncountable cannot be written as $ \{x_1,x_2,...\} $. Note that the set of reals as well as any interval in R is uncountable.

Note that a finite or countable space (a collection of sets) may contain elements that are uncountable. For example the set {Ø,[0,1]} is a finite set with 2 elements but the interval [0,1] is uncountable.

If you are interested to learn more about countable and uncountable sets, you may find this Math Squad tutorial useful.

We will often consider indexed collections of sets such as

where $ I $ is called the index set.

The index set can be

• finite: $ I=\{1,...,n\} $ for some finite natural number n so that the collection of sets is $ I=\{A_1,...,A_n\} $

• countable: $ I $ is the set of natural numbers i.e. $ I=\{1,2,3,...\} $, so the collection is $ \{A)_1,A_2,A_3,...\} $

• uncountable: so the collection is $ \{A_{\alpha}, \alpha $∈$ I\} $cfor an uncountable set $ I $. If $ I=R $, the set of reals, then the set in the collection can be written as $ A_{\alpha} $ for some real number $ \alpha $

Definition $ \qquad $ The union of an indexed family of sets is defined as

Note that if $ I $ is finite, we can write the union as

If $ I $ is countable, we can write the union as

If $ I $ is uncountable, we can write the union as

Definition $ \qquad $ The intersection of an indexed family of sets is defined as

Note that if $ I $ is finite, we can write the intersection as

If $ I $ is countable, we can write the intersection as

If $ I $ is uncountable, we can write the intersection as

Definition $ \qquad $ $ \{A_i, i $∈$ I\} $ is disjoint if $ A_i $∩$ A_j $ = Ø ∀ i,j∈I, i≠j.

Definition $ \qquad $ the collection $ \{A_i, i $∈$ I\} $ is a partition of S, the sample space, if it is disjoint and if

References

• M. Comer. ECE 600. Class Lecture. Random Variables and Signals. Faculty of Electrical Engineering, Purdue University. Fall 2013.

Back to all ECE 600 notes