a) La A og B være endelige mengder. Vis at $| A \cup B | = |A| + |B| - | A \cap B |$
Fant i læreboken at den heter "Principle of inclusion-exclusion" og det er jo ikke så vanskelig å overbevise seg selv om at det er sant, men å vise det synes jeg var vanskelig. Med mindre det er innafor å bruke kun ord er jeg helt blank og fant ingenting på google. Noen som har noen hint/tips til å gjøre det på en pen måte?
b)
La $A_{j}$, $j = 1,...,n$ $n \geq 1$ være endelige mengder. Benytt induksjon til å vise at: $\left|\bigcup_{j = 1}^{n}A_{j}\right| \leq \sum_{j = 1}^{n}|A_{j}|$
Dette prøvde jeg, ved å bruke identiten i oppgave a
Basisstep: $n = 1 \Rightarrow \left|\bigcup_{j = 1}^{1}A_{1}\right| = |A_{1}| \leq \sum_{j = 1}^{1}|A_{1}| = |A_{1}|$ Ok.
Hypotese: Antar at for $n = k$, $k \geq 1$ så holder $\left|\bigcup_{j = 1}^{k}A_{j}\right| \leq \sum_{j = 1}^{k}|A_{j}|$
Induksjonsstep: $n = k + 1 \Rightarrow \left|\bigcup_{j = 1}^{k + 1}A_{j}\right| = \left|\bigcup_{j = 1}^{k}A_{j} \cup A_{k + 1}\right| = \left|\bigcup_{j = 1}^{k}A_{j}\right| + |A_{k + 1}| - \left|\bigcup_{j = 1}^{k}A_{j} \cap A_{k + 1}\right| \leq \sum_{j = 1}^{k}|A_{j}| + |A_{k + 1}| = \sum_{j = 1}^{k+1}|A_{j}|$.
Jeg vet ikke helt hva jeg driver med, vet ikke hvordan jeg skal få brukt hypotesen. Noen som kan gi et hint?
. Likevel, en mulighet er å dele opp i tiilfeller:
)