7 ms·

A Crash Course in the Mathematics Of Infinite Sets

51 points by davesque 13y ago

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

Sniffnoy 13y ago
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.
- thejteam 13y ago
  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>>
  - hypersoar 13y ago
    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.
    - thejteam 13y ago
      Thanks, I temporarily got CH and well-ordering mixed up.
  - Sniffnoy 13y ago
    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.)
davesque 13y ago
A very dense and readable summary of some of the key concepts in set theory. Warning!! May cause mind-blowing.
losethos 13y ago
C:\TAD\Text\WEALTH.TXT lty distribution. Without any intervention of law, therefore, the private interests and passions of men naturally lead them to divide and distribute the stock of every society among all the different employments carried on in it; as nearly as possible in the proportion which is most agreeable to the interest of the whole society. All the different regulations of the mercantile system necessarily derange more or less this natural and most advantageous distribution of stock. But those which concern
jaekwon 13y ago
:/ does this have any practical application?
- recuter 13y ago
  http://mathoverflow.net/questions/10334/what-practical-applications-does-set-theory-have http://mathoverflow.net/questions/10334/what-practical-appli... You might enjoy: http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
- pfortuny 13y ago
  What about your question?
  - deleted 13y ago
    [deleted]
- jackmaney 13y ago
  http://ars.userfriendly.org/cartoons/?id=20070105 http://ars.userfriendly.org/cartoons/?id=20070105
- Sajaki 13y ago
  SQL is based on Set theory. http://seanmehan.globat.com/blog/2011/12/20/set-theory-and-sql-concepts/ http://seanmehan.globat.com/blog/2011/12/20/set-theory-and-s...
  - tel 13y ago
    It's actually based on Relation theory, but Set theory is pretty much a requirement.
DonGateley 13y ago
Is that all there is to it?
deleted 13y ago
[deleted]
- Sharlin 13y ago
  Please either define "exists" or formulate your claim without using the word :)
  - deleted 13y ago
    [deleted]
    - deleted 13y ago
      [deleted]
  - bachback 13y ago
    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-6 http://en.wikipedia.org/wiki/Georg_Cantor#cite_note-daub266-...
    - xcthulhu 13y ago
      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 https://en.wikipedia.org/wiki/Inaccessible_cardinal
      - 13y ago
3rd3 13y ago
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 http://en.wikipedia.org/wiki/Finitism
nimble 13y ago
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.
freefrancisco 13y ago
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?
- jfarmer 13y ago
  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?

51 points by davesque 13y ago

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

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.

thejteam 13y ago
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>>
- hypersoar 13y ago
  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.
  - thejteam 13y ago
    Thanks, I temporarily got CH and well-ordering mixed up.
- Sniffnoy 13y ago
  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.)

davesque 13y ago

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

losethos 13y ago

C:\TAD\Text\WEALTH.TXT lty distribution. Without any intervention of law, therefore, the private interests and passions of men naturally lead them to divide and distribute the stock of every society among all the different employments carried on in it; as nearly as possible in the proportion which is most agreeable to the interest of the whole society. All the different regulations of the mercantile system necessarily derange more or less this natural and most advantageous distribution of stock. But those which concern

jaekwon 13y ago

:/ does this have any practical application?

recuter 13y ago
http://mathoverflow.net/questions/10334/what-practical-applications-does-set-theory-have http://mathoverflow.net/questions/10334/what-practical-appli... You might enjoy: http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument
pfortuny 13y ago
What about your question?
- deleted 13y ago
  [deleted]
jackmaney 13y ago
http://ars.userfriendly.org/cartoons/?id=20070105 http://ars.userfriendly.org/cartoons/?id=20070105
Sajaki 13y ago
SQL is based on Set theory. http://seanmehan.globat.com/blog/2011/12/20/set-theory-and-sql-concepts/ http://seanmehan.globat.com/blog/2011/12/20/set-theory-and-s...
- tel 13y ago
  It's actually based on Relation theory, but Set theory is pretty much a requirement.

DonGateley 13y ago

Is that all there is to it?

deleted 13y ago

[deleted]

Sharlin 13y ago
Please either define "exists" or formulate your claim without using the word :)
- deleted 13y ago
  [deleted]
  - deleted 13y ago
    [deleted]
- bachback 13y ago
  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-6 http://en.wikipedia.org/wiki/Georg_Cantor#cite_note-daub266-...
  - xcthulhu 13y ago
    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 https://en.wikipedia.org/wiki/Inaccessible_cardinal
    - 13y ago

3rd3 13y ago

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 http://en.wikipedia.org/wiki/Finitism

nimble 13y ago

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.

freefrancisco 13y ago

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?

jfarmer 13y ago
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?