Mängder?

  • $\{2,3,5,6\}$ är mängden som innehåller talen $2$, $3$, $5$ och $5$, dvs. $2\in \{2,3,5,6\}$, $3\in \{2,3,5,6\}$ osv. men $4\notin \{2,3,5,6\}$.
  • Mängderna $\{2,3,5,6\}$ och $\{6,5,3,2,2,2\}$ är desamma eftersom ordningen och upprepningar inte har någon betydelse för frågan om ett element hör till mängden eller inte och det är det enda som räknas.
  • Istället för att räkna upp elementen i en mängd kan man definiera en mängd som de element i en mängd $A$ som har en viss egenskap $P$, dvs. $B=\{ x\in A: P(x)\}$ där $P(x)$ för varje $x\in A$ antingen är sant eller falskt, tex. $\{x\in \mathbb{R} : x\leq 4\}$. Men ...

Russells paradox

Vad kan vi säga om $\{ x\,:\, x\notin x\}$?

  • Ge ett namn åt detta: $A=\{ x\,:\, x\notin x\}$.
  • Antag att $A\in A$:
    • Då uppfyller $A$ villkoret $x\notin x$ dvs. $A\notin A$, en motsägelse.
  • Antag att $A\notin A$:
    • Då uppfyller $A$ villkoret $x\notin x$ så enligt definitionen av $A$ gäller $A\in A$, igen en motsägelse.
  • Slutsats?
  • Det går inte att definiera mängder hur some helst utan att få större problem än man hade!

Definitioner

  • $\emptyset =\{\}$ är den tomma mängden som inte har några element alls.
  • $A\subset B$ om varje element i $A$ också är ett element i $B$ och då säger vi att $A$ är en delmängd av $B$.
  • $A\cup B= \{x: x\in A \text{ eller } x\in B \}$ är unionen av $A$ och $B$.
  • $A\cap B= \{x: x\in A \text{ och } x\in B\}$ är snittet av $A$ och $B$.
  • $A\setminus B = \{ x: x\in A \text{ och } x\notin B\}$ är differensen mellan $A$ och $B$.
  • $A^c = \Omega\setminus A$ är komplementet till $A$ ifall $A\subset \Omega$ och det är klart vad $\Omega$ är.






Standardbeteckningar

  • $\mathbb{N}_0=\{0,1,2,3,\ldots \}$ är mängden av alla icke-negativa naturliga tal.
  • $\mathbb{N}_+=\{1,2,3,\ldots\}$ är mängden av alla positiva naturliga tal.
  • $\mathbb{N}=\mathbb{N}_0$ eller $\mathbb{N}_+$
  • $\mathbb{Z}=\{\ldots -3,-3,-1,0,1,2,3,4,\ldots\}$ är mängden av alla heltal.
  • $\mathbb{Q}=\{\frac mn : m,n\in \mathbb{Z}, \, n\neq 0\}$ är mängden av alla rationella tal.
  • $\mathbb{R}$ är mängden av alla reella tal.
  • $\mathbb{C}$ är mängden av alla irrationella tal.

Satslogik

Om $a$ och $b$ är satser eller påståenden som kan vara sanna eller falska, men inte någonting mitt emellan, så gäller

  • satsen $a\&\& b$ är sann då $a$ och $b$ är sanna.
  • satsen $a || b$ är sann då $a$ eller $b$ är sann (och också då både $a$ och $b$ är sanna).
  • satsen $! a$ är sann då $a$ inte är sann, dvs. falsk.
  • satsen $a\to b$ är sann då $(! a) || b$ är sann, dvs. då antingen $b$ är sann eller $a$ är falsk. Men ...
  • $a\leftrightarrow b$ är sann då $(a\to b)\&\& (b\to a)$ är sann.
I matematisk logik används vanligen $\wedge$ istället för $\&\&$, $\vee$ istället för $||$ och $\neg$ istället för $!$.

Implikationen $\to$

Observera att implikationen $a\to b$ som logisk sats inte alltid motsvarar vad man i dagligt tal menar med en implikation, dvs. ''av $a$ följer $b$'' eftersom $a\to b$ är sann då $a$ är falsk och den inte säger något om orsakssamband.

I vardagligt tal är "följer" (eller "implicerar", etc) ett verb till skillnad från "och" och "eller" men här är $\&\&$, $||$ och $\to$ alla sk. konnektiv

Predikatlogik

Förutom de operationer ($!$, $\&\&$, $||$, $\to$ och $\leftrightarrow$) som finns i satslogiken använder predikatlogiken all- och existenskvantorerna $\forall$ och $\exists$ som uttrycker "för alla" och "det existerar".

Förutom predikat kan man också använda funktioner vars värde hör till det område som behandlas ("domain of discourse"). En funktion med noll argument är då en konstant. Funktioner och konstanter kan också uttryckas med hjälp av predikat, men det blir lätt onödigt klumpigt.

Induktionsprincipen

Om $P(n)$ är ett påstående (som för alla $n\geq n_0$ antingen är sant eller falskt) så kan vi visa att $P(n)$ sant för alla $n\geq n_0$ genom att visa att

  • $P(n_0)$ är sant,
  • $P(k+1)$ är sant ifall $P(k)$ är sant (dvs. $P(k)\to P(k+1)$) då $k\geq n_0$.

Exempel

Visa med hjälp av induktion att

\[ \sum_{i=1}^n i = 1+2 + 3+\ldots n = \frac{n(n+1)}2,\quad n\geq 1. \]

    Påståendet $P(n)$ är alltså $\sum_{i=1}^n i= \frac{n(n+1)}2$ och $n_0=1$.

    • Påståendet $P(1)$ samma som att $1= \frac {1(1+1)}2$ vilket är sant.
    • Antag nu att $P(k)$ är sant och $k\geq 1$. Eftersom $P(k)$ är sant gäller $\sum_{i=1}^k i = \frac {k(k+1)}2$ vilket innebär att \begin{multline*}{\small \sum_{i=1}^{k+1} i = \sum_{i=1}^k i+ (k+1) = \frac {k(k+1)}2+ (k+1) }\\ {\small =(k+1)\biggl(\frac{k}2+1\biggr)= \frac{(k+1)((k+1)+1)}{2},} \end{multline*} dvs. $P(k+1)$ är sant.
    Påståendet följer nu av induktionsprincipen!