Cantor diagonal argument is almost surely inconsistent


Here we construct table consisted of realization of Bernoulli processes; using Cantor diagonal argument we construct row that is not in the table, and finally we show that constructed number is almost surely in the table countably infinite number of times.

Consider doubly infinite table X_{k,m}, where index k \in \mathbb{N} enumerates rows, and index m \in \mathbb{N} enumerates columns. Each element X_{k,m} is independent binary random variable with equally probable possible states 0 and 1. Suppose x_{k,m} is a realization of random variables. We are going to fix it for the rest of the post.

Cantor diagonal argument Let row y_{k} = 1-x_{k,k}. Since, y is different from every row in at lest one place it is not in the table. Using induction we will check the next row diagonal, and will get proof by induction .

Theorem There are countably many rows equal to y in the table with probability 1.
Proof 1. Select the subset of rows (x_{k,\circ}) where the first column has value y_1: A^1=\{ x_{k,\circ} | x_{k,1}= y_1 \}. Since x_{k,m} is a realization of independent random variable, there are infinite number of rows in A^1 with probability one. Moreover, viewing A^1 as a table one can see that a_{k,1} = y_1, \forall k , and a_{k,m}, m>1, \forall k is a realization of equi-probable binary random variable.

Induction step. Suppose there is a set of countable many rows A^k such that a_{p,m}^k= y_m, \forall m<=k, \forall p. We select from the table A^k a subset of rows that have A^{k+1}= \{ a^k_{p, \circ} | a^k_{p,k+1}=y_{k+1} \} . The set A^{k+1} consists of countable infinite number of rows with probability 1. Moreover, the table A^{k+1} divided into 2 parts. The left part- columns from 1 to k+1 – all rows coincide with y_1 ... y_{k+1}. The right part – all columns starting from k+2 are realization of independent random variable.

Therefore, by induction, there is set “A^{\infty} that is countably infinite with probability 1, and each member consists of rows y. QED.

If one interpret table x_{k,m} as membership table, e.g. a set B_{k}= \{ e_m : x_{k,m} =1 \} than we have countable infinite representation of power set of countably infinite set by the theorem, whereas Cantor diagonal argument says the opposite. Therefore, if one replace the axiom of choice with the axiom of “free will’ – there exist Bernoulli process one have contradictory statement about sets cardinality. Axiom of choice is than deductible from the fact that all members of the sets A^k are ordered by the rows and particular implementation of random variables.

Applying weights to the column, e.g. representing real numbers r=\sum x_{k,m} 2^{-m} shows there are countable many reals, and moreover there are countable many equal reals.

About these ads
This entry was posted in Uncategorized. Bookmark the permalink.

One Response to Cantor diagonal argument is almost surely inconsistent

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s