Set Theory Basics

---

Before starting Statistics you need a basic understanding of Probability, and before that you need a basic understanding of Set Theory.

And when I say basic I mean basic, I am not an expert on anything past rudimentary knowledge.

---

Possible bastardization of notation,

$$E = EF \cup EF^{c} \quad \text{union of two mutually exclusive sets}$$ $$E \cup F = E \cup E^c F \quad \text{union of two mutually exclusive sets}$$

De Morgan's laws

$$ \left( \bigcup E_i \right) ^{c} = \bigcap E_i^{c}$$

Border only, think about simple 2 circle Venn or olympic rings if you want

$$\bigcup E_i^{c} = \left( \bigcap E_i \right) ^{c}$$

Everything except the super middle

Mutually Exclusive | NME | Dependent | Independent

ME $\rightarrow$ always Dependent -- flipping a coin, if you know it's heads, def not tails

Dependent can be ME -- flipping a coin OR NME -- roll 2 die, get 4, sum 6, events nme and dep

NME can be Indep -- get ace or spades, nme but indep OR Dep -- see above

Indep $\rightarrow$ always NME -- Indep means intersection not zero $P(EF) = P(E)P(F) > 0$

I think this is interesting. Usually for independent stuff I think of two circles that don't intersect. Two islands if you will. But Two islands means ME $ \Rightarrow$ Dependent. For, you're either on Hawaii or you're on Ireland then knowing you're not on Hawaii means you're on Ireland. For independence, the intersection must be greater than zero.

Multisets

• A \underline{Set} is a collection of DISTINCT objects/elements/members $\{a,b\}$
• The cardinality of a set is the number of objects in a set. The set $\{a,b\}$ has a cardinality of $2$
• Unlike a Set, a \underline{Multiset} allows for multiple instances for each of its elements. $[a,a,a,b,b]$ and you say that the element $a$ has multiplicity $3$ and $b$ has multiplicity $2$.
• For example $120 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5$ and so the multiset of prime factors is $[2,2,2,3,5]$
• Let's say you want to create a Multiset of size $k$ with members/elements coming from a Set of DISTINCT elements of size $n$. Note that $k$ can be greater or equal to or less than $n$. The number of Multisets you can create is

$$\left( \binom{n}{k} \right) = \binom{n+k-1}{n-1} = \binom{n+k-1}{k} = \frac{(n+k-1)!}{k!(n-1)!}$$

Multiset example 1

Let's say we have a set $\{a,b,c,d\}$ which has cardinality $4=n$ and you want to create a multiset of size $10=k$, then you can calculate the total number of possible multisets by using stars and bars. There are $k=10 \, \, \star$'s broken up into $n-1=3$ distinct boxes.

$$ \, \, \, \, \star \star \star | \star \star \star \star \star | | \star \star \quad \quad \text{a,a,a,b,b,b,b,b,d,d}$$ $$ | \star \star \star | \star \star \star \star | \star \star \star \quad \text{b,b,b,c,c,c,c,d,d,d}$$

Note there are $13$ spots to put either a star or bar,

$$\_ \, \, \_ \, \, \_ \, \, \_ \, \, \_ \, \, \_ \, \, \_ \, \, \_ \, \, \_ \, \, \_ \, \, \_ \, \, \_ \, \, \_ \quad \text{fill $\_$'s with $\star$'s or $|$'s}$$

And so the total number of multisets is

$$\left( \binom{4}{10} \right) = \binom{n+k-1}{n-1} = \binom{4+10-1}{4-1} = \binom{13}{3} = \binom{13}{10} = 286 $$

Multiset example 2

Let's say we have a set $\{a,b,c,d\}$ which has cardinality $4=n$ and you want to create a multiset of size $3=k$, then you can calculate the total number of possible multisets by using stars and bars. There are $k=3 \, \, \star$'s broken up into $n-1=3$ distinct boxes. There are $6$ spaces to put $3$ bars and $3$ stars.

$$\star | \star | \star | \quad \text{a,b,c}$$ $$ \star \star \star |\,|\,| \quad \text{a,a,a}$$ $$ |\,| \star \star \star | \quad \text{c,c,c}$$

And so the total number of multisets is

$$\left( \binom{4}{3} \right) = \binom{n+k-1}{n-1} = \binom{4+3-1}{4-1} = \binom{6}{3} = 20 $$