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?
Induksjon på mengder
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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:
(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|$.
Betrakt et vilkårlig element $e$. Det er fire muligheter:
- $e\not\in A,B$
- $e\in A\land e\not\in B$
- $e\not\in A\land e\in B$
- $e\in A,B$
(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|$
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|$