{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "$$\\author{\\text{Giorgio Renzi}}$$\n", "$$\\text{Ingegneria Informatica - 0926, Alma Mater Studiorum - Università di Bologna}$$\n", "$$\\text{\\href{mailto:giorgio.renzi@studio.unibo.it}{giorgio.renzi@studio.unibo.it}}$$\n", "\n", "# Relazioni\n", "\n", "## Prodotto cartesiano\n", "\n", "**Definizione** Siano $A$ e $B$ due insiemi. L'insieme delle coppie ordinate $(a,b)$, con $a\\in A$ e $b\\in B$, si chiama **prodotto cartesiano** tra $A$ e $B$ e si indica con\n", "\n", "$$A\\times B:={(a,b)\\mid a\\in A, b\\in B)}$$\n", "\n", "## Relazioni\n", "\n", "**Definizione** Una proprietà $\\mathcal{A}$ definita in $S\\times T$ è detta **relazione** tra $S$ e $T$; diremo che $s\\in S$ è in relazione con $t\\in T$ se si ha $\\mathcal{A}(s,t)$ vera.\n", "\n", "Data una relazione $\\mathcal{R}$:\n", "\n", "$$\\mathcal{D}om(R)=\\{a\\in A\\mid \\text{s è in relazione tramite}\\ \\mathcal{R}\\ \\text{con almeno un elemento di}\\ B\\}\\subseteq S$$\n", "\n", "$$\\mathcal{C}od(R)=\\{b\\in B\\mid \\text{b è in relazione tramite}\\ \\mathcal{R}\\ \\text{con almeno un elemento di}\\ A\\}\\subseteq T$$\n", "\n", "$$\\mathcal{G}raf(R)=\\{(a,b)\\in A\\times B\\mid \\mathcal{R}(a,b)\\ \\text{è vera}\\}\\subseteq A\\times B$$\n", "\n", "### Relazioni binarie\n", "\n", "**Definizione** Una relazione $\\mathcal{R}$ tra $S$ e $S$ (cioè una proprietà che mette in relazione tra loro elementi di $S$), è detta **relazione binaria** in $S$. Sia $\\mathcal{R}$ una relazione binaria; diremo:\n", "- $\\mathcal{R}(x,y)$ è **riflessiva** se $\\forall x\\in S$ $\\mathcal{R}(x,x)$ è vera\n", "- $\\mathcal{R}(x,y)$ è **simmetrica** se $\\forall x,y\\in S$ $\\mathcal{R}(x,y)$ vera $\\implies \\mathcal{R}(y,x)$ vera\n", "- $\\mathcal{R}(x,y)$ è **antisimmetrica** se $\\forall x,y\\in S$ $\\mathcal{R}(x,y)$ vera e $\\mathcal{R}(y,x)$ vera $\\implies x=y$\n", "- $\\mathcal{R}(x,y)$ è **transitiva** se $\\forall x,y,z\\in S$ $\\mathcal{R}(x,y)$ vera e $\\mathcal{R}(y,z)$ vera $\\implies \\mathcal{R}(x,z)$\n", "\n", "### Relazioni di equivalenza\n", "\n", "La relazione binaria $\\mathcal{R}$ su $A$ si dice **relazione di equivalenza** se è riflessiva, simmetrica e transitiva. La relazione di equivalenza si indica con il simbolo $\\sim$.\n", "\n", "### Relazioni d'ordine\n", "\n", "**Definizione** La relazione binaria $\\mathcal{R}$ su $A$ si dice **relazione d'ordine** se è riflessiva, antisimmetrica e transitiva. Alcuni esempi di relazione d'ordine sono $<$, $\\leq$, $>$, $\\geq$.\n", "\n", "**Definizione** Una relazione d'ordine si dice **totale** se\n", "\n", "$$\\forall x,y\\in A\\ \\text{si ha}\\ \\mathcal{R}(x,y)\\ \\text{oppure}\\ \\mathcal{R}(y,x)$$\n", "\n", "cioè, comunque si fissino due elementi di A, essi sono **confrontabili**. Altrimenti la relazione d'ordine è detta **parziale**.\n", "\n", "Indichiamo con $(\\mathbb{R}, \\leq)$ l'insieme ${R}$ ordinato con la relazione $\\leq$.\n", "**Legge di tricotomia**: $\\forall x,y\\in \\mathbb{R}$ vale solo una delle seguenti possibilità:\n", "- $x < y$\n", "- $x > y$\n", "- $x = y$\n", "\n", "# Massimo e minimo\n", "\n", "**Definizione** Sia $A \\subset \\mathbb{R}$ non vuoto. $m$ si dice **massimo** (risp. **minimo**) di $A$ se:\n", "\n", "- $m \\in A$\n", "\n", "- $m \\geq x\\ \\text{(risp. } m\\leq x \\text{)}\\ \\forall x\\in A$\n", "\n", "Se $m$ esiste, usiamo la notazione\n", "\n", "$$m=\\max A\\ \\text{(risp. } m=\\min A \\text{)}$$\n", "\n", "Il minimo e il massimo **se esistono sono unici**.\n", "\n", "# Maggiorante e minorante\n", "\n", "**Definizione** Sia $A \\subset \\mathbb{R}$ non vuoto. $m\\in \\mathbb{R}$ si dice **maggiorante** (risp. **minorante**) di $A$ se:\n", "\n", "$$m\\geq x\\ \\text{(risp. } m\\leq x \\text{)}\\ \\forall x\\in A$$\n", "\n", "Se $A$ possiede un maggiorante (risp. minorante), allora **ne possiede infiniti**.\n", "Il massimo di A è un maggiorante. Il minimo di A è un maggiorante.\n", "\n", "# Insieme superiormente (inferiormente) limitato\n", "\n", "**Definizione** Un insieme $A\\subset \\mathbb{R}$ non vuoto che ammette maggiorante (risp. minorante) si dice **superiormente limitato** (risp. **inferiormente limitato**). Un insieme superiormente e inferiormente limitato si dice insieme limitato.\n", "\n", "# Estremo superiore ed estremo inferiore\n", "\n", "**Definizione** Sia $A\\subset \\mathbb{R}$ un insieme superiormente limitato. Il minimo dei maggioranti si dice **estremo superiore** di $A$ e si indica con $\\sup A$:\n", "\n", "$$\\sup A=\\min\\{y\\in \\mathbb{R}\\mid y\\geq x, \\forall x\\in A\\}$$\n", "\n", "**Definizione** Sia $A\\subset \\mathbb{R}$ un insieme inferiormente limitato. Il massimo dei minoranti si dice **estremo inferiore** di $A$ e si indica con $\\inf A$:\n", "\n", "$$\\inf A=\\max\\{y\\in \\mathbb{R}\\mid y\\leq x, \\forall x\\in A\\}$$\n", "\n", "**Teorema** $(\\mathbb{R}, \\leq)$ è un **insieme totalmente ordinato e completo**, cioè $\\forall A\\in \\mathbb{R}$ inferiormente limitato, l'insieme $M$ dei suoi minoranti ha massimo.\n", "\n", "**Proposizione** Ogni sottoinsieme di $\\mathbb{R}$ superiormente limitato (risp. inferiormente limitato) ammette estremo superiore (risp. estremo inferiore).\n", "\n", "**Definizione** Sia $A\\subseteq \\mathbb{R}$:\n", "- se $A$ non possiede maggioranti, diremo che $A$ è un insieme **non superiormente limitato**\n", "\n", "$$\\sup A=+\\infty$$\n", "\n", "- se $A$ non possiede minoranti, diremo che $A$ è un insieme **non inferiormente limitato**\n", "\n", "$$\\inf A=-\\infty$$\n", "\n", "- se $A$ è limitato sia inferiormente che superiormente, diremo che $A$ è limitato.\n", "\n", "**Proposizione** Ogni sottoinsieme di ${R}$ ammette estremo superiore e inferiore (finiti o non finiti)\n", "\n", "# Insiemi $\\mathbb{N}, \\mathbb{Z}, \\mathbb{Q}, \\mathbb{R}$\n", "\n", "## Intervalli\n", "\n", "**Definizione** Siano $a,b\\in\\mathbb{R}$\n", "- Intervallo limitato e chiuso\n", "\n", "$[a,b]=\\{x\\in\\mathbb{R}\\mid a\\leq x\\leq b\\}$\n", "\n", "- Intervallo superiormente non limitato e chiuso\n", "\n", "$[a,+\\infty[=\\{x\\in\\mathbb{R}\\mid x\\geq a\\}$\n", "\n", "- Intervallo inferiormente non limitato e chiuso\n", "\n", "$]-\\infty,b]=\\{x\\in\\mathbb{R}\\mid x\\leq b\\}$\n", "\n", "- Intervallo limitato e aperto\n", "\n", "$]a,b[=\\{x\\in\\mathbb{R}\\mid a< x a\\}$\n", "\n", "- Intervallo non inferiormente limitato e aperto\n", "\n", "$]-\\infty,b[=\\{x\\in\\mathbb{R}\\mid x< b\\}$\n", "\n", "- Intervallo chiuso a sinistra e aperto a destra\n", "\n", "$[a,b[=\\{x\\in\\mathbb{R}\\mid a\\leq x< b\\}$\n", "\n", "- Intervallo chiuso a destra e aperto a sinistra\n", "\n", "$]a,b]=\\{x\\in\\mathbb{R}\\mid a< x\\leq b\\}$\n", "\n", "## Proprietà degli insiemi\n", "\n", "**Proprietà di densità** $\\mathbb{Q}$ è denso in $\\mathbb{R}$, ovvero\n", "\n", "