A couple of questions on set theory

[Dods]

Hi. I'm studying calculus in high school right now, and I became really interested in how calculus could be developed from a mathematically rigorous point of view. One of my instructors suggested I learn some set theory, so for about a week I've been researching stuff on the internet - very introductory stuff, like what subsets, unions, intersections are, the difference between naive set theory and ZF(C)...
I've gotten Naive Set Theory by Paul R. Halmos.

Set theory's turned out to be a lot more fun than I thought (it's nice to deal with this kind of math for a change) but I have a few questions.

My first question is: In a few places, it’s been said that the axiom of specification resolves Russell’s Paradox, but I couldn’t find anywhere how exactly it does this.

As I understand it, the axiom says that for every set $A$ and condition $P(x)$, there exists a set $B$ whose elements are all the elements of $A$ that satisfy the condition $P(x)$, or
$$B =\{x\in A~\vert~P(x)\}$$

That would mean Russell's paradoxical set $R= \{x|x\notin x\}$ would have to be rewritten in the form $R=\{x\in A~\vert~x\notin x\}$.

How does this guarantee or prove that Russell's paradox doesn't arise? What if $A\in A$ - then you would have $$\{A\in A~\vert~A\notin A\}$$ which would mean that if $A\in A$, by definition $A\notin A$, and if $A\notin A$, $A$ is a member of $A$.

I researched a bit and found that one of the axioms of ZFC implies no set can be a member of itself, but some sources said you don't need this axiom to resolve Russell's paradox. I tried to prove that $A\notin A$, and that went nowhere. I feel like I'm missing something basic.

Another thing I thought of: the axiom of specification guarantees that $R=\{x\in A~\vert~x\notin x\}$ exists only if you can find a suitable set $A$. Maybe the axiom doesn't prove that the paradox doesn't arise, only that it won't arise as long as no suitable $A$ is shown to exist? I don't know.

Any help would be greatly appreciated!

 

[micromass]

The point of the specification axiom is to make sure that the Russsell set $\{x~\vert~x\notin x\}$ does not define a set anymore in obvious way. The only way that it would define a set is that there exists a suitable set $A$ such that $\{x\in A~\vert~ x\notin x\} = \{x~\vert~ x\notin x\}$. Such a set has not been found yet and we're confident that it won't be found.

But you touch a sensitive point here. You want to prove that Russell's paradox cannot arise. Such a thing is (as far as I know) impossible. A very related issue is Godel's theorems. This theorems state that we can never prove that ZFC is consistent. That is, we can never show that paradoxes won't arise. Maybe we will be able to show that Russell's paradox won't show up, but it has been proven that we can't do that for all paradoxes.

So the sad part is that ZFC is (probably) without paradoxes, but we can never prove it to be the case. The best we can do is to say that no paradoxes has ever shown up the last 100 years that we've used ZFC.

Another point you bring up is the foundation axiom. This axiom can be used to rigorously show that there are no sets such that $A\in A$. But this would not prevent Russell's paradox to show up. Indeed, it has been proven that if ZFC without the foundation axiom has a paradox, then ZFC with the foundation axiom also has a paradox (although not the same one). In fact, as far as 99% of mathematics is concerned, the foundation axiom is a pretty useless axiom.

 

[Dods]

Thank you very much for giving me such a clear reply! Sorry that I didn't reply sooner, I've been sitting exams.

I have a question though: I've seen the Cartesian product for the 2-dimensional plane defined as:

$$\mathbb R^2 =\{(x,y)~\vert~x,y\in {\mathbb R}\}$$

and in general, a Cartesian square as

$$X\times Y =\{(x,y)~\vert~x\in X\ \text{and}\ y\in Y\}$$

This doesn't seem to follow the $\{x\in A~\vert~P(x)\}$ format. Is this notation also valid, or is this kind of standard abuse of notation, or shorthand for something else?

I thought up a way to construct the $\mathbb R^2$ set so that it does follow the format, but I have no idea if what I've come up with makes sense. Of course, if the format above is ok, this construction isn't necessary.

Thanks again :)

 

[micromass]

It's an abuse of notation. You're right that what you've written down doesn't follow the format. However, we can make it follow the format. Remember that

$$(x,y) := \{\{x\},\{x,y\}\}$$

by definition of the ordered pair.

Now, since $x,y\in X\cup Y$, we know that $\{x\}, \{x,y\} \in \mathcal{P}(X\cup Y)$ and thus $\{\{x\}, \{x,y\}\} \in \mathcal{P}(\mathcal{P}(X\cup Y))$. So we can write

$$X\times Y = \{ a \in \mathcal{P}(\mathcal{P}(X\cup Y))~\vert~\exists x\in X:~\exists y\in Y:~a = \{\{x\},\{x,y\}\}\}$$
This is the official way of defining the cartesian product. Of course, it can be simplified as follows:

$$X\times Y = \{(x,y) \in \mathcal{P}(\mathcal{P}(X\cup Y))~\vert~ x\in X, y\in Y\}$$

but this is already an abuse of notation.

Since $\mathcal{P}(\mathcal{P}(X\cup Y))$ is annoying to write, we use the shorthand

$$X\times Y = \{(x,y)~\vert~x\in X,~y\in Y\}$$

This is an even larger abuse of notation, since the format doesn't make it clear that it's a set. However, since we can define it as a set, we allow the abuse of notation.

 

[micromass]

I think there's a { missing at the end there.

$\{\{\{x\},\{x,y\}\}\}$

That was a good post to read.

I think it's right how I wrote it. Why do you think there s another $\{$ needed?

 

[reenmachine]

I think it's right how I wrote it. Why do you think there s another $\{$ needed?

Sorry , had a brain cramp and forgot about the { at the far left.I will delete my post not to confuse anybody.

 

[Dods]

Thank you very much micromass!

Now, since $x,y\in X\cup Y$, we know that $\{x\}, \{x,y\} \in \mathcal{P}(X\cup Y)$ and thus $\{\{x\}, \{x,y\}\} \in \mathcal{P}(\mathcal{P}(X\cup Y))$. So we can write

$$X\times Y = \{ a \in \mathcal{P}(\mathcal{P}(X\cup Y))~\vert~\exists x\in X:~\exists y\in Y:~a = \{\{x\},\{x,y\}\}\}$$
This is the official way of defining the cartesian product.

You say later that this is "annoying to write" - this definition might look clunky to you but the way this set is constructed seems really elegant to me! Right now all the formal math/ logic I see looks really cool and exciting, especially having only been studying formulas in calculus up till now.

Just a question about the set

$$X\times Y = \{ a \in \mathcal{P}(\mathcal{P}(X\cup Y))~\vert~\exists x\in X:~\exists y\in Y:~a = \{\{x\},\{x,y\}\}\}$$

I think that I get what it means, but how exactly would I read this out? I know it's something like "the set of all $a$ in $\mathcal{P}(\mathcal{P}(X\cup Y))$ such that there exists a $x$ in $X$ and there exists a $y$ in $Y$ so that $a = \{\{x\},\{x,y\}\}$. I don't know how to read the colons in the sentence - I thought they meant "such that" but that would make the start of the sentence "there exists a $x$ in $X$ such that there exists a $y$ in $Y$" which doesn't make sense to me.

Of course, it can be simplified as follows:

$$X\times Y = \{(x,y) \in \mathcal{P}(\mathcal{P}(X\cup Y))~\vert~ x\in X, y\in Y\}$$

but this is already an abuse of notation.

Is this an abuse of notation because you have $(x,y) \in \mathcal{P}(\mathcal{P}(X\cup Y))$ and not $a \in \mathcal{P}(\mathcal{P}(X\cup Y))$, and because you don't have qualifiers on $x$ and $y$?

Would it be okay if I posted some basic proofs/construction of sets here for feedback, so that I can get used to the format sets need to be in? I don't know if the sets I'm constructing are valid and I don't know if my proofs are okay.

Thanks a lot again! :)

 

[micromass]

I think that I get what it means, but how exactly would I read this out? I know it's something like "the set of all $a$ in $\mathcal{P}(\mathcal{P}(X\cup Y))$ such that there exists a $x$ in $X$ and there exists a $y$ in $Y$ so that $a = \{\{x\},\{x,y\}\}$. I don't know how to read the colons in the sentence - I thought they meant "such that" but that would make the start of the sentence "there exists a $x$ in $X$ such that there exists a $y$ in $Y$" which doesn't make sense to me.

The way you read it out is perfect. The : is actually just a placeholder, it isn't necessarily read at as "such as" (but it often will be).

Is this an abuse of notation because you have $(x,y) \in \mathcal{P}(\mathcal{P}(X\cup Y))$ and not $a \in \mathcal{P}(\mathcal{P}(X\cup Y))$

Yes.

and because you don't have qualifiers on $x$ and $y$?

No, that is ok. A notation like

$$\{a\in \mathbb{R}~\vert ~ a=2\}$$

is perfectly valid even though there are no quantifiers.

Would it be okay if I posted some basic proofs/construction of sets here for feedback, so that I can get used to the format sets need to be in? I don't know if the sets I'm constructing are valid and I don't know if my proofs are okay.

Sure, go ahead!

 

[Dods]

Hey,
I just wanted to say that I really really appreciate the help so far. I haven't been able to post the last few days but hopefully by tomorrow things will get back to normal.

I was going to try a proof but realized there was a question I needed to ask:

From what I understand, "If" refers to a sufficient condition: If the food is honey, Winnie the Pooh will eat it, no matter how full he gets.

"Only if" refers to a necessary condition: Only if the food is honey, will Pooh eat it. This would mean that he turns up his nose at any non-honey food, but should he be served honey, there is no guarantee he will eat it.

"If and only if" would then refer to a sufficient and necessary condition. Is all that correct?

Anyway, if I have statements p and q, and I say p if and only if q, does that also mean q if and only p?

Another point: if I have statements t, u and v, and I know that t if and only if u or v, can I say:

t if v

?

Thanks :)

 

[verty]

Hey,
I just wanted to say that I really really appreciate the help so far. I haven't been able to post the last few days but hopefully by tomorrow things will get back to normal.

I was going to try a proof but realized there was a question I needed to ask:

From what I understand, "If" refers to a sufficient condition: If the food is honey, Winnie the Pooh will eat it, no matter how full he gets.

"Only if" refers to a necessary condition: Only if the food is honey, will Pooh eat it. This would mean that he turns up his nose at any non-honey food, but should he be served honey, there is no guarantee he will eat it.

"If and only if" would then refer to a sufficient and necessary condition. Is all that correct?

Anyway, if I have statements p and q, and I say p if and only if q, does that also mean q if and only p?

Another point: if I have statements t, u and v, and I know that t if and only if u or v, can I say:

t if v

?

Thanks :)

I would avoid this form: t if v, it is too similar to the problematic t only if v. "I will go with you only if it rains" --> this implies obligation in English, as does "I will go with you if it rains". I think it is better to reserve "if" for contexts in which "only if" has the opposite meaning. I prefer t when v or t whenever v.

 

[micromass]

Hey,
I just wanted to say that I really really appreciate the help so far. I haven't been able to post the last few days but hopefully by tomorrow things will get back to normal.

I was going to try a proof but realized there was a question I needed to ask:

From what I understand, "If" refers to a sufficient condition: If the food is honey, Winnie the Pooh will eat it, no matter how full he gets.

"Only if" refers to a necessary condition: Only if the food is honey, will Pooh eat it. This would mean that he turns up his nose at any non-honey food, but should he be served honey, there is no guarantee he will eat it.

"If and only if" would then refer to a sufficient and necessary condition. Is all that correct?

Yes, that is correct.

Anyway, if I have statements p and q, and I say p if and only if q, does that also mean q if and only p?

Yes, but it actually requires a proof. The best way to prove this is by truth tables. Have you covered this already?

Another point: if I have statements t, u and v, and I know that t if and only if u or v, can I say:

t if v

Like the previous poster said, it is true, but it might not be opportune to say things like this. I would rather say

v implies t

In fact, I never use "if" and "only if". They are too confusing to me. I only work with "implies". I do use "if and only if".

 

[reenmachine]

Very fast learner there , much faster than me! I hope you hang in there man! It took me a couple of weeks to understand all of these concepts on a basic level.

 

[Dods]

reenmachine - Thanks a lot for the encouragement, I hope I hang in there too! :) I had a look at your thread and your progress seems amazing!

micromass and verty -

Thanks a lot for the advice! :)
I think I see what you mean, that saying "v implies t", "t whenever v" is less confusing than "t if v".
micromass, I haven't covered truth tables yet. I'll google them. Do you know a good reference or book on the subject?

If we know that "t if and only if u or v", what sort of sentences can we derive from that, that are definitely true, with just t and u in them, or just t and v?

Lets say we have the sentence:

$x^2=x\ \ \ \text{if and only if}\ \ \ x = 0\ \ \text{or}\ \ x = 1$

where:

t is $x^2=x$,
v is $x = 0$, and
u is $x = 1$.

I'd expect that we can then derive the following sentences:

$x^2=x$ when $x=0$

$x^2=x$ when $x=1$

or equivalently, we know that the sentences

t if v

t if u

are true,

because when we have "t if and only if u or v" the "or" relation between our u and v suggests that u on its own, and v on its own, are sufficient conditions for our t to be true. It reminds me of multiplication being distributive over addition - it's like here the "if" operator "distributes" over the "or" operator: t if(u or v) = (t if u) or (t if v).

Also, I don't think the "only if" operator distributes over the "or" - that is, I don't think the truth of "t if and only if u or v" implies the truth of the sentences "t only if u", "t only if v". If it did, we would have (returning to the example):

$x^2=x\ \ \ \text{if and only if}\ \ \ x = 0\ \ \text{or}\ \ x = 1$ implies $x^2=x\ \ \ \text{only if}\ \ \ x = 1$

which is obviously false.

This is all just intuition, all this could be way off, and even if it's correct I wouldn't know how to prove it. I don't know if you can even talk about the distributivity of logical operators. I'm just trying to work as much of this out myself with examples and so on.

If you can talk about the distributivity of logic operators, it would seem that the situation is reversed when you have a sentence like "t if and only if u and v" - the "only if" operator seems to distribute over the "and", and the "if" operator doesn't -

For example, let's say we had, where $x$ is an integer:

$x^2=x\ \ \ \text{if and only if}\ \ \ x > -1\ \ \text{and}\ \ x < 2$

You can derive the sentences

$x^2=x$ only if $x > -1$

$x^2=x$ only if $x < 2$

because

$x^2=x\ \ \ \text{only if}\ \ \ x > -1\ \ \text{and}\ \ x < 2$

=$x^2=x\ \ \ \text{only if}\ \ x < 2$ and $x^2=x\ \ \ \text{only if}\ \ x > -1$But you couldn't have $x^2=x\ \ \ \text{if}\ \ \ x > -1$ because $x > -1$ is not a sufficient condition for $x^2=x$

I hope I've not made a total idiot of myself. I'm now really curious about this!

 

[micromass]

You touch some interesting points. I think most of your questions can be answered if you learn truth tables. A truth table is a technique to see whether certain formulas are true or whether two formulas are equivalent.

For example, you have the following formula $P~\leftrightarrow~(Q~\wedge~R)$. What does this mean? Well, the $\leftrightarrow$ is a symbol for "if and only if". The $\wedge$ is a symbol for "and". The $P$, $Q$ and $R$ can be anything. Let us construct the truth table of this:

$$\begin{array}{c|c|c|c|c} P & Q & R & Q\wedge R & P\leftrightarrow (Q\wedge R)\\ \hline 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 & 1\\ 0 & 1 & 0 & 0 & 1\\ 0 & 1 & 1 & 1 & 0\\ 1 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 & 0\\ 1 & 1 & 1 & 1 & 1 \end{array}$$

What does this mean? Well take a look at the second line. There we say that $P$ and $Q$ are false and that $R$ is true. But in that case, we have that $Q~\text{and}~R$ is also true. So we are in a situation where $P$ is false and $P~\text{and}~R$ is false. So the equivalence $P~\text{if and only if}~(Q~\text{and}~R)$ is true. Indeed, something like $A~\leftrightarrow~B$ is true if both $A$ and $B$ are false, or if they are both true.

However, in the last line, we have that $P$, $Q$ and $R$ are both true. So $Q~\wedge~R$ is also true. So both $P$and $Q~\wedge~R$ is true. So the equivalence is true here.

Now, let us construct the truth table of $(P~\leftrightarrow R)~\wedge~(Q~\leftrightarrow~R)$. We get

$$\begin{array}{c|c|c|c|c|c} P & Q & R & P\leftrightarrow R & P\leftrightarrow Q & (P~\leftrightarrow R)~\wedge~(Q~\leftrightarrow~R)\\ \hline 0 & 0 & 0 & 1 & 1 & 1\\ 0 & 0 & 1 & 0 & 1 & 0\\ 0 & 1 & 0 & 1 & 0 & 0\\ 0 & 1 & 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 & 0 & 0\\ 1 & 0 & 1 & 1 & 0 & 0\\ 1 & 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 1 & 1 & 1 & 1 \end{array}$$

Now, look at both columns of the truth tables. The columns are not equal. Thus the statements
$$P\leftrightarrow (Q\wedge R)$$
and
$$(P~\leftrightarrow R)~\wedge~(Q~\leftrightarrow~R)$$
are not equivalent statements.
However, we do see from the truth tables that if the second formula is true, then the first formula is true as well. So we do get that the statement $(P~\leftrightarrow R)~\wedge~(Q~\leftrightarrow~R)$ implies the statement $P\leftrightarrow (Q\wedge R)$.

Now, you can do this with all the examples in your post and you can check whether two formulas are equivalent or if one implies the other.

Good books to read are Vellemans "how to prove it" and the book of proof (which can be found for free online).
More advanced logic books are Enderton "A Mathematical Introduction to Logic" and Mendelson's "Introduction to Mathematical Logic"

 

[micromass]

Before you can construct your own truth tables, you'll need to know the different logical connectives and their truth tables.

1) The connective "not". So a statement "Not A" is true if and only if "A" is false. The not connective is denoted by $\neg A$. The truth table is

$$\begin{array}{c|c} A & \neg A\\ \hline 0 & 1\\ 1 & 0 \end{array}$$

2) The connective "and". A statement "A and B" is true only if A and B are both true and is false otherwise. The and connective is denoted by $A\wedge B$. The truth table is

$$\begin{array}{c| c | c} A & B & A\wedge B\\ \hline 0 & 0 & 0\\ 0 & 1 & 0\\ 1 & 0 & 0\\ 1 & 1 & 1 \end{array}$$

3) The connective "or". A statement "A or B" is true if either A or B is true or both. The connective is denoted by $A\vee B$. The truth table is

$$\begin{array}{c| c | c} A & B & A\vee B\\ \hline 0 & 0 & 0\\ 0 & 1 & 1\\ 1 & 0 & 1\\ 1 & 1 & 1 \end{array}$$

Here is a little disconnect from everyday language. If we say "Is the care blue or red?", then we don't expect the answer "both". But in mathematics, "or" can certainly mean that both are true.
The "or" from everyday language is called the "exclusive or" and isn't used very much.4) The implication. This is denoted by $A\rightarrow B$. The truth table is a bit tricky here and confuses a lot of newcomers. The idea is that the only way that $A\rightarrow B$ is false happens if $B$ is false and $A$ is true. This leads to the following truth table

$$\begin{array}{c| c | c} A & B & A\rightarrow B\\ \hline 0 & 0 & 1\\ 0 & 1 & 1\\ 1 & 0 & 0\\ 1 & 1 & 1 \end{array}$$

The first two lines might seem a bit weird, but you can see this as the definition of the implication.

5) The double implication: $A\leftrightarrow B$. This is true if $A$ and $B$ have the same truth value. Thus:

$$\begin{array}{c| c | c} A & B & A\leftrightarrow B\\ \hline 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\\ 1 & 1 & 1 \end{array}$$

These are the basic truth tables. Now you can construct truth tables of your own.

 

[Dods]

Thank you for the explanation and for giving me the truth tables for the logical connectives :)
I'll try proving some of the statements in my last post. Thank you also for pointing out the difference between two sentences being equal and one sentence implying another, a point I think wasn't completely clear to me.

There we say that $P$ and $Q$ are false and that $R$ is true. But in that case, we have that $Q~\text{and}~R$ is also true.

How can $Q~\text{and}~R$ be true if $Q$ is false and $R$ is true? In the truth table for "and" that you gave, $Q~\text{and}~R$ is true when both variables are true.

Also, when you have $A\rightarrow B$ I assume that's the same as $A\ \text{implies} \ B$ or $B\ \text{when} \ A$?

Good books to read are Vellemans "how to prove it" and the book of proof (which can be found for free online).
More advanced logic books are Enderton "A Mathematical Introduction to Logic" and Mendelson's "Introduction to Mathematical Logic"

I'll check those out!

 

[micromass]

How can $Q~\text{and}~R$ be true if $Q$ is false and $R$ is true? In the truth table for "and" that you gave, $Q~\text{and}~R$ is true when both variables are true.

You're right, sorry. if $Q$ is false and $R$ is true, then $Q~\text{and}~R$ is false.

Also, when you have $A\rightarrow B$ I assume that's the same as $A\ \text{implies} \ B$ or $B\ \text{when} \ A$?

Yes.

 

[reenmachine]

Here's the link for the book of proof.It's free.

http://www.people.vcu.edu/~rhammack/BookOfProof/

It seems the web page changed a bit , I think he made a second edition.

I suggest you buy it , I have the book and it looks much better than the online version and it's cheap (like 10$).The online version has some weird notations like the brackets and they are ugly as hell.

 

[Dods]

Thanks for the info reenmachine. I'll have to see if I can buy the book where I live, ordering books from here is hell.

micromass, I had a question:

4) The implication. This is denoted by $A\rightarrow B$. The truth table is a bit tricky here and confuses a lot of newcomers. The idea is that the only way that $A\rightarrow B$ is false happens if $B$ is false and $A$ is true. This leads to the following truth table

$$\begin{array}{c| c | c} A & B & A\rightarrow B\\ \hline 0 & 0 & 1\\ 0 & 1 & 1\\ 1 & 0 & 0\\ 1 & 1 & 1 \end{array}$$

The first two lines might seem a bit weird, but you can see this as the definition of the implication.

I'm trying to visualize each of the four cases. I understand why $A\rightarrow B$ is false when B is false and A is true. I think I understand why $A\rightarrow B$ is true when A and B are both false (the way I thought about it, if you have the statement $$3^2 = 10\ \text{implies} \ 11- 3^2 = 1$$

it doesn't matter if they are false, the first part still implies the second part) although this example seems a little off to me.

I don't understand how $A\rightarrow B$ is true when A is false and B is true? Could you explain?
Or am I missing the point? Are all the cases other than "A is true and B is false" true because you've defined "A is true and B is false" to be the only false case?

Thanks again for all your great help!

 

[micromass]

The way I see it, is that an implication $A\rightarrow B$ is only useful if $A$ is true. In that case, you can decide immediately that $B$ is true as well. In other cases, the implication is useless. Now, if $A$ is false, then there is nothing you can decide about $B$. For example

If "I am president Obama" then "I am human"

This is certainly a true implication. But if I apply the sentence "I am president Obama" to myself, then this is false. Still, the sentence "I am human" remains true and the implication itself is also true.

Or

If "I am president Obama" then "I am american"

This is again a true implication. But if I apply both sentences "I am president Obama" and "I am american" to myself, then they are false.

The only time we care about the above implications is if I actually am president Obama. That is the only interesting case, so it's the only thing we really care about. What happens to the implication if I'm not president Obama, is pretty useless information.

The philosophy behind the implication is that the only way an implication is false is if $A$ is true and $B$ is false. The rest always makes the implication true. Even though if $A$ is false, then this is a vacuous truth: we don't really care about it.

 

[reenmachine]

Thanks for the info reenmachine. I'll have to see if I can buy the book where I live, ordering books from here is hell.

Take note that the book is probably identical except for the notations , so it's not a big deal and you can use the online version.

 

[Dods]

Here goes at trying to use the truth tables:

I want to show that $P\leftrightarrow Q$ is equivalent to $(P~\rightarrow Q)~\wedge~(Q~\rightarrow~P)$

We have:

$$\begin{array}{c|c|c|c|c|c} P & Q & P\rightarrow Q & Q\rightarrow P & (P~\rightarrow Q)~\wedge~(Q~\rightarrow~P)\\ \hline 0 & 0 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 0\\ \end{array}$$
We know that this is the truth table for $P\leftrightarrow Q$ is:
$$\begin{array}{c| c | c} P & Q & P\leftrightarrow Q\\ \hline 0 & 0 & 1\\ 0 & 1 & 0\\ 1 & 0 & 0\\ 1 & 1 & 1 \end{array}$$

We can see that the columns for $P\leftrightarrow Q$ and $(P~\rightarrow Q)~\wedge~(Q~\rightarrow~P)$ are identical, therefore the two statements are equivalent.

 

[micromass]

That's right!

 

[Dods]

Awesome! :) Tomorrow I'll do some more truth tables, and try to get my head around dome stuff in the book of proof...

G'night guys, thanks a lot!

 

[Dods]

In one of my last post I raised the question of how $(U\vee V)\rightarrow T$ is related to $(U\rightarrow T)\vee (V\rightarrow T)$ or in words, the relationship between the statements

t if (u or v)

(t if u) or (t if v)

These statements are not equal (and I'll prove it) and I think $(U\vee V)\rightarrow T$ implies $(U\rightarrow T)\vee (V\rightarrow T)$, although I won't give a proof right now.

----

Prove $[(U\vee V)\rightarrow T ] \neq [(U\rightarrow T)\vee (V\rightarrow T)]$

Proof-

Asuume $(U\vee V)\rightarrow T$ equals $(U\rightarrow T)\vee (V\rightarrow T)$. That means that under the conditions that $(U\vee V)\rightarrow T$ is false, $(U\rightarrow T)\vee (V\rightarrow T)$ is false.

$(U\vee V)\rightarrow T$ is false when $(U\vee V)$ is true and $T$ is false (we know from the $A\rightarrow B$ proof table that for any $A$ and $B$, $A\rightarrow B$ is false when $A$ is true and $B$ is false).

Lets consider the case where

$T$ is false
$U$ is true
$V$ is false *

We immediately have that $(U\vee V)$ is true (by definition of OR, if $A$ is true and $B$ is false, $A\vee B$ is true) and, be extension, that
$(U\vee V)\rightarrow T$ is false. In addition, we have $(U\rightarrow T)$ is false, and $(V\rightarrow T)$ is true.

The fact that $(U\vee V)\rightarrow T$ is false means that that $(U\rightarrow T)\vee (V\rightarrow T)$ should also be false (our initial assumption was that the two statements are equal). However, seeing as $(V\rightarrow T)$ is true and $(U\rightarrow T)$ is false, $(U\rightarrow T)\vee (V\rightarrow T)$ must be true (by definition of OR, if $A$ is true and $B$ is false, $A\vee B$ is true).

Our initial assumption that $(U\vee V)\rightarrow T$ equals $(U\rightarrow T)\vee (V\rightarrow T)$ has led us to a contradiction and therefore must be wrong.

Therefore, $[(U\vee V)\rightarrow T ] \neq [(U\rightarrow T)\vee (V\rightarrow T)]$.

* We could have easily set $V$ to true and $U$ to false and continues in a nearly identical proof. Also, throughout the proof I've assumed that $A\vee B$ is the same as $B\vee A$. I could have structured it carefully and not needed this assumption but its such a basic assumption I think I'm fine like this.

--------

Eagerly/nervously awaiting to hear what you think of my proof! :) I'm not used to verbose proofs and most of the set-theoretic proofs I've seen are like that, so I'm trying that "style" out to be ready for set theory proofs.

Thanks :)

 

[micromass]

Eagerly/nervously awaiting to hear what you think of my proof! :) I'm not used to verbose proofs and most of the set-theoretic proofs I've seen are like that, so I'm trying that "style" out to be ready for set theory proofs.

In almost all cases, I would say that "verbose" proofs are better. But in this case, I think that simply making the truth tables of both statements should have been enough to make the conclusion. It's much shorter for you to type and much easier to read. In all other cases, a verbose proof is better.

In one of my last post I raised the question of how $(U\vee V)\rightarrow T$ is related to $(U\rightarrow T)\vee (V\rightarrow T)$ or in words, the relationship between the statements

t if (u or v)

(t if u) or (t if v)

These statements are not equal (and I'll prove it) and I think $(U\vee V)\rightarrow T$ implies $(U\rightarrow T)\vee (V\rightarrow T)$, although I won't give a proof right now.

The word "equal" is not really right here. I think that "equivalent" would be better.

Prove $[(U\vee V)\rightarrow T ] \neq [(U\rightarrow T)\vee (V\rightarrow T)]$

Proof-

Asuume $(U\vee V)\rightarrow T$ equals $(U\rightarrow T)\vee (V\rightarrow T)$. That means that under the conditions that $(U\vee V)\rightarrow T$ is false, $(U\rightarrow T)\vee (V\rightarrow T)$ is false.

$(U\vee V)\rightarrow T$ is false when $(U\vee V)$ is true and $T$ is false (we know from the $A\rightarrow B$ proof table that for any $A$ and $B$, $A\rightarrow B$ is false when $A$ is true and $B$ is false).

Lets consider the case where

$T$ is false
$U$ is true
$V$ is false *

You assume this case, and you mention in the footnote an analogous case. But what about the case that $U$ and $V$ are both true? This needs to be covered as well.

We immediately have that $(U\vee V)$ is true (by definition of OR, if $A$ is true and $B$ is false, $A\vee B$ is true) and, be extension, that
$(U\vee V)\rightarrow T$ is false. In addition, we have $(U\rightarrow T)$ is false, and $(V\rightarrow T)$ is true.

The fact that $(U\vee V)\rightarrow T$ is false means that that $(U\rightarrow T)\vee (V\rightarrow T)$ should also be false (our initial assumption was that the two statements are equal). However, seeing as $(V\rightarrow T)$ is true and $(U\rightarrow T)$ is false, $(U\rightarrow T)\vee (V\rightarrow T)$ must be true (by definition of OR, if $A$ is true and $B$ is false, $A\vee B$ is true).

Our initial assumption that $(U\vee V)\rightarrow T$ equals $(U\rightarrow T)\vee (V\rightarrow T)$ has led us to a contradiction and therefore must be wrong.

Therefore, $[(U\vee V)\rightarrow T ] \neq [(U\rightarrow T)\vee (V\rightarrow T)]$.

* We could have easily set $V$ to true and $U$ to false and continues in a nearly identical proof. Also, throughout the proof I've assumed that $A\vee B$ is the same as $B\vee A$. I could have structured it carefully and not needed this assumption but its such a basic assumption I think I'm fine like this.

The rest I'm ok with. But drawing truth tables would make this a lot easier.

 

[Dods]

The word "equal" is not really right here. I think that "equivalent" would be better.

You're right :)

You assume this case, and you mention in the footnote an analogous case. But what about the case that $U$ and $V$ are both true? This needs to be covered as well.

Surely even if I find just one case where statement A is true and statement B is false, the two statements are not equivalent?

The rest I'm ok with. But drawing truth tables would make this a lot easier.

OK. I just needed to see if the progression of my ideas was logical, I've done almost no proofs. :)
Thanks micromass.

 

[micromass]

Surely even if I find just one case where statement A is true and statement B is false, the two statements are not equivalent?

Yes, you're right. Ignore my comment then.

 

[Dods]

I haven't been active for a few days because I've been studying for my exams. But tomorrow my exams in most subjects will be over and I'll be able to come back to this and keep learning math!

Again, thank you so much for your help and encouragement! I really appreciate it.

 

[micromass]

I haven't been active for a few days because I've been studying for my exams. But tomorrow my exams in most subjects will be over and I'll be able to come back to this and keep learning math!

Again, thank you so much for your help and encouragement! I really appreciate it.

Good luck with your exams then! I look forward to discussing new math!

 

[Dods]

Ok, so I was thinking, is there a truth table for the "only if" operator?

I tried to build a truth table for $P\ \text{only if}\ Q$.

Case 1: $P$ is false, $Q$ is false.

I think in this case $P\ \text{only if}\ Q$ is vacuously true, although I'm still not comfortable with vacuous truths.

Case 2: $P$ is false, $Q$ is true.
Case 3: $P$ is true, $Q$ is true.

In these cases the statement $P\ \text{only if}\ Q$ is true - $Q$ is a necessary condition for $P$, but not a sufficient one so both cases make sense.

Case 4: $P$ is true, $Q$ is false.

In this case the statement is false - $Q$ is necessary for $P$, so we can't have $P$ true when $Q$ is false.

That gives us the following truth table:

$$\begin{array}{c| c | c} P & Q & P\ \text{only if}\ Q\\ \hline 0 & 0 & 1\\ 0 & 1 & 1\\ 1 & 1 & 1\\ 1 & 0 & 0 \end{array}$$

That is equivalent to the table for $P~\rightarrow Q$

Also, earlier we showed that $P\leftrightarrow Q$ is equivalent to $(P~\rightarrow Q)~\wedge~(Q~\rightarrow~P)$.

So that's really the same as saying $P\leftrightarrow Q$ is equivalent to $(P\ \text{only if}\ Q)~\wedge~(P\ \text{if}\ Q)$.

Is all that right?

 

[micromass]

Everything that you wrote down is right! You seem to grasp this logic stuff pretty well.

 

[Dods]

~Thanks :)

At some point I've post some more truth tables and logic related stuff, but I have some more set-theoretic questions.

Lets say I want all the subsets of ${\mathbb R}$ that have 3 distinct real numbers in them.

So that's like:

$$T = \{t\in \mathcal{P}(\mathbb R)~\vert~\exists a,b,c \in \mathbb R:~a \neq b, a \neq c, b \neq c :~ t = \{a,b,c\}\}$$

right?

Edit: changed $a \neq b \neq c$ into the statements above.

 

[micromass]

~Thanks :)

At some point I've post some more truth tables and logic related stuff, but I have some more set-theoretic questions.

Lets say I want all the subsets of ${\mathbb R}$ that have 3 distinct real numbers in them.

So that's like:

$$T = \{t\in \mathcal{P}(\mathbb R)~\vert~\exists a,b,c \in \mathbb R:~a \neq b, a \neq c, b \neq c :~ t = \{a,b,c\}\}$$

right?

Edit: changed $a \neq b \neq c$ into the statements above.

That's right, although we usually will abuse notation and say

$$T = \{\{a,b,c\}\in \mathcal{P}(\mathbb R)~\vert~a \neq b, a \neq c, b \neq c\}$$

 

[Dods]

Ok, so let's say we have the set of all subsets of of $\mathbb R$ that have 3 distinct real numbers in them:

$$T = \{t\in \mathcal{P}(\mathbb R)~\vert~\exists a,b,c \in \mathbb R:~a \neq b, a \neq c, b \neq c :~ t = \{a,b,c\}\}$$

What if I want to add a constraint that involves $a$, or $b$ or $c$ or a similar variable directly?

For instance, what if I want the set of all subsets of of $\mathbb R$ that have 3 distinct real numbers in them, and that all share a common element?

To get that last bit I might add a statement something like this:

"for all $\{a,b,c\}, \{d,e,f\}$, if $d \neq a$ and $e \neq a$, then $f = a$"

But is it allowed to add formulas or statements that directly involve $a$ or $b$ or $\{a,b,c\}$ and not $t$s? For instance, could I say "for all $\{a,b,c\}, \{d,e,f\}$" or would I first have to define a $t_1=\{a,b,c\}$, $t_2=\{d,e,f\}$...and so on? (assuming I don't want to abuse the notation)