Question about proof from a guy with a highschool education

[micromass]

About this , would it be better to write $\{∀x\in\mathbb N\,|\,\exists y\in\mathbb N~~ x=2^y\}$ ?

No. The well-formed formula is

$\{x\in A~\vert~\varphi(x)\}$

and not

$\{\forall x\in A~\varphi(x)\}$

That's just notation though. We chose one form above the other because we wanted our notations to be the same in every case.

 

[Fredrik]

Since $\{x\in A\,|\,\varphi(x)\}$ is to be read "the set of all $x\in A$ such that $\varphi(x)$", I see your point, but no one writes a $\forall$ there. As micromass said, this is just a notational convention, so it doesn't require any deeper analysis.

However, if we denote this set by B, then we have
$$\forall x \left(x\in B \Leftrightarrow \left(x\in A\ \land\ \varphi(x)\right)\right),$$ where $\Leftrightarrow$ is read as "if and only if", and $\land$ is read as "and". (These logical symbols are defined by truth tables that I assume are included in the logic section of the Book of Proof). This "sentence" can be thought of as the definition of the notation $B=\{x\in A\,|\,\varphi(x)\}$.

The symbol $\leftrightarrow$ is often used instead of $\Leftrightarrow$.

Edit: I actually messed up that sentence in the language of set theory when I posted this, but I have changed it, so it should be OK now.

 

[reenmachine]

Since $\{x\in A\,|\,\varphi(x)\}$ is to be read "the set of all $x\in A$ such that $\varphi(x)$", I see your point, but no one writes a $\forall$ there. As micromass said, this is just a notational convention, so it doesn't require any deeper analysis.

However, if we denote this set by B, then we have
$$\forall x \left(x\in B \Leftrightarrow \left(x\in A\ \land\ \varphi(x)\right)\right),$$ where $\Leftrightarrow$ is read as "if and only if", and $\land$ is read as "and". (These logical symbols are defined by truth tables that I assume are included in the logic section of the Book of Proof). This "sentence" can be thought of as the definition of the notation $B=\{x\in A\,|\,\varphi(x)\}$.

The symbol $\leftrightarrow$ is often used instead of $\Leftrightarrow$.

Edit: I actually messed up that sentence in the language of set theory when I posted this, but I have changed it, so it should be OK now.

Extremely clear! Thanks a lot!

Just a minor question , why the () instead of the {}? Or more precisely , why isn't the sentence $$\forall x \left(x\in B \Leftrightarrow \left(x\in A\ \land\ \varphi(x)\right)\right),$$ between {}?

 

[Fredrik]

Because what I did there defines the meaning of the curly brackets.

The alphabet of the formal language of set theory includes only a bare minimum of symbols. Typically, we would define it as containing the symbols $\land$, $\lnot$ (read as "and" and "not") and only a few others. Then we use the fundamental symbols to define new ones, to make things easier for ourselves. For example, it would be convenient to have a symbol that we can think of as representing the word "or", so we make the following definition: For arbitrary statements p and q, we define the expression $p\lor q$ to mean $\lnot(\lnot p \land \lnot q)$. Now the symbol $\lor$ can be read as "or".

This will make more sense when you have studied truth tables. The only motivation I can give you right now is that the statement "p or q" is true if and only if it's not true that p and q are both false.

The set-builder notation is introduced the same way. For all sets A,B and all properties $\varphi$, we define the notation
$$B=\left\{x\in A\,|\,\varphi(x)\right\}$$ to mean
$$\forall x \left(x\in B \Leftrightarrow \left(x\in A\ \land\ \varphi(x)\right)\right).$$ This too can be viewed as short notation for a significantly longer expression, where the $\Leftrightarrow$ is expressed using $\land$ and $\lnot$.

 

[reenmachine]

Because what I did there defines the meaning of the curly brackets.

The alphabet of the formal language of set theory includes only a bare minimum of symbols. Typically, we would define it as containing the symbols $\land$, $\lnot$ (read as "and" and "not") and only a few others. Then we use the fundamental symbols to define new ones, to make things easier for ourselves. For example, it would be convenient to have a symbol that we can think of as representing the word "or", so we make the following definition: For arbitrary statements p and q, we define the expression $p\lor q$ to mean $\lnot(\lnot p \land \lnot q)$. Now the symbol $\lor$ can be read as "or".

This will make more sense when you have studied truth tables. The only motivation I can give you right now is that the statement "p or q" is true if and only if it's not true that p and q are both false.

The set-builder notation is introduced the same way. For all sets A,B and all properties $\varphi$, we define the notation
$$B=\left\{x\in A\,|\,\varphi(x)\right\}$$ to mean
$$\forall x \left(x\in B \Leftrightarrow \left(x\in A\ \land\ \varphi(x)\right)\right).$$ This too can be viewed as short notation for a significantly longer expression, where the $\Leftrightarrow$ is expressed using $\land$ and $\lnot$.

Thanks a lot , I actually knew a little bit about $\lnot$ and these kind of statements from when I red a little bit about formal logic.

EDIT:

Suppose that F=It's friday , A=I'm alone , B=I'm at home and C=I'm playing baseball:

In chronological order of knowledge:

1)B→A↔¬F
2)F→(B∧¬A)∨(¬B∧(A∨¬A))
3)C↔F∧(¬B∧¬A)
4)¬B∧F → C∧¬A
5)F→ ¬B ↔C

Therefore with the additionnal statements we can conclude that the bolded red in the 2nd statement F→(B∧¬A)∨(¬B∧(A∨¬A)) is impossible but was a possibility before knowing the next statements.

That would mean:
If I'm at home , then I'm alone if and only if it's not friday
If it's friday , then either (I'm at home and not alone) or (not at home and alone or not alone).
I'm playing baseball if and only if it's friday and I'm not at home and not alone.
If I'm not at home on friday , then I'm playing baseball.
If it's friday , then I'm not at home if and only if I play baseball.

We could also conclude that I'll never be alone on friday , whether I'm at home or playing baseball , which are my only two options.

 

[reenmachine]

$$\forall x \left(x\in B \Leftrightarrow \left(x\in A\ \land\ \varphi(x)\right)\right).$$ This too can be viewed as short notation for a significantly longer expression, where the $\Leftrightarrow$ is expressed using $\land$ and $\lnot$.

Giving it a try just for fun:

$$\forall x \left(x\in B \Leftrightarrow \left(x\in A\ \land\ \varphi(x)\right)\right).$$

∀x (x ∈ B → ¬(¬x ∈ A) ∧ ¬(¬p(x)))

?

 

[Fredrik]

What I had in mind was to first rewrite $p\leftrightarrow q$ as
$$(p\land q)\lor (\lnot p\land\lnot q).$$ Then you can use the definition of $\lor$ I mentioned earlier. An alternative is to rewrite $p\leftrightarrow q$ as
$$(p\rightarrow q)\land(q\rightarrow p).$$ Then you can use that $p\rightarrow q$ is defined as $\lnot(p\land\lnot q)$.

What you did was just to replace the $\leftrightarrow$ with $\rightarrow$, and insert $\lnot\lnot$ in two places.

 

[micromass]

Edit: Is my first rewrite even correct? I have deja vu. Feels like this is a mistake I've made before. I need to think about it.

The truth table seems to say that it's correct, so I think it is.

 

[Fredrik]

The truth table seems to say that it's correct, so I think it is.

Yes, I just checked it myself. I saw your post just after I deleted the comment where I questioned it.

 

[reenmachine]

Edit: Is my first rewrite even correct? I have deja vu. Feels like this is a mistake I've made before. I need to think about it.

I think it is.

Suppose P= I love her and Q= She loves me

Then I love her if and only if she loves me

-

I love her and she loves me OR I don't love her and she don't loves me

-

If I love her she loves me AND If she loves me I love her

And finally that:

It's not true that I love her and she don't loves me.

 

[reenmachine]

Another try

∀x ( ¬(x ∈ B ∧ ¬(x ∈ A ∧ p(x))) ∧ ¬((x ∈ A ∧ p(x)) ∧ ¬x ∈ B) )

(big spaces for clearness)

Just to be sure , is there a difference between ¬(R) and ¬R ? (I don't think there is)

Take note that I used the alternative method you've proposed in your earlier post.I skipped the part with the arrows and directly defined p → q with ¬(p∧¬q).

 

[Fredrik]

That looks correct, except for a missing ) at the end. There's no difference between ¬(R) and ¬R. The "she loves me" argument is fairly convincing, but if you want to know for sure, you must verify that the truth tables are the same. 1=true, 0=false.

p     q     p ↔ q
1     1       1[/color]
1     0       0[/color]
0     1       0[/color]
0     0       1[/color]

p     q     (p∧q) ∨ (¬p ∧ ¬q)
1     1       1   1[/color]  0  0  0    
1     0       0   0[/color]  0  0  1
0     1       0   0[/color]  1  0  0
0     0       0   1[/color]  1  1  1

 

[reenmachine]

That looks correct, except for a missing ) at the end. There's no difference between ¬(R) and ¬R. The "she loves me" argument is fairly convincing, but if you want to know for sure, you must verify that the truth tables are the same. 1=true, 0=false.

p     q     (p∧q) ∨ (¬p ∧ ¬q)
1     1       1   1[/color]  0  0  0    
1     0       0   0[/color]  0  0  1
0     1       0   0[/color]  1  0  0
0     0       0   1[/color]  1  1  1

Good , finally I got something right

About this part of the code in the quote , both the left and right side of the ∨ has to be completely different for it to be true is that correct? either 0 or 111 /or/ 1 or 000 for this specific case.

 

[Fredrik]

About this part of the code in the quote , both the left and right side of the ∨ has to be completely different for it to be true is that correct? either 0 or 111 /or/ 1 or 000 for this specific case.

The ∨ operation has the following truth table:

p     q     p∨q
1     1      1
1     0      1
0     1      1
0     0      0

Don't confuse "p or q" with "either p or q", which has 0 1 1 0 in the final column.

Maybe I should have used more colors in the big truth table.

p     q     (p∧q) ∨ (¬p ∧ ¬q)
1     1       1[/color]   1[/color]  0[/color]  0[/color]  0[/color]    
1     0       0[/color]   0[/color]  0[/color]  0[/color]  1[/color]
0     1       0[/color]   0[/color]  1[/color]  0[/color]  0[/color]
0     0       0[/color]   1[/color]  1[/color]  1[/color]  1[/color]

First you write down all possible truth values of p and q. That's the first two columns. Then you use the black columns to fill in the green columns. Then you use the green and black to fill in the brown columns. Then you use the brown to fill in the red. The brown and green columns are just intermediate steps. The actual truth table consists of the black and red columns.

Can you use truth tables to show that "if p then q" is equivalent to "if not q then not p"?

 

[reenmachine]

Can you use truth tables to show that "if p then q" is equivalent to "if not q then not p"?

Let's verify:

p     q      v   ¬q   ¬p
[U][B]1     1      1    0    0[/B][/U] 
1     0      0    1    0
0     1      0    0    1
0     0      1    1    1

?

Or did you wanted me to show the proof based on your tables?

 

[reenmachine]

I made a mistake that basically switched all the numbers in the last colums but that's because I originally misplaced both the ¬q and ¬p and replaced them without changing the 1s and 0s.It wasn't a logical mistake.

fixed

 

[Fredrik]

I meant that you should write down the truth table for p→q, and then write down the truth table for ¬q→¬p. They should be the same.

I don't understand the table you did.

Edit: Here's what I wanted you to do. Fill in numbers instead of the question marks in the tables below. In the second one, the first and third column of question marks should contain the truth values of ¬q and ¬p respectively, and the second column should contain the truth values of ¬q→¬p. The first and third are not part of the actual truth table, but it will be easier for you to write down the correct truth values for ¬q→¬p if you first write down the truth values of ¬p and ¬q.

p     q     p→q
1     1      ?
1     0      ?
0     1      ?
0     0      ?

p     q    ¬q → ¬p
1     1    ?  ? ?
1     0    ?  ? ?
0     1    ?  ? ?
0     0    ?  ? ?

 

[reenmachine]

p     q     p→q
1     1      1
1     0      0
0     1      0
0     0      1

p     q    ¬q → ¬p
1     1    0  1 0
1     0    1  0 0
0     1    0  0 1
0     0    1  1 1

?

 

[Fredrik]

The first one is 75% right. The final column should be 1 0 1 1. What you wrote down are the truth values of p↔q.

In the second one, you got the negations right. But the implication has the same problem as in the first table.

 

[reenmachine]

The first one is 75% right. The final column should be 1 0 1 1. What you wrote down are the truth values of p↔q.

In the second one, you got the negations right. But the implication has the same problem as in the first table.

? confusing here

p     q     p→q
1     1      1
1     0      0
0     1      1
0     0      1

Not so sure about the second one.

p     q    ¬q → ¬p
1     1    0  1 0
1     0    1  0 0
0     1    0  1 1
0     0    1  1 1

So ''if p , then q'' doesn't exclude that ''if not p , then q'' ? Therefore only the statement ''if p , then not q'' will be considered false?

 

[Fredrik]

Yes, that's right.

 

[CompuChip]

Yes and that is really by definition. Consider p being the statement "it is Friday" and q "I am alone". Let's consider the statement S: $p \implies q$.

If you are alone because it is Friday then the statement is clearly true. If it is Friday and your house is filled with friends, it is clearly false. This matches our intuition about what "implies" means.

Now suppose it's not Friday. You may be alone, or not. Basically, S has nothing to say about this. Still, we have to assign either "true" or "false" to it. The choice is somewhat arbitrary, I think looking at the intuitive meaning an argument can be made for both. So we need to make a choice, and we define S to be true if p is false, whatever the value of q.
Note that if we defined it to be true, then $p \implies q$ would have had exactly the same truth table as $p \land q$. If we defined it to be true if p is false and q is false, it would have had the same truth table as $p \Leftrightarrow q$. And if we had defined it to be true if p is false and q is true we would get the same truth table as for $q$.

 

[Fredrik]

So ''if p , then q'' doesn't exclude that ''if not p , then q'' ? Therefore only the statement ''if p , then not q'' will be considered false?

I'm not sure I understand this question, which you seem to have edited in seconds after I replied "yes, that's right". If you're asking why p→q is considered true when p is false (regardless of whether q is true or false), then CompuChip already gave you a good reply: If we make the final column 1 0 0 0, we get the truth table of ∧. If we make it 1 0 0 1, we get the truth table of ↔. If we make it 1 0 1 0, we get the truth table of q.

I will contribute the following example: Your friend is sure that his team is going to win the big game, so he says "if my team loses tonight, I will wear a dress to work tomorrow". His team wins. Is there any kind of clothing he can wear at work the next day that will force you to conclude that he lied to you? (If the final column of the truth table doesn't end with 1 1, the answer would be yes).

 

[reenmachine]

Yes and that is really by definition. Consider p being the statement "it is Friday" and q "I am alone". Let's consider the statement S: $p \implies q$.

If you are alone because it is Friday then the statement is clearly true. If it is Friday and your house is filled with friends, it is clearly false. This matches our intuition about what "implies" means.

Now suppose it's not Friday. You may be alone, or not. Basically, S has nothing to say about this. Still, we have to assign either "true" or "false" to it. The choice is somewhat arbitrary, I think looking at the intuitive meaning an argument can be made for both. So we need to make a choice, and we define S to be true if p is false, whatever the value of q.
Note that if we defined it to be true, then $p \implies q$ would have had exactly the same truth table as $p \land q$. If we defined it to be true if p is false and q is false, it would have had the same truth table as $p \Leftrightarrow q$. And if we had defined it to be true if p is false and q is true we would get the same truth table as for $q$.

Yeah this is what I thought , basically anything that is possible is true and the rest if false.

thanks man!

 

[reenmachine]

Is there any kind of clothing he can wear at work the next day that will force you to conclude that he lied to you?

The answer would be no.

I like these logical statements exercises , so much fun.

thanks a lot !

 

[Fredrik]

The answer would be no.

Right. My point was that this example provides the motivation for the choice to define → this way, with 1 1 in the final two positions of the truth table.

I like these logical statements exercises , so much fun.

Section 2.6 of the Book of Proof has more of them. So you can either do a few of those, or just prove a few of the the equivalences (2.1)-(2.5) using truth tables.

Do you understand all the exercises from post #249 now, including how to solve 2nd-degree polynomial equations, and how to derive the formula for the solutions of a 2nd-degree polynomial equation?

 

[reenmachine]

Do you understand all the exercises from post #249 now, including how to solve 2nd-degree polynomial equations, and how to derive the formula for the solutions of a 2nd-degree polynomial equation?

Here's the link for the exercises: http://www.people.vcu.edu/~rhammack/BookOfProof/Sets.pdf

I'm going to try a couple of random ones , if you think there's some in particular that I should attempt please tell me so.

Solutions:

1.{...,-21,-16,-11,-4,-1,4,9,...}
3.{-2,-1,0,1,2,3,4,5,6}
13.{...,-2,-1,0}
15.{...,-2,-1,0,1,2,3,...}
21.$\{x\in\mathbb N\,|\,\exists y\in\mathbb N~~ x=y^2\}$
27.$\{x\in\mathbb R\,|\,\exists y\in\mathbb R~~ x=yπ/2\}$

?

thanks!

 

[micromass]

Here's the link for the exercises: http://www.people.vcu.edu/~rhammack/BookOfProof/Sets.pdf

I'm going to try a couple of random ones , if you think there's some in particular that I should attempt please tell me so.

Solutions:

1.{...,-21,-16,-11,-4,-1,4,9,...}

Why -4?

3.{-2,-1,0,1,2,3,4,5,6}

OK

13.{...,-2,-1,0}

OK

15.{...,-2,-1,0,1,2,3,...}

This is true, but I'm curious how you found it.

21.$\{x\in\mathbb N\,|\,\exists y\in\mathbb N~~ x=y^2\}$

OK

27.$\{x\in\mathbb R\,|\,\exists y\in\mathbb R~~ x=yπ/2\}$

Why do you take $y\in \mathbb{R}$? In that case, shouldn't things like $\frac{\sqrt{2}\pi}{2}$ also be in the set?

 

[reenmachine]

Why -4?

Guess it's -6 , just a brain cramp.

This is true, but I'm curious how you found it.

I had no clue how to solve at first but then I thought to myself , it's not 5a=2b or 5a+2b=something , it's just 5a+2b , so basically all numbers in Z could be inserted there.

Why do you take $y\in \mathbb{R}$? In that case, shouldn't things like $\frac{\sqrt{2}\pi}{2}$ also be in the set?

$\{x\in\mathbb R\,| xπ/2\}$ ? I'm confused about what to do.

EDIT:$\{x\in\mathbb R\,|\,\exists y\in\mathbb Z~~ x=yπ/2\}$ ?

 

[Fredrik]

15.

As I said before, it's the set of all 5a+2b such that a and b are integers. It's pretty obvious that this is the set of all integers, $\mathbb Z$, as you have now concluded. (Edit: Ohh...after reading micromass' reply below, I see it's not as obvious as I thought. It's only obvious that this set will be a subset of $\mathbb Z$). If you want to prove that this "guess" is correct, you need to rely on the axiom that says that two sets are equal if and only if they have the same elements. Define $Z=\{5a+2b\,|\,a,b\in\mathbb Z\}$. We want to prove that $Z=\mathbb Z$.

Let $x\in Z$ be arbitrary. The definition of Z tells us that there exist $a,b\in\mathbb Z$ such that $5a+2b=x$. Since $\mathbb Z$ is closed under addition and multiplication, this implies that $x\in\mathbb Z$.

Let $x\in\mathbb Z$ be arbitrary. Define $a,b\in\mathbb Z$ by $a=x$ and $b=-2x$. We have $a,b\in\mathbb Z$ and $5a+2b=5x+2(-2x)=5x-4x=x$. This implies that $x\in Z$.

21. Note that your result can be simplified to $\left\{n^2\,|\,n\in\mathbb N\right\}$. The proof of that is similar to the proof of 15. (Most people use n and m for integers rather than x and y, but it's not necessary to do this. n is a dummy variable here, so you can use x instead).

27. The answer in your edit is correct, and can be simplified to $\left\{\frac{n\pi}{2}\,\big|\,n\in\mathbb Z\right\}$.