Paradoks Russell


Di sekolah, secara abstrak, kita biasanya mendefinisikan sebuah himpunan dengan cara menyatakan suatu properti P yang harus dipenuhi dan hanya dipenuhi oleh semua anggota himpunan tersebut; kita tulis himpunan tersebut dengan notasi

\{x | P(x)\}.

Contoh, misalkan A=\{x | (x \in \mathbb{N}) \text{ dan } (x>3)\} adalah suatu himpunan dengan resep yang jelas. Kita pun bisa memeriksa bahwa 5 merupakan anggota dari himpunan A, atau kita tulis 5 \in A. Kita juga bisa memeriksa bahwa 0 bukan anggota dari himpunan A, dan kita tulis 0 \notin A.

Sedikit logika dan refleksi

Ingat bahwa notasi a \in b berarti a merupakan anggota dari b; dan a \notin b berarti a bukan anggota dari b. Logika matematika menyatakan bahwa untuk sembarang objek a dan b, kita harus punyai a \in b atau a \notin b (sesuatu bernilai benar atau salah di matematika), dan tidak boleh keduanya sekaligus!

Intuisi kita mengatakan bahwa kita bisa membuat himpunan atau koleksi objek dengan “resep” P sesuka hati kita seperti di atas; kita definisikan saja himpunan apa dengan anggota-anggotanya seperti apa. Nanti, kalau kita dikasih suatu objek (apapun), kita bisa menentukan nantinya dengan mengecek resep P tadi apakah objek ini anggota himpunan kamu atau bukan. That’s all the essence of playing with sets in mathematics, right? (Bahkan, kalau kamu merupakan matematikawan, pasti kamu tahu seberapa pentingnya himpunan dalam hidupmu 😉 ).

The Paradox

Tahun 1901, filsuf dan matematikawan Bertrand Russell menemukan paradoks jika kita mengadopsi intuisi ini. Artinya, intuisi kita perlu diperbaiki. Berikut adalah permasalahan yang dia temukan.

Pandang himpunan

Y=\{x | x \notin x\}.

Dalam bahasa sehari-hari, Y merupakan himpunan semua objek (himpunan) x yang tidak mengandung dirinya sendiri.

Sekarang, pertanyaannya adalah apakah Y \in Y? Kita coba berandai-andai; kan hanya ada dua kemungkinan: Y \in Y atau Y \notin Y. Mana yang sebenarnya?

Andaikan yang pertama:  Y \in Y. Karena Y anggota dari Y, maka Y memenuhi resep keanggotaan Y itu sendiri; namun resep itu mengatakan bahwa Y \notin Y. Kontradiktif! Jadi, andaian ini tidak mungkin,

Oke, bagaimana kalau kita andaikan yang kedua: Y \notin Y. Oke, ternyata Y memenuhi resep keanggotaan himpunan Y yang kita definisikan tadi; jadi harusnya Y \in Y. Kontradiktif lagi! Jadi, andaian ini juga tidak mungkin.

Kita sudah menciptakan sesuatu yang bernama Y yang kita pikir merupakan himpunan, namun kita tidak bisa mengatakan apakah Y \in Y maupun Y \notin Y. Ini kan ngawur?

Jadi, objek apakah Y ini sebenarnya? Apakah dia pantas disebut sebuah himpunan? Atau bahkan, apakah dia pantas disebut sebagai objek di dunia matematika? Or maybe we should drop mathematical theory as it is mere bullshit? Mungkin himpunan-himpunan yang didefinisikan para pakar matematika itu semuanya kontradiktif dengan dirinya sendiri?

Lahirnya Set Theory

Paradoks Russell ini menjadi benih kelahiran bidang kajian yang sangat besar di bidang logika dan fondasi matematika yang disebut Teori Himpunan (terjemahan: Set Theory).

Teori himpunan adalah bidang kajian yang mencoba memberi aturan tentang apa yang merupakan himpunan dan bukan dan membangun (ulang) matematika dengan aturan-aturan tersebut. Dengan teori himpunan, kita bisa secara formal menceritakan konsep bilangan, konsep ketakhinggaan (infinity), dan melihat secara detail keanehan-keanehan yang terjadi di matematika.

Salah satu teori yang secara sosial diterima para pakar matematika sebagai fondasi matematika adalah teori ZFC (Zermelo-Fraenkel theory + Axiom of Choice). Bisa jadi satu buku sih kalau saya menulis tentang ZFC, tapi saya akan dengan senang hati menulis tulisan sedikit demi sedikit tentang teori ini di blog post selanjut-selanjutnya tentang dalam seri #logika. Ditunggu ya. 😉



Against eating only dead animals

I try to spare sometime to study human food to figure out what I should and should not eat and make conscious choice about it. Why? Because I think I am privileged enough to do so; I have more options than other people and hence I am responsible of making the best choice out of several options that I have.

So, I do not like the idea of killing animals. This is one of the reasons for having less meat consumption. There are of course other reasons for it such as CO2 emission for processing meat in large scale.

Anyway, I want to focus on not killing animals now. One way to get away from killing is to eat the dead one already. But I am pretty sure this is not really a good idea because otherwise this beautiful idea would have worked out. And I am happy enough with the answer from Simon Bridge in an online forum.

I copy his answer below.

Most of the animals we eat are dead at the time of eating/cooking. “Aged” meat can be dead for quite a while. The exceptions iirc are some seafood. Oysters are traditionally consumed alive while lobsters are traditionally killed by plunging into boiling water as the first stage in cooking. That sort of thing.

Your father is talking about finding an already-dead animal, taking it home and cooking it. The trouble with scavenged prey is that you don’t know the circumstances that it died in – when we kill an animal we have some (with modern farming: lots of) control over the condition of the animal when it is killed. We also have certain knowledge of what it died of. Imagine an animal dies from disease, or from poisoning – is it a good idea to eat it?

Similarly – what sort of organism has taken up in the carcass while it was lying there?

It is technically possible to overcome objections by being careful in selecting the found-meat, as well as preparing it. .e. maybe you saw the animal keel over right in front of you? However, the risks are higher.

As for this approach to obtaining meat as an alternative to killing, you should be able to follow why it is a bad idea institutionally to wait around for an animal to die by itself before processing it for food. i.e. it won’t be in the farmer’s interest to keep the animal in good health.

However, I understand that it is legal in some US States to eat roadkill. Presumably it is not legal to serve it in restaurants though.


It is interesting how there are some exceptions indeed such as seafood and roadkill. I will look for more info later when I have more time. Moreover, since it is difficult to institutionalize this idea, then if I want to survive with this way of obtaining meat, I need to resolve a lot of technical difficulties in recognizing edible dead meat in the wild.

The different forms of quantum computing skepticism

Windows On Theory

(see also pdf version)

Quantum computing is one of the most exciting developments of computer science in the last decades. But this concept is not without its critics, often known as “quantum computing skeptics” or “skeptics” for short. The debate on quantum computing can sometimes confuse the physical and mathematical aspects of this question, and so in this essay I try to clarify those. Following Impagliazzo’s classic essay, I will give names to scenarios or “potential worlds” in which certain physical or mathematical conditions apply.

Potential worlds

Superiorita is the world where it is feasible to build scalable quantum computers, and these computers have exponential advantage over classical computers. That is, in superiorita there is no fundamental physical roadblock to building large quantum computers, and hence the class BQP is a good model of computation that is physically realizable. More precisely, in superioriata the amount of resources (think…

View original post 2,547 more words

Non-deterministic version of accepting and deciding

{\bf NP} is the class of languages that can be decided in polynomial time by a non-deterministic Turing Machine. Now let {\bf NP}' be the class of languages that can be recognized in polynomial time by a non-deterministic Turing machine.

We can ask the same question: Is {\bf NP}={\bf NP}'?

Theorem. {\bf NP}={\bf NP}'.

The proof is almost the same, except that we use non-deterministic Turing Machine, instead of deterministic one. For completeness of the detail, I will write the proof.

Proof. Clearly, {\bf NP} \subseteq {\bf NP}'. Now, let L \in {\bf NP}'. Then there exists a non-deterministic Turing Machine that will accept x \in L in p(n) time, for some polynomial p. Now, we construct a non-deterministic Turing Machine M' that will decide L in polynomial time. Let M' on input x runs a simulation of M(x) in p(n) time. If it halts and ACCEPT, then M' also accepts. Otherwise, REJECT. \square

Still, the proof is non-constructive.

Non-constructive proof in complexity

Let {\bf P} be a class of languages that can be decided in polynomial time by a deterministic Turing Machine. Let {\bf P}' be a class of languages that can be accepted (recognized) in polynomial time by a deterministic Turing Machine.

Theorem. {\bf P}={\bf P}'.

This theorem appears in CLRS book. The proof is non-constructive, roughly as follows.

Proof. It is true that {\bf P} \subseteq {\bf P}' because if it can be decided, then it can be recognized. To prove {\bf P}' \subseteq {\bf P}, let L \in {\bf P}'. Because it can be recognized in polynomial time, then there is a polynomial p(n) such that L can be recognized by a Turing Machine M in p(n) time for input x of length |x|=n. We now construct a polynomial-time deterministic Turing Machine M' that decides L. Let M' is a Turing Machine with input x simulates M(x) up to p(n) time. If it halts and ACCEPT, then M' also ACCEPT. Otherwise, simply REJECT. \square

The main idea of the proof is that if an input x is in L, then the Turing Machine M must have definitive answer before the p(n)-th step. If not, then we are sure that x is not an element of L.

The non-constructive part of the proof is when the proof uses polynomial bound p(n). The only thing that is given is the fact that L \in {\bf P}, and the question is how can we find a polynomial bound for L? Is there a constructive method to find such polynomial p?

From Las Vegas to Monte Carlo with Markov’s Inequality

One of the basic results in probability theory tells us that it is unlikely a random event deviates from its expected value with high probability.
Theorem 1. (Markov’s Inequality)
For any non-negative real valued random variable X, we have
{\text Pr}[X \ge \alpha] \le \frac{\mathbb{E}[X]}{\alpha}.

Note that
\mathbb{E}[X] = \sum_{x \ge 0} x \cdotp p_X(x)
= \underbrace{\sum_{x<\alpha} x \cdotp p_X(x)}_{\ge 0} + \sum_{x \ge \alpha} x \cdotp p_X(x)
\ge \sum_{x \ge \alpha} \alpha \cdotp p_X(x)
\ge \alpha \cdotp \text{Pr}[X \ge \alpha],
as desired. \Box

There is an interesting application of this inequality in theoretical computer science. Knowing this probability bound, it allows us to control a probabilistic algorithm derived from another probabilistic algorithm.

There are at least two classes of probabilistic algorithms that are interesting when we look at in which aspect it is random:

  • a class of algorithms whose output is always correct, but its running time is random (can take very long time),
  • a class of algorithms whose running time is deterministic (for example, is a deterministic function in the length of input), but its answer is sometimes wrong.

The first class is usually called Las Vegas algorithm and the second class is usually called Monte Carlo algorithm. How are these two algorithms related?

It appears that if we can solve a problem using Las Vegas algorithm, we can also solve it using a Monte Carlo algorithm with reasonably small error probability. Let me argue why this is a useful fact. For many practical purposes, we want to have a decision right after certain amount of time; it is okay to make mistakes sometimes (as we may be able to handle it later).

To obtain a Monte Carlo algorithm, we can just simulate the Las Vegas algorithm with little modifications. Our modifications aim at fulfilling two requirements: it runs in a “fixed” time and it outputs an answer in a reasonably good probability. To fulfill the first requirement, we can just fix a threshold for the number of computational steps the Las Vegas algorithm takes, say t(x) steps for an input of size x. If after t(x) steps, our Las Vegas algorithm outputs an answer, we can just output the same answer in our Monte Carlo algorithm. This will always be a correct answer by the nature of Las Vegas algorithm. If not, we just output a made-up answer (depending on our need).

But, how should we choose t(x)? We have freedom here to choose the function t(x), but we may want to use this to fulfill the second requirement: to get a correct answer with good probability. Note that we can analyze our Las Vegas algorithm to obtain its expected running time on input x, say p(x). We know that our Monte Carlo algorithm will output a correct answer at least when the simulation finishes in t(x) steps. If X is the running time of the simulation of our Las Vegas algorithm, then the probability of having a correct answer is at least
\text{Pr}[X < t(x)] = 1- \text{Pr} [ X \ge t(x) ]
\ge 1 - \frac{ \mathbb{E}[X] }{t(x)}
= 1- \frac{p(x)}{3p(x)}
= \frac23,
which is good, if we pick t(x)=3p(x). Obviously, we can also pick larger t(x) to gain better probability. But, as long as we pick t(x)>2p(x), we can also amplify this probability by doing multiple simulations and process a final answer (in case of Boolean answer, for example, we do majority voting).

Note that we have described an abstraction of how to transform any Las Vegas algorithm to a Monte Carlo algorithm. This can be very useful if instead of getting an always-correct-answer, we know when we will get an answer and maybe do a post-processing to the answer afterwards.

Now, our curious mind would ask: Can we obtain a Las Vegas algorithm from a Monte Carlo algorithm? If yes, how? If not, why is it not allowed by nature? Are the collection of problems that can be solved using Las Vegas algorithms and the collection of problems that can be solved using Monte Carlo algorithms the same? If we talk about polytime algorithm, a mathematical-minded reader may want to read more about complexity class {\bf ZPP}, {\bf BPP}, and possibly other probabilistic complexity classes.