The Weinerworks

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

Chapter 2: Basic Structures: Sets, Functions, Sequences, and Sums

Hot diggity – you’re about to get a bunch of new symbols and terms to add to your math vocabulary.

This section is a gentle introduction to a bunch of the basic notions you’ll be battling for the rest of this book. So, let’s dig in.

What is a set? A set is basically a list of stuff. Importantly, a set has no particular order – it is simply a big list of shit. For convenience, you can list it in any order you want, but no particular order is more valid than another.

For this book, we will be using something called naive set theory, which I understand to mean something like “set theory that was perfectly fine before everything went crazy in the early 20th century – I’m looking in your direction, Bertrand Russell.” Or, otherwise stated “set theory that basically makes human sense, and we won’t deal with axiomatizing it.”

Now, some housekeeping:

Sets are denoted inside curly brackets like so:

S= {1,4,3}

I read that as “S is the set which contains 1, 4, and 3.”

You can specify bigger sets using ellipses, like so:

S = {1, 2, 3… 999}

I read that as “S is the set which contains all the integers 1 through 999 inclusive.”

You can also use the handy vertical bar, “|” which I read verbally as “such that.”

The book’s example is:

O = {x | x is an odd positive integer less than 10}

You can read that as “O is the set of all x, such that x is an odd, blah blah blah…”

Or, it can be read as “O is the set that contains odd positive integers less than 10.” Same thing.

You can also use this little forky doodad “∈” which I read as “is a member of” or “is an element of.”

The book’s example is

Q+ = {x ∈ R | x=p/q, for some positive integers p and q}

This is a definition of positive rational numbers. I read it as “Q+ is the set where x is a member of the Real Numbers, such that x is a ratio of two positive integers.”

Or, more human friendly “Q+ is the set of reals that can be expressed as a ratio of two positive integers.”

Got it? There’s nothing really hard here – there’s just a lot to take in. You’ll get all that when we get to practice.

The book then gives us a definition of what it means for two sets to be equal. The simple version is “two sets are equal if they contain the same shit.” The rigorous version is that sets A and B are equal if ∀x(x∈A⇔x∈B).

That is, if being a member of A means you’re a member of B, and vice versa, then the two sets are equal, and we say A=B. For example, the set of people who think Return of the Jedi was better than Empire Strikes Back is equal to the set of people who are wrong about whether Return of the Jedi was better than Empire strikes back.

Additionally, you can have what are called empty, or null, sets. A null set is a set that contains nothing. You may ask why even bother with this, but it’s a common result to a lot of questions. For example, the set of people who are interested in your complaint about why we bother with null sets is a null set.

More importantly, null sets are sort of like having 0 in arithmetic. So, they come up pretty often. As such, we have a shorthand for them: ∅. As far as I can tell, Scandinavian language is full of null sets.

We also learn what’s called a singleton set. This is just a set containing only one member. Jokes on this topic are too easy, so I’ll lay off.

Venn Diagrams

You may believe that Venn Diagrams are mainly used for dirty jokes online. This is correct. However, they are also useful for explaining relations between sets. In the classic Venn Diagram, you have two sets which share some but not all members. But there are many other possible diagrams. A set may contain another set inside it. Two sets may exactly overlap. Two sets maybe be contained in a bigger set.

A Venn Diagram is a non-rigorous way to express relations visually. It’ll come in handy later on as you work problems. It also introduces you to have sets can relate to one another.

For example, if every element of A is in B, you can say “A⊆B” which is read as “A is a subset of B.” The symbols look conveniently like the “less/greater than” symbols, which makes it very intuitive. It also leads to some conclusions, which the book lists – every set contains ∅, and every set contains itself. Hopefully it’s pretty clear why.

For the case where A ≠ B and A⊆B (that is, B has everything in A plus some other stuff too) we say “A⊂B.” Read that as “A is a proper subset of B.” If you were to draw a Venn Diagram of A and B, B would encircle A and be larger than A.

Cardinality

Cardinality is just the number of members of a set. ∅ contains 0 members. {1,2,3} contains 3 members. You can also have infinite sets, but we’ll get into how to define their cardinality a little later on.

The Power Set

The power set is basically all the possible distinct sets you can build from some other set. It is denoted by P(S) where S is the set in question.

The book’s example is P({0,1,2}) = {∅, {0}, {1}, {2}, {0,1}, {0,2}, {1,2}, {0,1,2} }

Woof. But, you should be able to see what’s going on. The power set is the set of all possible subsets of the set in question. If that’s confusing, think of it like this: If you have a penny, a nickel, and a quarter, the power subset would be a list of all possible amounts of change you could give someone using those coins. You could give them none, all, just one, or some combination of two. So, the power subset is sort of like every arrangement of the elements of a set when order doesn’t matter.

Note that {∅} is not the same as ∅. The first is a set that has one element (the null set), and the second is the null set itself.

Cartesian Products

So far, we’ve dealt with situations where order doesn’t matter. But, what if we insist on order mattering?! We get the somewhat ugly name “ordered n-tuple.” “Tuple” as in “quinTUPLEt.”

An ordered n-tuple is a list of n elements where each element is assigned a position. So, for two ordered n-tuples are only equivalent if they contain the same elements in the same order.

This leads us two a concept called the Cartesian Product:

A×B = { (a,b) | a ∈ A ∧ b ∈ B }

This might look tricky at first, but it’s actually quite simple. It says that the Cartesian Product is the set containing all pairs of numbers, where each pair consists of an element from A and an element from B, in the order specified. So, if you have two lists, the Cartesian Product is every possible pair you could make using exactly one element from each list in order.

Note, that this leads to the result that A×B ≠ B×A. For example, if A is the set of Apples and B is the set of Boners, A×B will contain elements like (Granny Smith, Girthy) and (Fuji, Tumescent). If it’s B×A, it’ll contain elements like (Erect, Pink Lady) and (Enormous, Red Delicious).

You can also come up with Cartesian Products for trios (x, y, z) or even larger amounts. To denote this, you do like so:

A1×A2×…×An = {(a1,a2,…,an) | ai∈Ai for i = 1,2,…,n}

That is, take n sets and Cartesian Productify them together, and you’ll get an n-tuple with corresponding members.

Using Set Notation with Quantifiers

Hopefully by now this is pretty straightforward. If you start talking about the elements of a set, quantifiers allow you to specify whether you’re talking about all the members or some of them.

Truth Sets of Quantifiers

When you’re talking about a set, you can specify a subset called the Truth Set. The truth set is just the set containing elements for which the Truth Set is true.

For example, say the Truth Set for the statement “is good” is given by T(), and we have the set of all musicians, M.

M contains all musicians. T(M) is a subset of M which contains elements for which the statement “this element is good” is true. So, M includes Vanilla Ice. T(M) does not.

This is very much a section where you’ll want to work lots of problems. None of the ideas here are complicated, but you need to be fluent with them.

Next stop: Interesting Problems in 2.1

Chapter 1 Review Problems

Most of the problems here were preeeetty darn easy. If something is still confusing you, go ahead and do it. But, if not, a lot of this is busywork. I picked out 3 particular problems from the supplementary exercises that I thought were fun or tricky.

11

“Suppose that on an island there are three types of people, knights, knaves, and normals. Knights always tell the truth, knaves always lie, and normals sometimes lie and sometimes tell the truth. Detectives questioned three inhabitants of the island – Amy, Brenda, and Clair – as part of the investigation of a crime. The detectives knew that one of the three committed the crime, but not which one. They also knew that the criminal was a knight, and that the other two were not. Additionally, the detectives recorded these statements:

Amy: “I am innocent.”

Brenda: “What Amy says is true.”

Clair: “Brenda is not a normal.”

Tricky tricky…

First, I defined a few terms:

K(x) = x is a knight.

A(x) = x is a knave.

N(x) = x is a normal

C(x) = x is the criminal

Next, I started with Amy, partially because her statement is the most self-contained, and partially because she was the first person the question listed. Here was my chain of logic:

K(Amy) → ¬C(Amy) → ¬K(Amy)

That is, if Amy is the Knight, based on her statement (I am innocent) she can’t be the criminal. But, we are given that the criminal is a knight. So, if Amy is not the criminal, she must not be the knight. The logic then says that if she’s a knight, she’s not a knight! Contradiction! Thus, Amy cannot be a knight.

Since there is only one knight, we know one of the other two is a knight and is guilty. I started with Brenda. Here was my logic;

K(Brenda) → (K(Amy)⊕N(Amy))

¬K(Amy)

Thus,

K(Brenda) → N(Amy)

That is, if Brenda is the knight, then Amy is telling the truth. If Amy tells the truth, she can’t be a knave, and is thus either a knight or normal, but not both. We just established that Amy is not a knight. Thus, if it’s the case that Brenda is a knight, then it’s the case that Amy is a normal.

This is more information, but is sadly not conclusive. So, we turn to our last islander.

K(Clair) → K(Brenda) ⊕ A(Brenda)

A(Brenda) → C(Amy)

¬C(Amy)

Thus,

K(Clair) → K(Brenda), which is false because there is only one knight.

So, Clair is not a knight and Amy is not a knight. Thus, Brenda is the knight, and thus Brenda is the criminal.

BOOM!

This is one of the awesome things about logic. In order to reach these conclusions without symbolic logic, you’d have to hold a lot of simultaneous ideas in your head. By using symbols and rules of inference, things simplify quite a bit.

19

“Use existential and universal quantifiers to express the statement ‘Everyone has exactly two biological parents” using the propositional function P(X,y) which represents “x is the biological parent of y.’”

Uniqueness quantifying can be a little tricky because you have to state what’s right and then exclude anything that could be wrong. Here’s what I went with:

∀x∃y∃z P(x,y)∧P(x,z)∧z≠y∧∀w(w≠y∧y≠z)→¬P(x,w)

(Edit: Reader Brett notes that I didn’t exclude the possibility that x is the parent of x. I should have said “z≠y and y≠x and x≠z.”)

Wow… that looked way prettier on paper.

I read that as “There is some person x and at least one person y and at least one person z, such that y is a parent of x and z is a parent of x, and y and z are not the same person. Also, for all people, w, unless w is the same as y or z, w is not a parent of x.

You’ll note there are really two chunks the first chunk (before the second universal quantifier) basically says this “Everyone has at least 2 people who are biological parents.”

You’ll note that this leaves out the possibility that an individual might have more than 2 parents. Sure, YOU know that’s not biologically possible, but the math doesn’t. So, you have to exclude the possibility.

So, the second chunk basically says this “If you select anyone from the set of people who isn’t y or z, then that anyone is not a parent of x.”

Remember, the trick to declaring a finite number using only universal and existential qualifiers is to declare a certain minimum number exist and that nothing exists in addition to that minimum.

39

“Disprove the statement that every positive integer is the sum of the 36 fifth powers of nonnegative integers.”

This intuitively seems right. After all, fifth powers get really big really fast. So, at a certain point it seems like there’ll a gap between what you want to produce and what you can.

Right off the bat, it’s obvious you can get anything from 0 to 36 by just using 1s. The next number you’re allowed to use is 32. So, what I did was to look for a patern.

To get 37, you need 32(1) + 1(5) + 0(30)

This method clearly takes you all the way to 67, because you have 35 ones to burn after initially using a 32.

Now, we check what happens when you start with 64. This clearly takes you all the way to 98, which is 32(2) + 34(1).

The thing to notice here is you’re getting diminishing returns. For 32+ blah, you had 35 ones to burn. For 64+ blah, you had 34 ones to burn.

So, we can start looking at how big the bands are, and if they get too small to carry on.

32(1): 32-67 (difference of 35)

32(2): 64-98 (difference of 34)

32(3): 96-129 (difference of 33)

Notice the overlaps are disappearing!

32(4): 128-160 (difference of 32)

32(5): 160-191 (difference of 31)

32(6): 192-222 (difference of 30)

32(7): 224-something

At this point, we see 223 is unreachable. You can also see that if you keep playing this game, you’ll got lots and lots of unreachable numbers. 223 is just the lowest one.

And with that, we’ve graduated to Chapter 2! This is where a lot of the fun, including Venn Diagrams (darling of internet dork humor) begins.

Next stop: Chapter 2 – Basic Structures: Sets, Functions, Sequences, and Sums