Induksi-epsilon

Dalam matematika, induksi-$\in$ (induksi-epsilon atau induksi-himpunan) merupakan sebuah ragam induksi transfinit.

Dianggap sebagai sebuah skema aksioma teori himpunan alternatif, ini disebut Aksioma (skema) induksi (himpunan)

Ini dapat digunakan dalam teori himpunan untuk membuktikan bahwa semua himpunan memenuhi sebuah sifat $P(x)$ yang diberikan. Ini merupakan sebuah kasus khusus mengenai induksi cukup beralasan.

Pernyataan

Ini menyatakan, untuk suatu sifat $P$, bahwa untuk setiap himpunan $x$, kebenaran $P(x)$ mengikuti dari kebenaran $P$ untuk semua unsur $x$, maka sifat $P$ ini berlaku untuk semua himpunan. Dalam simbol:

$\forall x.{\Big (}\left(\forall y\in x.\,P(y)\right)\rightarrow P(x){\Big )}\ \rightarrow \ \forall z\,P(z)$

Perhatikan bahwa untuk "kasus bawah" dimana $x$ melambangkan himpunan kosong, $\forall y\in x$. $P(y)$ adalah kebenaran hampa.

Perbandingan dengan induksi bilangan asli

Di atas dapat dibandingkan dengan induksi-$\omega$ atas bilangan asli $n\in \{0,1,2\dots \}$ untuk sifat-sifat bilangan $Q$. Ini dapat diungkapkan sebagai

${\Big (}Q(0)\land \forall n.(Q(n)\to Q(n+1)){\Big )}\ \to \ \forall m.\,Q(m)$

Memperkenalkan beberapa konvensi untuk karena pencerminan Induksi Himpunan, ini dapat diutlis sebagai

$\forall n.{\Big (}Q(n-1)\to Q(n){\Big )}\ \to \ \forall m.\,Q(m)$

dimana untuk "kasus bawah" $n=0$ kita ambil "$Q(-1)$" menjadi benar oleh definisi. Perhatikan bahwa induksi-himpunan dapat juga diperlakukan dalam sebuah cara yang memperlakukan kasus bawah dengan eksplisit.

Dengan tautologi klasik seperti $(A\to B)\iff (\neg A\lor B)$, prinsip induksi-$\omega$ di atas dapat diterjemahkan ke pernyataan berikut:

$\exists n.{\Big (}Q(n-1)\land \neg Q(n){\Big )}\ \lor \ \forall m.\,Q(m)$

Ini mengungkapkan bahwa, untuk suatu sifat $Q$, baik terdapat suatu bilangan (pertama) $n$ yang mana $Q$ tidak berlaku, meskipun $Q$ berlaku untuk kasus sebelumnya, atau - jika tidak ada seperti kasus palsu - $Q$ adalah benar untuk semua bilangan.

Demikian, dalam teori Zermelo–Fraenkel klasik, induksi-himpunan dapat diterjemahkan ke pernyataan berikut, menjelaskan bentuk apa mengenai contoh berlawanan mencegah sebuah sifat himpunan $P$ berlaku untuk semua himpunan:

$\exists x.{\Big (}\left(\forall y\in x.\,P(y)\right)\,\land \,\neg P(x){\Big )}\ \lor \ \forall z\,P(z)$

Ekspresi ini bahwa, untuk suatu sifat $P$, baik ada sebuah himpunan $x$ yang mana $P$ tidak berlaku sementara $P$ menjadi benar untuk semua unsur $x$, atau $P$ berlaku untuk semua himpunan.

Untuk suatu sifat, jika salah satu dapat membuktikan bahwa $\forall y\in x$. $P(y)$ menyiratkan $P(x)$, maka kasus palsu dikesampingkan dan rumusnya menyatakan bahwa $\forall z\,P(z)$ terpisah harus berlaku.

Kebebasan

Dalam konteks dari konstruksi Zermelo–Fraenkel teori himpunan konstruktif, mengutip Aksioma keteraturan akan menyiratkan kaidah menengah terkecuali dan juga induksi himpunan. Tapi kemudian hasil teorinya akan menjadi teori himpunan Zermelo–Fraenkel standar. Namun, sebaliknya, induksi himpunan menyiratkan baik bukan dari dua. Dengan kata lain, dengan sebuah kerangka logika konstruktif, induksi himpunan seperti yang dinyatakan di atas lebih lemah sempurna daripada keteraturan.

Lihat pula

• Induksi matematis
• Induksi transfinit
• Induksi beralasan
• Teori himpunan konstruktif
• Teori himpunan takberalasan