Wikipedia:Reference desk/Archives/Mathematics/2012 September 18

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.

September 18

The continuum and cardinality

Hi. Not homework, but this is something I'm curious about. It is easy to show that R and (0,1) have the same cardinality, by taking the function f: (0,1) ↔ R f(x) = tan[π(x-1/2)] which clearly is a bijection. How would one show that (0,1) and [0,1] have the same cardinality, by a similar argument (constructing a function)? Thanks. 24.92.74.238 (talk) 00:33, 18 September 2012 (UTC)

Well, it can't be quite that simple, because (0,1) and [0,1] are not homeomorphic (for example, [0,1] is compact, and (0,1) is not). So the function can't be bicontinuous. But you can find a general method for doing that sort of thing at Schroeder-Bernstein theorem. Someone may be able to give a cleverer answer. --Trovatore (talk) 01:12, 18 September 2012 (UTC)

I don't know about clever, but here's another: map $1/n$ to $1/(n+1)$ and $-1/n$ to $-1/(n+1)$ for $n$ a positive integer, and leave every other point fixed. This is a bijection from [0,1] to (0,1).--2404:2000:2000:5:0:0:0:C2 (talk) 03:05, 18 September 2012 (UTC)

That's not quite a map from one of the sets to the other, but the general idea works. Essentially if you have an infinite set M and a finite or countable set S then to find a bijection between M and $M\cup S$ you take a countable set $L\subset M$ and construct a bijection from L to $L\cup S$ using the idea of Hilbert's Hotel, a construction that uses the enumeration of L like the 2404 IP above has suggested. —Kusma (t·c) 07:41, 18 September 2012 (UTC)

Whoops, for some reason I was thinking [-1,1] instead of [0,1].--121.73.35.181 (talk) 08:06, 18 September 2012 (UTC)

Just define a sequence in (0, 1), e.g. $(a_{n})_{n\in \mathbb {N} ^{+}}=1/(n+1)$ and shift it by two positions. The two endpoints of [0, 1] then land in the two just released points:

$f(x)={\begin{cases}a_{1}&{\mbox{ if }}x=0\\a_{2}&{\mbox{ if }}x=1\\a_{i+2}&{\mbox{ if }}x=a_{i}\\x&{\mbox{ otherwise}}\end{cases}}$

CiaPan (talk) 09:04, 18 September 2012 (UTC)

Some people think I am homeomorphic, but I am actually bicontinuous. μηδείς (talk) 18:50, 18 September 2012 (UTC)

Complexity class of minimalist pangram construction

Some time ago, I solved a word puzzle which asked the puzzler to find the minimal number of names necessary out of a given list of 100 names to construct a pangram. I was able to solve the problem without too much difficulty by inspection alone; what I did was I looked for the least common letters, which appeared in only a few names, and then worked backwards from the names containing the least common letters to construct the minimal pangram.

I was thinking some more about the problem, and while the 100-name problem was easy to solve manually, I suspect that the same problem with large inputs might be quite difficult, even for a computer.

Consider the following generalized version of the problem:

You have an alphabet consisting of c characters and a list of s strings of variable lengths which altogether contain at least 1 of every character of the alphabet. Your task is to construct a minimalist (defined as requiring the fewest possible strings) pangram out of those strings.

The difficulty is the "minimalist" part. It is fairly easy to construct a pangram; indeed, you can easily see that there is an upper bound of c on the number of strings required, as, at most, you need one string that represents each character of the alphabet. The lower bound, though, seems very hard. The algorithm I outlined above of working backwards from least common letters seems extremely inefficient when c and s are large numbers, as the branching factor of possibilities is so large even after minimizing the tree by working starting from the least common letters. It can heuristically produce a close-to-minimal pangram very quickly, but the absolute minimal pangram with that approach would require going through that entire huge tree.

So my question is, does anyone know the complexity class of this problem? Is this pangram-construction problem a well-known problem in the literature which already has many papers written on it? If so, does Wikipedia have an article on it? (Perhaps linked somewhere from list of NP-complete problems, if my intuition that the problem is computationally difficult is correct; there are so many problems in that list, and I don't really know what to look for.) Or perhaps I am overestimating the difficulty of the problem, and some efficient algorithm is known; if so, how does that efficient algorithm work?

—SeekingAnswers (reply) 02:43, 18 September 2012 (UTC)

Assuming that there are no grammatical constraints on the sentence, it's a set cover problem. 130.188.8.27 (talk) 10:14, 18 September 2012 (UTC)

That's it, exactly! Thanks. —SeekingAnswers (reply) 03:37, 22 September 2012 (UTC)

see humanities reference desk

i'm asking purely in terms of elegance and what is a good definition. i understand the current definitions. 80.98.245.172 (talk) 19:02, 18 September 2012 (UTC)

Summarizing the question stated there: If the count of hours turns over at 12:00 and the count of months turns over at 1/1, one of them must be wrong, so which is it? —Tamfang (talk) 20:11, 18 September 2012 (UTC)

Inconsistent, yes. Wrong, no. Mathematicians cannot agree on whether to start the natural numbers at 0 or 1. Dbfirs 20:21, 18 September 2012 (UTC)

You misspelled "some people, even some mathematicians, erroneously start the natural numbers at 1". Hope this helps. --Trovatore (talk) 22:34, 18 September 2012 (UTC)

Naturally! — but only in the last 200 years. I recall a lecturer who insisted on using "zeroth" when most people said "first". Dbfirs 07:16, 19 September 2012 (UTC)

I happen to know what question you folks are talking about, because I participated in the responses. But in general, please provide a link to whatever it is you're referring to. The above would completely bamboozle many people. -- ♬ Jack of Oz ♬ ^{[your turn]} 22:14, 18 September 2012 (UTC)

Agreed, but I wish you would have provided the link, rather than just complain about the lack of one. Here it is Wikipedia:Reference_desk/Humanities#Either_the_Calendar_is_wrong_or_the_Clock_is._It.27s_that_simple.. StuRat (talk) 22:18, 18 September 2012 (UTC) *

Have to agree, an RD star for that one, as actually providing the needed link. μηδείς (talk) 22:22, 18 September 2012 (UTC)

I wanted to explain why it's important for the instigator of the thread, or the first respondent, to provide a link in these circumstances. I wasn't complaining per se. I identified the issue and suggested a solution. Now, I'm in trouble. Interesting. And someone who did actually complain gets a star. Interesting. -- ♬ Jack of Oz ♬ ^{[your turn]} 22:30, 18 September 2012 (UTC)

This reminds me of the debate over where computer arrays should start counting. In Fortran, they traditionally start with one, so the first object in the array is the first element: ARRAY(1). In C, they start counting at zero, so the first object in the array is the zeroth element: ARRAY(0). (The C convention does makes sense in terms of the first element having a zero offset, however.) StuRat (talk) 22:25, 18 September 2012 (UTC)

Anything that involves modular arithmetic is a nuisance when arrays start at 1, and, as you say, in languages where actual memory locations and offsets are visible, it makes sense for the first element to be at offset zero. Other than that, I cannot think of any situation where arrays starting at 0 are helpful from a programmers' perspective. 86.176.210.77 (talk) 00:08, 19 September 2012 (UTC)

I'm taking an online computer class at UC Berkeley, and they have 4 quizzes, called Quiz 0 through Quiz 3. I'm serious. :-) StuRat (talk) 04:36, 22 September 2012 (UTC)