| Line 5: | Line 5: | ||
'''Random Variables and Signals''' | '''Random Variables and Signals''' | ||
</font size> | </font size> | ||
| − | |||
| − | |||
<font size= 3> Subtopic 1: Set Theory Review</font size> | <font size= 3> Subtopic 1: Set Theory Review</font size> | ||
| Line 163: | Line 161: | ||
| − | '''Definition''' <math>\qquad</math> the collection <math>\{A_i, i</math>∈<math>I</math> is a | + | '''Definition''' <math>\qquad</math> the collection <math>\{A_i, i</math>∈<math>I</math> is a '''partition''' of ''S'', the sample space, if it is disjoint and if |
<center><math>\bigcup_{i \in I} A_i = \mathcal{S}</math></center> | <center><math>\bigcup_{i \in I} A_i = \mathcal{S}</math></center> | ||
Revision as of 21:16, 23 September 2013
Random Variables and Signals
Subtopic 1: Set Theory Review
Contents
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 atleast 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.
Set Operations
Definition $ \qquad $ The intersection of sets $ A $ and is defined as
Definition $ \qquad $ The union of sets $ A $ and is defined as
Definition $ \qquad $ The complement of a set $ A $, denoted $ A^c $, Ā, or A' is defined as
Definition $ \qquad $ The set difference $ A-B $ or A\B is defined as
Note that
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
- Union is commutative ⇔ A ∪ B = B ∪ A
- Intersection is commutative ⇔ A ∩ B = B ∩ A
- Union is associative ⇔ A ∪ (B ∪ C) = (A ∪ B) ∪ C
- Intersection is associative ⇔ A ∩ (B ∩ C) = (A ∩ B) ∩ C
- Intersection is distributive over union ⇔ A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
- Union is distributive over intersection ⇔ A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)
- (A')' = A
- DeMorgan's Law: (A ∩ B)' = A' ∪ B'
- DeMorgan's Law: (A ∪ B)' = A' ∩ B'
- S' = Ø, where S is the sample space
- A ∩ S = A
- A ∩ Ø = Ø
- A ∪ S = S
- A ∪ Ø = A
- A ∪ A' = S
- A ∩ A' = Ø
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.
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.
