Transfinite Theory as an Extension of the Natural Numbers

[sandReckoner]

Greetings, comrades!

In a previous thread, a user articulated a common argument:

Two sets of objects (let's call them A and B) are said to have the same

cardinality, if and only if, they have "1-to-1 correspondence." This is to say, if

every object in A can be attached to a unique object in B, and vice-versa. An

intuitive example would be: "Every knight has a horse, and every horse has a

knight." Let the first set, A, represent some set of horses and let the second set,

B, be represented by a set of knights. Even if we haven't counted the set of horses

or the set of knights, we can know that they have an equal number of horses and

knights if we can't mount every knight to a horse and have no horses or knights left

over.

His analogy mapping knights to horses makes intuitive sense, but how can we apply this idea to two infinite sets of knights and horses? How can we treat finite and transfinite sets equal in that sense and then treat them unequal in the sense that two transfinite sets can have the same cardinality but one can be a proper subset of the other (unlike finite sets)?

Is there a robust, analytic proof of the first statement in the quote? Is it simply a definition? Is there some justification for the induction argument?

Also, as an aside, could someone please explain the general applications of transfinite cardinality? Set theory in general? My textbook always explains what to do very well but not always why.

Thanks!
~sR#j

 

[alan2]

It is definition (although well motivated). The usual notions of counting tend to break down when speaking of infinite sets. Two sets have the same cardinality iff there exists a 1-1 correspondence between the sets. So, for example, the set of all positive integers and the set of all even positive integers. One is a proper subset of the other yet they have the same cardinality. Map 1 to 2, 2 to 4, 3 to 6, etc. Asking a question about how many elements each set contains doesn't really make sense anymore in the way we traditionally think of counting a finite number of things.

 

[SteveL27]

Is there a robust, analytic proof of the first statement in the quote? Is it simply a definition? Is there some justification for the induction argument?

The first statement begins: "Two sets of objects (let's call them A and B) are said to have the same cardinality ..."

Its a definition. Just like "An integer is said to be even if it's divisible by 2". The phrase "said to be" or "said to have" indicates a definition.

There is no induction here.

If you tell us what textbook you're reading, and for what course, it would be easier for us to put the idea of 1-1 correspondence into the proper context for you.

 

[sandReckoner]

Thanks a lot. I covered this in an early section of an Abstract Algebra book. I think the confusion came with the fact that the difference between any pairing of natural numbers and even natural numbers diverges for increasing n. So I think I was treating an infinite limit like its finite counterpart after all.

Can you explain the purpose of the definition? Why define equal cardinals as such? Also, why compare infinities?

 

[SteveL27]

Thanks a lot. I covered this in an early section of an Abstract Algebra book. I think the confusion came with the fact that the difference between any pairing of natural numbers and even natural numbers diverges for increasing n. So I think I was treating an infinite limit like its finite counterpart after all.

Can you explain the purpose of the definition? Why define equal cardinals as such? Also, why compare infinities?

Well, it turns out that there are infinite sets that can NOT be put into 1-1 correspondence with other infinite sets. For example, the counting numbers 1, 2, 3, ... can NOT be put into 1-1 correspondence with the real numbers. This was a shocker when Cantor published this discovery in 1874 or so. Cantor showed that there is a whole hierarchy of transfinite cardinals, each one larger than the ones before.

You may find this article interesting and instructive.

http://en.wikipedia.org/wiki/Georg_Cantor

Cantor's work was the beginning of modern set theory. Today, set theorists have a huge inventory of transfinite cardinals. Studying them has implications for our understanding of mathematical logic and the consistency of the axioms of mathematics.

As far as practical uses in daily life, so far there aren't any. But in math, cardinalities are very important. And since cardinalities are related to mathematical logic and the study of what we can define, compute, and prove using finite strings of symbols, these ideas are important in modern computer science.

Ultimately it may be the case that we still don't know why transfinite numbers are important. After all, they are only 140 years old. That's pretty recent in mathematics. There are a lot of logicians and philosophers still trying to work out the deeper meanings of set theory.

By the way, Galileo was one of the first people to notice that there's a 1-1 correspondence between the set of counting numbers and the set of perfect squares.

https://www.google.com/search?aq=f&sourceid=chrome&ie=UTF-8&q=galileos+paradox

I don't know if this really answers your question. You asked why these things are important and all I've said is that mathematicians, logicians, computer scientists, and philosophers think they're important! That's kind of circular.

But if you're reading abstract algebra, I have a more practical answer. In algebra you will be introduced to the concept of an isomorphism, which is a 1-1 correspondence having certain additional properties. So it turns out that 1-1 correspondence is important in math even if you don't care about transfinite cardinalities.

 

[Bacle2]

Just to add a bit:

While the definition of equality in cardinality between sets A,B is defined as A~B iff
there is a bijection, sometimes, when defining a bijection seems difficult, equivalent results are used; specifically, Cantor-Schroeder-Bernstein says that A~B iff there is an injection f:A-->B and an injection g:B--->A .

As an example, CSB allows us (more accurately, make it easier to) to show that the cardinality of the subset of R^R (all functions f:R-->R) of continuous functions has cardinality |R| : use the constant functions and the functions defined on the rationals.

Cardinality results are useful in some math results, e.g., there are cardinality limits to the metrizability of a space. Also, we may care , e.g., about whether a space has a
dense, countable subset, or, whether a space is 1st-countable or not --for one, if it is not, it is not metrizable. There is also the issue of compactness and Lindelof properties; these are spaces that are not too large by certain measures, which allow us to use some properties we cannot otherwise use.

 

[SW VandeCarr]

I understand Cantor showed that $\aleph _ 0 < 2^{\aleph_0}$ and that $2^{\aleph_0}= C$. According to the Continuum Hypothesis, there are no transfinite cardinal numbers intervening between $\aleph_0$ and C.

What I don't understand is if the set of natural numbers, $\aleph_0$ is countable, why is C uncountable given it is defined as the power set. Why aren't the subsets of the power set countable?

 

[alan2]

I'm not the expert on this topic but, as I recall, the proof is the other way around. One can find a 1-1 correspondence between the power set of N and the set of all binary representations on [0,1] by ordering the natural numbers and assigning 1 or zero dependent on whether a particular member of N is in a particular subset. For example, the subset {2,3,5} can be represented by 0.01101000... Since the set of all binary representations on [0,1] is uncountable (and of the same cardinality as R) by Cantor's diagonalization argument, then the power set is uncountable. I'm sure the pure mathematicians can fill in details but that's the basic argument.

 

[Bacle2]

An interesting issue, I think, is how to construct a model (by forcing, IIRC) in which, when CH does not hold, in which there _are_ intermediate cardinalities between c and Aleph_0.

In a strict sense, there are more than one mathematics, and a branching into different mathematics for each undecidable statement into a mathematics that either accepts or rejects the statement.

 

[SW VandeCarr]

An interesting issue, I think, is how to construct a model (by forcing, IIRC) in which, when CH does not hold, in which there _are_ intermediate cardinalities between c and Aleph_0.

In a strict sense, there are more than one mathematics, and a branching into different mathematics for each undecidable statement into a mathematics that either accepts or rejects the statement.

Well, that's true. There are a number of mathematicians who do not accept the CH. In 1963 Cohen showed that the status of the CH is independent of ZFC. That is, ZFC does not depend on the CH being true.

However, my question is, given the CH, how is the cardinality of the continuum defined in terms of the power set of the natural numbers? It's clear that the interval [0,1] has the cardinality of C because it contains the irrational numbers which are not accounted for in Cantor's diagonalization argument. But every non negative integer power of 2 is is a natural number and only a natural number. Any set whose elements are drawn from the set of natural numbers must be finite, or have the cardinality of the infinite set of natural numbers. No?

 

[SteveL27]

An interesting issue, I think, is how to construct a model (by forcing, IIRC) in which, when CH does not hold, in which there _are_ intermediate cardinalities between c and Aleph_0.

In a strict sense, there are more than one mathematics, and a branching into different mathematics for each undecidable statement into a mathematics that either accepts or rejects the statement.

Another point of view is that there is only one mathematics but many different axiom systems attempting to capture its important properties. Newton invented calculus some two centuries before we had epsilon-delta theory. Euler showed zeta(2) = pi^2/6 using methods that would be regarded as hopelessly unrigorous today. Wiles freely used the existence of an inaccessible cardinal to prove FLT. [If anyone's interested I can post links to support that latter claim. The bottom line is that most experts are convinced the same proof could be done without an inaccessible, but nobody's actually bothered to do it.]

In other words it's arguable that mathematicians just do math; and the foundationalists attempt to formalize what the mathematicians do.

It's a little like the existence of many different maps that describe the same territory. Just because there are lots of different maps (some showing the streets, some showing the utility lines, some showing the topography, some showing the population demographics) that doesn't mean there are lots of different territories. There's only one territory and a lot of attempts to abstract its properties in graphical form.

The question of whether there's one math and lots of axiom systems; or whether there's no math until there's an axiom system; and then a different math depending on the axiom system; is of course a question of philosophy.

 

[micromass]

Well, that's true. There are a number of mathematicians who do not accept the CH. In 1963 Cohen showed that the status of the CH is independent of ZFC. That is, ZFC does not depend on the CH being true.

However, my question is, given the CH, how is the cardinality of the continuum defined in terms of the power set of the natural numbers? It's clear that the interval [0,1] has the cardinality of C because it contains the irrational numbers which are not accounted for in Cantor's diagonalization argument. But every non negative integer power of 2 is is a natural number and only a natural number. Any set whose elements are drawn from the set of natural numbers must be finite, or have the cardinality of the infinite set of natural numbers. No?

Yes, every subset of $\mathbb{N}$ is either finite or countable.
The cardinality of the continuum is always the same as the cardinality of the power set of the natural numbers. This has nothing to do with CH.

I don't really see the problem?

 

[SteveL27]

Well, that's true. There are a number of mathematicians who do not accept the CH. In 1963 Cohen showed that the status of the CH is independent of ZFC. That is, ZFC does not depend on the CH being true.

However, my question is, given the CH, how is the cardinality of the continuum defined in terms of the power set of the natural numbers? It's clear that the interval [0,1] has the cardinality of C because it contains the irrational numbers which are not accounted for in Cantor's diagonalization argument. But every non negative integer power of 2 is is a natural number and only a natural number. Any set whose elements are drawn from the set of natural numbers must be finite, or have the cardinality of the infinite set of natural numbers. No?

The question is HOW MANY subsets there are. Each subset of N is either finite or countably infinite (or empty). But how many subsets are there? There are C. Can we find a collection of subsets whose cardinality is greater than that of N but less than C? That's CH.

It's easy to map the reals to the power set of N. Given a subset of the natural numbers, you set f(n) = 1 if n is in the subset, 0 otherwise. Then f(0), f(1), f(2), ... forms a binary decimal representing a real in [0,1]. It's easy to see this is a bijection (except for the countably infinite number of binary decimals with two representations, the usual problem we typically ignore).

 

[Bacle2]

Another point of view is that there is only one mathematics but many different axiom systems attempting to capture its important properties. Newton invented calculus some two centuries before we had epsilon-delta theory. Euler showed zeta(2) = pi^2/6 using methods that would be regarded as hopelessly unrigorous today. Wiles freely used the existence of an inaccessible cardinal to prove FLT. [If anyone's interested I can post links to support that latter claim. The bottom line is that most experts are convinced the same proof could be done without an inaccessible, but nobody's actually bothered to do it.]

In other words it's arguable that mathematicians just do math; and the foundationalists attempt to formalize what the mathematicians do.

It's a little like the existence of many different maps that describe the same territory. Just because there are lots of different maps (some showing the streets, some showing the utility lines, some showing the topography, some showing the population demographics) that doesn't mean there are lots of different territories. There's only one territory and a lot of attempts to abstract its properties in graphical form.

The question of whether there's one math and lots of axiom systems; or whether there's no math until there's an axiom system; and then a different math depending on the axiom system; is of course a question of philosophy.

But the problem I have with this view is that, if you accept there is only one mathematics, then this mathematics must somehow then contain/allow for statements and their negations, and this is the definition of an inconsistent theory. I can't see a way out of this.

SW : Alan's bijection is the one I am familiar with.

 

[SteveL27]

But the problem I have with this view is that, if you accept there is only one mathematics, then this mathematics must somehow then contain/allow for statements and their negations, and this is the definition of an inconsistent theory. I can't see a way out of this.

I agree, of course. But this is all philosophy.

How do you account (not you personally, but how does ONE account) for the immense effort set theorists have put into the question of determining whether CH is true or false? There is a pervasive belief among (some? many? most?) mathematicians that CH has a truth value; that CH is a statement about "the" real numbers; and that the challenge is to find the right set of axioms to answer the question one way or another.

I'm not actually taking sides here, and of course your question is a good one. But a lot of people do think CH has a truth value and that the proper set of axioms will someday reveal that truth value.

 

[micromass]

I'm not actually taking sides here, and of course your question is a good one. But a lot of people do think CH has a truth value and that the proper set of axioms will someday reveal that truth value.

This is certainly true for old set theory. But the old set-theorists did not expect at all that CH was independent from ZFC. But I don't think it holds anymore for the modern set theory. Nowadays, modern set theory deals with whatever axioms that give nice results. A lot of set theoretical research goes for example to the axiom of determinacy which falsifies the axiom of choice. Still this is valid research.
What axioms are the right one is nowadays more of a philosophical question than a mathematical question.
However, I think a lot of people have accepted that the answer to CH is independent of the current axioms.

 

[SW VandeCarr]

Yes, every subset of $\mathbb{N}$ is either finite or countable.
The cardinality of the continuum is always the same as the cardinality of the power set of the natural numbers. This has nothing to do with CH.

I don't really see the problem?

I needed the CH to be able to say $2^{\aleph_0} = C$. Otherwise I would need to consider $2^{\aleph_0} = \aleph_1$ and therefore the possibility of larger cardinals. I'm not sure where C fits in this scheme. In any case, I just wanted to state my question concisely.

The question is HOW MANY subsets there are. Each subset of N is either finite or countably infinite (or empty). But how many subsets are there? There are C. Can we find a collection of subsets whose cardinality is greater than that of N but less than C? That's CH.

It's easy to map the reals to the power set of N. Given a subset of the natural numbers, you set f(n) = 1 if n is in the subset, 0 otherwise. Then f(0), f(1), f(2), ... forms a binary decimal representing a real in [0,1]. It's easy to see this is a bijection (except for the countably infinite number of binary decimals with two representations, the usual problem we typically ignore).

OK. I think I'm beginning to see this. Any irrational number, in principle, can be thought of as a non ending string. So there will be subsets consisting of such strings representing numbers coded in some base. These would be the irrationals. Presumably every irrational number would have a unique infinite string in the power set. The string elements would be countable, but there would be an infinite number of strings.

 

[micromass]

I needed the CH to be able to say $2^{\aleph_0} = C$.[ Otherwise I would need to consider $2^{\aleph_0} = \aleph_1$ and therefore the possibility of larger cardinals. I'm not sure where C fits in this scheme. In any case, I just wanted to define the problem concisely.

No. You misunderstand CH. The equality $2^{\aleph_0}=C$ is ALWAYS true, whether CH is true or not. It is $2^{\aleph_0}=\aleph_1$ that needs CH.
Without CH, we could have $2^{\aleph_0}=\aleph_2$ for example.

 

[SW VandeCarr]

No. You misunderstand CH. The equality $2^{\aleph_0}=C$ is ALWAYS true, whether CH is true or not. It is $2^{\aleph_0}=\aleph_1$ that needs CH.
Without CH, we could have $2^{\aleph_0}=\aleph_2$ for example.

Now I'm confused. CH states that there are no large cardinals between $\aleph_0$ and C. How does C relate to the large cardinals, assuming they exist?

 

[micromass]

Now I'm confused. CH states that there are no large cardinals between $\aleph_0$ and C. How does C relate to the large cardinals, assuming they exist?

What do you mean with the term "large cardinal" here?? In its conventional use, CH makes no statement about large cardinals. CH simply says that $C=\aleph_1$.
The equality $C=2^{\aleph_0}$ is always true however.
Equivalently, CH says that there is no cardinal between $\aleph_0$ and C. It makes no statement about "large cardinals".

Without CH, C can equal a large cardinal (assuming it exists) or C can equal an ordinary cardinal like $\aleph_2$. There is a very light constraint on what C can equal, however: for example C can't equal $\aleph_\omega$ but it can equal $\aleph_{\omega+1}$.

 

[SteveL27]

I needed the CH to be able to say $2^{\aleph_0} = C$. Otherwise I would need to consider $2^{\aleph_0} = \aleph_1$ and therefore the possibility of larger cardinals. I'm not sure where C fits in this scheme. In any case, I just wanted to state my question concisely.

As micromass has pointed out, the phrase "large cardinal" has a specific meaning in set theory that's way beyond the kind of cardinals we're talking about here. Without CH, it may be that $2^{\aleph_0} = \aleph_{47}$, say. But $\aleph_{47}$ is by no means a "large cardinal." Large cardinals are cardinals whose existence is not given by the standard axioms of set theory; but whose existence is not ruled out by the standard axioms, either. $\aleph_{47}$ is a perfectly ordinary cardinal whose existence is guaranteed by the standard axioms.

We don't need CH to show that $2^{\aleph_0} = C$. That's an easy proof, namely the one I gave mapping subsets of N to binary decimals.

OK. I think I'm beginning to see this. Any irrational number, in principle, can be thought of as a non ending string. So there will be subsets consisting of such strings representing numbers coded in some base. These would be the irrationals. Presumably every irrational number would have a unique infinite string in the power set. The string elements would be countable, but there would be an infinite number of strings.

A real number can be thought of as a nonending string. That includes the irrationals as well as the rationals. 1/3 = .3333... in decimal is the most familiar nonterminating rational. But even the terminating rationals are infinite strings. For example 1/2 = .50000... = .49999... has two such nonterminating expansions. There are only countably many reals that have two different expansions, so we typically only consider the .49999... representation when we're doing our mapping. There are only countably many reals that have two different representations, so they don't cause a problem when we're doing uncountability proofs.

Each string element as you call it, or binary decimal, is a string consisting of countably many digits. There are uncountably many such strings.

 

[Bacle2]

I agree, of course. But this is all philosophy.

How do you account (not you personally, but how does ONE account) for the immense effort set theorists have put into the question of determining whether CH is true or false? There is a pervasive belief among (some? many? most?) mathematicians that CH has a truth value; that CH is a statement about "the" real numbers; and that the challenge is to find the right set of axioms to answer the question one way or another.

I'm not actually taking sides here, and of course your question is a good one. But a lot of people do think CH has a truth value and that the proper set of axioms will someday reveal that truth value.

But I think it ends up being even more confusing , as a result of Lowenheim-Skolem, we
have models for different structures that are elementary-equivalent, but not isomorphic;
maybe the most familiar are the standard and non-standard reals. Which are the "legitimate" or "true" reals, integers, etc?

 

[lavinia]

I understand Cantor showed that $\aleph _ 0 < 2^{\aleph_0}$ and that $2^{\aleph_0}= C$. According to the Continuum Hypothesis, there are no transfinite cardinal numbers intervening between $\aleph_0$ and C.

What I don't understand is if the set of natural numbers, $\aleph_0$ is countable, why is C uncountable given it is defined as the power set. Why aren't the subsets of the power set countable?

The subsets are countable. But the number of subsets is uncountable.

 

[SW VandeCarr]

The subsets are countable. But the number of subsets is uncountable.

Yes. I got it. Thanks.