Variations on Cantor's celebrated diagonal argument
Srečko Brlek (UQAM)
Abstract: Given a square $n \times n$ tableau $T=\left(a_i^j\right)$
on a finite alphabet $A$, let $L $ be the set of its
row-words. The permanent $\Perm(T)$ is the set of words
$a_{\pi(1)}^1a_{\pi(2)}^2\cdots a_{\pi(n)}^n$, where $\pi$ runs through
the set of permutations of $n$ elements. Cantorian tableaux are those for
which $\Perm(T)\cap L=\emptyset.$ Let $s=s(n)$ be the cardinality of $A$. We
show in particular that for large $n$, if $s(n) <(1-\epsilon) n/\log n$ then
most of the tableaux are non-Cantorian, whereas if $s(n) >(1+\epsilon) n/\log
n$ then most of the tableaux are Cantorian. We conclude our article by the
study of infinite tableaux. Consider for example the infinite tableaux whose
rows are the binary expansions of the real algebraic numbers in the unit
interval. We show that the permanent of this tableau contains exactly the set
of binary expansions of all the transcendental numbers in the
unit interval.
Algebraic Combinatorics Seminar home