Wikipedia:Reference desk/Archives/Mathematics/2007 November 10

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.

November 10

Fractionj Boxes

in comes 1 out comees -289 un comes 31 out comes?

I forgot it and the rule was 289. —Preceding unsigned comment added by 24.255.112.68 (talk) 01:41, 10 November 2007 (UTC)

Set question

Is the following a valid set?

D = {2,4,6,8,10,12,2}

I've been reading Set and it says that this is the equivalent to:

D = {2,4,6,8,10,12}

I'm interested, because then the cardinality of the set D is 6. Would this also be correct? - Ta bu shi da yu 15:22, 10 November 2007 (UTC)

Yes, the top is a valid set. And it does, in fact, only contain 6 elements, no matter how many duplicates of the same elements you write, because written duplicates don't count toward the number of members of the set as there are no duplicates in sets, by definition. Usually, sets are written without duplicates so as not to confuse the reader. Gscshoyru 15:30, 10 November 2007 (UTC)

Cheers :-) I just read multiset, and it appears that the cardinality of the first set would be 7 if viewed as a multiset... have I understood that article correctly? - Ta bu shi da yu 15:53, 10 November 2007 (UTC)

Yes. Note, though, that multisets are not used nearly as much as sets. -- Meni Rosenfeld (talk) 16:02, 10 November 2007 (UTC)

That is because mathematicians appear to avoid the concept also when it is more appropriate than set or list. For example, the roots of a polynomial are a multiset, and a data "set" is often best viewed as a multiset; just think of computing averages. It doesn't help their popularity that there is no commonly understood notation for the multiset equivalents of {...} and ∪.  --Lambiam 18:45, 11 November 2007 (UTC)

If this were a true/false question on a test, I would put "false", {2,4,6,8,10,12,2} is not a valid set, because it contains duplicate elements, and sets do not. It's a silly semantic distinction, but I can't rationalize the correct answer being "true". —Keenan Pepper 18:49, 10 November 2007 (UTC)

No, the answer is true, and any teacher marking the answer as "false" should be looking for another job (or writing an angry letter to whoever is to blame for a directive to do so). A set is a collection of elements. Every object can either be an element of a given set, or not. There are many ways to write sets. One of them is as a bunch of stuff enclosed in braces, and it refers to the unique set containing everything inside the braces and nothing else. So, {2,4,6,8,10,12,2} denotes the set containing 2, 4, 6, 8, 10, 12, 2 and nothing else. The fact that we have chosen to mention twice that the set contains 2 alters nothing - it is still a set, one that also happens to be denotable by {2,4,6,8,10,12}. -- Meni Rosenfeld (talk) 19:22, 10 November 2007 (UTC)

I suppose a good way of looking at it is that the second set is a proper set with no written duplicates and the first is an improper set since it has a duplicate of 2. A math-wiki 10:47, 11 November 2007 (UTC)

No... The first is a perfectly proper set. It is just a clumsy way of writing that set. If we assume that every person, at birth, is allocated a given amount of characters he will type in his entire life, and dies when he finishes his allocation, then we have needlessly shortened our lifespan by writing this set in this way. But, as I said before - it is still a set. -- Meni Rosenfeld (talk) 11:42, 11 November 2007 (UTC)

I'll put it another way. It's not like "sets don't have duplicates, and if something has duplicates then it's not a set". It's that the concept of multiplicity doesn't have anything to do with sets, that is, sets don't recognize that such a thing as duplicates exist - it's not part of their existence. Hence, when the symbol {2, 2} is interpreted as a set, it doesn't have a "duplicate 2". It just denotes the set that has 2, has 2, and doesn't have anything which is neither 2 nor 2. Again, this is an obfuscated description of the set in question, but a valid one nonetheless. -- Meni Rosenfeld (talk) 13:30, 11 November 2007 (UTC)

Okay, here's a question that's not just silly semantics: Is there any set that can be expressed if elements are allowed to have duplicate representations (for example, as $\{f(x):x\in S\}$ where the function f is not guaranteed to be one-to-one), but that cannot be expressed (at least, not with our current mathematical knowledge) if each element must be listed exactly once? —Keenan Pepper 18:02, 11 November 2007 (UTC)

If f : S → T, that set comprehension means the same as {y ∈ T | ∃ x ∈ S · f(x) = y}. I'd say that each element is only "listed" once here.  --Lambiam 18:34, 11 November 2007 (UTC)

The question is pretty vague, and the answer can depend on how we choose to make it more precise. One possibility is, given a set S and a function f on S, must there be some set $D\subseteq S$ such that $f(D)=f(S)$ and f is one-to-one on D (so that our set can be described as $\{f(x)|x\in D\}$)? I think this is equivalent to (or at least a weaker version of) the axiom of choice. -- Meni Rosenfeld (talk) 18:54, 11 November 2007 (UTC)

Yes, that's equivalent (over ZF) to the statement that surjections have right inverses, and thus equivalent to choice. Algebraist 22:38, 11 November 2007 (UTC)

Whoa. Whoa. That's cool. —Keenan Pepper 23:02, 11 November 2007 (UTC)

I merely made that comparison to point out that there is a visual difference (though trivial) between the two. Of course they function the same and are in fact equivalent in most axiomizations of set theory (most notably in ZFC, but not in naive set theory). A math-wiki 03:00, 12 November 2007 (UTC)

Are you saying that in naive set theory (which, as the name suggests, is not a formal axiomatization), {2,4,6,8,10,12,2} and {2,4,6,8,10,12} are not the same set? Where did you get this idea? -- Meni Rosenfeld (talk) 16:36, 13 November 2007 (UTC)

Wow... I really set of a maths debate! - Ta bu shi da yu 12:53, 13 November 2007 (UTC)

If I recall correctly from reading the articles here on wikipedia, A set in naive set theory contains elements such as numbers, variables, letters, object names, whatever, ... not just explictly mathematical quantities. And furthermore each object in a set need not be distinct it could have 3 twos and six x's for example. Thus the two sets above are clearly not consider identical in naive set theory. Of course in ZFC there are consider the same due to (Axiom of choice??, not sure which axiom it is, but there obvious must be one.) A math-wiki 08:20, 14 November 2007 (UTC)

Did you even take a look at the article before posting this? True, elements in naive set theory can be non-rigorously-defined objects, but of course for any object there are just two possibilities, it is either an element of a set, or not. Our article contains the line "Repetition (multiplicity) of elements is irrelevant; for example, {1,2,2} = {1,1,1,2} = {1,2}."

As for ZFC, I don't think this is even an axiom (though the axiom of extensionality is closely related). It's merely the fact that the only binary predicate introduced by the language of ZFC is membership.

No intention to sound condescending, but seriously, do you even know what the axiom of choice is, seeing that you suggest it as an explanation of something? -- Meni Rosenfeld (talk) 13:12, 14 November 2007 (UTC)

I did a while back, not right before posting though. I see now that I must have not remembered that part correctly. And no I have not read the Axiom of Choice but from what I could grasp from it's prior mention in several places I suggested it might be what made that distinction. (hence the question marks) Again I was in error. A math-wiki 04:54, 15 November 2007 (UTC)

Yeah, the axiom of choice is interesting, but it is still not the ultimate answer to life, the universe, and everything... In particular, it is much more "advanced" than the triviality we have discussed here. -- Meni Rosenfeld (talk) 09:33, 15 November 2007 (UTC)

relatively prime integers

Please help me prove the following: Suppose a1|c, a2|c ... ak|c & (a1,a2,...,ak)=1 then a1a2...ak|c. I suppose all I have to show is that [a1,a2,...,ak]=a1a2...ak. This is clear for k=2 but I don't think it holds in general. --Shahab 18:31, 10 November 2007 (UTC)

a_1 = 6, a_2 = 10, a_3 = 15, c = 30. All three divide c, and their gcd is 1, but their product is greater than c and therefor does not divide it. Gscshoyru 18:41, 10 November 2007 (UTC)

Thank you. BTW is there any relation between (a1,...,ak) and [a1,...,ak]?--Shahab 19:08, 10 November 2007 (UTC)

Of course. If a set of numbers share a common divisor, then the least common multiple will be less than the products of the numbers in the set (say there are n elements) by dividing out (n-1) copies of each common prime divisor. SamuelRiv 19:19, 10 November 2007 (UTC)