Wikipedia:Reference desk/Archives/Mathematics/2009 December 2

Welcome to the Wikipedia Mathematics Reference Desk Archives
The page you are currently viewing is an archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

December 2

Sets and the absolute infinite

The question "Infinity" was removed and Trovatore said something that made me think of my life long problem: infinity. I never truely understood what infinity is. What exactly is the "absolute infinite"? Is it just an ontological/philosophical notion? From in the article "absolute infinite", I quote

"More generally, as noted by A.W. Moore, there can be no end to the process of set formation, and thus no such thing as the totality of all sets, or the set hierarchy. Any such totality would itself have to be a set, thus lying somewhere within the hierarchy and thus failing to contain every set."

I agree with this; even if we do away Russell's paradox by not allowing arbitrary set formation there still can't be a "collection of everything". But then I don't understand what the class of all ordinals means (sorry I've yet to properly study set theory; I will soon). Does it mean all ordinals in a model of ZFC? But then how we construct the von Neumann universe, which requires (at least I think) the presupposed notion of "all ordinals"? Can someone please explain this to me when the I hear the word infinity I can't stop thinking because I don't understand it and it's quite painful! Money is tight (talk) 01:28, 2 December 2009 (UTC)

Well, this is a somewhat controversial point. But from a realist point of view, or at least one realist point of view, "the class of all ordinals" is a linguistic convenience, not a name for an object. It is not possible to collect all the ordinals into a completed totality — if it were, that totality would have to be an ordinal itself, and then you have the Burali-Forti paradox.

It is not actually necessary to have "all ordinals"; all you need is the predicate "is an ordinal". That allows you to understand the predicate "is a set" according to the construction of the von Neumann hierarchy. --Trovatore (talk) 01:43, 2 December 2009 (UTC)

I have studied a lot of mathematics, and currently I work as a math teacher. But I have never found the concept of infinity to be odd in any way. As I wrote in the now removed section, most students first come across the concept when discussing limits. For instance,

$\lim _{x\to \infty }{1 \over x}=0$

because $1/x$ gets closer and closer to 0 as $x$ gets larger and larger, i.e., for every tolerance $\epsilon >0$, there is a $\omega$ such that $x>\omega \Rightarrow |1/x|<\epsilon$, or in words: if $x$ is chosen sufficiently large (greater than ω), than the distance between $1/x$ and 0 can be made arbitrarily small (smaller than the tolerance ε).

You might also consider sets. The number of elements in the set {apple, car, boy} is three, and the number of positive integers {1, 2, 3, ...} is infinite. What's the magic? (Note: I am not familiar with the concepts of the "Neumann universe", and the article absolute infinity seems to me, at a first glance, be more about philosophy/religion than about mathematics.) --Andreas Rejbrand (talk) 01:45, 2 December 2009 (UTC)

With respect, Andreas, I think you may be missing some of the prerequisites to follow Money is tight's question, which is in a set-theoretic context. Have a look at our articles on ordinal number, von Neumann hierarchy, proper class. --Trovatore (talk) 02:03, 2 December 2009 (UTC)

One can speak of collections of sets, like the collection ω of all natural numbers (coded as finite ordinals). In ZFC, the collection ω is a set which implies it satisfies certain properties, namely the axioms of ZFC. One can also speak of the collection of all ordinals. That collection necessarily cannot satisfy the axioms of ZFC, so it is not a set. It is still a perfectly good collection; a collection that isn't a set is called a proper class. Tim Gowers (iirc, I can't find a link right now) made an analogy to a library where you can go check out books. The library has certain rules about what exact subcollections of books you could check out--for example, you can check out all 9 of the library's Abraham Lincoln biographies, but you can't check out every book in the library at the same time. Most users don't care about the exact rules as long as they can check out the books that they want to read. The non-checkoutable subcollections correspond to proper classes, and most of the time, only "library theorists" (resp. set theorists) have to worry about them. NBG set theory is a version of set theory (a conservative extension of ZFC) that handles classes formally. 67.117.145.149 (talk) 04:06, 2 December 2009 (UTC)

NBG has a satisfactory interpretation where you treat class variables as standing for predicates, and do some sort of metalinguistic translation to figure out what the formulae are really saying. Treating classes as real objects is problematic, because it's not clear why they shouldn't be sets.

The coherent realist account is to treat all objects that occur in the von Neumann hierarchy as sets, and to consider proper classes as a linguistic convenience for discussing predicates, not as collections of individuals at all.

At first glance this may appear restrictive, like we don't want to look at certain things. But it's actually not. Suppose we say, at some point we have all the sets, and the collection of all those is a proper class. OK. But now we want to look at the "powerclass" of that class, and keep on going, making a new meta-hierarchy above that. And perhaps then we finish that meta-hierarchy, close it off, and keep going.

The realist says, I don't really see any important difference between your classes and hyperclasses and so on, and sets. So this is what I'm going to do: I'm going to use the word set to refer to anything that occurs anywhere in your hierarchies and meta-hierarchies and so on.

Then we look back and realize that, every time you thought you had jumped from sets to classes or hyperclasses to hyperhyperclasses or whatever, all you had actually done was find a level of the von Neumann hierarchy at the level of some inaccessible cardinal.

But what about the collection of all the realist's "new sets", revalued to include everything proposed as part of the hirarchies and superhierarchies? Well, that collection does not exist at all, as an object. It can't, under pain of the paradoxes. But it does exist as a linguistic convenience, standing in place of a predicate. And now we're back to the "coherent realist account" I mentioned in the second paragraph. --Trovatore (talk) 04:22, 2 December 2009 (UTC)

Thanks for your answer. I will use the word "absolute infinite" to mean the concept of non-ending set formation. Do you mean this: first envisage a collection of ordinals with no largest element (so we can think of the collection as a limit ordinal, I don't know why it also has to be an inaccessible cardinal). Then we construct the von Neumann universe regarding this collection as "all ordinals". So when you said "every time you thought you had jumped from sets to classes or hyperclasses to hyperhyperclasses or whatever, all you had actually done was find a level of the von Neumann hierarchy at the level of some inaccessible cardinal", do you just mean the absolute infinite of ordinals? In article von Neumann hierarchy it says V(inaccessible cardinal) is a model for ZFC, and I had a look at the article "large cardinal" in the section Motivations and epistemic status, and I think we can regard a collection of ordinals that's also also an inaccessible cardinal as "all the ordinals" in defining the hierarchy. Of course we can "add a lot more ordinals", but since they are absolutely limitless we must stop somewhere. Is it like that? Money is tight (talk) 00:24, 3 December 2009 (UTC)

To be honest I'm not entirely clear what you're asking here. I'll have to read it more carefully at some later time to figure out how to respond. --Trovatore (talk) 00:58, 3 December 2009 (UTC)

I knew I was too confusing. Here's my problem: when a young child is first taught what an apple is, he'll make the conclusion that there's a set of all apples. However, what he really means is the set of all apples on Earth, with Earth itself acting as a bounded domain that we imagine beforehand (in contrast to Cantor "absolute infinity"). When we first see the definition of sets, we make the naive assumption that there's a set of all sets, or class of all sets to avoid paradoxes. But this requires we imagine a domain containing "everything", including urelements, objects of the real world and of course, itself. Then we "pick out" from this domain the things that are sets. It's clear this domain cannot exist because it would be subject to Cantor's paradox. Now I think no one really understand what the "absolute infinite" is, because any attempt to understand it requires us to visualize something in our mind, and anything we visualize has the property that it's a "bounded domain/totality".

If the class of all sets is defined to be the von Neumann universe in order to avoid the above problem, then I don't understand the following. Ordinals are defined to be a set that's well ordered by membership relation. Hence I interpret the class of all ordinals to mean the collection of sets in the class of all sets that are ordinals. Then somehow we define the von Neumann universe as the class of all sets, which is to me circular. Thanks for any help Money is tight (talk) 23:20, 3 December 2009 (UTC)

Ah, OK, now I think I see. You're right, in a lot of common presentations, this is circular. It ceases to be circular once you have an intuitive notion of "ordinal" that doesn't depend on your notion of "set". I think that quite possibly set theory courses could profitably start by discussing ordinals at an informal level, before sets are even introduced. (In fact this is also reasonably historical — Cantor had a notion of ordinal, and as far as I know, he never represented them as sets at all.)

My personal experience is that ordinals clicked into place as something distinct from sets at least partly in response to a piece in Gödel, Escher, Bach, called the Birthday Cantatatata. While there are certainly things in GEB I don't agree with, even some I'd characterize as flat errors, it's a marvelously enjoyable work, and that particular piece has the very strong merit (even though it's not its main purpose!) of making the ordinals very intuitive. --Trovatore (talk) 23:36, 3 December 2009 (UTC)

A strange puzzle

A camel has 3000 bananas which it needs to get to the market 1000 miles away. The camel can only carry 1000 bananas at once, and it must eat 1 banana for each mile it travels. The camel is allowed to leave some bananas on the ground and come back for them later, or the puzzle would be impossible. What is the maximum number of bananas that the camel can get to the market?

I've been able to get 533 bananas, but I haven't been able to show that there isn't any method to get more. What is the maximum amount and how do you get it? Also, how do you know there isn't a way to get more than that amount? --70.250.212.43 (talk) 01:41, 2 December 2009 (UTC)

This is the Jeep problem. Staecker (talk) 02:06, 2 December 2009 (UTC)

It's not exactly the same; the Jeep problem requires you to travel as far as possible with a specific amount of fuel, but the camel problem requires you to get to a specific point with as much left as possible. The problems are similar, but not identical. --70.250.212.43 (talk) 02:12, 2 December 2009 (UTC)

You're right- not exactly the same. Another difference is that one involves a camel and the other involves a jeep. The reasoning and solutions are more or less the same though. Staecker (talk) 02:15, 2 December 2009 (UTC)

Indeed. Work out maximum "cross the desert" distance for initial 3000 bananas using second variant of jeep problem, subtract 1000 miles from this, and this is the number of bananas that the camel has left when it reaches the market. If bananas are divisble then exact answer is 1000 x 8 / 15 = 533 1/3 bananas; if bananas are indivisble then this rounds down to 533 bananas. One of the references in the article may have a proof. Gandalf61 (talk) 11:27, 2 December 2009 (UTC)

Does this problem get more interesting (and less Jeep-like) if, say, there are 4k bananas? --Tardis (talk) 17:01, 2 December 2009 (UTC)

676 4/21 bananas if bananas are divisible; 675 bananas if they are indivisible. Maybe there is a way to get the indivisible solution up to 676, but I can't see it. Gandalf61 (talk) 17:14, 2 December 2009 (UTC)

[self-reply; edit conflict] Hmm. I think the same "you'll need this cache $2n-2k-1$ times" logic gives us 71000/105 (676) bananas from 4k; I'm not sure how one proves such an answer optimal. So that's not too different, but what if you have some large number of bananas (maybe 100k)? Does it at some point become beneficial to simply solve the problem twice, or does the 1k penalty for having to walk back to base to start over always prevent that? It just seems bizarre that the correct answer would end up involving "go 20 feet; lay down all but 0.007576 bananas; go back". Moreover, something interesting probably happens sooner, when you ought to be able to carry more than 1k to market and you have to leave some caches to come back and get after having delivered some to market. I think the "go x distance" variant may be more interesting than we give it credit for, at least if x isn't too close to the maximum distance you could go anyway. --Tardis (talk) 17:17, 2 December 2009 (UTC)

[self-reply-reply] I guess it doesn't get any more interesting: with, say, 8k bananas, you find that you want to place the 7th cache at 46027/45045=102.2% the distance to the target, so you just go to the target instead and drop off everything you don't need to return to the 6th cache, which is 41003/45045=91.0% of a full load. Then you do the last run and deliver another 43024/45045=95.5% of your maximum carrying capacity, for a total delivery of 186.5% of a load (which is still just 23.3% of the total!). I was imagining that you would lay down large caches near the goal and almost start the problem in reverse from there, but it doesn't seem helpful. Since you know how many times you must set out from base, you just apply the (crossing) jeep problem as if you were going to go much farther, and repeatedly deliver to the other side. Still, no proof occurs to me that this is optimal (except the non-rigorous idea that the harmonic progression is the most efficient in one problem and is thus probably the most efficient otherwise). --Tardis (talk) 17:35, 2 December 2009 (UTC)

Sorry, I don't follow your 8k solution. I think the 6th cache is at 31012/45045=68.85% of the distance to the target, and the camel initially leaves 3/5 of a load there. On the 7th run the camel takes 1/5 of a load from this cache on the way out, which tops him up to a full load. He then uses 14033/45045 of the load to get to the market, delivers 16979/45045 of a load, returns to the 6th cache with the remaining 14033/45045 of his load, takes another 1/5 of a load from the 6th cache, and so returns home via the other caches. On the 8th trip the camel takes the final 1/5 of a load from the 6th cache, which tops him up to a full load, uses 14033/45045 of this load to get to market, and delivers 31012/45045 of a load. Total amount delivered to market is (16979+31012)/45045 = 47991/45045 = 106.54% of a load. How do you manage to deliver 186.5% of a load ? Gandalf61 (talk) 10:08, 3 December 2009 (UTC)

No, you're exactly right. Instead of $\sum _{n=2}^{7}{\frac {1}{2n+1}}$, I used $\sum _{n=1}^{6}{\frac {1}{2n+1}}$, leaving off the first intercache distance rather than the last. My error was disguised by the fact that I got the 7th cache's nominal location correct, since it didn't involve leaving off anything. --Tardis (talk) 15:22, 3 December 2009 (UTC)

The Jeep problem does not have the proof that the solution given is indeed the best strategy. How can one prove that there are no strategies better? (Igny (talk) 02:32, 4 December 2009 (UTC))

You can find a proof in Fine's original paper here. It takes about four pages. — Emil J. 15:10, 4 December 2009 (UTC)

Absolute Levi-Civita

Is there a name for $|\varepsilon _{ijkl\dots }|$, a simplification of the Levi-Civita symbol? It's some sort of dual to the Kronecker delta (not the multivariate version given in the article), which is 0 if any indices differ (or else 1), where this is 0 if any indices match (or else 1). (Clearly for two indices it's merely $1-\delta _{ij}$.) --Tardis (talk) 21:53, 2 December 2009 (UTC)

I've never heard of a name for it. Things only get named if they get used - does that symbol have any uses? --Tango (talk) 01:05, 3 December 2009 (UTC)

For instance, you may wish to express the expansion of the permanent of a matrix as a sum of $\scriptstyle \prod _{i=1}^{n}a_{i,\sigma _{i}}$, over all $\scriptstyle (\sigma _{1},\dots ,\sigma _{n})\in \{1,\dots ,n\}^{n},$ weighted with $|\varepsilon _{\sigma _{1},\dots ,\sigma _{n}}|.$ --pma (talk) 09:20, 3 December 2009 (UTC)

You could, but isn't that exactly the same as doing it over all $\scriptstyle (\sigma _{1},\dots ,\sigma _{n})\in S_{n}$ with no weighting? --Tango (talk) 12:20, 3 December 2009 (UTC)

Yes. --pma (talk) 13:16, 3 December 2009 (UTC)

So not a very useful use, then. --Tango (talk) 14:51, 3 December 2009 (UTC)

Well, sometimes there are good reasons for writing a sum or an integral on a subset S of a set R as a sum or integral on R weighted with the characteristic function of S. But, of course, even in that case, it doesn't mean that one needs to give a name to the characteristic function. --pma (talk) 16:15, 3 December 2009 (UTC)

My use: I have a complicated expression that may be paraphrased as ${\frac {\partial }{\partial x_{i}}}\sum _{j}\sum _{k\neq j}\sum _{l\neq j,k}x_{j}^{2}x_{k}^{3}x_{l}^{4}=\sum _{j}\sum _{k\neq j}{\Big (}\sum _{l\neq j,k}(\delta _{ij}2x_{j}x_{k}^{3}x_{l}^{4}+\delta _{ik}3x_{j}^{2}x_{k}^{2}x_{l}^{4})+|\varepsilon _{ijk}|4x_{j}^{2}x_{k}^{3}x_{i}^{3}{\Big )}$. I'm not sure (and I'm not asking, of course) if that's the best way to write it, or if it should be something like $2x_{i}\sum _{j\neq i}\sum _{k\neq i,j}x_{j}^{3}x_{k}^{4}+3x_{i}^{2}\sum _{j\neq i}\sum _{k\neq i,j}x_{j}^{2}x_{k}^{4}+4x_{i}^{3}\sum _{j\neq i}\sum _{k\neq i,j}x_{j}^{2}x_{k}^{3}$ instead, with more summation symbols but fewer different indices and no Kronecker deltas or Levi-Civitas. I'm not claiming it's a common need, but that's what inspired me to ask the question. --Tardis (talk) 20:35, 3 December 2009 (UTC)