Es kommt ein bisschen darauf an wie ihr Gleichmächtigkeit definiert habt. Ich kenne es so, dass zwei Mengen gleichmächtig sind, wenn es eine Bijektion zu \(\mathbb{N}\) gibt. \(\mathbb{N}\) ist bekanntlich abzählbar. Wenn \(\mathcal{P} (\mathbb{N})\) überabzählbar sein soll, dann können die beiden nicht gleichmächtig sein. Also kann es also keine Bijektion zu \(\mathbb{N}\) geben.

Dein \(A_n\) beschreibt eine Teilmenge von \(\mathbb{N}\). Wir nehme eine eindeutige Abbildung \(\varphi:\mathbb{N} \longrightarrow \mathcal{P} (\mathbb{N})\). Einem Element \(n\in \mathbb{N}\) wird also auf \(\varphi(n)=A_n\in \mathcal{P} (\mathbb{N})\) als eine Teilmenge von \(\mathbb{N}\) abgebildet. Deine Menge \(A=\{n\in \mathbb{N} \mid n\notin \varphi(n)=A_n\}\). Die Menge \(A\) besteht also aus allen Elementen \(n\in \mathbb{N}\), für die \(n\) selbst nicht zur Menge \(\varphi(n)=A_n\) gehört. 

Der Gedanke ist nun, dass die eine Bildmenge finden möchtest auf die nicht abgebildet wird, damit es also keine Bijektion geben kann und somit \(\mathbb{N}\) und \(\mathcal{P} (\mathbb{N})\) auch nicht gleichmächtig sein können.

Jetzt kommt der Widerspruchsgedanke. Angenommen deine Abbildung \(\varphi\) ist bijektiv. Dann gibt es also ein \(m\in \mathbb{N}\), so dass \(\varphi(m)=A\) tatsächlich erfüllt ist. Dann gibt es zwei Möglichkeiten:

(1) \(m\in A\). Dann gilt \(m\notin \varphi(m)=A\). Dies führt zum Widerspruch.

(2) \(m\notin A\). Dann gilt \(y\notin \varphi(m)\), wodurch \(y\in A\) erfüllt ist. Dies führt ebenso zum Widerspruch.

D.h., es gilt Bilder von \(\varphi\), die nicht erreicht werden. Also kann \(\varphi\) nicht surjektiv und damit auch nicht bijektiv sein. Somit sind \(\mathbb{N}\) und \(\mathcal{P} (\mathbb{N})\) nicht gleichmächtig. Da \(\mathbb{N}\) abzählbar ist, ist folglich \(\mathcal{P} (\mathbb{N})\) überabzählbar.

Ich hoffe durch die Bijektion wird es deutlicher.