Perché non si può dedurre la proprietà Riflessiva dalla Simmetria e dalla Transitività?

La risposta sintetica è: i quantificatori sono importanti, molto importanti.

La domanda mi è stata posta da studenti che iniziavano a studiare le relazioni di equivalenza. Si domandavano: perché è necessaria la Riflessività? Non può essere dedotta dalla Simmetria e dalla Transitività?

Ricordiamo allora la definizione di relazione di equivalenza.

Dati due insiemi $A$ e $B$, si dice Relazione un qualunque sottoinsieme del prodotto cartesiano $A\times B$. Una relazione può essere definita anche tra elementi di uno stesso insieme $A$: in questo caso, la relazione sarà un sottoinsieme del prodotto cartesiano $A\times A$ ($A^{2}$).

Una relazione $R$ in $A\times A$ è una equivalenza se gode delle proprietà Riflessiva, Simmetrica e Transitiva.

Proprietà Riflessiva (M): $\forall x\in A, (x,x)\in R$

Proprietà Simmetrica (S): $(x,y)\in R \Rightarrow (y,x)\in R$

Proprietà transitiva (T): $(x,y)\in R \wedge (y,z)\in R\Rightarrow (x,z)\in R$

Ora l’argomentazione portata da chi si poneva la questione era: S $\Rightarrow (x,y)\in R\Rightarrow (y,x)\in R$, quindi, applicando la T, $(x,x)\in R$, che sembra proprio la proprietà riflessiva M.

Sembra… Il punto chiave sta nel fatto che né la S né la T garantiscono che tutti gli elementi di A siano legati ad almeno un elemento di A dalla relazione R: manca cioè il quantificatore universale “per ogni” ($\forall$). Quantificatore che è invece presente nella proprietà riflessiva M.

In altri termini, la proprietà riflessiva M – proprio grazie al quantificatore universale “per ogni” ($\forall$) – è l’unica delle tre che garantisce di non lasciare alcun elemento di A fuori dalla relazione R; cosa che non fanno la S e la T.

Vale la pena ricordare che una relazione di equivalenza su un insieme A determina naturalmente dei sottoinsiemi di A, detti classi di equivalenza, che costituiscono una partizione di A. Ebbene, per definizione stessa di partizione, nessun elemento di A può restare escluso.

Chiudo con un esempio. La relazione così definita:

$R:\left \{(m,n)\in \mathbb{Z}^{2} : mn>0\right \}$

è evidentemente simmetrica e transitiva; inoltre quasi tutti gli elementi di $\mathbb{Z}$ sono in relazione $R$ con se stessi. Peraltro la relazione non è riflessiva perché $0\in\mathbb{Z}$ non è in relazione $R$ con se stesso (né con nessun altro elemento di $\mathbb{Z}$).

Per qualunque commento, dubbio o domanda, usate pure la sezione commenti dell’articolo. Grazie. A presto.

RESISTENZA EQUIVALENTE DI UNA CONNESSIONE INFINITA DI RESISTENZE SERIE PARALLELO

In queste poche righe vedremo come si può calcolare la resistenza equivalente della seguente rete costituita da infinite coppie di resistenze connesse in serie e in parallelo:

Indichiamo con $R_{EQ}$ la resistenza equivalente della rete di figura.

Se tagliamo idealmente la rete come indicato dalla linea tratteggiata nella figura sotto, è chiaro che la resistenza equivalente della rete a destra della linea è ancora la nostra $R_{EQ}$.

Abbiamo quindi:

$R_{EQ}=aR+bR||R_{EQ}$,

$R_{EQ}=aR+\frac{bR\cdot R_{EQ}}{bR+{R_{EQ}}}$,

$(bR+R_{EQ})R_{EQ}=aR(bR+R_{EQ})+bRR_{EQ}$ (*)

Con pochi passaggi algebrici e risolvendo l’equazione di secondo grado nella variabile $R_{EQ}$, si ha:

$R_{EQ}=\frac{aR}{2}(1+\sqrt{1+\frac{4b}{a}})$ (1)

Analizziamo brevemente alcuni casi particolari.

  1. $a=0$. In questo caso tutte le resistenze $aR$ sono cortocircuiti, quindi la resistenza equivalente attesa è nulla. Infatti, sostituendo $a=0$ nella (*) si ottiene $R_{EQ}=0$.
  2. $b=0$. In questo caso, tuttel el resistenze $bR$ sono dei cortocircuiti, quindi tutte le resistenze a destra della prima $aR$ saranno cortocircuitate. Pertanto, la resistenza equivalente complessiva è attesa essere $aR$. Infatti, sostituendo $b=0$ nella (1), si ottiene $R_{EQ}=aR$.
  3. Consideriamo infine il caso $a=b\neq0$. Sostituendo nella (1), si ha:

$R_{EQ}=\frac{1+\sqrt{5}}{2}R \cong 1.618R$ (2)

In molti avranno riconosciuto il numero aureo ($\frac{1+\sqrt{5}}{2}$) nella (2). Sembra che sia nascosto ovunque…

Vediamo un altro modo per ottenere lo stesso risultato della (2), che ci fornirà anche una ragione per cui il numero aureo appare nella (2).

Costruiamo la resistenza equivalente ad un passo per volta. Ricordiamo che stiamo calcolando la $R_{EQ}$ nel caso della rete con tutte le resistenze uguali tra loro ($R$)

Al primo step, calcoliamo la resistenza equivalente della rete costituite solo dalle prime due resistenze:

$R_{EQ,1}=2R=\frac{2}{1}R$

Al secondo step, aggiungiamo una coppia di resistenze (una in serie, l’altra in parallelo):

$R_{EQ,2}=R+R||2R=R+\frac{2R^{2}}{3R}=\frac{5}{3}R$

Al terzo step, aggiungiamo un’altra coppia di resistenze (una in serie, l’altra in parallelo):

$R_{EQ,3}=R+R||(R+R||2R)=R+R||\frac{5}{3}R=R+\frac{(\frac{5}{3}R^{2})}{\frac{8}{3}R}=R+\frac{5}{8}R=\frac{13}{8}R$

È evidente che stiamo ottenendo la seguente successione:

$\left \{R_{EQ,n}\right \}=\left \{ \frac{2}{1}R, \frac{5}{3}R, \frac{13}{8}R, \frac{34}{21}R, … \right \}$

Questa successione ci ricorda la successione di Fibonacci:

$f_{n}=\left \{ 1,1,2,3,5,8,13,21,34,55,… \right \}$

Infatti:

$\left \{R_{EQ,n}\right \}=\left \{ \frac{f_{2n+1}}{f_{2n}}R \right \}$ (3)

Ora, poiché la successione (3) è una estratta della $\left \{ \frac{f_{n+1}}{f_{n}}R \right \}$ (i.e. la successione dei rapporti dei termini consecutivi della successione di Fibonacci) che tende al numero aureo, si ha:

$R_{EQ}=\lim_{n}R_{EQ,n}=\lim_{n}\frac{f_{2n+1}}{f_{2n}}R=\lim_{n}\frac{f_{n+1}}{f_{n}}R=\frac{1+\sqrt{5}}{2}R$,

che coincide con la (2).

MCD e mcm tra due numeri: una relazione molto interessante!

Dati due numeri Naturali n e m, si ha: $\mathbf{n\cdot m = MCD(n,m)\cdot mcm(n,m)}$ (1)

È una relazione tanto interessante quanto utile: in Informatica, ad esempio, esistono diversi algoritmi per il calcolo del MCD tra due numeri per cui la (1) consente facilmente di implementare un algoritmo che calcoli il mcm:

$mcm(n,m) = \frac{n\cdot m}{MCD(n,m)}$ (2)

Dalla (1) si ricava anche:

$MCD(n,m) = \frac{n\cdot m}{mcm(n,m)}$ (3)

Esempi

1. Consideriamo i numeri 3 e 4, primi tra loro. Si ha: $mcm(3,4)=12$; $MCD(3,4)=1$ quindi $3\cdot 4=mcm(3,4)\cdot MCD(3,4)=12\cdot 1$

2. Consideriamo ora i numeri 12 e 90. Si ha: $mcm(12,90)=180$; $MCD(12,90)=6$ quindi $12\cdot 90=mcm(12,90)\cdot MCD(12,90)=180\cdot 6$

3. Consideriamo i numeri 24 e 30. La loro scomposizione in fattori primi è: $24=2^{3}\cdot 3$ e $30=2\cdot 3\cdot 5$. Ricordiamo che per calcolare il mcm occorre moltiplicare i fattori comuni a 24 e 30 e quelli non comuni, presi una sola volta col massimo esponente: $mcm(24,30)=2^{MAX(3,1)}\cdot 3\cdot 5= 2^{3}\cdot 3\cdot 5= 120$. Il MCD invece si calcola moltiplicando i soli fattori comuni a 24 e 30, presi una sola volta col minimo esponente: $MCD(24,30)=2^{min(3,1)}\cdot 3=2^{1}\cdot 3=6 $. Quindi: $mcm(24,30)\cdot MCD(24,30)=\left [ 2^{MAX(3,1)}\cdot 3\cdot 5\right ]\cdot \left [ 2^{min(3,1)}\cdot 3 \right ]= \left [ 2^{3}\cdot 3\cdot 5 \right ]\cdot \left [ 2^{1}\cdot 3 \right ]=$

$=(2^{3}\cdot 3)\cdot (2\cdot 3\cdot 5)=24\cdot 30=720$.

Dimostrazioni

Fornirò due dimostrazioni della proposizione esposta perché alquanto diverse tra loro.

Dimostrazione 1

Siano dunque n e m due naturali. La loro scomposizione in fattori primi si può scrivere convenientemente come segue:

$n=c_{n_1}^{e_{n_1}}\cdot c_{n_2}^{e_{n_2}}\cdot … \cdot c_{n_k}^{e_{n_k}}\cdot u_{n_1}^{e’_{n_1}}\cdot u_{n_2}^{e’_{n_2}}\cdot … \cdot u_{n_i}^{e’_{n_i}}=\prod_{\alpha =1}^{k}c_{n_\alpha }^{e_{n_{\alpha }}}\cdot \prod_{\beta =1}^{i}u_{n_\beta }^{e’_{n_{\beta }}}$ (4)

$m=c_{m_1}^{e_{m_1}}\cdot c_{m_2}^{e_{m_2}}\cdot … \cdot c_{m_k}^{e_{m_k}} \cdot u_{m_1}^{e’_{m_1}}\cdot u_{m_2}^{e’_{m_2}}\cdot … \cdot u_{m_j}^{e’_{m_j}} =\prod_{\alpha =1}^{k}c_{m_\alpha }^{e_{m_{\alpha }}}\cdot \prod_{\gamma =1}^{i}u_{m_\gamma }^{e’_{m_{\gamma }}} $ (5)

in cui i fattori indicati con la lettera c (Common) sono i fattori comuni alle scomposizioni di n e m (e dunque sono in numero uguale, k, con esponenti non necessariamente uguali), mentre i fattori indicati con la lettera u (Uncommon) sono non comuni.

Procedendo come nell’esempio 3, si ha:

$MCD(n,m)= \prod_{\alpha =1}^{k}c_{n_\alpha }^{min(e_{n_{\alpha }}, e_{m_{\alpha }})}$ (6)

$mcm(n,m)= \prod_{\alpha =1}^{k}c_{n_\alpha }^{MAX(e_{n_{\alpha }}, e_{m_{\alpha }})} \cdot \prod_{\beta =1}^{i}u_{n_\beta }^{e’_{n_{\beta }}} \cdot \prod_{\gamma =1}^{i}u_{m_\gamma }^{e’_{m_{\gamma }}} $ (7)

Moltiplicando tra loro la (6) e la (7) si ha:

$mcm(n,m)\cdot MCD(n,m)= \prod_{\alpha =1}^{k}c_{n_\alpha }^{ min(e_{n_{\alpha }}, e_{m_{\alpha }})+MAX(e_{n_{\alpha }}, e_{m_{\alpha }})} \cdot \prod_{\beta =1}^{i}u_{n_\beta }^{e’_{n_{\beta }}} \cdot \prod_{\gamma =1}^{i}u_{m_\gamma }^{e’_{m_{\gamma }}} $ (8)

Peraltro, trattandosi soltanto di due numeri, è chiaro che

$ min(e_{n_{\alpha }}, e_{m_{\alpha }})+MAX(e_{n_{\alpha }}, e_{m_{\alpha }})= e_{n_{\alpha }} + e_{m_{\alpha }}, \forall \alpha \epsilon \left \{1,…,k \right\} $ (9)

Dalla (8) e la (9) si ottiene dunque:

$mcm(n,m)\cdot MCD(n,m)= \prod_{\alpha =1}^{k}c_{n_\alpha }^{ e_{n_{\alpha }}+e_{m_{\alpha }}} \cdot \prod_{\beta =1}^{i}u_{n_\beta }^{e’_{n_{\beta }}} \cdot \prod_{\gamma =1}^{i}u_{m_\gamma }^{e’_{m_{\gamma }}} = $

$= \prod_{\alpha =1}^{k}c_{n_\alpha }^{e_{n_{\alpha }}}\cdot \prod_{\beta =1}^{i}u_{n_\beta }^{e’_{n_{\beta }}} \cdot \prod_{\alpha =1}^{k}c_{m_\alpha }^{e_{m_{\alpha }}}\cdot \prod_{\gamma =1}^{i}u_{m_\gamma }^{e’_{m_{\gamma }}} = n \cdot m$ (10),

come volevasi dimostrare.

Dimostrazione 2

Siano ancora n e m due naturali e sia D il MCD(n,m) e G il mcm(n,m).

Riscriviamo dunque la (1) come $n\cdot m=G\cdot D$.

Dimostrare la (1) equivale quindi a dimostrare che:

(H) $D=MCD(n,m)\Rightarrow$ (T) $G=\frac{nm}{D}=mcm(n,m)$ (11)

Dimostrare che G – così come è definito dal secondo membro della (11) – è il mcm(n,m) equivale a dimostrare le due seguenti affermazioni:

(a) G è multiplo di n e m

(b) Non esistono multipli di n e m minori di G

Per dimostrare l’affermazione (a), poichè D – per l’ipotesi (H) – è divisore sia di n che di m, si ha:

$\exists k\epsilon N_0:n=kD$ (12)

$\exists h\epsilon N_0:m=hD $ (13)

dalla (12) si ricava $G=\frac{n\cdot m}{D}=\frac{kDm}{D}=km\Rightarrow\textbf{G è multiplo di m}$

analogamente, dalla (13) si ricava $G=\frac{n\cdot m}{D}=\frac{nhD}{D}=hn\Rightarrow\textbf{G è multiplo di n}$,

sicché la (a) è dimostrata.

Per provare la (b), supponiamo per assurdo che $\exists G'<G : G’=h’n=k’m$, (sicché k'<k e h'<h). Posto $D’=\frac{nm}{G’}$, si ha:

$\frac{n}{D’}=\frac{G’}{m}=h’\Rightarrow$ D’ è divisore di n

$\frac{m}{D’}=\frac{G’}{n}=k’\Rightarrow$ D’ è divisore di m.

Quindi D’ è divisore comune di n e m.

Peraltro, l’ipotesi G'<G $\Rightarrow D’=\frac{nm}{G’}>\frac{nm}{G}=D\Rightarrow D’>D \Rightarrow $ D non è MCD, contro l’ipotesi iniziale (H).

L’assurdo cui si è pervenuti mostra la tesi: non esistono multipli di n e m minori di G, sicchè anche la (b) è dimostrata.

Quindi G è il mcm(n,m).