In classical mathematics $2^{\aleph_0}\ge\aleph_1$, right? So if $2^x=\aleph_0$, what does $x$ equal?

In other words, can we define a logarithm for $\aleph_0$, and what should it be. Is it infinite? Finite? Undefined?

Should a definition in a computational context be necessarily the same as in the classical context, or can/should it be modified, like other mathematical definitions are modified to accomodate computability (e.g. limits in the context of computable reals)


migrated from cs.stackexchange.com May 13 '15 at 20:11

This question came from our site for students, researchers and practitioners of computer science.

  • $\begingroup$ If we don't assume the axiom of choice, maybe something with Dedekind-finite sets would work here $\endgroup$ – Omnomnomnom May 13 '15 at 20:33
  • $\begingroup$ It is not true that in classical mathematics $2^{\aleph_{0}}=\aleph_{1}$. That is the continuum hypothesis and its truth value (if it has one) is unknown since it is independent of the set theoretic axioms (ZFC). $\endgroup$ – Quinn Culver May 14 '15 at 2:09

A simple answer would be that if we interpret $2^A$ as denoting the powerset of $A$, there should be no $X$ such that $\mid2^X\mid = \aleph_0$. The cardinality of $X$ itself cannot be $\aleph_0$ (or we would have $\mid2^X\mid > \aleph_0$), but it also cannot be any finite number, or we would have $\mid2^X\mid$ also finite.

In the absence of an infinite cardinal smaller than $\aleph_0$, a set with the cardinality of $X$, as defined here, cannot exist.

  • $\begingroup$ It also can't be incomparable with $\aleph_0$, since otherwise one could compose a bijection with the singleton map $\: X\to 2^X \:$ to get an injection into $\omega$. $\endgroup$ – user57159 May 7 '15 at 9:33

There are two things to point out here.

  1. $2^{\aleph_0}=\aleph_1$ is an assertion called "The Continuum Hypothesis". It cannot be proved, nor disproved, from the standard axioms of set theory.

  2. Note that in $\Bbb N$ not every number has a logarithm. For this you need to extend to the real numbers. For example $\log_25$ is not a natural number at all. So the equation $2^x=5$ has no solutions when talking about the natural numbers.

    Since cardinals are not real numbers, but they do extend the natural numbers, it means that $2^x=5$ has no solutions in terms of cardinal arithmetic either.

    Why am I bringing this up? Because it shows you that you don't have to have a logarithm. And indeed for $\aleph_0$ you don't. Because if $x<\aleph_0$, then $x$ is finite and $2^x$ is finite; and if $x=\aleph_0$ then $2^x>x$ by Cantor's theorem.

As a side note, it might be worth pointing out that on a considerably large class of cardinals there is no solution to the equation $2^x=\kappa$ (where $\kappa$ is the cardinal in question).,


Note: This question was initially asked on the Computer Science site, where issues of computability are often more essential, and this answer was written in that context.

In a nutshell: If we consider only computable subsets of a countable set, then the cardinality of the "computable powerset" is also countable, so that we can write $2^{\aleph_0}=\aleph_0$. But, the question would be more answerable if there was a stated purpose to the suggested extension of logarithm to $\aleph_0$.

We can do mathematics only with what has been defined within a consistent logic. Considering infinity as a number to be added to the natural numbers is fine, as long as we can give it a consistent meaning, i.e. have a consistent logic. However, it may well be that adding infinity to a simple theory of numbers will work well, but that consistency is lost when adding new axioms commonly used by mathematicians.

Another point is that, when introducing extensions, there are often many ways to define them, each potentially with good side or bad sides. For example, there are discussion, that may also be seen as related to logarithm and exponential, on whether $0^0$ should have a meaning, and which: 0 or 1. There are several pages on this on the web (search: 0 power 0), including on SE. Depending on what you are doing, one choice may be wiser or more helpful than another.

While it is usually considered that $0^0$ is undefined, it is often convenient to define $0^0=1$, particularly in discrete mathematics. This emphasizes that making such extensions is usually to answer a need or a purpose. But the question asked fails to stat any purpose, which limits the usefulness of this discussion.

As explained in André Souza Lemos' answer, there is no way to propose a solution in the context of classical mathematics.

Then, we should recall that this site is about computer science. Hence one should assume that questions must be interpreted in a CS context, i.e. in computability related terms. So we should probably interpret $2^A$ as the "computable powerset" of a countable set $A$, i.e. the set of computable subsets of $A$. Note that computable reals may be seen as characteristic functions for computable subsets of natural numbers, in the same way that usual reals are characteristic functions for arbitrary subsets of natural numbers.This changes nothing where finite sets are concerned, which is nice because the logarithm and exponential functions are primarily defined for natural numbers, i.e. set cardinalities, and this is precisely the approach taken by the question.

In such a context, the computable powerset of a denumerable set is also denumerable. Hence one could consistently define $2^{\aleph_0}=\aleph_0$. Then, it would also be consistent to define $\log_2 \aleph_0=\aleph_0$. When I am saying that these definitions are consistent, I only mean to say that they are consistent with respect to the few issues we have been considering. Whether they are consistent with some significant logic of computable arithmetics (and also useful) remains to be defined and checked formally.

You note that saying here $\log_2 \aleph_0=\aleph_0$ is in contradiction with André Souza Lemos' answer, and $2^{\aleph_0}=\aleph_0$ contradicts the assertion made in the question that $2^{\aleph_0}=\aleph_1$. But this is only because I have been considering a different mathematical context.

The power/logarithm notation, seen as operating on numbers, is initially defined on finite cardinalities, i.e. natural numbers. They can be extended in various ways (for example on reals). Here the issue is to extend them to infinite cardinalities, and any extension is a matter of context and consistency.

It is also a matter of purpose, and that is lacking here. But maybe someone will have an idea about it.

Bertrand Russel wrote: "Mathematics may be defined as the subject in which we never know what we are talking about, nor whether what we are saying is true."

  • $\begingroup$ In the context of computability, when we want to look at only the computable subsets of $\mathbb{N}$, we often also want to look at only the computable bijections... In that case, we encounter the problem that there is no computable enumeration of (only) subsets of $\mathbb{N}$ that includes all the subsets of $\mathbb{N}$ (by an easy effective diagonalization argument). So, even in computable analysis where we look at only computable sets, although the collection of all computable subsets of $\mathbb{N}$ is countable, it is still "computably uncountable". $\endgroup$ – Carl Mummert May 16 '15 at 10:56
  • $\begingroup$ @CarlMummert Well, I guess there are many ways one can want to look at it. My main point was not to say that this or that is the answer, but more that there is no answer, but rather an arbotrary choice (as for any extension) that must meet some constraints (consistency) and that should preferably have a useful role in understanding some structures. - - - This said, do you mean to say that my terminology "countable powerset" is ill-chosen ... I guess I acn agree with that. $\endgroup$ – babou May 16 '15 at 11:35

The logarithm of an infinite cardinal number $\alpha$ is defined as follows: $$\log\alpha=\min\{\beta\ |\ 2^\beta\ge\alpha\}.$$ This definition is given on p. 74 of Cardinal Functions in Topology by István Juhász, and I am not aware of any competing definitions. According to this definition, $$\log\aleph_0=\log\aleph_1=\aleph_0.$$ It should be noted that $$2^{\log\aleph_0}\gt\aleph_0.$$ The equation $2^x=\aleph_0$ has no solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy