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!

Aargh! Paradox!

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