|
Non sarà un punto focale di questo libro, ma spesso verrà usato un vocabolario minimo di tale teoria. Questa sezione introduce notazione e vocabolario usati.
{{Avanzamento|0%|28 ottobre 2019}}
== Definizioni estensionali e intensionali ==
{{Definizione|Un insieme è una ''collezione'' di oggetti, detti ''elementi'' dell'insieme. Scriviamo <math>x \in S</math> per dire che l'oggetto <math>x</math> è un elemento dell'insieme <math>S</math> e <math>x \not\in S</math> per dire che l'oggetto <math>x</math> non è elemento di <math>S</math>.}}
<math>x=y</math> sta a denotare che l'oggetto <math>x</math> è uguale all'oggetto <math>y</math>; <math>x \neq y</math> denota che l'oggetto <math>x</math> ''non'' è uguale all'oggetto <math>y</math>. Se <math>S</math> e <math>T</math> sono due insiemi e <math>S=T</math>, allora, per ogni oggetto <math>x</math>, <math>x \in S</math> sse <math>x \in T</math>, dove ''sse'' significa ''se e solo se''. Viceversa, secondo il ''principio di estensionlità'', se <math>S</math> e <math>T</math> sono due insiemi e, per ogni oggetto <math>x</math>, <math>x \in S</math> sse <math>x \in T</math>, allora <math>S=T</math>.
Osserviamo quindi che <math>\{x,y,x\}=\{x,y\}</math>, e che <math>\{x,y\}=\{y,x\}</math>; infatti, in un insieme tutti gli elementi sono distinti e l'ordine in cui essi compaiono è irrilevante.
L'''insieme vuoto'', ovvero l'insieme senza elementi, viene denotato con <math>\emptyset</math>.
Per ogni oggetto <math>x</math> esiste un insieme <math>\{x\}</math> il cui unico elemento è proprio <math>x</math>; <math>\{x\}</math> viene di solito detto ''singoletto''.
Più in generale, per ogni collezione finita di oggetti <math>x_1,...,x_n</math> esiste un insieme <math>\{x_1,...,x_n\}</math> i cui elementi sono esattamente tali oggetti. La definizione di insiemi appena vista, che consiste nell'enumerazione esplicita dei suoi elementi, si dice ''estensionale''. Un insieme può anche essere definito in modo ''intensionale'', descrivendolo in modo "implicito" come la collezione di elementi che condividono una certa proprietà <math>P</math>. Scriviamo <math>\{x|P(x)\}</math> per indicare l'insieme di tutti gli oggetti <math>x</math> che hanno la proprietà <math>P</math>. L'insieme di tali <math>x</math> è detto l'''estensione'' di <math>P</math>. Così, l'insieme vuoto può, per esempio, essere esemplificato come <math>\emptyset=\{x|x \neq x\}</math>.
Qui e nel seguito, le proprietà vengono indicate con nomi ad iniziale maiuscola. Le entità, quando denotate da espressioni, sono indicate con nomi ad iniziale minuscola. I nomi propri sono indicati con iniziale maiuscola.
La definizione intensionale permette di specificare un insieme come tutti gli elementi che verificano un certo enunciato, costruito combinando delle proprietà sulla base di operazioni ''vero-funzionali''.
Per esempio, se scriviamo <math>A=\{x \in \N|x>3\ e\ x<5\}</math>, la frase "<math>x>3\ e\ x<5</math>" è un enunciato vero-funzionale che stabilisce una proprietà degli elementi <math>x</math> che appartengono ad <math>A</math>; in questo caso, il solo numero <math>4</math>. Quindi, la definizione intensionale di <math>A</math> sta per l'enunciato<blockquote><math>x \in A</math> sse <math>x \in \N\ e\ x>3\ e\ x<5</math></blockquote>che risulta dalla combinazione di più enunciati elementari: <math>x \in A</math>, <math>x \in \N</math>, <math>x>3</math>, <math>x<5</math>.
Ci limitiamo qui ad introdurre dei concetti di base delle operazioni vero-funzionali utilizzate nella definizione di insiemi, e rimandiamo alla logica proposizionale per un'introduzione formale agli enunciati e alla loro costruzione tramite ''connettivi logici''. Sono operazioni vero-funzionali <math>non,\ e,\ oppure,\ implica,\ sse</math>.
{{Definizione|Se <math>A</math> non menziona operazioni vero-funzionali, allora è un enunciato elementare (anche detto ''atomo''), ed è verificato in base al contesto.}}
{{Definizione|
Dati due enunciati <math>A</math> e <math>B</math> e le operazioni vero-funzionali <math>non,\ e,\ oppure,\ se...allora,\ sse</math>, un enunciato è verificato in accordo alle seguenti regole:
# <math>non(A)</math> è verificato sse <math>A</math> non è verificato.
# <math>(A\ e\ B)</math> è verificato sse sono verificati entrambi <math>A</math> e <math>B</math>.
# <math>(A\ oppure\ B)</math> è verificato sse è verificato <math>A</math>, oppure è verificato <math>B</math>.
# <math>(A\ implica\ B)</math>è verificato sse non è verificato <math>A</math>, oppure è verificato <math>B</math>.
# <math>(A\ sse\ B)</math> è verificato sse entrambi <math>A</math> e <math>B</math> sono verificati, oppure entrambi <math>A</math> e <math>B</math> non sono verificati.
}}
Dalle precedenti definizioni, si può evincere che un enunciato <math>A</math> può essere una proprietà, come <math>Cane(x)</math>, <math>Padre(Geppetto,Pinocchio)</math>, oppure può risultare dalla combinazione di altri enunciati, tramite le operazioni vero-funzionali, in accordo alle precedenti regole. In genere, si usano le parentesi per stabilire la precedenza delle operazioni; talvolta, in contesti in cui la precedenza degli operatori non dà adito ad ambiguità, le parentesi sono omesse, ad esempio <math>nonA</math>.
==== Proprietà 1 ====
Per il simbolo <math>=</math> valgono le seguenti proprietà, dove <math>A</math>, <math>B</math> e <math>C</math> possono essere entità, insiemi oppure enunciati:
# <math>A=A</math> (Riflessività);
# <math>A=B</math> sse <math>B=A</math> (Simmetricità);
# se <math>A=B</math> e <math>B=C</math> allora <math>A=C</math> (Transitività).
== Sottoinsiemi ==
Se <math>S</math> e <math>T</math> sono due insiemi e tutti gli elementi di <math>S</math> sono anche elementi di <math>T</math>, diciamo che <math>S</math> è un sottoinsieme di <math>T</math> e scriviamo <math>S \subseteq T</math>. Se <math>S</math> e <math>T</math> hanno gli stessi elementi scriviamo <math>S=T</math>:<blockquote><math>S=T\ \overset{def}=S \subseteq T\ e\ T \subseteq S</math>
(1)</blockquote>Se <math>S \subseteq T</math> e <math>S \neq T</math>, diciamo che <math>S</math> è un ''sottoinsieme proprio'' di <math>T</math> e che <math>T</math> è un ''sovrainsieme proprio'' di <math>S</math>, e scriviamo <math>S \subset T</math>. L'operatore <math>\subset</math> è detto ''inclusione stretta'' ed è definito come segue:<blockquote><math>S \subset T\ \overset{def}=S \subseteq T\ e\ T \nsubseteq S</math>
(2)</blockquote>dove <math>T \nsubseteq S</math> (<math>T \not\subset S</math>) sta ad indicare che <math>S</math> non è sottoinsieme (proprio) di <math>T</math>. Ogni insieme è sottoinsieme di sé stesso; <math>\emptyset</math> è sottoinsieme di ogni insieme.
Introduciamo per <math>\subset</math>, <math>=</math> e <math>\subseteq</math> le seguenti definizioni:
{{Definizione|
# <math>S \subseteq T</math> sse, per ogni <math>x</math>, <math>x \in S\ implica\ x \in T</math>;
# <math>S=T</math> sse, per ogni <math>x</math>, <math>x \in S\ sse\ x \in T</math>;
# <math>S \subset T</math> sse <math>S \subseteq T\ e\ T \nsubseteq S</math>.
}}
==== Proprietà 2 ====
Per <math>\subseteq</math> valgono le seguenti proprietà:
# <math>S \subseteq S</math>, per ogni insieme <math>S</math> (Riflessività);
# se <math>S_1 \subseteq S_2</math> e <math>S_2 \subseteq S_3</math> allora <math>S_1 \subseteq S_3</math> (Transitività);
# se <math>S_1 \subseteq S_2</math> e <math>S_2 \subseteq S_1</math> allora <math>S_1=S_2</math> (Antisimmetricità);
Queste proprietà si derivano dalle definizioni date sopra.
==== Proposizione 1 ====
# <math>S \not\subset S</math>, per ogni insieme <math>S</math>;
# se <math>S_1 \subset S_2</math> e <math>S_2 \subseteq S_3</math> allora <math>S_1 \subset S_3</math>;
# se <math>S_1 \subseteq S_2</math> e <math>S_2 \subset S_3</math> allora <math>S_1 \subset S_3</math>.
''Dimostrazione''
# Se <math>S \subset S</math>, per l'equazione (2) abbiamo che <math>S \subseteq S</math> e <math>S \nsubseteq S</math>, contraddizione.
# Segue dalla transitività.
# Come sopra, segue dalla transitività di <math>\subseteq</math>.
== Operazioni ==
=== Unione ===
L'''unione'' di due insiemi <math>S</math> e <math>T</math>, scritto <math>S \cup T</math>, è l'insieme di tutti gli oggetti che sono elementi di <math>S</math> oppure di <math>T</math>. Definiamo l'unione come:<blockquote><math>S \cup T\ \overset{def}=\{x|x \in S\ oppure\ x \in T\}</math>.</blockquote>
==== Proprietà ====
Per l'operazione <math>\cup</math> valgono le seguenti proprietà:
# <math>S \cup S=S</math> (Idempotenza);
# <math>S_1 \cup S_2=S_2 \cup S_1</math> (Commutatività);
# <math>S \cup \emptyset=\emptyset \cup S=S</math> (Elemento neutro);
# <math>S_1 \cup S_2=S_2</math> sse <math>S_1 \subseteq S_2</math> (Assorbimento);
# <math>(S_1 \cup S_2)\cup S_3=S_1 \cup (S_2 \cup S_3)</math> (Associatività);
# <math>S_1 \subseteq S_1 \cup S_2</math>;
# <math>S_2 \subseteq S_1 \cup S_2</math>.
''Dimostrazione''
# <math>S \cup S=\{x|x \in S\ oppure\ x \in S\}=\{x|x \in S\}=S</math>;
# <math>S_1 \cup S_2=\{x|x \in S_1\ oppure\ x \in S_2\}=\{x|x \in S_2\ oppure\ x \in S_1\}=S_2 \cup S_1</math>;
# <math>S \cup \emptyset=\emptyset \cup S=\{x|x \in S\ oppure\ x \in \emptyset\}=\{x|x \in S\}=S</math>;
# <math>S_1 \cup S_2=\{x|x \in S_1\ oppure\ x \in S_2\}=\{x|x \in S_2\}=S_2</math> sse, per ogni <math>x</math>, <math>x \in S_1\ implica\ x \in S_2</math> sse <math>S_1 \subseteq S_2</math>;
#<math>(S_1 \cup S_2)\cup S_3=\{x|x \in S_1\ oppure\ x \in S_2\}\cup\{x|x \in S_3\}=\{x|x \in S_1\ oppure\ x \in S_2\ oppure\ x \in S_3\}=</math><math>=\{x|x \in S_1\}\cup\{x|x \in S_2\ oppure\ x \in S_3\}=S_1 \cup (S_2 \cup S_3)</math>;
#<math>S_1=\{x|x \in S_1\} \subseteq \{x|x \in S_1\ oppure\ x \in S_2\}=S_1 \cup S_2</math>;
#analoga alla precedente.
==== Unione di famiglie di insiemi ====
Sia <math>\mathcal F</math> un insieme i cui elementi sono insiemi, cioè sia <math>\mathcal F</math> una famiglia di insiemi. L'unione di tali insiemi è l'insieme<blockquote><math>\bigcup\mathcal F=\{x|x \in X,\text{per qualche } X \in \mathcal F\}</math>.</blockquote>Nel caso in cui abbiamo una famiglia di insiemi <math>\{S_i|i \in \N\}</math>, scriviamo l'unione di tali insiemi <math>\bigcup_{i \in \N}S_i</math> o, più semplicemente, <math>\bigcup_i S_i</math>.
=== Intersezione ===
L'''intersezione'' di due insiemi <math>S</math> e <math>T</math>, scritto <math>S \cap T</math>, è l'insieme di tutti gli oggetti che sono elementi sia di <math>S</math> che di <math>T</math>. <math>S</math> e <math>T</math> sono ''disgiunti'' sse la loro intersezione è vuota. Definiamo l'intersezione come:<blockquote><math>S \cap T\ \overset{def}=\{x|x \in S\ e\ x \in T\}</math>.</blockquote>
==== Proprietà ====
Per l'operazione <math>\cap</math> valgono le seguenti proprietà:
# <math>S \cap S=S</math> (Idempotenza);
# <math>S_1 \cap S_2=S_2 \cap S_1</math> (Commutatività);
# <math>S \cap \emptyset=\emptyset \cap S=\emptyset</math>;
# <math>S_1 \cap S_2=S_1</math> sse <math>S_1 \subseteq S_2</math> (Assorbimento);
#<math>(S_1 \cap S_2)\cap S_3=S_1 \cap (S_2 \cap S_3)</math> (Associatività);
#<math>S_1 \cap S_2 \subseteq S_1</math>;
#<math>S_1 \cap S_2 \subseteq S_2</math>.
''Dimostrazione''
#<math>S \cap S=\{x|x \in S\ e\ x \in S\}=\{x|x \in S\}=S</math>;
#<math>S_1 \cap S_2=\{x|x \in S_1\ e\ x \in S_2\}=\{x|x \in S_2\ e\ x \in S_1\}=S_2 \cap S_1</math>;
#<math>S \cap \emptyset=\emptyset \cap S=\{x|x \in S\ e\ x \in \emptyset\}=\emptyset</math>;
#<math>S_1 \cap S_2=\{x|x \in S_1\ e\ x \in S_2\}=\{x|x \in S_1\}=S_1</math> sse, per ogni <math>x</math>, <math>x \in S_1\ implica\ x \in S_2</math> sse <math>S_1 \subseteq S_2</math>;
#<math>(S_1 \cap S_2)\cap S_3=\{x|x \in S_1\ e\ x \in S_2\}\cap\{x|x \in S_3\}=\{x|x \in S_1\ e\ x \in S_2\ e\ x \in S_3\}=\{x|x \in S_1\}\cap\{x|x \in S_2\ e\ x \in S_3\}=S_1 \cap (S_2 \cap S_3)</math>;
#<math>S_1 \cap S_2=\{x|x \in S_1\ e\ x \in S_2\} \subseteq \{x|x \in S_1\}=S_1</math>;
#analoga alla precedente.
==== Proprietà distributive ====
<math>\cup</math> e <math>\cap</math> sono legate dalle seguenti proprietà:
# <math>S_1 \cap (S_2 \cup S_3)=(S_1 \cap S_2) \cup (S_1 \cap S_3)</math>;
# <math>S_1 \cup (S_2 \cap S_3)=(S_1 \cup S_2) \cap (S_1 \cup S_3)</math>.
''Dimostrazione''<blockquote>1. <math>S_1 \cap (S_2 \cup S_3)</math></blockquote><blockquote><math>=\{x|x \in S_1\ e\ x \in (S_2 \cup S_3)\}</math></blockquote><blockquote><math>=\{x|x \in S_1\ e\ (x \in S_2\ oppure\ x \in S_3)\}</math></blockquote><blockquote><math>=\{x|(x \in S_1\ e\ x \in S_2)\ oppure\ (x \in S_1\ e\ x \in S_3)\}</math></blockquote><blockquote><math>=\{x|x \in (S_1 \cap S_2)\ oppure\ x \in (S_1 \cap S_3)\}</math></blockquote><blockquote><math>=(S_1 \cap S_2) \cup (S_1 \cap S_3)</math>;</blockquote><blockquote>2. <math>S_1 \cup (S_2 \cap S_3)</math></blockquote><blockquote><math>=\{x|x \in S_1\ oppure\ x \in (S_2 \cap S_3)\}</math></blockquote><blockquote><math>=\{x|x \in S_1\ oppure\ (x \in S_2\ e\ x \in S_3)\}</math></blockquote><blockquote><math>=\{x|(x \in S_1\ oppure\ x \in S_2)\ e\ (x \in S_1\ oppure\ x \in S_3)\}</math></blockquote><blockquote><math>=\{x|x \in (S_1 \cup S_2)\ e\ x \in (S_1 \cup S_3)\}</math></blockquote><blockquote><math>=(S_1 \cup S_2) \cap (S_1 \cup S_3)</math>.</blockquote>
==== Intersezione di famiglie di insiemi ====
Sia <math>\mathcal F</math> un insieme i cui elementi sono insiemi, cioè sia <math>\mathcal F</math> una famiglia di insiemi. L'intersezione di tali insiemi è l'insieme<blockquote><math>\bigcap\mathcal F=\{x|x \in X,\text{per ogni } X \in \mathcal F\}</math>.</blockquote>Nel caso in cui abbiamo una famiglia di insiemi <math>\{S_i|i \in \N\}</math>, scriviamo l'intersezione di tali insiemi <math>\bigcap_{i \in \N}S_i</math> o, più semplicemente, <math>\bigcap_i S_i</math>.
=== Complementazione ===
Sia dato un insieme <math>U</math>, che chiamiamo ''universo''. La differenza di un insieme <math>S \subseteq U</math> rispetto a <math>U</math> si chiama ''complemento di <math>S</math> in'' <math>U</math>, oppure ''complemento di <math>S</math>'', se l'insieme <math>U</math> può essere sottinteso. Per indicare il complemento di <math>S</math> scriviamo <math>\overline S</math>. In modo intensionale, definiamo il complemento di <math>S</math> come:<blockquote><math>\overline S=\{x|x \in U\ e\ x \not\in S\}</math>.</blockquote>
==== Proprietà ====
Per la complementazione valgono le seguenti proprietà:
# <math>\overline U=\emptyset</math>;
# <math>\overline \emptyset=U</math>;
# <math>\overline\overline S=S</math> (Doppia negazione insiemistica);
# <math>\overline{S_1 \cup S_2}=\overline{S_1} \cap \overline{S_2}</math> (Legge di De Morgan per <math>\cup</math>);
#<math>\overline{S_1 \cap S_2}=\overline{S_1} \cup \overline{S_2}</math> (Legge di De Morgan per <math>\cap</math>);
#<math>S \cap \overline S=\emptyset</math> (Contraddizione insiemistica);
#<math>S \cup \overline S=U</math> (Terzo escluso insiemistico);
#<math>S_1=S_2</math> sse <math>\overline{S_1}=\overline{S_2}</math>;
#<math>S_1 \subseteq S_2</math> sse <math>\overline{S_2} \subseteq \overline{S_1}</math>.
''Dimostrazione''
# <math>\overline U=\{x|x \in U\ e\ x \not\in U\}=\emptyset</math>;
# <math>\overline \emptyset=\{x|x \in U\ e\ x \not\in \emptyset\}=U</math>;
#<math>\overline\overline S=\{x|x \in U\ e\ x \not\in \overline S\}=\{x|x \in U\ e\ x \not\in \{x|x \in U\ e\ x \not\in S\}\}=\{x|x \in U\ e\ non(x \in \{x|x \in U\ e\ x \not\in S\})\}=</math><math>=\{x|x \in U\ e\ non(x \in U\ e\ x \not\in S)\}=\{x|x \in U\ e\ (x \not\in U\ oppure\ x \in S)\}=\{x|(x \in U\ e\ x \not\in U)\ oppure\ (x \in U\ e\ x \in S)\}=</math><math>=\{x|x \in U\ e\ x \in S\}=U \cap S</math>; dato che <math>S \subseteq U</math>, abbiamo che <math>U \cap S=S</math>;
#<math>\overline{S_1 \cup S_2}=\{x|x \in U\ e\ x \not\in (S_1 \cup S_2)\}=\{x|x \in U\ e\ non(x \in \{x|x \in S_1\ oppure\ x \in S_2\})\}=\{x|x \in U\ e\ non(x \in S_1\ oppure\ x \in S_2)\}=</math> <math>=\{x|x \in U\ e\ (x \not\in S_1\ e\ x \not\in S_2)\}=\{x|x \in U\ e\ x \not\in S_1\ e\ x \in U\ e\ x \not\in S_2\}=\{x|x \in U\ e\ x \not\in S_1\} \cap \{x|x \in U\ e\ x \not\in S_2\}=\overline {S_1} \cap \overline {S_2}</math>;
#<math>\overline{S_1 \cap S_2}=\{x|x \in U\ e\ x \not\in (S_1 \cap S_2)\}=\{x|x \in U\ e\ non(x \in \{x|x \in S_1\ e\ x \in S_2\})\}=\{x|x \in U\ e\ non(x \in S_1\ e\ x \in S_2)\}=</math> <math>=\{x|x \in U\ e\ (x \not\in S_1\ oppure\ x \not\in S_2)\}=\{x|(x \in U\ e\ x \not\in S_1)\ oppure\ (x \in U\ e\ x \not\in S_2)\}=\{x|x \in U\ e\ x \not\in S_1\} \cup \{x|x \in U\ e\ x \not\in S_2\}=</math><math>=\overline {S_1} \cup \overline {S_2}</math> ;
#<math>S \cap \overline S=\{x|x \in S\ e\ x \in \overline S\}=\{x|x \in S\ e\ (x \in \{x|x \in U\ e\ x \not\in S\})\}=\{x|x \in S\ e\ (x \in U\ e\ x \not\in S)\}=</math> <math>=\{x|x \in S\ e\ x \in U\ e\ x \not\in S\}=\emptyset</math>;
#<math>S \cup \overline S=\{x|x \in S\ oppure\ x \in \overline S\}=\{x|x \in S\ oppure\ (x \in \{x|x \in U\ e\ x \not\in S\})\}=\{x|x \in S\ oppure\ (x \in U\ e\ x \not\in S)\}=</math> <math>=\{x|(x \in S\ oppure\ x \in U)\ e\ (x \in S\ oppure\ x \not\in S)\}=\emptyset</math>; dato che <math>S \subseteq U</math>, abbiamo che<math>\{x|(x \in S\ oppure\ x \in U)\ e\ (x \in S\ oppure\ x \not\in S)\}=\{x|x \in U\ e\ (x \in S\ oppure\ x \not\in S)\}</math>; Dato che <math>(x \in S\ oppure\ x \not\in S)</math> è una tautologia classica, deduciamo che <math>\{x|x \in U\ e\ (x \in S\ oppure\ x \not\in S)\}=\{x|x \in U\}=U</math>;
#<math>S_1=S_2</math> sse <math>\overline{S_1}=\{x|x \in U\ e\ x \not\in S_1\}=\{x|x \in U\ e\ x \not\in S_2\}=\overline {S_2}</math>, sostituendo <math>S_1</math> con <math>S_2</math> per l'uguaglianza;
#Dato che <math>S_1 \subseteq S_2</math>, per assorbimento dell'unione abbiamo che <math>S_2=S_1 \cup S_2</math>, quindi, per la legge di De Morgan, <math>\overline{S_2}=\overline{S_1 \cup S_2}=\overline{S_1} \cap \overline{S_2}</math>, dunque, per assorbimento dell'intersezione, <math>\overline{S_2}=\overline{S_1} \cap \overline{S_2}</math> sse <math>\overline{S_2} \subseteq \overline{S_1}</math>.
== Insieme potenza ==
L'insieme ''potenza'' di un insieme <math>S</math>, scritto <math>\wp S</math> (detto anche ''insieme delle parti'' di <math>S</math>) è l'insieme formato da tutti i sottoinsiemi di <math>S</math>:<blockquote><math>\wp S=\{X|X \subseteq S\}</math>.</blockquote><math>\bigcup\wp S=S</math>, per ogni insieme <math>S</math>.
==== Cardinalità dell'insieme potenza ====
Se <math>|S|=n</math> (con <math>n \geq 0</math>), allora <math>|\wp S| = 2^n</math>.
''Dimostrazione''
Procediamo per induzione.
Se ''<math>n=0</math>,'' necessariamente <math>S=\emptyset</math>. E quindi <math>\wp S = \{ \emptyset \}</math>, dunque <math>|\wp S| = 2^0 = 1</math>.
Sia ''<math>n+1>0</math>'', e supponiamo l'asserto vero per <i><math>n</math></i>. Cioè, se ''<math>S</math>'' è un insieme tale che <math>|S| = n</math>, allora <math>|\wp S| = 2^n</math>.
Poiché adesso si ipotizza che <math>|T| = n+1 > 0</math>, necessariamente <math>T \neq \emptyset</math>, e dovrà avere almeno un elemento. Sia <math>x</math> un elemento dell'insieme. Un qualunque sottoinsieme di ''<math>T</math>'' può contenerlo o meno:
*I sottoinsiemi che non contengono <math>x</math> sono sottoinsiemi di <math>T \backslash \{x\}</math>. Poiché <math>|T \backslash \{x\}| = n</math>, tali sottoinsiemi sono, per ipotesi induttiva, <math>2^n</math>.
*I sottoinsiemi che contengono <math>x</math> sono sottoinsiemi del tipo <math>X \cup \{x\}</math>, con <math>X \subseteq T \backslash \{x\}</math>; quindi anche tali sottoinsiemi sono, per ipotesi induttiva, <math>2^n</math>.
Quindi i sottoinsiemi di S sono in tutto <math>2^n+2^n=2\cdot 2^n=2^{n+1}</math>.
{{Avanzamento|25%|31 luglio 2018}}
[[Categoria:Logica matematica|Insiemi]]
| 