» Home Page
Question Bank: Domande a Scelta Multipla
--» Geometria I: Alcuni esperimenti di domande sulla cardinalità

Per risolvere le seguenti domande, a volte potrebbe servire conoscere ed utilizzare il Teorema di Cantor o il Teorema di Cantor-Bernstein-Schröder. Può essere utile anche sapere come risolvere il primo problema di Hilbert o qualche proposizione ad esso collegata.

  1. Esiste una corrispondenza biunivoca $f\colon \mathbb{N} \to \mathbb{Q}$, cioè i numeri interi e i numeri razionali hanno la stessa cardinalità (l'insieme dei numeri razionali è numerabile).
    1. Vero+

      SÌ!

    2. Falso+

      NO!
      I razionali non nulli si scrivono in modo unico come $\frac{p}{q}$ con $q\gt 0$, $p$ e $q$ senza divisori comuni. Sia $U_n$ l'insieme di razionali la cui forma ridotta è $\frac{p}{q}$ con $q= n$. Allora $\mathbb{Q}$ si scrive come unione disgiunta di insiemi finiti \[ \mathbb{Q} = \{0\} \cup U_1 \cup U_2 \cup \ldots \cup U_n \cup \ldots \] Allora si può definire ricorsivamente una corrispondenza biunivoca $f\colon \mathbb{N} \to \mathbb{Q}$...

  2. Esiste una corrispondenza biunivoca $f\colon \mathbb{N} \to \mathbb{N}\times \mathbb{N}$. Vero o falso?
    1. Vero+

      SÌ!

    2. Falso+

      NO!
      Basta usare un procedimento analogo a quello della domanda precedente.

  3. Esiste sempre una corrispondenza biunivoca tra l'insieme delle parti $2^X$ di un insieme $X$ e l'insieme di tutte le funzioni $f\colon X \to \{0,1\}$.
    1. Vero+

      SÌ!

    2. Falso+

      NO!
      Per ogni sottoinsieme $A\subset X$, la funzione caratteristica è definita da \[ \chi_A(x) = \begin{cases} 1 & \text{ se } x\in A \\ 0 & \text{ se } x\not\in A. \end{cases} \] Questo ci dà una mappa che associa ad $A\in 2^X$ la funzione $\chi_A$. Questa è una corrispondenza biunivoca.

  4. C'è una corrispondenza biunivoca $(0,1) \approx \mathbb{R}$.
    1. Vero+

      SÌ!

    2. Falso+

      NO!
      Si ha $(-\frac{\pi}{2},\frac{\pi}{2}) \approx (0,1)$, e $(-\frac{\pi}{2},\frac{\pi}{2}) \approx \mathbb{R}$ con la funzione tangente.

  5. C'è una corrispondenza biunivoca $[0,1] \approx [0,1)$.
    1. Vero+

      SÌ!

    2. Falso+

      NO!
      Consideriamo la funzione $f\colon [0,1{]} \to [0,1)$ definita da \[ f(x) = \begin{cases} \frac{1}{2^{n+1}} & \text{ se $x=\frac{1}{2^n}$ con $0\leq n\in \mathbb{N}$} \\ x & \text{ altrimenti }. \end{cases} \] Si ha $f(1) = \frac{1}{2}$, $f(\frac{1}{2}) = \frac{1}{4}$... e $f(x)=x$ altrimenti. Quindi $0\leq f(x)\lt 1$ ed è ben definita. È anche biunivoca, dato che se $y=\frac{1}{2^n}\in [0,1)$, allora $n\gt 0$ e quindi esiste $x=\frac{1}{2^{n-1}}$ tale che $f(x) = y$.

  6. Esiste una corrispondenza biunivoca $(0,1) \approx [0,1)$.
    1. Vero+

      SÌ!

    2. Falso+

      NO!
      Sia $f\colon [0,1{]} \to [0,1)$ la funzione biunivoca dell'esercizio precedente. La sua restrizione a $[0,1)$ è una corrisondenza biunivoca $[0,1) \approx (0,1)$.

  7. Esiste una corrispondenza biunivoca $f\colon 2^\mathbb{N} \to \mathbb{R}$, e quindi l'insieme delle parti di $\mathbb{N}$ e $\mathbb{R}$ hanno la stessa cardinalità.
    1. Vero+

      SÌ!

    2. Falso+

      NO!
      L'insieme delle parti $2^\mathbb{N}$, per il punto precedente, è in corrispondenza biunivoca con l'insieme di tutte le funzioni $\mathbb{N}\to \{0,1\}$, cioè le successioni $a_n$ a valori in $\{0,1\}$. Consideriamo i punti dell'intervallo $[0,1{)}\subset \mathbb{R}$ con cifre decimali, nell'espansione in base $3$, tutte diverse da $2$. Questo è un insieme che è in corrispondenza biunivoca con $2^\mathbb{N}$, e quindi $|2^\mathbb{N}| \lt |[0,1{)}|$. D'altra parte ogni $x\in[0,1{)}$ ha una unica espansione (senza che sia definitivamente $1$) in cifre binarie, e quindi $|[0,1)| \lt |2^\mathbb{N}|$, da cui per il teorema di Cantor-Schröder-Bernstein http://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80%93Schroeder_theorem si ha che $[0,1) \approx 2^{\mathbb{N}}$. Non rimane che usare il medesimo teorema e trovare una funzione iniettiva $\mathbb{R} \to [0,1)$.

  8. Le cardinalità di $\mathbb{R}$ e di $\mathbb{N} \times \mathbb{R}$ coincidono.
    1. Vero+

      SÌ!

    2. Falso+

      NO!
      È chiaro che $\mathbb{R}\lt \mathbb{N} \times \mathbb{R}$. Inoltre, dato che $\mathbb{R} \approx (0,1)\subset \mathbb{R}$, la funzione $\mathbb{N}\times (0,1) \to \mathbb{R}$ definita da \[ (n,t) \ni \mathbb{N} \times (0,1) \mapsto n+t\in \mathbb{R} \] è iniettiva, e quindi $\mathbb{N} \times \mathbb{R} \lt \mathbb{R}$. Usiamo il teorema di Cantor-Bernstein-Schröder http://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80%93Schroeder_theorem per dedurre che \[ \mathbb{R} \lt \mathbb{N} \times \mathbb{R} \lt \mathbb{R} \Longrightarrow \mathbb{R} \approx \mathbb{N} \times\mathbb{R}. \] Equivalentemente, in modo diretto, possiamo osservare che $\mathbb{R} \approx [0,1) \times \mathbb{N}$, e che $[0,1) \approx \mathbb{R}$.

  9. Se $A,B,C$ sono tre insiemi, allora l'insieme delle funzioni da $A$ a $C^B$ (cioè all'insieme delle funzioni da $B$ a $C$) è in corrispondenza biunivoca con l'insieme delle funzioni dal prodotto cartesiano $A\times B$ a $C$.
    1. Vero+

      SÌ!

    2. Falso+

      NO!
      Basta associare ad ogni funzione $f\colon A\times B \to C$ la funzione $\hat f \colon A \to C^B$ definita da $\hat f(a) (b) = f(a,b)$.

  10. L'insieme di tutte le funzioni $f\colon \mathbb{R} \to \{0,1\}$ ha la stessa cardinalità dell'insieme di tutte le funzioni $f\colon\mathbb{R} \to \mathbb{R}$ (che è di più della cardinalità di $\mathbb{R}$).
    1. Vero+

      SÌ!

    2. Falso+

      NO!
      Scriviamo $\mathbb{R}^\mathbb{R}$ come l'insieme delle funzioni $\mathbb{R}\to\mathbb{R}$, $2^X$ come l'insieme delle funzioni $X\to \{0,1\}$. Dato che $\mathbb{R}\approx 2^\mathbb{N}$ e $\mathbb{N}\times \mathbb{R} \approx \mathbb{R}$, per i risultati precedenti si ha \[ \mathbb{R}^\mathbb{R} \approx (2^\mathbb{N})^\mathbb{R} \approx 2^{(\mathbb{N} \times \mathbb{R})} \approx 2^ \mathbb{R}. \]

  11. L'insieme $X$ di tutte le funzioni continue $f\colon \mathbb{R} \to \mathbb{R}$ ha la stessa cardinalità di $\mathbb{R}$.
    1. Vero+

      SÌ!

    2. Falso+

      NO!
      Per restrizione, ad ogni funzione continua $f\colon\mathbb{R} \to \mathbb{R}$ possiamo associare una funzione continua $f\colon \mathbb{Q} \to \mathbb{R}$. Due funzioni continue con la stessa restrizione a $\mathbb{Q}$ coincidono, e quindi l'applicazione è una applicazione iniettiva dall'insieme di tutte le funzioni continue $\mathbb{R}\to \mathbb{R}$ all'insieme di tutte le funzioni continue $\mathbb{Q}\to \mathbb{R}$, che è un sottoinsieme di $\mathbb{R}^\mathbb{Q}$. Ora, si ha (si vedano i punti precedenti) \[ \mathbb{R}^\mathbb{Q} \approx \mathbb{R}^\mathbb{N} \approx (2^\mathbb{N})^\mathbb{N} \approx 2^{\mathbb{N} \times \mathbb{N}} \approx 2^\mathbb{N} \approx \mathbb{R}. \] da cui \[ X \lt \mathbb{R}. \] Ora, ad ogni $x\in \mathbb{R}$ possiamo associare la funzione costante $c_x$, per cui $\mathbb{R}\lt X$, e ancora per il teorema di Cantor-Bernstein-Schröder deduciamo che $X\approx \mathbb{R}$.

  12. L'insieme di tutte le funzioni $f\colon \mathbb{R} \to \{0,1\}$ ha la stessa cardinalità di $\mathbb{R}$.
    1. Vero+

      NO!
      Si può usare il Teorema di Cantor: la cardinalità dell'insieme delle parti di $X$ è sempre strettamente maggiore della cardinalità di $X$. http://en.wikipedia.org/wiki/Cantor%27s_theorem

    2. Falso+

      SÌ!

  13. Esiste una corrispondenza biunivoca $f\colon \mathbb{N} \to \mathbb{R}$, cioè l'insieme dei numeri reali è numerabile.
    1. Vero+

      NO!
      $\mathbb{R} \approx 2^\mathbb{N}$, e per il Teorema di Cantor non può essere in corrispondenza biunivoca con $\mathbb{N}$

    2. Falso+

      SÌ!

  14. Non può mai esistere una corrispondenza biunivoca tra un insieme $X$ e l'insieme delle sue parti $2^X$.
    1. Vero+

      SÌ!

    2. Falso+

      NO!
      Si tratta del Teorema di Cantor: la cardinalità dell'insieme delle parti di $X$ è sempre strettamente maggiore della cardinalità di $X$. http://en.wikipedia.org/wiki/Cantor%27s_theorem

  15. Se $X$ è un insieme infinito di numeri reali la cui cardinalità è diversa da quella di $\mathbb{R}$, cioè per cui non esiste una funzione iniettiva $f\colon \mathbb{R} \to X$, allora è vero o falso che $X$ deve essere numerabile (cioè esiste una corrispondenza biunivoca $X\approx \mathbb{N}$)?
    1. Vero+

      NO!
      Purtroppo si tratta dell'Ipotesi del Continuo (il primo dei 23 problemi di Hilbert), che non può essere dimostrata né vera né falsa, dai comuni assiomi della teoria degli insiemi (ZF) (http://en.wikipedia.org/wiki/Continuum_hypothesis).

    2. Falso+

      NO!
      Purtroppo si tratta dell'Ipotesi del Continuo (il primo dei 23 problemi di Hilbert), che non può essere dimostrata né vera né falsa, dai comuni assiomi della teoria degli insiemi (ZF) (http://en.wikipedia.org/wiki/Continuum_hypothesis).

  16. Sia $A$ l'insieme di tutte le funzioni che mandano i numeri reali dell'intervallo $[0,1]\subset \mathbb{R}$ nell'insieme di tutti i sottoinsiemi numerabili di $[0,1]$. È vero o falso che per ogni $f\in A$, esistono $x,y\in [0,1]$ tali che \[ x\not\in f(y),\ y \not\in f(x) ? \]
    1. Vero+

      NO!
      Purtroppo si tratta dell'Assioma di simmetria di Freiling, che non può essere dimostrato né falsificato, dai comuni assiomi della teoria degli insiemi (http://en.wikipedia.org/wiki/Freiling%27s_axiom_of_symmetry).

    2. Falso+

      NO!
      Purtroppo si tratta dell'Assioma di simmetria di Freiling, che non può essere dimostrato né falsificato, dai comuni assiomi della teoria degli insiemi (http://en.wikipedia.org/wiki/Freiling%27s_axiom_of_symmetry).