anonymous
  • anonymous
Need help with an impossible discrete math problem.
Mathematics
  • Stacey Warren - Expert brainly.com
Hey! We 've verified this expert answer for you, click below to unlock the details :)
SOLVED
At vero eos et accusamus et iusto odio dignissimos ducimus qui blanditiis praesentium voluptatum deleniti atque corrupti quos dolores et quas molestias excepturi sint occaecati cupiditate non provident, similique sunt in culpa qui officia deserunt mollitia animi, id est laborum et dolorum fuga. Et harum quidem rerum facilis est et expedita distinctio. Nam libero tempore, cum soluta nobis est eligendi optio cumque nihil impedit quo minus id quod maxime placeat facere possimus, omnis voluptas assumenda est, omnis dolor repellendus. Itaque earum rerum hic tenetur a sapiente delectus, ut aut reiciendis voluptatibus maiores alias consequatur aut perferendis doloribus asperiores repellat.
katieb
  • katieb
I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!
anonymous
  • anonymous
1 Attachment
anonymous
  • anonymous
@amistre64 @KingGeorge Anyone know how to do this problem?
amistre64
  • 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
  • anonymous
all I know about power sets is that a power set is the set of all subsets
amistre64
  • amistre64
yes, and there is a relationship between the number of elements from A to P(A)
amistre64
  • amistre64
2^(n-1) if memory serves
amistre64
  • amistre64
since it says for ALL nonempty finite sets ... try a small one
anonymous
  • anonymous
So a set with only one number?
anonymous
  • anonymous
I don't understand what the A-OK is suppose to mean
amistre64
  • amistre64
A set is A-OK if it is a subset of the Power set ...
amistre64
  • 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
  • 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
  • amistre64
lol, i was thinking abc and wrote 123
anonymous
  • anonymous
haha
amistre64
  • amistre64
yes
amistre64
  • amistre64
..and my times up for today. they are closing shop :/ good luck
anonymous
  • anonymous
uh oh, ok thanks for the help!
anonymous
  • anonymous
So would I need to find what the power set S is equal to then?
KingGeorge
  • 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
  • anonymous
ok cool
KingGeorge
  • 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
  • anonymous
awesome
KingGeorge
  • 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
  • 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
  • anonymous
not really =\
KingGeorge
  • 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
  • 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
  • KingGeorge
That's a really strange way of saying it, but I think you have the idea.
anonymous
  • anonymous
ok, haha
anonymous
  • anonymous
So we have not yet showed that there is not an A-OK set S with |S| = d^|A|-1, right?
KingGeorge
  • KingGeorge
No. The next step we have to do a case by case analysis.
KingGeorge
  • 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
  • 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
  • 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
  • anonymous
And laying out all the cases proves that.
KingGeorge
  • 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
  • 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
  • anonymous
Couldn't the only special case be an empty set?
KingGeorge
  • 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
  • anonymous
I'm not sure, 0?
anonymous
  • anonymous
so yeah, P(∅)={∅}
KingGeorge
  • 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
  • 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
  • anonymous
ah, I see, that makes sense!
anonymous
  • anonymous
and that would be the final answer then. :)
anonymous
  • anonymous
Thank you so much for the help!
KingGeorge
  • KingGeorge
Excellent. So for part b, the answer is actually yes, despite what our instincts say after part a.
anonymous
  • anonymous
Right, looks great.
anonymous
  • anonymous
Could I get your thoughts on one more thing real quick?
KingGeorge
  • KingGeorge
Sure.
anonymous
  • 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
  • anonymous
Seems like a paradox to me
KingGeorge
  • 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
  • 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
  • anonymous
Thanks again for all the help.
KingGeorge
  • KingGeorge
No problem.

Looking for something else?

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