Insiemi e operazioni

Dopo aver fissato il concetto di insieme e la sua rappresentazione con i diagrammi di Venn, introduciamo le quattro operazioni fondamentali — unione, intersezione, complementare e differenza — e le due leggi di De Morgan che le collegano. Chiude la sezione la differenza simmetrica, la versione insiemistica dell‘“aut” logico.

• Che cos’è un insieme
• Le operazioni fondamentali tra insiemi
• Le leggi di De Morgan
• La differenza simmetrica

After fixing the concept of a set and its representation with Venn diagrams, we introduce the four fundamental operations — union, intersection, complement and difference — and the two De Morgan’s laws that connect them. The section closes with the symmetric difference, the set-theoretic version of the logical “aut”.

• What a set is
• The fundamental operations between sets
• De Morgan’s laws
• The symmetric difference

La teoria degli insiemi è il linguaggio con cui si formalizza tutta la matematica. I diagrammi di Venn sono il modo più intuitivo per visualizzarne gli oggetti e le operazioni.

Definizione — Insieme

Un insieme è una collezione di oggetti, detti elementi, ben definiti e distinti. Si indica con lettere maiuscole ($A, B, C,\ldots$).

Ogni insieme si rappresenta con una regione del piano racchiusa in un cerchio; il rettangolo che contiene tutto è l’insieme universo $U$.

Tre insiemi $A$, $B$, $C$ dentro l’universo $U$: le sovrapposizioni mostrano gli elementi condivisi.

Storia — I diagrammi di Venn

Il logico inglese John Venn introdusse questi diagrammi nel 1880, nell’articolo On the Diagrammatic and Mechanical Representation of Propositions and Reasonings, per rappresentare le proposizioni della logica. Perfezionò idee precedenti di Eulero, i cui “cerchi di Eulero” mostravano le relazioni tra classi ma non tutte le loro possibili sovrapposizioni. La forza dei diagrammi di Venn sta nel disegnare tutte le regioni logicamente possibili, colorando poi quelle effettivamente occupate (Boyer; Katz).

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Diagramma di venn · Insieme
Persone: Leonhard Euler (Eulero) · John Venn

Set theory is the language in which all of mathematics is formalised. Venn diagrams are the most intuitive way to visualise its objects and operations.

Definition — Set

A set is a collection of objects, called elements, that are well defined and distinct. It is denoted by capital letters ($A, B, C,\ldots$).

Every set is represented by a region of the plane enclosed in a circle; the rectangle containing everything is the universal set $U$.

Three sets $A$, $B$, $C$ inside the universe $U$: the overlaps show the shared elements.

History — Venn diagrams

The English logician John Venn introduced these diagrams in 1880, in the paper On the Diagrammatic and Mechanical Representation of Propositions and Reasonings, to represent the propositions of logic. He refined earlier ideas of Euler, whose “Euler circles” showed the relations between classes but not all of their possible overlaps. The strength of Venn diagrams lies in drawing every logically possible region and then shading only those that are actually occupied (Boyer; Katz).

Links

Topics: Set theory
Concepts: Venn diagram · Set
People: John Venn

Tra due insiemi si definiscono quattro operazioni fondamentali, ciascuna illustrata dal relativo diagramma di Venn.

Proprietà — Le quattro operazioni

• Unione: $A\cup B = \{x : x\in A \;\text{oppure}\; x\in B\}$
• Intersezione: $A\cap B = \{x : x\in A \;\text{e}\; x\in B\}$
• Complementare: $\overline{A} = \{x\in U : x\notin A\}$
• Differenza: $A\setminus B = A\cap\overline{B}$

Da sinistra a destra: unione, intersezione, complementare di $A$ e differenza $A\setminus B$.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Complementare · Diagramma di venn · Differenza di insiemi · Intersezione · Unione

Between two sets four fundamental operations are defined, each illustrated by the corresponding Venn diagram.

Property — The four operations

• Union: $A\cup B = \{x : x\in A \;\text{oppure}\; x\in B\}$
• Intersection: $A\cap B = \{x : x\in A \;\text{e}\; x\in B\}$
• Complement: $\overline{A} = \{x\in U : x\notin A\}$
• Difference: $A\setminus B = A\cap\overline{B}$

From left to right: union, intersection, complement of $A$ and difference $A\setminus B$.

Links

Topics: Set theory
Concepts: Complement · Venn diagram · Difference of sets · Intersection · Union

Le leggi di De Morgan mostrano come il complementare “scambia” unione e intersezione. Sono utilissime per semplificare condizioni logiche complesse.

Proprietà — Leggi di De Morgan

Il complementare di un’unione è l’intersezione dei complementari, e viceversa: $\overline{A\cup B} = \overline{A}\cap\overline{B}, \qquad \overline{A\cap B} = \overline{A}\cup\overline{B}.$

La stessa regione (in viola) si ottiene sia come $\overline{A\cup B}$ sia come $\overline{A}\cap\overline{B}$.

Esempio — Caffè nero decaffeinato

“Prendo un caffè nero decaffeinato.” Poniamo $A$ = al latte, $B$ = con caffeina. La frase corrisponde a $\overline{A}\cap\overline{B}$.

La sua negazione (“non prendo un caffè nero decaffeinato”) è, per De Morgan, $\overline{\overline{A}\cap\overline{B}} = A\cup B:$ “prendo un macchiato oppure con caffeina (o entrambi)”.

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Complementare · Intersezione · Leggi di de morgan · Unione
Competenze: Usare formule
Persone: Augustus De Morgan

De Morgan’s laws show how the complement “swaps” union and intersection. They are extremely useful for simplifying complex logical conditions.

Property — De Morgan's laws

The complement of a union is the intersection of the complements, and vice versa: $\overline{A\cup B} = \overline{A}\cap\overline{B}, \qquad \overline{A\cap B} = \overline{A}\cup\overline{B}.$

The same region (in purple) is obtained both as $\overline{A\cup B}$ and as $\overline{A}\cap\overline{B}$.

Example — Decaffeinated black coffee

“I have a decaffeinated black coffee.” Let $A$ = with milk, $B$ = with caffeine. The phrase corresponds to $\overline{A}\cap\overline{B}$.

Its negation (“I do not have a decaffeinated black coffee”) is, by De Morgan, $\overline{\overline{A}\cap\overline{B}} = A\cup B:$ “I have a macchiato or with caffeine (or both)”.

Links

Topics: Set theory
Concepts: Complement · Intersection · De Morgan’s laws · Union
Skills: Using formulae
People: Augustus De Morgan

La differenza simmetrica contiene gli elementi che appartengono a uno solo dei due insiemi, escludendo quelli in comune. È l‘“aut” logico: “o l’uno o l’altro, ma non entrambi”.

Definizione — Differenza simmetrica

La differenza simmetrica di $A$ e $B$ è: $A\mathbin{\triangle} B = (A\cup B)\setminus(A\cap B) = (A\setminus B)\cup(B\setminus A).$ Contiene gli elementi che appartengono a uno solo dei due insiemi.

La differenza simmetrica $A\triangle B$: i due “spicchi” esterni, senza la zona comune.

Osservazione — OR esclusivo

Nella logica:

• $\cup$ corrisponde al vel (OR inclusivo, “o… o… o entrambi”).
• $\triangle$ corrisponde all’aut (OR esclusivo, “o… o… ma non entrambi”).

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Diagramma di venn · Differenza simmetrica · Disgiunzione esclusiva

The symmetric difference contains the elements that belong to only one of the two sets, excluding those in common. It is the logical “aut”: “either one or the other, but not both”.

Definition — Symmetric difference

The symmetric difference of $A$ and $B$ is: $A\mathbin{\triangle} B = (A\cup B)\setminus(A\cap B) = (A\setminus B)\cup(B\setminus A).$ It contains the elements that belong to only one of the two sets.

The symmetric difference $A\triangle B$: the two outer “slices”, without the common region.

Remark — Exclusive OR

In logic:

• $\cup$ corresponds to the vel (inclusive OR, “either… or… or both”).
• $\triangle$ corresponds to the aut (exclusive OR, “either… or… but not both”).

Links

Topics: Set theory
Concepts: Venn diagram · Symmetric difference · Exclusive disjunction

La teoria degli insiemi come la usiamo oggi nasce tra il 1874 e il 1897 dal lavoro di Georg Cantor. La sua idea rivoluzionaria fu trattare l’infinito attuale — un insieme infinito considerato come un tutto già completo — invece dell’infinito soltanto potenziale (un processo che non finisce mai) che la matematica aveva usato fin dai tempi di Aristotele.

Confrontare gli infiniti

Cantor propose un criterio semplicissimo per dire quando due insiemi hanno “la stessa quantità” di elementi: esiste una corrispondenza biunivoca tra di essi. Con questo metro scoprì fatti sorprendenti. I numeri naturali $\mathbb{N}$, gli interi $\mathbb{Z}$ e persino i razionali $\mathbb{Q}$ hanno tutti la stessa cardinalità: si dicono numerabili. Ma i numeri reali $\mathbb{R}$ non lo sono. Con il celebre argomento diagonale (1891) Cantor dimostrò che nessuna lista $x_1, x_2, x_3, \ldots$ può contenere tutti i reali dell’intervallo $[0,1]$: costruendo un numero che differisce dall’$n$-esimo nella $n$-esima cifra decimale, si ottiene sempre un reale mancante dalla lista. Esistono dunque infiniti di grandezza diversa, che Cantor indicò con i numeri aleph: $\aleph_0$ per il numerabile, una cardinalità maggiore per il continuo (Boyer; Dunham).

Dedekind e la definizione di insieme infinito

Amico e corrispondente di Cantor, Richard Dedekind diede nel 1888 una definizione elegante e paradossale: un insieme è infinito se può essere messo in corrispondenza biunivoca con una sua parte propria. Ad esempio $n \mapsto 2n$ mette $\mathbb{N}$ in biiezione con i soli numeri pari, che sono “la metà” ma altrettanto numerosi — proprio la stranezza che Galileo aveva già notato. Dedekind usò inoltre le sue sezioni per costruire rigorosamente i numeri reali a partire dai razionali (Katz; Stillwell).

I paradossi e la crisi dei fondamenti

Questa libertà ebbe un prezzo. Nel 1901 Bertrand Russell scoprì un paradosso che scuote la teoria “ingenua”: si consideri l’insieme $R$ di tutti gli insiemi che non appartengono a se stessi. Se $R$ appartiene a se stesso, allora per definizione non deve appartenervi; se non vi appartiene, allora deve appartenervi. Una contraddizione insanabile, resa popolare dall’immagine del barbiere che rade tutti e soli quelli che non si radono da sé. La risposta della matematica non fu abbandonare gli insiemi, ma fondarli su assiomi prudenti (la teoria di Zermelo–Fraenkel). David Hilbert difese l’eredità di Cantor con parole rimaste famose: «Nessuno potrà scacciarci dal paradiso che Cantor ha creato per noi» (Boyer; Dunham).

Video consigliati

• How To Count Past Infinity — Vsauce

Collegamenti

Argomenti: Teoria degli insiemi
Concetti: Cardinalita · Infinito · Insieme
Persone: Bertrand Russell · Georg Cantor · Richard Dedekind

Set theory as we use it today was born between 1874 and 1897 from the work of Georg Cantor. His revolutionary idea was to treat the actual infinite — an infinite set regarded as a whole, already complete — rather than the merely potential infinite (a process that never ends) that mathematics had used ever since Aristotle.

Comparing infinities

Cantor proposed a very simple criterion for saying when two sets have “the same amount” of elements: there exists a one-to-one correspondence between them. With this yardstick he discovered surprising facts. The natural numbers $\mathbb{N}$, the integers $\mathbb{Z}$ and even the rationals $\mathbb{Q}$ all have the same cardinality: they are said to be countable. But the real numbers $\mathbb{R}$ are not. With his celebrated diagonal argument (1891) Cantor proved that no list $x_1, x_2, x_3, \ldots$ can contain all the reals of the interval $[0,1]$: by building a number that differs from the $n$-th one in its $n$-th decimal digit, one always obtains a real missing from the list. There are therefore infinities of different sizes, which Cantor denoted with the aleph numbers: $\aleph_0$ for the countable, a greater cardinality for the continuum (Boyer; Dunham).

Dedekind and the definition of an infinite set

A friend and correspondent of Cantor, Richard Dedekind gave in 1888 an elegant, paradoxical definition: a set is infinite if it can be put into one-to-one correspondence with a proper part of itself. For instance $n \mapsto 2n$ places $\mathbb{N}$ in bijection with the even numbers alone, which are “half” of them yet just as numerous — precisely the oddity that Galileo had already noticed. Dedekind also used his cuts to construct the real numbers rigorously starting from the rationals (Katz; Stillwell).

The paradoxes and the crisis of foundations

This freedom had a price. In 1901 Bertrand Russell discovered a paradox that shakes the “naïve” theory: consider the set $R$ of all sets that do not belong to themselves. If $R$ belongs to itself, then by definition it must not; if it does not belong to itself, then it must. An irreparable contradiction, made popular by the image of the barber who shaves all and only those who do not shave themselves. Mathematics’ answer was not to abandon sets but to found them on cautious axioms (Zermelo–Fraenkel theory). David Hilbert defended Cantor’s legacy with words that have remained famous: “No one shall drive us from the paradise which Cantor created for us” (Boyer; Dunham).

Recommended videos

• How To Count Past Infinity — Vsauce

Links

Topics: Set theory Concepts: Set · Cardinality · Infinity People: Georg Cantor · Richard Dedekind · Bertrand Russell