Question: Counting Continuous Functions

[Surlethe]

Is the set of the equivalence classes of all the continuous functions from the reals to the reals countable?

In this case, I wish to define all continuous functions arrived at in a similar manner as equivalent -- e.g., all linear functions in one class. So this leads to another question: how does one define the equivalence classes for the set above?

In essence, I am asking: is it possible to count the ways we can make a continous function from the reals to the reals?

Furthermore, does generalizing the question to the set of equivalence classes of all continuous functions from any set of numbers to the Reals change the answer? What about from any set to any other set?

[Kuroneko]

Is the set of the equivalence classes of all the continuous functions from the reals to the reals countable?

No. This is very simple once you realize the following: what is the cardinality (or bounds on) of the set of all partions of a given set?

In this case, I wish to define all continuous functions arrived at in a similar manner as equivalent -- e.g., all linear functions in one class. So this leads to another question: how does one define the equivalence classes for the set above?

Hint: it is not necessary to specify any algorithmic method; see previous hint.

In essence, I am asking: is it possible to count the ways we can make a continous function from the reals to the reals?

That's not the right question.

Furthermore, does generalizing the question to the set of equivalence classes of all continuous functions from any set of numbers to the Reals change the answer? What about from any set to any other set?

A related but not necessary problem: prove that the cardinality of the set of continuous f:R->R is no more than the cardinality of all f:Q->R, where Q and R are the set of rationals and reals, respectively. (This is not necessary to answer your questions; but it is related in that it allows you to prove an exact cardinal number for the cardinality of the set of equivalence classes, rather than simply "more than \aleph_0 and less than 2^{2^{\aleph_0}}").
As for your question, see the first hint again.

[Kuroneko]

(This is not necessary to answer your questions; but it is related in that it allows you to prove an exact cardinal number for the cardinality of the set of equivalence classes, rather than simply "more than \aleph_0 and less than 2^{2^{\aleph_0}}").

This should have read "... no more than 2^{2^{\aleph_0}}." There are exactly that many equivalence classes of continuous real functions. The original question itself could be answered by simpler means if you are not looking for the cardinality of the set of equivalence classes but only whether or not it is greater than \aleph_0. Let X be the set of continuous functions f:R->R. Observe that F_r:R->R defined by F_r(x) = r for real r is a unique continuous function from the reals to the reals, and that there are 2^{\aleph_0} > \aleph_0 of functions in that form. For each F_r(x), generate an equivalence class
[f ≡ g] iff [ (f = g = F_r) OR ¬(f = F_r OR g = F_r) ],
i.e., f is equivalent to g iff they are both F_r or they are both not F_r. It is very easy to verify that this is an unique equivalence relation for each real r. There are therefore at least as many equivalence classes as real numbers. QED.

In general, one can prove in ZFC that (1) the cardinality of equivalence classes of an infinite set X at least 2^{|X|}, which is obvious from previous post, and that (2) the cardinality of equivalence classes of an infinite set X is no more than 2^{|X|}, using the fact that |X^2| = |X|.

[Surlethe]

Thank you for the reply. I think I follow it.

I shouldn't ask questions which have answers above my head . . .

[Kuroneko]

Ah, I was uncertain of your knowledge of set of set theory. This isn't actually all that difficult once the concept of partition is made clear. For a given set X, a set Y of subsets of X is a partition iff all members of Y are nonempty, pairwise-disjoint, and the union of which is X. For example, say X = {1,2,3}. For Y = {{1,2},{3}}, note that both {1,2} and {3} are disjoint subsets of X and their union is X; therefore, Y is a partition of X. Other possible partitions of X: {{1,2,3}}, {{1},{2,3}}, {{1,3},{2}, {{1},{2},{3}}. Make some partitions of {1,2,3,4}; there are fifteen total.

An equivalence relation ≡ is reflexive (a≡a), symmetric (a≡b implies b≡a), and transitive (a≡b and b≡c implies a≡c). It can be verified rather easily for any given partition Y of X, "member of the same element of Y" is a unique equivalence relation on X. For example, if X = {a,b,c,d,e} and Y = {{a,b,c},{d,e}}, we have a≡b≡c and d≡e. The converse also holds: every equivalence relation on X induces a unique partition--we can simply put equivalent elements of X into the same element of the partition.

For every set X with at least two elements, the set of equivalence classes has greater cardinality than X. Pick an element x in X, and create the two-element partition Y = {{x},X-{x}} [1], which corresponds to the equivalence relation "everything that is not x is equivalent, but x is not equivalent to anything but itself." Back to your original question, there is obviously uncountably many continuous real functions (F_r(x) = r for each real r being a unique continuous function), so this argument shows that there are uncountably many equivalence classes on continuous real functions.

This result can be made much stronger. Pick a nonempty proper subset A of X, and create the two-element partition Y = {A,X-A}. Since there are 2^{|X|}-2 such subsets, there must be at least as many equivalence classes on X, though possibly much more, since we are neglecting paritions of sizes other than two. (Note that for infinite X, 2^{|X|}-2 = 2^{|X|}.) If X is infinite, then there are also no more than 2^{|X|} equivalence relations, assuming standard ZFC or ZF+GHC set theory [2], since from every such partition one can create a unique function f:X²->{0,1} defined by f(x,y) = 1 iff x≡y, ensuring that there are no more than 2^{|X²|} = 2^{|X|} such equivalence classes. Thus, the set of equivalence classes on an infinite set X has same cardinality of the power set of X.

For your original question, this means that the set of equivalence classes of continuous real functions is not just uncountable, but has more than continuum many elements--under ZF+GHC, \aleph_2 = 2^{\aleph_1} elements, as compared to the reals (\aleph_1 = 2^{\aleph_0}) and the integers (\aleph_0).


[1] The notation A-B for sets A and B represents the set of all elements of A that are not in B. In other words, X-{x} is everything in X except x.
[2] If you are learning set theory, this is likely what you are studying, even if your sources do not make mention of any alternatives.

[Kuroneko]

For every set X with at least two elements, the set of equivalence classes has greater cardinality than X.

"Greater" should have read "greater than or equal to." While the above statement is true, it is not actually proven until the next paragraph., except if X is finite.I was getting ahead of myself (if a mod is willing to change it and get rid of this, I would appreciate it).

[drachefly]

Now seems like a good time to ask...

what does this mean
aleph-1 = 2^(aleph-0)

If that's so, how is it that you can't define a map between them?
I mean, you can just go around filling in the binary tree that this equation suggests... if it has a naive meaning. Since it has meaning at all, obviously this naive meaning is wrong.

Or is the problem that if you begin tracing out the binary tree you never actually get to the bottom, and so you never actually select ANY element of aleph-1? Hmm. I'm not sure that's sensible either.

So, what does it really mean?

[Kuroneko]

I don't know how much set theory you have studied, so please forgive me if some of the following is a review. I will, however, assume familiarity with at least basic concepts of set theory.

Now seems like a good time to ask... what does this mean aleph-1 = 2^(aleph-0)]

Under ZF or compatible [1] set theory, sets are said to have the same cardinality iff there exists a bijection (one-to-one correspondence) [2] between them. One can then define, for a given set A, a 'cardinal number' α = |A|, which is a purely formal object [3] describing the cardinality of the set, with α=β iff there is a bijection between A and B, where A has cardinality α and B has cardinality β (note for every cardinal number there is some set with that cardinality, simply by definition). The utility of this is that one can define artihmetic on cardinal numbers: α+β = |A∪B| = |{x:x∈A∨x∈B}| if A and B are disjoint; αβ = |A×B| = |{(a,b): a∈A∧b∈B}|; β^α = |{f:α→β}|. The last one is the most interesting.

If that's so, how is it that you can't define a map between them?

What do you mean? At first I thought you were looking for an explicit bijection between two representative sets, but your subsequent comments indicate something else is the difficulty.

I mean, you can just go around filling in the binary tree that this equation suggests... if it has a naive meaning. Since it has meaning at all, obviously this naive meaning is wrong.

If β = 2 (i.e., β is the cardinality of any two-element set, say B = {0,1}), then given an A such that |A| = α, 2^α is the cardinality of the set of functions from A to {0,1}. I'm not sure what you mean by "binary tree." There is, however, considerable similarity between 2^α and binary sequences. If A is the set of naturals {0,1,2,..}, then a function f:A→{0,1} is simply the sequence x_0,x_1,x_2,... of "binary digits." For abitrary sets A, this can be loosely thought of as a "sequence" indexed by members of A (instead of the naturals), except that there is no guarantee that A has any sort of order defined on it (consider A = {chicken,egg}--which should come before the other? Or, for that matter, the real numbers--there is no "next" real number after any given one).

For any subset X of A, there is a unique function f:A→{0,1} defined by f(x) = 1 if x in X and f(x) = 0 otherwise [4]. The converse also holds. Thus, 2^α is the cardinality of the power set of any set with cardinality α. But to answer your question fully, it remains to specify exactly what is meant by \aleph_0 and \aleph_1.

Or is the problem that if you begin tracing out the binary tree you never actually get to the bottom, and so you never actually select ANY element of aleph-1? Hmm. I'm not sure that's sensible either.

In ZFC, ZF set theory is adjoined with the axiom of choice (AC), cardinal numbers are guaranteed to be well-orderable: for any collection [5] of cardinal numbers, there is always a smallest cardinal among them [6]. The cardinality of the natural numbers is by definition \aleph_0, which can be proven to be smallest infinite cardinal, in the sense that there is no set with cardinality greater than every finite cardinal (0,1,2,...) and lesser than \aleph_0. The well-ordering property ensures that there is a next largest cardinal \aleph_1, again in the sense that there is no set X for which \aleph_0 < |X| < \aleph_1 [7]. The contiuum hypothesis postulates that \aleph_1 = 2^{\aleph_0}, and it is known to be completely independent of ZFC (and consequently also ZF). The generalized contunuum hypothesis (GHC) postulates that the next largest cardinal after a given α is always 2^α. This is known to unprovable in ZFC, but ZF+GHC implies the axiom of choice, so ZF+GHC is an extension of ZFC.

[1] For example, vNBG or extensions like ZFC, ZF+GHC, etc.
[2] Formally, f:A→B iff for every b∈B, there is a unique a∈A for which f(a) = b.
[3] Well, in ZF. In ZFC, every set has a bijection with some ordinal number, which are well-ordered, so cardinal numbers can be defined as a certain type of ordinal number (to be specific, a cardinal is an ordinal that has no bijection with any lesser ordinal). Doing so, however, is not necessary--one can leave cardinals as simply formal objects.
[4] This is called the characteristic function of X, and usually denoted by χ_X.
[5] "Collection" meaning "set or class". In ZFC, there is no set of all cardinals, but in vNBG+AC set theory, there is a "class" of all cardinals. Classes are collections of objects which are not guaranteed to be sets.
[6] Compare with the rational or real numbers, in which this is not the case (e.g, open intervals).
[7] Again, contrast this property of cardinals with rationals or reals, among which it is always possible to find a number between any two distinct given ones.

[Surlethe]

Thank you, Kuroneko; your explanation is, I think, within my grasp; I'm going to tangle with it some more, and then make sure I understand it.

If β = 2 (i.e., β is the cardinality of any two-element set, say B = {0,1}), then given an A such that |A| = α, 2^α is the cardinality of the set of functions from A to {0,1}. I'm not sure what you mean by "binary tree." There is, however, considerable similarity between 2^α and binary sequences.

During discrete last week, someone in class pointed out when you create a power set, you're basically creating a combination of the binary choices. Since I am finding it hard to verbalize what I'm saying, I'll illustrate with an example.
The power set of A={1,2,3} would be equivalent to the set of binary numbers P(A)={000,001,010,011,100,101,110,111}, with 0 if the corresponding element of A is not in that element of P(A), and 1 if the corresponding element of A is in that element of P(A).
If that made any sense. Or is this what you mean by the set of functions from A to {0,1}?
In any case, I think he may be referring to the sequence
000
001
010
011
100
101
110
111
as a binary tree (in reference to my example).

[Kuroneko]

During discrete last week, someone in class pointed out when you create a power set, you're basically creating a combination of the binary choices. The power set of A={1,2,3} would be equivalent to the set of binary numbers P(A)={000,001,010,011,100,101,110,111}, with 0 if the corresponding element of A is not in that element of P(A), and 1 if the corresponding element of A is in that element of P(A). If that made any sense. Or is this what you mean by the set of functions from A to {0,1}?

Yes. For an arbitrary subset Y of X, for every x in X has exactly two possibilities: it is either in Y or not in Y. Therefore, a subset can be represented as a function f:X→{0,1}, where f(x) = 1 if x in Y and f(x) = 0 if not, or vice versa. Above, your '101', for example, corresponds to the function f:{1,2,3}→{0,1} for which f(1) = 1, f(2) = 0, f(3) = 1, assuming the digits are in the usual order. The set {0,1} can, of course, be replaced with any other two-element set.

In any case, I think he may be referring to the sequence 000, 001, 010 011, 100, 101, 110, 111 as a binary tree (in reference to my example).

Ah... I think I understand his comment now, but I don't think he is referring to such a sequence; rather, given his reference to "the bottom" in relation to selecting elements of sets, he is probably thinking of each node in the binary tree as a binary choice, with the _final_ row being a member of the above sequence (illustrated below). This is a pretty interesting way to think of this, but somewhat flawed. If X is infinite, there are infinitely many such "choices" before the final row is reached, but why that presents a conceptual problem is unclear. All it seems to force is that infinitely many rows do not have a preceding row, so that the graph is not connected in the usual sense, and therefore does does not actually form a binary tree.

Code: Select all

                 1?
               /    \
             /        \
           /            \
         2?              2?
        /  \            /  \
      /      \        /      \
     3?      3?      3?      3?
    /  \    /  \    /  \    /  \
  000 001 010 011 100 101 110  111