Math Is Fun Forum

dchilow

Member

Registered: 2007-03-05

Posts: 27

I need help with Abstract Math due Monday 3/19.

Let A be the set of subsets of [n] that havew even size, and let B be the set of subsets of [n] that have odd size.  Establish a bijection from A to B, thereby proving that |A| = |B|. (Such a bijection is suggested below for n=3.)

A  {empty set, {2,3}, {1,3}, {1,,2}}
B  {    {3}   ,   {2} ,   {1} ,  {1,2,3}}

Someone out there please know what this stuff is.

Last edited by dchilow (2007-03-14 06:05:35)

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: I need help with Abstract Math due Monday 3/19.

The map suggested is simply mapping a set of even size to the same set with the last element removed.  Make sure to order your sets which will save you from duplication.  Note that this mapping leaves the very last element in your parent set unmapped to, so simply map the null set to this.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: I need help with Abstract Math due Monday 3/19.

No it's not, that description only works for the middle two. That map seems to be just arbitrarily linking elements to each other, and while that works for that specific case, you couldn't use that in a general proof.

It's fairly easy to find a bijection for when n is odd, because then if you take a subset of [n] with an even number of elements, then the subset of [n] that contains all the elements that weren't in the first subset will have an odd number of elements. So you can just map each set to its complement.

Using the example of n=3 again, that would mean:

A: {empty set, {1,2}, {1,3}, {2,3}}
B: { {1,2,3}  ,  {3}  ,  {2}  ,  {1}  }

The case when n is even becomes a little trickier though. A bijection definitely exists, but I'm not sure how you'd define it.

Edit: Not worth bumping, but I realised a better answer so I thought I'd post it in case anyone decides to read this.

Instead of doing stuff with complements that will only work half the time, you map each set containing a 1 to the equivalent set that doesn't contain a 1.

eg.
{1, 2, 5, 6} --> {2, 5, 6}
{1, 3, 7}     --> {3, 7}
{2, 4, 9}     --> {1, 2, 4, 9}
etc.

The example in the first post does this, but it uses 3 instead of 1. I've changed it so that it will still work when n = 1 or 2.

Last edited by mathsyperson (2007-05-30 23:39:11)

---

Why did the vector cross the road?
It wanted to be normal.

Ricky

Moderator

Registered: 2005-12-04

Posts: 3,791

Re: I need help with Abstract Math due Monday 3/19.

Oh, right.  Not sure what I was thinking...

So here are the number of subsets of size k for n = 6:

k | number of subsets
-------------------------
0 | 1
1 | 6
2 | 15
3 | 20
4 | 15
5 | 6
6 | 1

Note that the palindromic property applies to all sets of size n, not just 6.

But the one thing to notice is that For any given odd k, there is no even k such that the number of subsets are the same.  So if there is a mapping, then it won't be from subsets of size a to subsets of size b, as this mapping can't be a bijection.

The complement was a great idea, mathsyperson.  However, for odd sized sets, I know of no natural operation which can be applied to a single even size subset which gives you a subset of odd size, or vice versa.  At least not one that can be a bijection.

But the defining characteristic of this mapping is that it sends some subsets of size a to subsets of size b, and some subsets of size a to size c.  So it must make the choice of where to send the subset to by something other than size.

---

"In the real world, this would be a problem.  But in mathematics, we can just define a place where this problem doesn't exist.  So we'll go ahead and do that now..."