Discrete! #26: Interesting Problems in 2.1

Interesting Problems in 2.1

These can be a little tough on the brain, and a few of them took me a while to get. Hopefully I can provide some clarity.

5

“For each of the following sets, determine whether 2 is an element of that set.”

a) {x ∈ R | x is an integer greater than 1}

b) {x ∈ R | x is the square of an integer }

c) {2, {2}}

d) {{2}. {{2}}}

e) {{2}, {2,{2}}}

f) {{{2}}}

Let’s go through!

a) Set containing x, which is a Real, such that x is an integer greater than 1. Clearly, the set containing real integers above 1 contains 2. CONTAINS

b) Set containing x, which is a Real, such that x is the square of an integer. There is no integer that, when squared, produces 2. Only the square root of two (or its negative) does this, and it’s irrational. DOES NOT

c) Clearly, this contains 2 as an element. CONTAINS

d, e, f) These three basically all ask you the question “Does the set containing the set containing 2 contain 2?” That is, is “2” an element of the set containing the set that contains 2. The answer is NO. In all of these cases, 2 is an element of a subset, not an element of the set we’re talking about. DOES NOT

21

How many elements does each of these sets have where a and b are distinct elements?

a) P({a,b,{a,b}})

b) P({∅,a,{a},{{a}}})

c) P(P(∅))

Woof.

The first one is pretty straightforward. 3 elements, and thus 2^3 possibilities: ∅, {a}, {b}, {{a,b}}, {a,b}, {a, {a,b}}, {b, {a,b}}, {a,b,{a,b}}

That only looks confusing, but if you simplify the set within the set to c, and then redo it, it’s all very clear.

b) is pretty much the same deal, only you have one more element. It’s 2^4, so its 16.

c) really screwed with my head. I figured out why and will try to explain both the confusion and the clarity.

So, to solve this problem, first you need to know the power set of the null set – P(∅)

We can rewrite that as

P({ })

What sets can we make from that? Only one: { {} }

I got confused here, because I thought we could also make the null set itself, as opposed to { {} }, which is the set WHICH CONTAINS the null set. My reasoning was that for any set, the null set is a subset. However, it is not true to say that for any set, the null set is an element.

When you take the power set, you’re just saying “what can I construct from what’s in here?” All of your constructions have to be sets, as in the above problems. Thus, the only possible answer is the set containing the set that contains no elements.

It’s a little hard on the brain, but it makes sense when you think about it.

So, now you’re taking P( { {} }). That inner set DOES contain the null set as an element. So, when we take the power set, we get { {}, { {} } }. That is, {∅, {∅}}

A little funky, but it makes sense.

27

Let A be a set. Show that ∅×A = A×∅ = 0.

I like to think of it this way: That “×” operator is basically like saying “How many pairs can you make using these two sets. Because one set is empty, the answer is “none.” In this case, reversing order doesn’t matter to the outcome. The question you’re asking is slightly different – in the first case, you’re asking the null set “How many first positions can you fill” and the answer is “none.” In the second case, you’re asking the null set “How many second positions can you fill” and the answer is “none.”

This one isn’t so hard, but it bolsters our intuitive sense that ∅ is sort of like 0 in its interactions.

38

This question basically shows you Russell’s Paradox. Instead of going through it explicitly, I’m going to try to explain the idea using examples:

Let S be the set of all sets that are not members of themselves.

Say that to yourself until you get it. S is the set of all sets that are not members of themselves. It’s the set of all sets that do not contain themselves as elements.

Now, suppose S is a member of itself. That leads to a clear contradiction since S is by definition NOT a member of itself.

So far, so good. Now here’s the funky thing:

Suppose S is not a member of itself. Well, remember we said S is the set of all sets that are not members of themselves. If S is not a member of itself, then its a member of itself, which it isn’t!

Kinda neat too, huh? For the purposes of this text, I don’t believe we get anywhere near why this might be a problem. BUT, it’s fun to think about.

Next stop: Set Operations

This entry was posted in Autodidaction, Discrete Math. Bookmark the permalink.

3 Responses to Discrete! #26: Interesting Problems in 2.1

1. Jim T says:

So the lesson for 21c is that instead of saying “contains,” you should use one of the symbols in the set { ⊆, ∈ }.

:-)

(Also, see 5(d-f).)

2. Lisa Ugray says:

#38 Has another way of framing the question, which is: There’s a barber in a town who shaves all those (and only those) that do not shave themselves. Who shaves the barber? In much the same way the barber can not shave themselves nor fail to. (Some versions of this add gender to the question and make it a riddle in which the barber is a woman who shaves all men who do not shave themselves.) The answer to the paradox is simply that no such barber exists. You’ve used language to describe an impossibility, and you’re surprised that it doesn’t work. I can say that the sky is bright green and it doesn’t make it so, and I can say that there’s a barber… and it also doesn’t make it so. Similarily, no such set S exists. The thing you said a few posts ago about using naive set theory, this is where it shows up. If you formalise a bit more the way you’re allowed to describe sets, you’ll find that the set S of the problem is impossible to describe.

3. Charlie C says:

Just to be pedantic:

If 5(f), 2 is neither an element nor an element of a subset of S = {{{2}}}. Instead, it’s an element of an element of an element of S. It’s “two levels down”. That is, it’s an element of Union(Union(S)).

(Note that I’m using Union as a unary operator on a set of sets, where if A = {a1,a2,…}, then Union(A) = a1 union a2 union a3 … and so on.)

When you finish this book, you should try for the hard stuff with a formal treatment of axiomatic set theory!