:/ does this have any practical application?
SQL is based on Set theory. http://seanmehan.globat.com/blog/2011/12/20/set-theory-and-s...
It's actually based on Relation theory, but Set theory is pretty much a requirement.
A Crash Course in the Mathematics Of Infinite Sets
21–30 of 30 posts
Re: A Crash Course in the Mathematics Of Infinite Sets
#22One 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 mismatc…
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.…
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.
Re: A Crash Course in the Mathematics Of Infinite Sets
#23Earlier quoted context omitted.
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 equat…
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
Re: A Crash Course in the Mathematics Of Infinite Sets
#24Earlier quoted context omitted.
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.…
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…
Thanks, I temporarily got CH and well-ordering mixed up.
Re: A Crash Course in the Mathematics Of Infinite Sets
#25Earlier quoted context omitted.
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 equat…
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.
Re: A Crash Course in the Mathematics Of Infinite Sets
#26One 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 mismatc…
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.…
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.)
Re: A Crash Course in the Mathematics Of Infinite Sets
#27The 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?
Re: A Crash Course in the Mathematics Of Infinite Sets
#28The 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…
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?
Re: A Crash Course in the Mathematics Of Infinite Sets
#29The 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…
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?"…
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.
Re: A Crash Course in the Mathematics Of Infinite Sets
#30Earlier quoted context omitted.
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?"…
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…
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.