What is a proof?

I was at lunch with some colleagues some days ago, and we started discussing about maths. Predictably, the conversation turned to the quite specific concept of proofs used by mathematicians. I had some insights, on the reasons for so many misunderstandings between mathematicians and others. I think many of them arise from a different understanding of the word "proof"

I want to exemplify on the classical result about the cardinality of the power set, so let us dive into math.

First, the power set ${P}(A)$ of a given finite set $A$ is the the enumeration of all the possible subsets of $A$.

If $A$ is, say, the set of $\{me, you\}$ the power set will contain:

1. the empty subset $\emptyset$
2. the subset containing only $me$
3. the subset containing only $you$
4. the subset containing both $me$ and $you$

It is a legitimate and somewhat interesting question: how many elements does the power set $A$ has, if $A$ has $n$ elements? Such counting questions are very common in math and constitute the basis of combinatorics. Let us look how we can come to a solution of the problem and, even cooler, a formal proof that the solution is correct.

Examples
The first step is, more often than not, to list some examples. For instance, if the set $A$ only contains one elements, the power set will contain:

1. the empty set
2. the subset consisting of that element

We now have an example for a 1 element set (2 subsets) and for a 2 element set (4 subsets). What about a 3 element set?

By the way, we have implicitly agreed on the working assumption that the cardinality of the power set only the depends on the cardinality of the original set. This is ok, if this is wrong, we will change it. (But yes, it will turn out that this is right).

Back to our example of our 3 element set $\{me, you, the\ others\}$. We have all which we have considered before:

1. the empty subset $\emptyset$
2. the subset containing only $me$
3. the subset containing only $you$
4. the subset containing both $me$ and $you$

and in addition, all of those plus $the\ others$

1. the subset containing only $the\ others$
2. the subset containing only $me, the\ others$
3. the subset containing only $you, the\ others$
4. the subset containing both $me, you$ and $the\ othes$

This totals to 8 elements. Let us summarize: for 1 element, 2 subsets, for 2 elements, 4 subsets and for 3 elements, 8 subsets. This looks suspiciously like $2^n$, with $n$ the cardinality of $A$. This will be our working hypothesis.

Insight
Having formulated our working hypothesis, we should ask ourself whether this can be possibly right. Upon thinking we recognize this: for every subset in our collection, every single element of $A$ can be present or not. Since we have $n$ elements, every element, we must make $n$ binary decisions of whether to include that element in the subset or not. This gives $2 \times 2 \times ... \times 2 $ possibilities. Yes! This is $2^n$. This is our insight, and typically it is enough if you are a physicists.
But it is not a proof. It is not a proof, as to be a proof it must be formalized in a standard way using the laws of logics. This is important, since this gives all mathematicians the chance of recognizing a proof as such.

The proof
Let us prove this, then. The standard way to prove stuff about natural numbers is the method of induction, which we will follow step by step. First we formulate our theorem in details.

If $A$ is a finite set with $n$ elements, then its power set $P(A)$ has $2^n$ elements.

We prove that this is true for 0. If the set $A$ is empty, then it has 0 elements, and one single subset, which is the empty set. $1  = 2^0$. Check.
To avoid being caught in misunderstandings and quarrels about 0 and empty sets, we will prove it also for a single element. This is not required, but we do it anyway. If $A$ has a single element, its subsets are the empty set and $A$ itself. $2 = 2^1$. Check.

Now let us go to the induction step. Let us assume, we known that if $A$ has $n$ elements, then we have $2^n$ distinct subsets of $A$. Let us reason about a hypothetical set $B$ with $n+1$ elements and let us pick one arbitrary element, which we will call $b$ out of $B$. Let us remove $b$ from $B$ and obtain $B'$ a set of obviously $n$ elements. We know from the induction assumption that $B'$ has $n$ elements and thus $2^n$ subsets, constituting the set $P(B')$. Let us now consider the set $X = \{S \cup \{b\} | S \in P(B')\}$.

Interestingly, $X$ and $P(B')$ are disjoint, as every set in $X$ contains $b$ which per construction absent from every set in $P(B')$. So, the cardinality of $X \cup P(B')$ will be the cardinality of $X$ plus the cardinality of $P(B')$.

It remains to show that

1. the cardinality of $X$ is $2^n$
2. $X \cup P(B') = P(B)$

For 1. we should give a bijective function for $P(B')$ to $X$, which turns out to be exactly the prescription with which we constructed $X$ in the first place. This kind of clerical tasks is typically left to the reader as an exercise, and we will comply with the mathematical tradition.

For 2. we notice that if $Y$ is a subset of $B$ it either contains $b$ or not. If not, it is in $P(B')$ and thus in  $X \cup P(B')$. If yes, it equals to $Y \setminus b \cup \{b\}$. Now, $Y \setminus b$ only consists of elements of $B$ apart of $b$, so it is in $P(B')$ and when we unit sets in $P(B')$ with $\{b\}$ we get by construction sets in $X$, so $Y$ is a set in $X$ and thus in $X \cup P(B')$. We just proved that $P(B) \subset X \cup P(B')$. The converse direction is left to the reader an exercise, as it follows the same principles. We also do not want to spoil him of the incredible feeling of finishing a proof.

Conclusion
What I hope I could convey is that sheer amount of work needed to go from an insight, giving us just a working hypothesis and some ideas, to a complete mathematical proof. The real question could be here: why bother? Indeed our insight was right, and the loosely described proof ($n$ binary decisions giving $2^n$ different possibilities) is perfectly fine.

I think the problem is often that this kind of insight often fails with more complex arguments, even in seemingly intuitive cases.

Formalized, standardized proofs in maths are a powerful method to fight the natural tendency of the human mind to fall victim of cognitive illusions and are thus one of the milestones of the human thinking!

Infinito

Nessuno potrà cacciarci dal Paradiso che Cantor ha creato

David Hilbert

Oggi, mentre ero ad un seminario, l'oratore ha affermato una cosa interessante. Cioè voleva convincerci del fatto che uno spazio di parametri fosse "quasi infinite dimensional". Voleva dire, in realtà che vi erano molti parametri: circa 1000000.

Così, mentre ero sotto la doccia, mi sono ricordato della spiegazione che mi diede una volta mio padre dell'infinito: un numero così grande che è più grande di qualsiasi altro numero che tu possa immaginare.

Certo è una buona spiegazione, ma poi porta a errori mentali come affermare che R^10000000 sia quasi infinito dimensionale. Questo perchè, dal punto di vista di noi uomini, prendere un numero più grande ci "avvicina" in qualche maniera all'infinito. Quindi, se prendo un numero molto grande, allora sarò molto vicino all'infinito.

Niente di più falso, per il semplice motivo che l'infinito non è un numero! Mettetevi infatti nei panni dell'infinito e considerate il numero 1. Allora 1/infinito è sicuramente più piccolo di 1/10, dato che infinito è maggiore di 10. Ma anche di 1/100. Ma anche di 1/1000 e così via. Adesso se considero il numero 11111111111111, che di certo è molto più grande di 1, ragionando nella stessa maniera, scopro che 11111111111111/infinito è minore di 1/10, di 1/100, di 1/1000 etc... Cioè, per l'infinito tutti gli altri numeri valgono 0, non conta quanto siano grandi.

Cos'è l'infinito, allora? Per ottenere la risposta, dobbiamo capire cos'è la grandezza di un insieme. In matematica si dice che due insiemi A e B sono ugualmente grandi o, più precisamente, equipotenti, se esiste una funzione f da A a B che sia bigettiva. Ad esempio, l'insieme dei giorni di una settimana e dei re di Roma sono equipotenti. Per vederlo, si consideri la funzione f che associa al lunedì Romolo, al martedì Numa Pompilio, al mercoledì Tullio Ostilio etc... questa funzione è chiaramente ingettiva, perchè si arriva ad ogni re da un solo giorno ed è anche surgettiva perchè si arriva a tutti i re.

In una visione ingenua della matematica, il numero 7 si può allora definire come la proprietà di essere equipotente all'insieme dei re di Roma.

Ora siamo pronti per dare una definizione. Come nel caso del numero 7, non diremo cos'è l'infinito, ma diremo come riconoscere un insieme che ha infiniti elementi.

Definizione
Un insieme è infinito se possiede un sottoinsieme proprio equipotente a se stesso.

Esempio
Ci sono infiniti numeri naturali. Per vederlo, si prenda la funzione che ad ogni naturale associa il proprio quadrato. Questa funzione è bigettiva dall'insieme dei naturali all'insieme dei quadrati perfetti. Dato che quest'ultimo è un sottoinsieme proprio dei numeri naturali, abbiamo provato l'asserto.

Eppoi, questa maniera di voler arrivare all'infinito per addizione mi sembra come voler arrivare al cielo costruendo una torre. Di Babele, è ovvio.

sugli isomorfismi nella saggezza popolare

il tempo é denaro

proverbio

qualche tempo fa ero a dresda, e discutevo con una dottoranda in economia della giustezza dell'ipotesi implicita delle scienze economiche, riassumbile in

a od ogni oggetto, astratto o concreto, é attribuibile un valore monetario.

questo ansatz é geniale e diabolico: é un voler ridurre il mondo, un vettore nello spazio di banach di dimensione mostruosamente infinita contenente tutte le possibilitá del reale, ad una sua rappresentazione nel campo dei numeri reali. in altre parole, questi economisti affermano di poter capire come va il mondo guardandone il suo duale.

ancora peggio! essi considerano una sola speciale forma lineare, ovvero quella che associa ad ogni oggetto, che mi permetto di identificare con un sottoinsieme compatto di questo mostruoso spazio di banach, il suo valore in euro.

anyway, il proverbio popolare ci azzecca in pieno: il tempo é anche solitamente rappresentato tramite il campo dei numeri reali, per cui é proprio vero:

il tempo é denaro, a meno di un isomorfismo.

ps: se qualcuno si lamenta, affermando che le forme lineari é meglio pensarle aventi valori nel campo dei numeri complessi, gli ricorderó che la teoria dei semigruppi lineari ci insegna che anche il campo naturale del tempo é quello dei numeri complessi.

firing rate e dimensioni finite

ieri ho pianificato con h.m. un articolo che dobbiamo scrivere. ci domandavamo perche´ e´ male occuparsi di modelli neurali basati sul firing rate, o a dimensione finita. h.m. e io siamo in due campi diversi delle neuroscienze, ma stranamente eravamo d´accordo sulla malvagita´ intrinseca di tali modelli. stamattina sono anche in grado di precisarlo: perche´ in questa maniera si pre-suppone che la codifica neurale sia il firing rate o il potenziale somatico, e´ non c´e´ nessuna evidenza per una simile assunzione.