Problem 7: How many elements belong to the union of two sets, A and B? (Obviously, the answer won't be a number but in terms of some other things)
Problem 8: How many subsets does a set have including itself and the null set?
Saturday, June 18, 2011
Power Set
These problems have a different flavor and can be done independently of the others.
Problem 7: How many elements belong to the union of two sets, A and B? (Obviously, the answer won't be a number but in terms of some other things)
Problem 8: How many subsets does a set have including itself and the null set?
Problem 7: How many elements belong to the union of two sets, A and B? (Obviously, the answer won't be a number but in terms of some other things)
Problem 8: How many subsets does a set have including itself and the null set?
Subscribe to:
Post Comments (Atom)
Problem 7: Well, I guess it's the number of elements in A plus the number of elements in B minus the number of elements that are in both (the number of elements in their intersection).
ReplyDeleteProblem 8: Hmm by experimenting with pugs, dalmations, chihuahuas, and wolfhounds, it seems like it's a power of twos thing? It seems like if a set has n elements, it has 2^n subsets? But Why would this be? I feel like there's some combinatorics stuff breathing down my neck here, which makes me uncomfortable.
Problem 7: perfect.
ReplyDeleteProblem 8: You're right about the answer, and you're right about combinatorics. But there is no need to fear combinatorics. In fact, combinatorics is probably the only subject that is taught the way it should be since it is largely just a collection of neat problems. However, I've never had it so I don't feel comfortable teaching it on here. Maybe someday though.
Anyway, you're on the right track. Do you want a hint or do you want to kick it around for a little while longer?
To be honest, I thought I answered it already. (If a set has n elements, it will have 2^n subsets.) Or do you want an explanation/proof why as well?
ReplyDeleteI'm not sure how to even start with making a proof of this. The immediate "why" that I see concerns truth tables in logic. Imagine three logical statements, p, q, and r. There are 8 possible combinations of truth/falsehood given these statements. Like:
p q r
T T T
T T F
T F T
T F F
F T T
F T F
F F T
F F F
Now imagine a set containing three elements, which we'll also call p, q, and r. Now consider subsets of that set. If each "T" in the truth table means "in the subset", then each line in the table represents a possible subset of the original set, with the first line being the original set {p,q,r} and the last line being the empty set.
I also see how the addition of another element, s, would double the number of possibilities in the table and therefore double the number of possible subsets, and that any further additional elements will increase the number of possibilities/subsets by another factor of two. But, I don't know how to make it more rigorous than that.
Right, I meant an explanation, and what you put there works perfectly fine, if not a little bit messy. The idea is just, like you said, that each element of the set is either in or out of every possible subset. So these possibilities all multiply together to make 2^n.
ReplyDeleteTo make it more rigorous we can use induction which works well when we have something that we need to prove for n = 1, 2, 3, ... like we do here. In a proof by induction we prove that something is true for the base case (n = 1), and then show that if it is true for a general case (n), then it is true for the next one (n+1).
Here, the fact that there are 2 subsets of a one-element set is trivial - so that's our base case. Now, assume that a set has n elements and 2^n possible subsets, then by adding an additional element we have doubled the number of subsets since this new element can either be in or out of each existing subset. Thus, if it is true for n, then it is true for n+1.
Induction is always fun, but I like this problem more for the coming up with the answer in the first place part. And you did well on that part.
Onward!
Oh wait, I forgot to say that all of this was to teach the concept of the Power Set. The Power Set of a set, denoted P(A) where A is the set that you are taking the power set of, is the set of all subsets of that set. So if A is a set with n elements, then P(A), the power set of A, will have 2^n elements.
ReplyDeleteThe number of elements in a set is sometimes called the set's order. Just an fyi.
Ok, here we go!