Need help with an impossible discrete math problem.

- anonymous

Need help with an impossible discrete math problem.

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- katieb

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- anonymous

##### 1 Attachment

- anonymous

@amistre64 @KingGeorge
Anyone know how to do this problem?

- amistre64

why does fermats little or last thrm ring a bell here ... must be that exponent business.
Do you recall the relationship between the order of a set, and the order of its power set?

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- anonymous

all I know about power sets is that a power set is the set of all subsets

- amistre64

yes, and there is a relationship between the number of elements from A to P(A)

- amistre64

2^(n-1) if memory serves

- amistre64

since it says for ALL nonempty finite sets ... try a small one

- anonymous

So a set with only one number?

- anonymous

I don't understand what the A-OK is suppose to mean

- amistre64

A set is A-OK if it is a subset of the Power set ...

- amistre64

spose A = {1,2,3}
P(A) = {{},{a},{b},{c}, ... , {a,b,c}}
S is A-OK if it is a subset .. contains some or all of the elements of P(A)

- anonymous

So it is basically asking: For all nonempty, finite sets A, is there a subset of the Power set S with |S| = d^(|A|-1)

- amistre64

lol, i was thinking abc and wrote 123

- anonymous

haha

- amistre64

yes

- amistre64

..and my times up for today. they are closing shop :/ good luck

- anonymous

uh oh, ok thanks for the help!

- anonymous

So would I need to find what the power set S is equal to then?

- KingGeorge

Find what \(P(S)\) is, is pretty straightforward. We need to find very specific subsets. Give me a couple minutes and I'll see if I come up with anything clever.

- anonymous

ok cool

- KingGeorge

Well, I haven't come up with anything too clever, but I think I have a solution. It requires a set of at least 4 elements, so it'll take a bit of time to type up. Hold on while I type it up.

- anonymous

awesome

- KingGeorge

First, here's the set of 4 elements \(\{a,b,c,d\}\), and here's a list of elements in the power set\[\emptyset\]\[\{a\},\,\{b\},\,\{c\},\,\{d\}\]\[\{a,b\},\,\{a,c\},\,\{a,d\},\,\{b,c\},\,\{b,d\},\,\{c,d\}\]\[\{a,b,c\},\,\{a,b,d\},\,\{a,c,d\},\,\{b,c,d\}\]\[\{a,b,c,d\}\]

- KingGeorge

What I want to show, is that you can't choose 8 of these such that each set is pairwise disjoint. This will show prove that for part \(a\), the answer is no. Do you see why?

- anonymous

not really =\

- KingGeorge

Well the size of the original set is 4. So if the answer to part a was yes, then we should be able to find a subset \(S\) of the power set of size \(2^{4-1}=8\) such that every element in that set has a trivial intersection with any other element.
So if there is no such set in this case, then we've clearly proved that the answer is no.
Did this help clear up any confusion?

- anonymous

Ah ok, I think it makes sense now. So you use the relationship between the number of elements from A to P(A) in order to show that each element intersects with another element?

- KingGeorge

That's a really strange way of saying it, but I think you have the idea.

- anonymous

ok, haha

- anonymous

So we have not yet showed that there is not an A-OK set S with |S| = d^|A|-1, right?

- KingGeorge

No. The next step we have to do a case by case analysis.

- KingGeorge

Case 1: Suppose that \(\{a\}\in S\). Then we cannot choose any other set with the element \(a\). So if we're trying to minimize the number of new letters, we should add \(\{b\}\). We repeat the same process, and so far, we have \[S=\{\{a\},\{b\},\{c\},\{d\}\}.\]From here, we can not add any other set that contains the letter \(a,b,c\) or \(d\). So we add the final element, and that's \(\{\emptyset\}\). So we have 5 elements in \(S\). This is clearly less than the 8 we want.
Case 2: Now suppose we start by adding \(\{a,b\}\). Here, we're even worse off as we already taken up two elements in a single set! You can work it out if you want, but this will lead to a maximum of 4 elements.
Case 3: We start with \(\{a.b.c\}\). Again, this is even worse, so again, we clearly will not reach 8 elements in the set S.
Finally, Case 4: We start with \(\{a,b,c,d\}\). Again worse. In this case, we can only add \(\{\emptyset\}\) to get two elements. Not 8.

- KingGeorge

So if this all made sense, you should be able to see why the answer to part a is no. This proves (in an unelegant way) that for a set of size 4, we can not satisfy the hypotheses, so the answer must be no.

- anonymous

So if we had more elements in the original list like 7 and added the 0 the answer would be yes. However in this case we can only get 5 elements at the most. Yeah, that makes sense.

- anonymous

And laying out all the cases proves that.

- KingGeorge

Correct. But if we had 7 elements, then we would need to be able to get a set of size \(2^{7-1}=64\), and not 8. So yes, in this case, we can get at most 5.

- KingGeorge

Now let's look at part b. This is just asking for the existence of a single case. So while it's obviously false for the general case (because of part a), there might be a special case where it works.

- anonymous

Couldn't the only special case be an empty set?

- KingGeorge

That's an excellent special case to choose. Although it's not the only one you could have chosen (set of size 1 and 2 would also work), that's a perfectly fine case to use.
So let the original set be \(\emptyset\). What is the power set of that?

- anonymous

I'm not sure, 0?

- anonymous

so yeah, P(∅)={∅}

- KingGeorge

Kind of. The power set of the empty set is a little strange. But it's actually \(\{\emptyset\}\). The set with the empty set in it. So we have exactly two choices for the set \(S\).
1. \(S=\emptyset\). (this has size 0)
2. \(S=\{\emptyset\}\). (this has size 1).

- KingGeorge

Obviously, we want to choose the larger S. Now let's take a step back, and see what number we had to be greater than.
Our original set had size 0, so we need more than \(2^{0-1}=\frac{1}{2}\) elements in \(S\). So if \(S=\{\emptyset\}\), it works!

- anonymous

ah, I see, that makes sense!

- anonymous

and that would be the final answer then. :)

- anonymous

Thank you so much for the help!

- KingGeorge

Excellent. So for part b, the answer is actually yes, despite what our instincts say after part a.

- anonymous

Right, looks great.

- anonymous

Could I get your thoughts on one more thing real quick?

- KingGeorge

Sure.

- anonymous

Ok it is a question without really an answer, I'm just suppose to write something "smart" for the solution.
Let R be the set of all sets that are not elements of themselves. Is R an element of itself?

- anonymous

Seems like a paradox to me

- KingGeorge

that thing right there, is called Russell's paradox, and almost single-handedly led to the creation of the set theory you're familiar with today. My best suggestion for you, if you want to come up with a working answer, is to think outside of set theory entirely. Or come up with a good enough reason for why it shouldn't be possible to create that set.

- anonymous

Ah ok! I just looked it up on Wikipedia I'll do some research on it and see what I can come up with. :)

- anonymous

Thanks again for all the help.

- KingGeorge

No problem.

Looking for something else?

Not the answer you are looking for? Search for more explanations.