# A couple of questions on set theory

1. May 18, 2013

### 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!

Last edited: May 18, 2013
2. May 18, 2013

### micromass

Staff Emeritus
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.

3. May 19, 2013

### 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 :)

Last edited: May 19, 2013
4. May 19, 2013

### micromass

Staff Emeritus
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.

5. May 19, 2013

### micromass

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

6. May 19, 2013

### reenmachine

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

7. May 21, 2013

### Dods

Thank you very much micromass!!

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.

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! :)

8. May 21, 2013

### micromass

Staff Emeritus
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).

Yes.

No, that is ok. A notation like

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

is perfectly valid even though there are no quantifiers.

9. May 23, 2013

### 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 realised 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 :)

Last edited: May 23, 2013
10. May 23, 2013

### verty

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.

11. May 23, 2013

### micromass

Staff Emeritus
Yes, that is correct.

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

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".

12. May 23, 2013

### 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.

Last edited: May 23, 2013
13. May 25, 2013

### 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, lets 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$

14. May 25, 2013

### micromass

Staff Emeritus
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"

15. May 25, 2013

### micromass

Staff Emeritus
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.

16. May 25, 2013

### 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.

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$?

I'll check those out!

17. May 25, 2013

### micromass

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

Yes.

18. May 25, 2013

### 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.

Last edited: May 25, 2013
19. May 25, 2013

### 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.

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!

20. May 25, 2013

### micromass

Staff Emeritus
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.