Question

Need help with an impossible discrete math problem.

Answer 1

@amistre64 @KingGeorge

Anyone know how to do this problem?

Answer 2

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?

Answer 3

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

Answer 4

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

Answer 5

2^(n-1) if memory serves

Answer 6

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

Answer 7

So a set with only one number?

Answer 8

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

Answer 9

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

Answer 10

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)

Answer 11

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)

Answer 12

lol, i was thinking abc and wrote 123

Answer 13

haha

Answer 14

yes

Answer 15

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

Answer 16

uh oh, ok thanks for the help!

Answer 17

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

Answer 18

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.

Answer 19

ok cool

Answer 20

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.

Answer 21

awesome

Answer 22

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\}\]

Answer 23

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?

Answer 24

not really =\

Answer 25

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?

Answer 26

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?

Answer 27

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

Answer 28

ok, haha

Answer 29

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

Answer 30

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

Answer 31

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.

Answer 32

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.

Answer 33

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.

Answer 34

And laying out all the cases proves that.

Answer 35

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.

Answer 36

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.

Answer 37

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

Answer 38

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?

Answer 39

I'm not sure, 0?

Answer 40

so yeah, P(∅)={∅}

Answer 41

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).

Answer 42

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!

Answer 43

ah, I see, that makes sense!

Answer 44

and that would be the final answer then. :)

Answer 45

Thank you so much for the help!

Answer 46

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

Answer 47

Right, looks great.

Answer 48

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

Answer 49

Sure.

Answer 50

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?

Answer 51

Seems like a paradox to me

Answer 52

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.

Answer 53

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

Answer 54

Thanks again for all the help.

Answer 55

No problem.