Cheat sheet di Matematica

LOGICA DEL PRIMO ORDINE (variabili)

Definizione 2.15. Sia F(x) una proposizione dipendente da x:

∃x• F(x) : esiste un modo di riempire i puntini che rende la frase vera (quantificatore esistenziale);

∀x• F(x) : in qualunque modo riempiamo i puntini la frase è vera (quantificatore universale).

Theorem 2.23. Siano P e Q due proposizioni. Allora:

Sia P(x) una proposizione dipendente. Allora:

∧ ∨• ¬(P Q) è equivalente a (¬P) (¬Q) (legge di De Morgan);

∀x• ¬(∃x P(x)) è equivalente a ¬P(x);

∨ ∧• ¬(P Q) è equivalente a (¬P) (¬Q) (legge di De Morgan);

∃x• ¬(∀x P(x)) è equivalente a ¬P(x).

¬(¬P) è equivalente a P (legge della doppia negazione);

⇒ ∧• ¬(P Q)

è equivalente a P ¬Q.

Gli elementi di logica devono essere razionali (no fallaci logiche)∈INSIEMI - x A :x è un elemento di A x /∈ A :x non è un elemento di A.

∅. ∈ ∅, ∀x ∅.

L’insieme vuoto non ha elementi. In logica, il vuoto è l’unico insieme che ¬∃x x o equivalentemente x /∈

Ci sono due modi per descrivere un insieme:

• Rappresentazione estensiva, ovvero scrivere tutti i suoi elementi. {}, l’ordine in cui scriviamo gli elementi di un insieme non importa. Non contano neanche le ripetizioni. ∈
• Rappresentazione intensiva, ovvero scrivere una proprietà che caratterizzi tutti gli elementi. Es. {x N : x è pari}⊆

Theorem 2.29. L’insieme vuoto è sottoinsieme ( )di qualsiasi insieme.

Theorem 2.30. Ogni insieme è sottoinsieme di se stesso.

∪ ∈ ∨ ∈

Definizione 2.33. l’unione dei due insiemi, A B, {x : (x A) (x B)}

tutto A B Diagrammi di Venn:

∈ ∈- Definizione 2.34. l’intersezione dei due insiemi, A∩B, {x : (x A)∧(x B)}, sia A sia B

- Definizione 2.35. Fissiamo un insieme V , e sia A un sottoinsieme di V. Si scrive come Ac.Il complementare di A in V è l’insieme degli elementi che stanno in V∈ ∈ma non in A, ovvero {x V : ¬(x A)}

∈P(x) {x V : P(x)}

- Definizione 2.36. Dati due insiemi A e B, A\B (si dice A meno B) è l’insieme degli elementi che stanno∧ ∩ ∈in A ma che non stanno in B, quindi {x A : x /∈ B}.

∨ ∪ ∅ ∈ ∈Le parti di un insieme: calcoliamo P({3, 5}): P({3, 5}) e {3, 5} P({3, 5}). Altri due sottoinsiemi sono¬ c {3} e {5}, e non ce ne sono altri, quindi P({3, 5}) = {∅, {3}, {5}, {3, 5}}.

⇒ ⊆ Attenzione: ∅- non confondere 3 con - non confondere {3} con {{3}}: entrambi insiemi - e {∅}, perché sono entrambi{3}! Il primo è un numero, con un

solo elemento, l'elemento del primo è un insieme, ma il primo non ha elementi, il secondo è un insieme. numero, l'elemento del secondo è un insieme. mentre il secondo ne ha uno.- Definizione 2.43. Una sequenza è una collezione ordinata di oggetti. Si scrive con le parentesi tonde.- Definizione 2.44. Dati due insiemi A e B, il prodotto cartesiano di A e B, scritto A × B, è l'insieme delle coppie il cui primo elemento è un elemento di A e il secondo elemento è un elemento di B.

FUNZIONI ES. Sofia, camminando fra la gente, nota i diversi colori delle magliette delle persone che incontra per strada. È una funzione che associa ad ogni persona il colore della sua maglietta.

• sono ben fissati la partenza e l'arrivo della funzione
• tutti gli oggetti di partenza devono essere considerati
• la funzione associa un unico oggetto ad ogni oggetto di partenza

- Definizione 2.46. Siano X e Y insiemi, e sia

Se f è un'associazione che associa elementi di X a elementi di Y. Allora f è una funzione se:

• X ∀x ∈ ∃y ∈ ∀x ∈ ∀y ∈ ⇒ ∈
• X Y f(x) = y;
• X Y (f(x) = y (∀z Y (f(x) = z y = z))).

In tal caso scriviamo f : X → Y.

Definizione 2.49. Sia f : X → Y. Allora X è il dominio di f, si scrive anche dom(f), e Y è il codominio di f.

La funzione "colore della maglietta" ha come codominio l'insieme dei colori, ma magari ci sono colori che non vengono indossati (p.es. eliotropo).

Definizione 2.51. L'insieme immagine di una funzione è l'insieme dei valori assunti da una funzione. Ovvero, se f : X→Y, ∈ ∃x ∈ allora Im(f) = {y Y : X f(x) = y}. Possiamo scrivere anche f[dom(f)].

La funzione "colore della maglietta" ha come insieme immagine l'insieme dei colori delle magliette.

⊆ ∈ ∃x ∈

Definizione 2.52. Sia

f : X → Y , e sia A ⊆ X. Allora f[A] è l'insieme immagine di f su A, ovvero {y ∈ Y : ∃ x ∈ A, f(x) = y}. ∈• Rappresentazione per rimpiazzamento: {f(x) : x ∈ A} è f[A]. ∈- Definizione 2.55. Una funzione f : X → Y si dice suriettiva se f[X] = Y , ovvero se preso un qualunque elemento y ∈ Y , ∃ un elemento x ∈ X tale che f(x) = y. Ovvero, ogni elemento di Y è immagine di un elemento di X.- Definizione 2.56. Una funzione f : X → Y si dice iniettiva se non esistono due elementi di X che sono stati associati allo stesso elemento di Y , ovvero ∀x1, x2 ∈ X, f(x1) = f(x2) ⇒ x1 = x2- Biettiva: un solo e unico elemento x → yFunzione inversa di f: scriviamo f^−1, questa associazione è una funzione con dominio Y e codominio X.Come con le proposizioni, gli insiemi e i numeri, si possono fare operazioni anche fra funzioni. La più comune e usata è la composizione. Si tratta di mettere due funzioni una dopo l'altra.

l'altra.- Definizione 2.60. Siano X, Y, Z insiemi, siano f : X → Y e g : Y → Z due funzioni. La funzione composta di f e g, scritta g ◦f,∈è la funzione di dominio X, codominio Z, che associa ad ogni x X g(f(x)).

ES. Come si risolve:g(x) = y e fog(x)=f(g(x))=f(y)=tripeti finchè non finisce gsoluzione= fog: A->C e fog(x)=fog(z)=tquando fog f B->C e g A->B fog->AC f II e g Iquando gof f A->B e g B->C gof->AC f I e g II

- Definizione 2.63. Una funzione f : X → Y si diceinvertibile se esiste una funzione g : Y → X tale che∈ ∈per ogni x X vale g ◦ f(x) = x, e per ogni y Y valef ◦ g(y) = y.

- Theorem 2.64. Per ogni funzione f, f è biiettiva se e soltanto se f è invertibile.

- Definizione 2.65. Sia A un insieme finito. La cardinalità di A, scritta |A|, è il numero di elementi di A.⊆

- Theorem 2.66. Se A e B sono due insiemi finiti, e A B, allora |A| ≤ |B|.

- Theorem 2.70. Siano A e

B due insiemi finiti. Allora• se |A| < |B|, esistono da A a B • se |A| > |B|, ex da A a B funzioni • se |A| = |B|, allora esistonofunzioni neutre e funzioni iniettive neutre e funzioni suriettive; funzioni di tutti i quattro tipi.∈ ∈- Theorem 2.75. |{n N : n > 0}| = |N|, come testimoniato da f : {n N : n > 0} → N, f(n) = n − 1.∈Ma se f : {n N : n > 0} → N è biiettiva, esisterà anche l’inversa, ovvero f−1(n) = n + 1, che ci testimonia dunque che‘‘infinito meno uno = infinito”, “infinito meno due = infinito”∈ ∈- Theorem 2.76. |{n N : n è pari }| = |N|, come testimoniato da f : {n N : n è pari} → N, f(n) = n/2. falla−1(n) = 2n- Theorem 2.79. Non esistono funzioni suriettive da N a RRELAZIONI - Definizione 2.82/3/4. Sia R una relazione su X. ∀a ∈• R si dice riflessiva se ogni elemento di X è in relazione con se stesso,

ovvero X aRa.∀a ∈• R si dice irriflessiva se nessun elemento di X è in relazione con se stesso, ovvero X ¬(aRa).∀a, ∈ ⇒• R si dice simmetrica se tutte le relazioni sono reciproche, ovvero b X (aRb bRa). ∀a, ∈• R si dice anti-simmetrica se nessuna relazione è reciproca a parte gli elementi in relazione con se stessi, ovvero b⇒X (aRb∧bRa a = b). Attenzione! Rimane il caso in cui per alcune coppie la relazione non è né simmetrica né anti-simmetrica. ∀x, ∈ ∧ ⇒• R si dice transitiva se si “trasmette” da un elemento all’altro, ovvero y, z X (xRy yRz xRz). Attenzione! C’è di⇒:nuovo il problema di Cosa succede se non esistono tre elementi, il primo in relazione con il secondo e il secondo inrelazione con il terzo? La relazione è transitiva (banalmente), proprio

perché l'antecedente dell'implicazione è falso, quindi l'implicazione è vera.

Definizione 2.86. Una relazione irriflessiva e simmetrica si chiama grafo. Basta disegnare un punto per ogni elemento dell'insieme su cui il grafo è definito, e unire con una linea gli elementi che sono in relazione fra di loro. Gli elementi dell'insieme su cui il grafo è definito si chiamano nodi o vertici, le linee che li uniscono si chiamano archi o lati o spigoli.

Definizione 2.87. Una relazione irriflessiva si chiama grafo diretto. (Non essendo la relazione simmetrica, disegniamo una freccia per indicare la direzione della relazione)

I grafi pesati: sono grafi a cui viene assegnato un numero per ogni arco.

Il grafo colorato: un grafo a cui vengono assegnati dei colori ai nodi. Tipicamente si vuole assegnare dei colori in modo che se due nodi sono collegati da uno stesso arco hanno dei colori diversi.

Definizione 2.89. Una relazione si dice

Di equivalenza se è riflessiva, simmetrica e transitiva.

Definizione 2.92. Una relazione riflessiva, anti-simmetrica e transitiva si chiama ordine. Raffigurazione visiva di un ordine. L'idea è questa: se a è in relazione con b, allora mettiamo a sotto b e le uniamo con un segmento. Non serve mettere una freccia, la posizione indica giù. ∀x, ∈ ∨.

Definizione 2.94. Una relazione d'ordine R su X si dice totale o lineare se y X xRy yRx. Linea dritta. Facciamo attenzione a un'altra cosa: secondo la definizione, < non è un ordine! Questo perché gli ordini sono riflessivi, e< invece è irriflessivo. Questo tipo di relazioni si chiama ordine debole.

Definizione 2.97. Sia R un ordine su X.

Theorem 2.98. Massimo e∈ ∀x ∈• Se esiste un elemento M X tale che X xRM, allora M è il massimo di X. minimo, se esistono, sono∈ ∀x ∈• Se esiste un elemento m X tale che