Hello everyone, and welcome to this week's Carmen's Core Concepts. This is week two, my name is Carmen Bruni, and this week we're gonna talk about some of the key concepts that we did in Math 135 in week 2. Again, I want to remind you that this isn't a substitute for lectures in any way, shape, or form. I'll be going way too quickly for this to be a substitute for lectures, but what this is supposed to do is its supposed to reinforce the key ideas of the week to give you an idea of what we did and to be used in conjunction with other tools, like going to lectures, like practicing the problems, etc etc.
This week, again, so a long table of contents. The idea is that every bullet should cover one minute, so if you'd like to look at a specific topic go to that minute mark and hopefully it's there. Clearly we'll be off by a minute since we start at zero minutes. We'll talk about divisibility theorems, converses, “if and only if”’s. We spent a lecture talking about sets, those are pretty important, and they’ll be used throughout your mathematical career. Quantified statements, again, another core concept of of mathematics, in general. So we'll talk about “for all” and “there exists”. We'll talk about assuming “for all” statements, we'll talk about domain and how it's important for problems, and then we'll talk about approach to quantified statement problems, if you're trying to prove or disprove them, how do you do that? Then we'll talk about negating and nesting quantifiers to finish up the week.
So let's start with divisibility theorems. So last week we finished off with Bounds By Divisibility, this week we'll start with it and talk about a couple of others. So let \(a, b, c \in \mathbb{Z}\).
$$\text{Bounds By Divisibility:}\, (a \mid b \land b \neq 0) \Rightarrow |a| \leq |b|$$So it gives us a bound on the size of $a$ and $b$. So if $a$ and $b$ $\gt 0$, then $a \leq b$ if $a \mid b$, for example.
Transitivity of Divisibility, so we call this TD. Transitivity itself is a very important mathematical concept. It's one of the conditions to be an equivalence relation, for example. So we'll see it again later. What do we have here? We have:
$$\text{Transitivity of Divisibility:}\, (a \mid b \land b \mid c) \Rightarrow a \mid c$$So the transitivity part is if the "middle" thing is the same, so in this case the $b$ on either side, and $a \mid b$ and $b \mid c$, then $a \mid c$. You can change divisibility with, let's say =, or other operators that you know. For example, $(a = b \land b = c) \Rightarrow a = c$. So many things are transitive.
Divisibility of Integer Combinations, one of the most used theorems of this course.
$$\text{Divisibility of Integer Combinations:}\, (a \mid b \land a \mid c) \Rightarrow \forall x,y \in \mathbb{Z}\, a \mid bx+cy$$So we'll talk about "for all" a little bit more in depth later, but I just want to use this symbol here, $\forall$, just to show that you can write DIC using just symbols. The proof of DIC it’s, again, one of these “follow your nose” type of proofs I like to say. Assume the hypothesis, and then it kind of just gradually leads you towards the conclusion.
At this point in the course, we really don't have any tools so if all you get is $a \mid b$ and $a \mid c$, you probably want to use the definition. Using the definition gives you integers $m$ and $n$ such that $am=b$ and $an=c$, and then for any $x, y \in \mathbb{Z}$, we have:
$$bx+cy=amx+any=a(mx+ny)$$and hence $a \mid bx+cy$. So the proof, again, is a “follow your nose” kind of proof. It's very short, very sweet, but this property here, this theorem, has a lot of applications. Let's see an example of them.
Here's just one example of applying it, so if $5 \mid a+2b$ and $5 \mid 2a+b$...well if I take $2 \times (a+2b)$, and add $-1 \times (2a+b)$, then $5 \mid (a+2b)(2)+(2a+b)(-1)$ Well what is that? Well it's $2a+4b-2a-b$. The $2a$ and $-2a$ are going to cancel and you’re going to be left with $5 \mid 3b$.
So this shows you a way that you can use Divisibility of Integer Combinations to find integer combinations to get things like… so to get rid of a variable, for example, so here we got rid of $a$, you can use them prove all sorts of things. Proving that big numbers are divisible if you know that smaller numbers are, so you can combine them to make bigger numbers that are divisible by certain numbers. Lots of interesting applications of DIC. Again, we're going to see this throughout the course, so it is worth its own slide to give an example. Very short, but it is a core concept and you really should try to understand DIC in its fullness.
Converses, so next week especially we're going to see a lot of words that begin with the letter C, and it's very easy to get them confused, so now is a good time that we just have this one to put it in your memory banks and make sure that you have it down solid.
Let $A$ and $B$ be statements. The $converse$ of $A \Rightarrow B$ is $B \Rightarrow A$. So an implication is hypothesis implies conclusion, the converse is conclusion implies hypothesis. A very simple definition. Converses are useful in mathematics. If you prove an implication and you prove its converse, that's much stronger than just proving an implication itself. It somehow gives you a classification-type theorem, which is a lot stronger than just an implication.
So as an example, the converse of Bounds By Divisibility is given by:
$$|a| \leq |b| \Rightarrow a \mid b \land b \neq 0$$Notice that this is false. There's many counter examples of this, so I mean, just take $a=6$ and $b=7$, for example. $6 \leq 7$ but clearly $6 \nmid 7$. There are plenty of examples where this can go awry. Okay, that's all I really want to say about converses.
But we can use converses in the next topic which is “if and only if” statements. So again, let $A$ and $B$ be statements, we say $A$ if and only if $B$, and it can be written as $A$ iff $b$ or $A \Leftrightarrow B$. So $A$ if and only if $B$, we defined it by a truth table.
| $A$ | $B$ | $A \Leftrightarrow B$ |
|---|---|---|
| $T$ | $T$ | $T$ |
| $T$ | $F$ | $F$ |
| $F$ | $T$ | $F$ |
| $F$ | $F$ | $T$ |
Here we said $A \Leftrightarrow B$ is true $\Leftrightarrow$ both $A$ and $B$ are true or false, so they share the same value. So if $A$ and $B$ share the same true or false value, then we say that $A \Leftrightarrow B$ is true, and otherwise it's false. So how do we prove "if and only if" questions in practice? This exercise is what actually shows it. I'm not going to prove it, I didn’t prove it in class either:
$$\text{Show that}\, A \Leftrightarrow B \equiv (A \Rightarrow B) \land (B \Rightarrow A)$$That's something I'll leave as an exercise. But this gives you an idea of how to prove it. Well you prove the normal thing, you prove the implication $A \Rightarrow B$, and then you prove its converse. So if an implication and its converse are true, then the statement is an "if and only if" statement. We'll see a practical example of "if and only if"s when we deal with sets afterwards. I wanted to say that to accumulate everything; to give a nice bridge between the two topics. But that basically covers the the end of the first lecture of the week.
Now we talk about sets. So a set is a collection of elements. This is a very vague definition, but it's definitely good enough for us, and we can do mathematics with this definition. Now you can get into some sticky situations if you're not careful with what you do. You can define some paradoxical things. But for now let's just take for granted a set as a collection of elements.
We have some examples of some sets. So for us, the natural numbers, $\mathbb{N}$, begin with 1 so I wanted to emphasize that here. For example, we also have the rational numbers, $\mathbb{Q}$. $\mathbb{Q}=\{a/b \in \mathbb{R}\,:\,a \in \mathbb{Z} \land b \in \mathbb{Z} \land b \neq 0$ We say here $\mathbb{R}$ is the universe, or sometimes the universe of discourse, either way. That's an example of defining the rationals.
We have the examples of the empty set, so the $\{\}$ is the empty set, $\emptyset$ is the empty set, and $\{\emptyset\}$ is not the empty set. This is the set containing the empty set, so $\{\emptyset\}$ has one element in it, the other two do not have an element in it. There's a big, big difference even though they look very similar, so I wanted to throw this out here just to remind you, okay $\{\emptyset\}$ is different this is a set consisting of a set, that's possible. On here, it's the set consisting of the empty set.
Last thing I want to mention is this notation:
$$x \in S\, \text{and}\, x \notin S$$For example, $2$ is inside the natural numbers, so $2 \in \mathbb{N}$ is a possibility, and $0 \notin \mathbb{N}$, for us. This is important in any proofs with sets. What do I mean by that? Well so sometimes if you get stuck in a set proof question, one thing that you might want to try to do is say, “Okay well I have an element, call it $x$ let's say in some bigger set, and now I know it's either in the smaller set, or it's not in the smaller set. And doing things like that might help you to progress in the proof, right? Elements are either in sets or not in sets. There's no limbo for elements and membership in sets. You're either in or you're out, there's no on the fence. So that's the rough intro to sets.
Some other set examples, so we did some exercises in class with these two, so I wanted to give two examples. The two most important ones that we did in class: the first one is the set of even numbers between $5$ and $14$ inclusive. Well if you're just dealing with the set of even numbers between $5$ and $14$, you can just write down all the even numbers between $5$ and $14$. There's no problem. You don't have to use set notation if you don't want to. So if you don't it's just
$$\{6, 8, 10, 12, 14\}$$That's perfectly fine. If you do use set notation, then something like this will work, for example:
$$\{n \in \mathbb{N} \,:\,5 \leq n \leq 14 \land 2 \mid n\}$$So here again we see that divisibility sign $\mid$; it’s going to pop up everywhere in this course. As another example, the set of all odd perfect squares. So here we're going to do it in a different way:
$$\{(2k+1)^2\,:\,k \in \mathbb{Z}\}$$So here we're going to define the members to be the elements of the form $(2k+1)^2$ and here what's $k$? Well $k$ is a member of the integers, $k \in \mathbb{Z}$. You can also do it as $k \in \mathbb{N}$. The difference here is that when $k \in \mathbb{Z}$, you're going to get multiple representations of the same element of a set. So remember that sets don't have overlap. So, I mean, you can't have three copies of $1$ in your set. Once $1$ is in your set, it's in your set. That's it. There's not multiple levels of $1$. There's just $1$ and that's it, okay? So here even though there's multiple ways to write the same element, it still describes the same set, that's fine. Multiple numbers have different representations, there’s sort of no avoiding this. Well in this case there is avoiding it but in many cases it's not.
I guess I should say, so be careful here. If you use $\mathbb{N}$ you actually miss $1$, I really should say $2k-1$. Not a huge deal.
Set operations. So let $S$ and $T$ be sets. We have a couple of definitions, so if you see $\#S$ or $|S|$, that is the size of the set $S$. The second notation is more common - $|S|$ is more common than $\#S$ but you might see either or.
$S \cup T =\{x\,:\,x \in S \lor x \in T\}$. This is called "S Union T". $S \cap T = \{x\,:\,x \in S \land x \in T\}$. This is called S Intersect T. So notice the similarity between the logic notations. $\cup$ and $\lor$ and $\cap$ and $\land$. They're similar and they're not completely independent, but they are different so don't use $\lor$ when you're talking about sets, and don't use $\cup$ when you're talking about statements.
$S-T$ is set difference, so $S-T=\{x \in S \,:\,x\notin T\}$.
$\bar S$ or $S^c$. I think we’re going to use $\bar S$ in this course, but $S^c$ is also common. This is the complement of $S$, so what does that mean? It means $\bar S =\{x \in U\,:\,x \notin S\}$ where U is the universal set. So if you use that, you can actually write this with set difference, it's just the set $U-S$.
The last thing I want to talk about is Cartesian Product, so $S \times T = \{(x,y)\,:\,x \in S \land y \in T\}$ This is important, right, so notice that the elements x and y are completely independent of themselves, so even if you take something like $Z \times Z$, it's not just all the elements of the form $(1, 1), (2,2), (3,3), (4,4)$, etc, right? $(1,2)$ is in that set and $(2,1)$ is in that set, right? Those are two different elements in that set, $(1, 2)$ and $(2,1)$. So it's the set of ordered pairs, order matters in a Cartesian Product. Again, this is just ways to combine sets to make new sets from old sets. Okay, so that's the end of set operations.
A little bit more of set terminology. So there are a lot of symbols in this notation. Now, if you managed to find this video, the chances are you've already looked at the Math 135 Resources Page, and know that there are symbol cheat sheets. You might need these for the first little bit just to help you remember what all the symbols mean. Again, it's a bad idea - really bad idea - to try to answer a question if you don't know what the symbols mean, if you don't understand the notation. Best advice is don't do it. If you don't understand the notation, don't try to answer problems. Try to understand the notation first and then try to answer the problem. It's far easier that way.
Okay, so let $S$ and $T$ be sets. Then S is a subset of T, that's denoted as $S \subseteq T$, and that means that every element of $S$ is in $T$. Here $S \subsetneq T$ means $S$ is a proper subset, or a strict subset, of $T$. So $S \subset T$ and there's some element in $T$ that's not in $S$, so they're not equal. Equality we'll get to in a minute.
So $S \supseteq T$ means $S$ contains $T$ and $S \supsetneq T$ means $S$ properly contains $T$. It's similar except now $T \subset S$ and $T \subset S$ and $S \neq T$ so there’s some element of $S$that's not in $T$.
$S = T$, what does that mean? So, set equality, this is sort of the… this is something that's really really important here, set equality. It means this. It means that $S \subseteq T$, and $T \subseteq S$ That's what set equality means. It's different than equality of integers, or equality of variables, things like this. The equality operator does get overloaded. So $S = T$ does mean that $S \subseteq T$, and $T \subseteq S$ . So if you are asked to prove that two sets are equal, you must show that $S \subseteq T$, and $T \subseteq S$. We're going to see an example that we saw in class on the next slide that helps, again, reiterate this fact and emphasize it.
$$\text{Show}\,S=T \Leftrightarrow S \cap T = S \cup T$$That's what we're going to prove. This is an "if and only if" proof, so we have to prove the implication and its converse. So the implication is,\, $S=T \Rightarrow S \cap T = S \cup T$ To show this, we need to show that $S \cap T \subseteq S \cup T$ and that $S \cap T \supseteq S \cup T$
How do we show the first thing? So to show that $S \cap T \subseteq S \cup T$ start with an element of $S \cap T$ and show that it must be inside $S \cup T$. First, suppose that $x \in S \cap T$. Well what does that mean? That means that $x \in S$ and $x \in T$. Well if $x \in S$ and $x \in T$, then definitely $x \in S$ or $T$, and so $x \in S \cup T$.
Next, suppose that $x \in S \cup T$, so $x \in S \lor x \in T$. Well what does that mean? Since $S = T$… so this is something that we didn't need in the first half of the proof, but in this half of the proof we're going to use that fact. Well if $x \in S$, then $x \in T$, and if $x \in T$, then $x \in S$ because $S = T$. So, in either case, we know that $x \in S$ and $x \in T$. And so thus, $x \in S \cap T$.
So what have we shown? We showed that an arbitrary element in the union must be in the intersection, and previous to that we showed that an arbitrary element of the intersection must be in the union. Here I've used the same letter $x$ to mean different things, okay? You could have chose different letters. The way I'm viewing this and the way I'm reading this is that $x$ ends after the paragraph, so the scope of $x$ is only each prargraph, okay? It's probably sloppy, you should probably use different letters. It's not a huge deal. It might be a huge deal if you start confusing them. For me, I know I guess I know what I wrote, so I understand what I'm doing. Just keep that in mind though, okay? So that shows the direction, $S=T \Rightarrow S \cap T = S \cup T$.
Now we need to prove the converse. So what does the converse say? Well we need to start with the conclusion: $S \cap T = S \cup T \Rightarrow S=T$ How do we do that? We show that $S \subseteq T$ and $T \subseteq S$, okay? Don't try to make your own rules up. Try to follow this reasonably mechanically and you should you should struggle less with sense.
So if we're showing that $S \subseteq T$, start with an element of $S$, an arbitrary element of $S$, well if $x \in S$ then $x \in S \cup T$ because well $x \in S$ so it's definitely in $S$ or $T$, and $S \cup T$ is equal to $S \cap T$. But if $x \in S \cap T$ then $x \in S$ and $x \in T$. So hence, $x \in T$.
Now in class, I mentioned that you can actually use the word "similarly", right? So now what I'm going to do is I'm going to just replace this letter $S$ with this letter $T$, and go through the proof exactly the same way, okay? $x \in T$ so therefore $x \in S \cup T$, which is equal to the $S \cap T$. Hence, instead of $x \in T$, now $x \in S$ and that proves the inclusion $S \subseteq T$ Now I’ve proved that $S \subseteq T$ and $T \subseteq S$ therefore they're equal, and that's the end of it.
So that is an "if and only if" proof with sets, so there's a lot on this slide; a lot to digest. If you understand this slide and what happened here, I feel like you're in pretty good shape with both sets and "if and only if" statements.
Onto quantifiers. So quantified statements. So this week, we talked about two quantified statements. We saw them a bit last week and a bit in the past, but now we're going to formally do them. So we saw $\forall$ and $\exists$. $\forall$ means “for all” and $\exists$ means “there exists”. So two examples in class that we did.
So how do we do that? Well so we're proving a “for all” statement, so start with an arbitrary element of the “for all” statement, and then show that $2n^2+11n+15$ is composite, with an arbitrary $n$. How did we do that? Well it's similar to our assignment problem that we had in Assignment 1, we factor.
$$2n^2+11n+15=(2n+5)(n+3)$$So we factor, we show that both of the factors are bigger than 1, because $n$ is a natural number, and thus $2n^2+11n+15$ is composite.
Here's an example of a “there exists” statement that we're going to prove.
$$\text{Prove}\, \exists k \in \mathbb{Z}\, \text{such that}\, 6=3k$$How do we do this? Well we're proving a there exist statement, so all we need to do is find such a $k$. Now, it is possible to prove existence statements without actually finding one. Hopefully we won't see that in this course. We might but I doubt it. Here though, we can just specifically find the $k$ that makes this work, and the $k$ that's going to work is actually $2$. Since $3 \times 2 = 6$, we see that $k = 2$ satisfies the given statement. And that's it.
So for proving “there exists” statements, it's enough to actually physically find an example. Proving a “for all” statement, you have to actually go through an arbitrary proof, like this. We'll see this in a couple slides. This is something that trips students up a lot, so I'd like to talk about it here.
Assuming a “for all” statement, so let's look at this statement:
$$\text{Let}\,a,b,c \in \mathbb{Z}.\, \text{If}\,\forall x \in \mathbb{Z},\, a \mid (bx+c)\,\text{then}\, a \mid (b+c)$$Now setting up this proof is… the first line’s very sort of… dry, it's obvious. If hypothesis, then conclusion. So assume the hypothesis. Now what you have to tell yourself is, what does this mean that I'm assuming the hypothesis? So I'm assuming that the statement, $\forall x \in \mathbb{Z},\, a \mid (bx+c)$ is true. I'm assuming this is true, so that means if I plug in any value for $x$, this is going to be a true statement.
What values can I plug in? If I plug in let's say $x=0$, then what do I learn?
$$a \mid (b(0)+c) = c$$I learn that $a \mid c$. If I plug in $x = 10$, what do I learn?
$$a \mid (b(10)+c) = (10b+c)$$Well I learn that $a \mid 10b + c$. And for all values of $x$ that you plug in, you're going to get a statement - a divisibility criteria - from that. In particular, how do we show that $a \mid (b + c)$? Well let's pick a good value of $x$, and it turns out that a good value of $x$ to pick is $1$. So I can plug in $1$ because I know that this “for all” statement is true. I'm given the “for all” statement. So I know that's true for $x = 1$, and when I plug that in:
$$a \mid (b(1)+c) = (b+c)$$I should get that $a \mid (b + c)$. This is important. This is a little bit subtle. Assuming a “for all” statement. You're assuming that a “for all” statement is true so you can plug in values and you can take that for granted.
Domain is important. So let's look at the example:
Which of the following are true:
$$\begin{align*} &1)\,\exists x \in \mathbb{Z},P(x)\\\\ &2)\,\forall x \in \mathbb{Z},P(x)\\\\ &3)\,\exists x \in \mathbb{R},P(x)\\\\ &4)\,\forall x \in \mathbb{R},P(x)\\\\ &5)\,\exists x \in S,P(x)\\\\ &6)\,\forall x \in S,P(x) \end{align*}$$Which of the following are true? So we know that over the $\mathbb{R}$, the only values that make this true are $\pm \sqrt{2}$. So, for $1)$ are there integers where $P(x)$ is true? Well no. The only ones are the irrational numbers, $\pm \sqrt{2}$.
For $2)$, well $\forall x \in \mathbb{Z}$ is $P(x)$ true? No. Right? I mean $0$, for example, $0^2=0 \neq 2$.
Let's look at the real numbers now. For $3)$, is there a real number that makes this true? The answer is yes. Well $\sqrt{2}$ makes it true.
Now let's look at $4)$, well is it true $\forall x \in \mathbb{R}$ $P(x)$ is true? That's false, right? I mean $0$ again is a counterexample. $0$ is a real number and $0^2=2$ is a false statement.
But what about for $S$ in $5)$? Well $\exists x \in S$ such that $P(x)$ is true, that's true. There's $\sqrt{2}$, for example.
$6)$, $\forall x \in S, P(x)$. Well that's also true, $S$ only has two elements: $\pm \sqrt{2}$, and they're both roots of $x^2-2=0$. So $6)$ is going to be true.
So here's an example - this actually gives you all the combinations. So something to think about, can I find one where there exists a set $T$ such that $\forall x \in T$, $P(x)$ is true, and $\exists x \in T$, $P(x)$ is false. Think about why that can't happen. It can't happen, and if you think about it you'll see why. So this basically gives all the possibilities.
A couple of final things to end off with so approaching quantified statement problems. So what do we want to say here? We're going to go through the four possibilities.
So a single counter example shows that $\forall x \in S,$ $P(x)$ is false. So if I want to disprove a “for all” statement, all I need to do is find a counter example. So here's an example: “Every even positive integer is composite”, that's false. $2$ is even, but $2$ is not composite, $2$ is prime.
Part 2, a single example does not prove that $\forall x \in S$, $P(x)$ is true. If you want to prove this just like we did a couple slides ago, you have to prove it for all elements of S. So here's an example: “Every even integer at least 4 is composite.” This is true but we cannot prove it by saying well $6$ is an even integer and it's composite, so I'm done. You can't do that, okay? That's not enough, right, because there are lots of even integers that aren't $6$, and that are at least $4$.
To prove that this is true, you must show that this is true for an arbitrary even integer $x \geq 4$. So what's the idea? Well $2 \mid x$ so $\exists k \in \mathbb{N}$ such that $2k=x$ and $k \neq 1$. You can do this to show that the number must be composite, it's divisible by $2$ and the two factors are greater than $1$.
Let's look at another one. So a single example does show that $\exists x \in S$, $P(x)$ is true. Claim: “some even integer is prime”, right? There exists an even integer such that it is prime. That claim’s true because $2$ is even and $2$ is prime. So there's an example of a “there exists” statement being true.
And then, the last one is sort of the trickiest one. What about showing $\exists x \in S$ such that $P(x)$ is false? How do we do that? It turns out the easiest way I like to think about this, is you actually negate this and we'll talk about negating quantifiers in the next slide, but if you negate this, what has to happen? Well the negation of this must be true. What's the negation of a “there exists” statement? It's a “for all” statement. $\forall x \in S$, $\neg P(x)$ is true, is equivalent to saying $\exists x \in S$ such that $P(x)$ is false. So this sort of logical equivalence here is actually a big hint for solving this type of problem. We'll see this is central in the idea of proof by contradiction, which we'll see next week, but I thought I'd mention it here and it seems like a really natural point to do so.
We can talk about negating quantifiers. These ones that I used in class, everyone in this room is born before 2010. Somebody in this room was not born before 2010, that's the negation. Someone in this room is born before 1990, the negation is: everyone in this room was born after 1990. So what am I trying to emphasize here? I'm trying to emphasize the “everybody” to “somebody”. Everybody should, in your mind, mean “for all”. Somebody means “there exists”, there's somebody. I started with somebody, or someone, in this room that's a “there exist” statement. What’s the negation of a “there exists” statement? It's an “everybody” statements, it’s a “for all” statement, okay?
Here's two more examples, so now let's do this mathematically. If I have:
$$\forall x \in \mathbb{R},|x| \lt 5$$Remember that equality has to come here because it wasn't in the original. The negation of a $\lt$ is a $\geq$.
Here the equality was in here, so the negation of a $\leq$ is strictly $gt$ That's negating quantifiers, that's basically it. So notice that the domains stay the same, something to keep in mind, you don't negate the domain or do something crazy with that. Leave that alone, just negate the quantifier.
Nesting quantifiers, I believe this is the last thing I want to talk about. What's the point of nesting quantifiers? Well the order of quantifiers matters, okay? The order in which you do things influences whether or not the statement’s true or false. So let's look at these four examples and these are basically the four examples that you can have for this problem
So hopefully that immediately just sounds ridiculous, right? I mean for every single real number $x$ and $y$, the difference of cubes is $1$? That can't be true. A simple counter example is $x = y = 0$.
That's true, right? You get to actually pick your $x$ and $y$ here. So I'm going to pick $x = 1$ and $y = 0$, that's definitely a good enough proof. You can pick many other ones, but that'll work and that's the easiest one I think.
So I give you a real number $x$, can you find a real number $y$ that that works for the given $x$, such that $x^3-y^3=1$. So this is where the order is important. You're given the $x$ first, and you can choose the $y$ depending on the $x$ that you were given, okay? So in this case, it's going to be true. Why? So start with an arbitrary $x$ and pick $y$ to depend on $x$, okay? So $y = \sqrt[3]{x^3-1}$. $y$ is allowed to depend on $x$ because it appears later in the statement. By the way, where does this come from? This $y = \sqrt[3]{x^3-1}$? Just solve for $y$ in the expression. And if you plug it in then you see that equality is satisfied. So $3$ is true.
What if I flip the quantifiers? So there's some $x$ such that for every single $y$ I pick, $x^3-y^3=1$. Hopefully that to you sounds ridiculous, right, I mean so there's some magical $x$ that every single $y$ value makes $x^3-y^3=1$? That doesn't sound right. It sounds like you have a way too much freedom. I mean $1$ is fixed and somehow $x^3$ is fixed, so $y^3$ should probably be fixed, that's sort of the intuition here.
But how do you disprove this? How do you write a formal disproof of this fact? So you're disproving a “there exists” statement, negate it, and prove the negation. So the negation of this is…well how do we do it? Bring the negation in, so negated $\exists$ that becomes a $\forall$, negate a $\forall$ that becomes a $\exists$ , leave the domains the same, and instead of an equality here, you put an inequality here. So the full negation is $\forall x \in \mathbb{R},\exists y \in \mathbb{R}, x^3-y^3 \neq 1$
So proof, what's the proof? Let $x \in \mathbb{R}$, be arbitrary, so I pick some $x \in \mathbb{R}$, now I need to find some $y$ such that $x^3-y^3 \neq 1$ Well just take $y = x$, right? I can pick $y$ now because once I've negated it and I start with my $x$, I get to choose $y$ depending on $x$ in this setting. Then $x^3-y^3=x^3-x^3=0 \neq 1$ That’s the idea. So the negation is true, so the original is false. Notice the difference here, so Example 3 and 4 look very similar, right, I've just changed the order of the $\forall$ and $\exists$, but it matters because the $x$ cannot depend on the $y$. The $y$ can depend on the $x$, but the $x$ cannot depend on the $y$. In this case, really, $y$ can't depend on anything because it's $\forall y$, so I mean you have to show this is true for every single value of $y$.
And that is nesting quantifiers. Okay, so order matters. Get a little bit of practice, again, doing assignments is probably the best way, doing practice problems, all those sorts of things. Ask questions, post on Piazza. If you have any questions, let me know. Hopefully this was helpful. Hopefully this gave you some insight into week 2’s concepts, and hopefully you join me for week 3. Thank you and good luck.