Discrete! #28: Interesting Problems in 2.2, Part B

Interesting Problems in 2.2, Part B (beginning with 45)

These were a lot of fun. Because it’s a half section, and because a lot of definitions were introduced, I’m going to go over a higher than typical percentage of the problems. LUCKY YOU.

45a

“Let = {1,2,3,…,i} for i = 1,2,3,…

Find (a)”

For this one, we’re basically asking “If you make a union of all sets of integers from 1 to some other number, what new set is created?” To get an idea of it, you can just start listing the sets.

for n=1, {1}

for n=2, {1,2}

for n=3, {1,2,3}

And so on. It rapidly becomes clear that all sets are proper subsets of the largest set. Thus, we conclude that the union of all these sets is the same as the largest set. In other words, the set {1,2,3,…n}.

45b

Here, we just want the intersection instead of the sum. Looking at our list above, it’s apparent that, no matter how large we go, no set can contain more than {1}, since that’s all that the first contains. That is, there is necessarily only one number shared by all all the specified sets. That number is 1, so we conclude that the set in question is simply {1}.

Note that more generally we could’ve specified the starting point at any number, and the new set would’ve been {that number}. Make sense?

47a

“Let be the set of all nonempty bit strings (that is, bit strings of length at least one) of length not exceeding i.

Find ”

This one messed me up because I didn’t understand the question. What it’s saying, rephrased, is “Think of all bit strings length one, and make that a set. Now, think of all bit strings, length one or two, and make that a set. Now, think of all bit strings, length one or two or three, and make that a set. And so on.

So, for the union, we’re putting together {0,1} with {0,1,00,01,10,11} with {0,1,00,01,10,11,000,001,010,100,011,110,101,111}, and so on.

Once again, it’s clear that the largest set contains all the smaller sets. So, we simply say “the largest set.” In other words, .

47b

The intersection works in a similar manner to 45b. Once again, every set contains the first set, but the first set contains none of the other sets. Thus, the first set contains all the elements that intersect elements from all the other sets. And so, we conclude that the set of intersections is simply {0,1} aka .

57

This problem introduces the idea of a “successor set.” I’m not sure what the use of these is (they seem pretty simple), but perhaps someone out there can enlighten me. The successor set of some set A is just the union of A and {A}.

a) {1, 2, 3}

The successor set then is { {1,2,3} 1,2,3} }.

b) ∅

You may be tempted (as I was) to say the successor set is { ∅, {∅} }. But, remember, the actual formulation for this would be ∅∪{∅}. Since ∅ unified with something else is like adding 0, the correct answer is just {∅}.

c) {∅}

That’s the union of {∅} and {{∅}}. Aka… { ∅, {∅} }

d) { ∅, {∅} }

That’s the union of { ∅, {∅} } and { { ∅, {∅} } } which is just { ∅, {∅}, { ∅, {∅} } }. That is, the new set is the null set, the set containing the null set, and the set containing both.

59

Here, we get introduced to the idea of multisets. The verbiage here gets a bit complex-sounding, so I’m gonna try to explain it with an analogy.

Suppose you’re about to go fight the Martians. You want to know what ships you have. If you just want a list of types, a regular old set will do. Let’s say those types are {Attacker, Battleship, Cruiser, Destroyer}.

In real life, it’s probably more important to know the number of each, and not just what types you have. Otherwise, 1 attacker, 200 battleships, 500 cruisers, and 800 destroyers is still just {Attacker, Battleship, Cruiser, Destroyer}.

I multiset contains the amount of instances of each thing as well. So, for the latter, you could say {1a, 200b, 500c, 800d}. Simple enough.

For operations, let’s suppose there are a number of armies each represented by a multiset.

In that case, the union operation is like saying “Gimme the best of each type.” So, the army made of the union of all armies would be the army which has the largest amount of each type. So, if there are two armies as follows: {1a, 200b, 500c, 800d}, {10a, 190b, 600c, 200d}, the union army would be {10a, 200b, 600c, 800d}.

The intersection army is the smallest amount of each type. So, for the above case, it’d be {1a, 190b, 500c, 200d}.

The difference between two is just subtracting one from the other. It’d be like a general saying “Lose this many of each type from your army!” Note, that this means differences are not always simple. In a multiset, you can’t have an amount less than zero. So, if you have 20 battleships and your commander says to lose 30, you simply go to 0. You cannot have -10 ships.

The sum then is quite simple. It’s just the additive combination of all armies.

With that in mind, 59 becomes quite simple. You should probably work it to get a flavor for this, but it’s really 1st grade arithmetic once you get the idea.

61

In 61, we get another new concept – fuzzy sets. In a sense, a fuzzy set is really just a decimal version of a multiset, where each member gets a value between 0 and 1. The smaller the value, the less it “belongs” to a set. The larger the value, the more it belongs.

This is a simple concept with a lot of application. You’ll note that in real life, pretty much everything is fuzzy. For example, suppose you were making a set of attractive people. If you were using regular sets, you’d have to either include or exclude people. This would work okay, but you’d have issues with people on the margin. Also, you’d be including a big set of people in “attractive” whose personal attractiveness is very different. With fuzzy sets, you can say “Zach Weinersmith is 1 attractive. George Clooney is .95 attractive. Marty Weiner is .20 attractive, et cetera.”

This also allows you set make a complement set, which is just what you’d expect. In the case of the above set, we could make a complement called the “ugly set.” Each member has a value equal to 1-(their value in the attractive set). So, it’d be “Zach Weinersmith is 0 ugly. George Clooney is .05 ugly. Marty Weiner is .80 ugly, et cetera.”

Much like multisets, for a union we just take the higher value and for an intersection, we just take the lower value.

Once again, the problems here are tedious once you get the concept, so I won’t be working them here.

Next stop: FUNCTIONS!