How can you organize this meeting with infinitely many people?

Question

You manage a gang with infinitely many gangsters. Each gangster in the gang has a finite number of enemies who will try to kill him if they meet. This hatred relation is commutative: whenever A wants to kill B, B wants to kill A.

You want to organize a meeting with infinitely members of the gang, but you want to avoid shoot-outs. So, you have to choose the gangsters in such a way that no 2 gangsters are enemies. How can you do that? What's the choice algorithm?

Does this require the axiom of choice?

To Jeredwm: Great answer! I just think there's a small point we should take into account. Since each gangster has a finite number of enemies, this doesn't rule out the possiblity that some gangsters have no enemy at all, so 0 enemies. I think this can be patched if we slightly modify the function M, extending it's domain to N0 = {0, 1,2,3.....}, defining g(0) as a vitual gangster that's an enemy of all other gangsters in the gang and defining the rule:

Let j be the largest number in N0 such that g(j) is an enemy of of g(i). Then,

M(i) = g(i,) If j = 0
M(i) = j, if j > 0,

Right?

Why did you remove your remark about the axiom of choice? It was OK, wasn't it?

If M(i) issuch that g(j) is an enemy of of g(i), if j > 0

Answer 1

[NOTE: the below is a unified version of my previous response together with my previous edits, just to enhance readability.]

No, the axiom of choice is not required.

I'm assuming that the enemies are *within* the gang; otherwise the problem doesn't make any sense.

The fact that there are "infinitely many" gangsters means precisely that there exists a 1-1 function from the natural numbers into [not necessarily onto] the set of gangsters. Let's call this function g(i).
(Note that g(N) is a countable subset of the set of gangsters; that's fine, as we'll be producing a countable set of "friendly" gangsters.)

Now, define a function M(i): N->N, by the following rule: "M(i) is the largest number j such that g(j) is an enemy of of g(i)." In other words, g(M(i)) is an enemy of g(i)'s, but g(j) is NOT an enemy of g(i) for any j > M(i). (Note this is possible since there are only finitely many enemies for each gangster.)***

Now, you can invite g(1), g(M(1)+1), g(M(g(M(1)+1))+1), etc. Or, to express this iteratively,
1. Invite g(1);
2. Any time you invite g(j), you can next invite g(M(j)+1) safely.

This guarantees a safe meeting of an infinite number of gangsters! (Details left to reader.)

*** TO Kernel: [...] Really, you should be a little less hasty with the thumbs-down.

[Apparently, Kernel deleted his response after seeing my rebuke to his objection.]

*** EDIT/COMMENT: 12/12/07 5pm edt
STEINER:

Actually, the best fix for the M function is this:
M(i) = max{ {i} u {j | g(j) is an enemy of g(i)} }.
Not only does this cover the case when the set of enemies is empty, but it also covers the case where all the enemies precede g(i) in the indexing.

I didn't delete my comment about the axiom of choice; I just incorporated it into the proof rather than leaving it as a comment afterwards. I stand by my statement that the axiom of choice is not required, as is demonstrated in the proof above.