matematikk.net

Hei. Har et par oppgaver som jeg lurer på i samme slengen.

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?

Som du sier, så er noen ting så åpenbare at det nesten er vanskelig å bevise de . Likevel, en mulighet er å dele opp i tiilfeller:

Betrakt et vilkårlig element $e$. Det er fire muligheter:

1. $e\not\in A,B$
2. $e\in A\land e\not\in B$
3. $e\not\in A\land e\in B$
4. $e\in A,B$

hveretter du bare kan sjekke at $e$ bidrar med like mye til begge sider i hvert tilfelle.

(b) har du jo løst! (uavhengig om du vet hva du driver med eller ikke )
\[|A_{k + 1}| - \left|\bigcup_{j = 1}^{k}A_{j} \cap A_{k + 1}\right|\]
må jo være mindre enn eller lik $|A_{k+1}|$, så
\[ \left|\bigcup_{j = 1}^{k}A_{j}\right| + |A_{k + 1}| - \left|\bigcup_{j = 1}^{k}A_{j} \cap A_{k + 1}\right| \leq \left|\bigcup_{j = 1}^{k}A_{j}\right| + |A_{k + 1}|\]
som ifølge hypotesen er mindre enn eller lik $|A_{k+1}| + \sum_{i=1}^{k}|A_i|=\sum_{i=1}^{k+1}|A_i|$.

a) Husk at $|C\cup D|=|C|+|D|$ dersom C og D er disjunkte. Det følger at også $|C\cup D\cup E|=|C|+|D|+|E|$ dersom C,D,E er parvis disjunkte.

Vi har at
$A\cup B=(A\setminus B)\cup (B\setminus A)\cup (A\cap B)$.

Siden $A\setminus B$, $B\setminus A$ og $A\cap B$ er parvis disjunkte vil

$|A\cup B|=|A\setminus B|+ |B\setminus A| + |A\cap B|=(|A\setminus B|+ |A\cap B|)+(|B\setminus A| + |A\cap B|)-|A\cap B|=|A|+|B|-|A\cap B|$