FOM Book: 4.1

I think it’s safe to say this has been the weirdest week I’ve had at SMCM in a while. I got the deadly stomach virus, found out I have three exams next week, got accepted into Cal State, Chico for an exchange program, and have to now pick classes at Chico that may or may not transfer back over or count for anything, among other things.

Too much information? Whatever.

ANYWAY, this has also been a weird week for FOM. I missed class on Monday (due to puking), Wednesday was a lot of awkward silence, and Friday was a lot of the same with some group work. I think the one thing I learned this week is that proof by induction is REALLY easy, and that I really need to get back on track with reading the book.

So, it’s almost 4PM on a sunny Friday afternoon, and I’m challenging myself to plug out the essential parts 4.1 that will help me prove things in the future.

The challenge starts now.

4.1 Exploration and Proof with Quantifiers

Order Can Be Everything

Changing the order of quantifiers can make a true statement false. In the book, they use the statements: (∃c∈ℕ)(∀a,b∈ℕ)(a|c and b|c) and (∀a,b∈ℕ)(∃c∈ℕ)(a|c and b|c). Looking at them, they look the exact same. BUT, (∀a,b∈ℕ)(∃c∈ℕ)(a|c and b|c) is true and (∃c∈ℕ)(∀a,b∈ℕ)(a|c and b|c) is false.

Why?

We can prove that the statement (∀a,b∈ℕ)(∃c∈ℕ)(a|c and b|c) is true by assuming the universal statement is true and finding some a and b that exist to make this true as well. Since we’re trying to prove the existential part, it’s simple because we need to find some instance where the open statement works.

But when we try to prove (∃c∈ℕ)(∀a,b∈ℕ)(a|c and b|c), we are trying to find a c that makes the universal statement true, which is a very subtle difference. When switched around this way, the statement says that every positive integer a and every positive integer b is a divisor of c. When looking at this, no matter what you choose for c, you can find a’s and b’s that are not divisors of c. So we can’t prove this.

∀ in the Hypothesis

When ∀ is in the hypothesis, we use the term specialization, which Casey doesn’t like for some reason, so I’ll try and explain this a different way. From what I understand, ∀ in a hypothesis is a huge perk for proving a specific value later, since all values are guaranteed in what we are assuming is true. (This seems rather intuitive).

∃ in the Hypothesis

When ∃ is in the hypothesis and conclusion, you use two steps to prove (which is really nice time-wise). ∃ is really just saying that there’s something out there that exists, so first step is name that something that exists, and then use it to prove the statement in question.

This is a very short summary of what 4.1 goes over. The rest of the section goes over specific definitions and theorems that use quantifiers in the hypothesis, which I’ll talk about later!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s