Category Archives: General

General topics concerning constructive and computable mathematics.

On a proof of Cantor’s theorem

The famous theorem by Cantor states that the cardinality of a powerset $P(A)$ is larger than the cardinality of $A$. There are several equivalent formulations, and the one I want to consider is

Theorem (Cantor): There is no onto map $A \to P(A)$.

In this post I would like to analyze the usual proof of Cantor’s theorem and present an insightful reformulation of it which has applications outside set theory. Continue reading On a proof of Cantor’s theorem

Are small sentences of Peano arithmetic decidable?

Recently there has been a discussion (here, here, here, and here) on the Foundations of Mathematics mailing list about completeness of Peano arithmetic (PA) with respect to “small” sentences. Harvey Friedman made several conjectures of the following kind: “All true small sentences of PA are provable.” He proposed measures of smallness, such as counting the number of distinct variables or restricting the depth of terms. Here are some statistics concerning such statements.

Continue reading Are small sentences of Peano arithmetic decidable?

Blog as a repository for research papers

I have created a blog category in which I will stick all my research papers. The idea is to allow people to comment on the papers and have an opportunity for discussion. There are some obvious advantages to this, such as: bug reports, opinions, references to related and relevant topics, a paper and a discussion about it are found in the same place, etc. Right now I do not see any obvious drawbacks, so I hope it will turn out to be a good idea.