Dimostrazione mediante biiezione

Questa voce sull'argomento matematica è solo un abbozzo.

Contribuisci a migliorarla secondo le convenzioni di Teknopedia. Segui i suggerimenti del progetto di riferimento.

Una dimostrazione mediante biiezione è un genere di dimostrazione utilizzata in combinatoria che ha come scopo una uguaglianza di due espressioni enumerative che forniscono le cardinalità di due insiemi finiti X e Y consiste nella determinazione di una funzione biiettiva ${\displaystyle \beta :X\to Y}$ dalla quale si può dedurre immediatamente ${\displaystyle |X|=|Y|}$.

Spesso la funzione β viene individuata precisando due costruzioni: una B che trasforma un qualsiasi elemento x di X in un elemento di Y con il ruolo di β(x) e una G che trasforma un qualsiasi elemento y di Y in un elemento di X e tale da fornire la funzione inversa della β.

Questo modo di procedere viene adottato in molte situazioni nelle quali serve conoscere la cardinalità di un insieme X tendenzialmente "complesso" e/o "nuovo" e la esistenza della biiezione β permette di ottenere ${\displaystyle |X|}$ dalla cardinalità ${\displaystyle |Y|}$ di un insieme più semplice, o precedentemente conosciuto.

In molti casi la conoscenza della β consente di ottenere una consapevolezza molto maggiore della struttura dei due insiemi e ad individuare un livello di astrazione superiore al quale entrambi gli insiemi si possono ricondurre con una più chiara visione dei problemi che riguardano i due insiemi. Negli ultimi decenni si sono trovate numerose dimostrazione mediante biiezione le quali hanno portato rilevanti avanzamenti per la combinatoria.

• Dimostrazione mediante doppio conteggio

Portale Matematica: accedi alle voci di Teknopedia che trattano di matematica