Nettkurs

Boka

Definere menger steg for steg

• Å definere mengder induktivt betyr å bygge dem opp nedenfra eller innenfra. Det er en måte å definere mengder på steg for steg.
• Når vi har definert mengden induktivt, har vi god kontroll på hvilke elementer som er i mengden. På denne måten blir det enklere å behandle og bevise påstander om mengden.

Lukket mengde og tillukningen

• At en mengde er lukket (closed) under en gitt operasjon, betyr at når vi utfører denne operasjonen på ett eller flere elementer i mengden, er vi garantert at resultatet er et element i den samme mengden.
• Hvis $M$ er en mengde, kalles den minste mengden som inneholder $M$ og som er lukket under en eller flere operasjoner, tillukningen (closure) av $M$ under disse operasjonene.

Tillukninger av binære relasjoner

• Hvis $R$ er en relasjon, kalles den minste relasjonen som inneholder $R$ og som har en gitt egenskap, tillukningen (closure) av $R$ med hensyn til denne egenskapen.
• Hvis egenskapen det er snakk om er refleksivitet, symmetri eller transitivitet, så kalles tillukningen henholdsvis den refleksive, symmetriske eller transitive tillukningen av $R$.

Induktivt definerte mengder

• En induktivt definert mengde (inductively defined set) er den minste mengden som inneholder en gitt mengde - kalt en basismengde (base set/initial set) - og som er lukket under gitte operasjoner.
• En mengde defineres induktivt i følgende tre steg:
  • Basissteget (base case/basis): å spesifisere en basismengde.
  • Induksjonssteget (induction step): å spesifisere operasjonene.
  • Tillukningen (closure) - å ta den minste mengden som inneholder basismengden og som er lukket under operasjonene.

Tallmengder

• Mengden av naturlige tall kan defineres induktivt som den minste mengden $\mathbb{N}$ som er slik at $0 \in \mathbb{N}$ og hvis $x\in\mathbb{N}$, så $x+1\in\mathbb{N}$.
• Mengden av partall er den minste mengden som inneholder $0$ og som er lukket under operasjonene som henholdsvis legger til og trekker fra $2$.

Utsagnslogisk formler (nytt definisjon)

• Mengden av utsagnslogiske formler (propositional formulas) er den minste mengden $X$ slik at følgende holder:

  • Enhver utsagnsvariabel er med i $X$. Disse utgjør basismengden og kalles atomære formler (atomic formulas).
  • Hvis $F$ er med i $X$, er $\lnot F$ med i $X$.
  • Hvis $F$ og $G$ er med i $X$, så er$(F\land G)$, $(F\lor G)$ og $(F \rightarrow G)$ er med i $X$.

  

Lister