Hacker News new | past | comments | ask | show | jobs | submit login
A Crash Course in the Mathematics Of Infinite Sets (earlham.edu)
51 points by davesque on Dec 3, 2013 | hide | past | web | favorite | 24 comments

One minor note: When discussing the continuum hypothesis, Suber refers to ZF (without the axiom of choice) as "the closest thing we have to 'standard' set theory". However, he implicitly uses the axiom of choice, or at least the axiom of dependent choice (I didn't really read enough to see whether there are other uses); without this you can't prove that aleph_0 is the smallest infinite cardinal. So there is a mismatch here; the implicit background this text is assuming seems to be more ZFC than ZF.

Just to elaborate for those not familiar with the terminology, the axion of dependent choice is a weaker version of the axiom of choice. It asserts that you can pick a countable(denumerable using the terminology in the post) sequence from any infinite set. The axiom of choice asserts (informally) that given any collection of sets, you can form another set which consists of one element from each set in the collection. The axiom of choice asserts that this holds true even when the number of sets is uncountable (non-denumerable).

The axiom of choice and the continuum hypothesis are equivalent, meaning the assumption of either one implies the other. <<EDIT: This is wrong, see below>>

This is a good reply, but I have to point out that the Continuum Hypothesis is certainly not equivalent to the Axiom of Choice. In fact, it's independent of the Zermelo Frankel axioms together with Choice. While broader mathematics community has pretty much now accepted Choice (it's too damn useful not to), no such consensus has arisen over the Continuum Hypothesis. However, unlike AC, I doubt many people outside set theory their have a strong opinion on CH.

Thanks, I temporarily got CH and well-ordering mixed up.

Well, the axiom of dependent choice is a bit stronger than that. And your contrast with the full axiom of choice makes it sound like dependent choice is just countable choice.

For the onlookers:

Axiom of choice -- Given any collection of disjoint sets, there's a set consisting of one element from each.

Axiom of countable choice (this is weaker) -- Given any countable collection of disjoint sets, there's a set consisting of one element from each.

Axiom of dependent choice (this is intermediate in strength) -- Suppose you have a set X and a binary relation R on X such that for any x in X, there's some y in X such that xRy holds. Then there's a sequence x_0, x_1, ..., consisting of elements in X, such that for any i, x_i R x_(i+1) holds.

Countable choice is not enough to prove that aleph_0 is the smallest infinite cardinal; dependent choice is. Of course you could weaken dependent choice and still be able to prove it, but not all the way to countable choice.

(Ignoring the AC/CH thing, that's been addressed already.)

The diagonalization argument has always bothered me, this is why.

Countable sets are shown to be countable by providing a mapping between the natural numbers and that set. Uncountable sets are shown to be uncountable by assuming they are and creating a new element from the set of all elements and showing that it was not accounted for in the first place.

But what happens when we try to use the mapping argument on the set of the reals, and the contradiction argument in the set of the integers?

For the countability of the reals, I can setup a binary tree of infinite depth with 0 on the left and 1 on the right. I then do a depth first walk of the tree and assign an integer to each of the nodes. Then the sequence of 0s and 1s from the root of the tree to any node we care to go to represents a binary number between 0 and 1 if we treat it as a binary fraction like he does in theorem 16. So any number we care to go down to in the binary tree can be assigned a natural number, and since the binary tree is infinite it can go down to any real number. So according to this argument the reals are countable.

Now for the diagonalization-like argument for incountability of the natural numbers. Assume the positive even numbers are countable, and that we have a list of all the even numbers assigned to a natural number. I can create a new even number by adding all of the numbers in the list, since all the numbers are positive, each number is smaller than the sum of all of the numbers on the list, so the number is not on the list, and we have to conclude that our assumption was wrong, and that the even numbers are uncountable.

If the first argument is wrong, why is it wrong for the reals but not wrong for the naturals? And if the second argument is wrong, why is it wrong for the naturals but not wrong for the reals?

Neither of your arguments really make sense, unfortunately.

For your first argument, the number of nodes in your tree isn't equinumerous with the naturals. If it is, can you define an injective function which takes as its input any (potentially infinite) path in your tree and returns a natural number?

For your second argument, what do you mean by "we have a list of all the even numbers assigned to a natural number?" Assigned how? The map n↦2n puts the naturals and even naturals in 1-1 correspondence and so we're done proving that they're equinumerous.

It sounds like either you imagine multiple even numbers being "assigned" to a particular natural number (which isn't what we care about) or that you're thinking of adding lists of an infinite number of even numbers somehow?

From the grandparent comment:

>> I then do a depth first walk of the tree and assign an integer to each of the nodes.

This is clearly wrong as the depth first walk on the said tree will keep on just taking the left-most path always and keep on assigning natural numbers to nodes on this left-most path. In other words, since the leftmost path is an infinite string of zeros, it is clearly denumerable and can have one-to-one correspondence to natural numbers (ordinals rather than cardinals though). Any other node in the tree never gets assigned any natural number, making the argument wrong.

I was left thinking though about what happens if a "breadth-first" search on this tree is used instead. Each row starting from the root as 2^N nodes (assuming N=0 for the root node). So you can assign '1' to the root node, '2' and '3' to the two children, '4', '5', '6', '7' to the grand children, and so on. Note that this assignment is very similar to that used in the proof of theorem 2 in the original post, just that the number of nodes/elements in theorem 2 is increasing linearly with the slanted row#, while in this binary-tree case, it is increasing exponentially.

Applying diagonalization now (by arranging the mapping in the usual way) though shows that 0.111111... is never assigned a natural number.

I cannot say however that I am 100% clear about this, and have had a corresponding confusion before using a different line of reasoning.

Yeah, 100%. There are (at least) two incorrect things the original commenter took for granted. First, that the infinite binary tree as he created it is equinumerous with the natural numbers and therefore can stand in for the "list" in Cantor's diagonalization argument. Second, that a depth-first traversal of this tree makes sense.

Your argument does a good job of showing why the first is a mistake. Assuming we can traverse it at all, it shouldn't matter whether we do so depth or breadth first. By traversing it breadth first we see clearly that we can always find a path through the three which does not correspond to any natural number, proving that the tree is not equinumerous with the naturals and, moreover, proving that there is an infinity which is "larger" than the infinity of the naturals.

I find infinite mathematical structures interesting from a philosophical point of view, because it’s not possible to reconstruct these concept in the physical world. In fact there is a mathematical-philosophical movement refusing infinite structures: http://en.wikipedia.org/wiki/Finitism

This seems to muddle cardinality. First he defines cardinality as "number of elements" and notes that infinite sets have infinite cardinality, but doesn't explain what that might mean. Then he introduces "same cardinality" as a new definition instead of letting it arise out of sameness of number. And next, without any new definition, starts referring to larger cardinality.

A very dense and readable summary of some of the key concepts in set theory. Warning!! May cause mind-blowing.


Please either define "exists" or formulate your claim without using the word :)

I'll side with Poincaré and there is not much to say other than that.

"The objections to Cantor's work were occasionally fierce: Poincaré referred to his ideas as a "grave disease" infecting the discipline of mathematics" http://en.wikipedia.org/wiki/Georg_Cantor#cite_note-daub266-...

Poincaré was a genius but math has moved forward since the 19th century.

Here's what I'd argue is the most important take away from set theory: for a given framework of mathematics, there are conjectures one can make that can be neither proved nor disproved. Perhaps the most high-profile of them is the continuum hypothesis.

Maybe P!=NP is such a conjecture. Maybe the existence of a solution to the Navier-Stokes equation is such a problem. For Poincaré, the very idea that there is math that can be neither proved nor disproved was not in his mental vocabulary.

On another note, Weil's celebrated proof of Fermat's last theorem relies on the existence of inaccessible cardinals[1], although I've heard it conjectured that they are not necessary.

[1] https://en.wikipedia.org/wiki/Inaccessible_cardinal

Well, I've studied under a pupil of Grothendieck, so, yes inaccessible cardinals are at the heart of his category theory. When you study this long enough, you will discover they essentially perform the function of what in computer science is the class concept (which why these structures were called 'universes'). But Russell already developed a type theory around 1900. Most mathematicians have never cared to really study Gödel for instance. Because you then would have to read Russell's principia mathematica and Frege's concept script.

A minor nitpick: It was Andrew Wiles who proved Fermat's last theorem. Andre Weil was another incredible mathematician (responsible for, among many other things, the celebrated Weil conjectures), but did not prove Fermat's last theorem.

Andre Weil was very opinionated and lived a very interesting life. I encourage you to read about it: http://en.wikipedia.org/wiki/Andr%C3%A9_Weil

Is that all there is to it?

:/ does this have any practical application?

It's actually based on Relation theory, but Set theory is pretty much a requirement.

What about your question?

Applications are open for YC Winter 2020

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact