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 > -1But 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}<br /> P &amp; Q &amp; R &amp; Q\wedge R &amp; P\leftrightarrow (Q\wedge R)\\<br /> \hline<br /> 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1\\<br /> 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1\\<br /> 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1\\<br /> 0 &amp; 1 &amp; 1 &amp; 1 &amp; 0\\<br /> 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\<br /> 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0\\<br /> 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0\\<br /> 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1<br /> \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}<br /> P &amp; Q &amp; R &amp; P\leftrightarrow R &amp; P\leftrightarrow Q &amp; (P~\leftrightarrow R)~\wedge~(Q~\leftrightarrow~R)\\<br /> \hline<br /> 0 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 1\\<br /> 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0\\<br /> 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0\\<br /> 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 &amp; 0\\<br /> 1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0\\<br /> 1 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0\\<br /> 1 &amp; 1 &amp; 0 &amp; 0 &amp; 1 &amp; 0\\<br /> 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1<br /> \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}<br /> A &amp; \neg A\\<br /> \hline<br /> 0 &amp; 1\\<br /> 1 &amp; 0<br /> \end{array}<br />

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}<br /> A &amp; B &amp; A\wedge B\\<br /> \hline<br /> 0 &amp; 0 &amp; 0\\<br /> 0 &amp; 1 &amp; 0\\<br /> 1 &amp; 0 &amp; 0\\<br /> 1 &amp; 1 &amp; 1<br /> \end{array}<br />

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}<br /> A &amp; B &amp; A\vee B\\<br /> \hline<br /> 0 &amp; 0 &amp; 0\\<br /> 0 &amp; 1 &amp; 1\\<br /> 1 &amp; 0 &amp; 1\\<br /> 1 &amp; 1 &amp; 1<br /> \end{array}<br />

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}<br /> A &amp; B &amp; A\rightarrow B\\<br /> \hline<br /> 0 &amp; 0 &amp; 1\\<br /> 0 &amp; 1 &amp; 1\\<br /> 1 &amp; 0 &amp; 0\\<br /> 1 &amp; 1 &amp; 1<br /> \end{array}<br />

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}<br /> A &amp; B &amp; A\leftrightarrow B\\<br /> \hline<br /> 0 &amp; 0 &amp; 1\\<br /> 0 &amp; 1 &amp; 0\\<br /> 1 &amp; 0 &amp; 0\\<br /> 1 &amp; 1 &amp; 1<br /> \end{array}<br />

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}<br /> A &amp; B &amp; A\rightarrow B\\<br /> \hline<br /> 0 &amp; 0 &amp; 1\\<br /> 0 &amp; 1 &amp; 1\\<br /> 1 &amp; 0 &amp; 0\\<br /> 1 &amp; 1 &amp; 1<br /> \end{array}<br />

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:

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

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:

<br /> \begin{array}{c| c | c} <br /> P &amp; Q &amp; P\ \text{only if}\ Q\\ <br /> \hline <br /> 0 &amp; 0 &amp; 1\\ <br /> 0 &amp; 1 &amp; 1\\ <br /> 1 &amp; 1 &amp; 1\\ <br /> 1 &amp; 0 &amp; 0 <br /> \end{array}<br />

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 ts? 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)

 

[micromass]

So for example, you want all three-element subsets of $\mathbb{R}$ that all have $0$ in common? I would do it like this

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

Is something like this that you want?

 

[micromass]

Or do you mean the set of all three-element subsets that have some element in common, but not necesarily a fixed one. This is pretty problematic. For example, let $A$ be that set. Then

\{1,2,3\},~\{1,4,5\} \in A

since $1$ is in both sets. But also

\{1,2,3\},~\{3,6,7\}\in A

since they have $3$ in common. but then $\{1,4,5\}$ and $\{3,6,7\}$ are both in $A$ and have no element in common!

I think what you want to do is talk about set $\{\{1,2,3\},\{1,4,5\}\}$ whose elements have one element in common. This would be a better notion. I would write it as follows:

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

 

[Dods]

Or do you mean the set of all three-element subsets that have some element in common, but not necesarily a fixed one. This is pretty problematic. For example, let $A$ be that set. Then

\{1,2,3\},~\{1,4,5\} \in A

since $1$ is in both sets. But also

\{1,2,3\},~\{3,6,7\}\in A

since they have $3$ in common. but then $\{1,4,5\}$ and $\{3,6,7\}$ are both in $A$ and have no element in common!

I think what you want to do is talk about set $\{\{1,2,3\},\{1,4,5\}\}$ whose elements have one element in common. This would be a better notion. I would write it as follows:

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

Ok, I understand the ambiguity when you have "some" element that isn't fixed, and how your example in the previous post where a=0 resolves this.

Would the set \{t \in \mathcal{P}(\mathcal{P}(\mathbb{R}))~\vert~\exists a,b,c,d,e,f:~a\neq b, b\neq c, c\neq a, d\neq e, e\neq f, f\neq d, a=d, t = (\{a,b,c\},\{d,e,f\})\}

give me all the pairs of three-distinct-element sets that have a common element?

Like:

$\{\{1,2,3\},\{1,4,5\}\}$

$\{\{6,7,2\},\{6,8,1\}\}$

$\{\{1,9,0\},\{11,1,0.5\}\}$

?

* I assume the ( ) in your expression are meant to be { }?

------

This sort of raised another question for me though.

In my earlier definition we talked about the set of all t \in \mathcal{P}(\mathbb R) and defined t=\{a,b,c\}~\text{where}~a\neq b, b\neq c, c\neq a.

Near the start of the thread when we talked about Cartesian products, we had the set of all a \in \mathcal{P}(\mathcal{P}(X\cup Y)) and defined it so that a = \{\{x\},\{x,y\}\}.

In both cases we defined our starting variable to be a set with some extra structure.

The question that this raised for me is, once we've defined, say t=\{a,b,c\}~\text{where}~a\neq b, b\neq c, c\neq a, can I then have statements like:

"for every \{a,b,c\}..."
"if a = 0 \text{then} ... b ..."

or would I have to relate these statements somehow to t?

 

[micromass]

* I assume the ( ) in your expression are meant to be { }?

Yes. Sorry.

This sort of raised another question for me though.

In my earlier definition we talked about the set of all t \in \mathcal{P}(\mathbb R) and defined t=\{a,b,c\}~\text{where}~a\neq b, b\neq c, c\neq a.

Near the start of the thread when we talked about Cartesian products, we had the set of all a \in \mathcal{P}(\mathcal{P}(X\cup Y)) and defined it so that a = \{\{x\},\{x,y\}\}.

In both cases we defined our starting variable to be a set with some extra structure.

The question that this raised for me is, once we've defined, say t=\{a,b,c\}~\text{where}~a\neq b, b\neq c, c\neq a, can I then have statements like:

"for every \{a,b,c\}..."
"if a = 0 \text{then} ... b ..."

or would I have to relate these statements somehow to t?

It depends on how rigorous you want to be. Statements like

\forall \{a,b,c\}

are not formally allowed. So any statement would have to be like

\forall t:~...~t=\{a,b,c\}~...

Of course, in reality this is far too complicated. So in reality, statements like

\forall \{a,b,c\}:~a=0

are perfectly allowed. So you don't need to relate to $t$ every time.

 

[Dods]

Thanks micromass!

I've been thinking about how to define a function in set-theoretic terms.

The definition I've come up with is: a subset of all the ordered pairs (x,y) where x<br /> is in some domain A and y is in some codomain B (that is, a subset of the Cartesian product A\times B), such that every element in the domain is paired with just one element of the codomain.

I still haven't completely thought through this definition, but I'll run with it for now.

We'd need to make the following rigorous:

"every element in the domain is paired with just one element of the codomain"

and that's assuming we already have a definition of a Cartesian product, that domain and codomain are just our terms for the sets in the Cartesian product, and (x,y) is defined to be \{\{x\},\{x,y\}\}.

So how to make that statement rigorous? I assume there are several ways to do that. The first thing that came to mind is the statement:

for every (a,b), (c,d), b \neq d \ \text{only if} a \neq c

If we look at the "only if" truth table I constructed earlier, we have:

<br /> \begin{array}{c| c | c} <br /> b \neq d &amp; a \neq c &amp; b \neq d \ \text{only if}\ a \neq c\\ <br /> \hline <br /> 0 &amp; 0 &amp; T\\ <br /> 0 &amp; 1 &amp; T\\ <br /> 1 &amp; 1 &amp; T\\ <br /> 1 &amp; 0 &amp; F <br /> \end{array}

that is, the following cases are allowed:

b = d, a = c

b = d, a \neq c ---> for a function from real numbers to real numbers this would allow us to have the pairs (2,4), (-2,4)

b \neq d, a \neq c ---> similarly would allow us to have the pairs (4,16), (-2,4)

It would not allow:

b \neq d, a = c ---> pairs like (3,9), (3,10)


This I think is what we want.

Now we have all the definitions ( cartesian product, ordered pair, "every element in the domain is paired with just one element of the codomain").

So my definition for f would be, in set builder notation:

f = \{p \in A\times B~\vert~\exists x\in A:~\exists y\in B:~p = \{\{x\},\{x,y\}\}:= (x,y):~\forall (a,b), (c,d), b \neq d \ \text{only if} a \neq c\}

Even if my verbal definition is right, I don't know if this set needs all the stuff up until "forall" (could you infer all that from the fact that p is in the cartesian product?), and it isn't fully rigorous because I deal directly with (a,b) - like \forall (a,b)...

And the definition doesn't involve a definition for the range or graph of a function.

I might have a completely silly definition (in fact, I'm waiting for you to pull it apart :D) but I think the best way to learn this is to give it a try myself at first, and then have someone pick it apart :)

 

[micromass]

The biggest problem with your definition is that you introduce some a,b,c and d that have no apparent connection with p. It's like

\{x\in A~\vert~\forall a,b:~a=b\}

when I read this out loud, I read it at: the set of all elements of A such that for each two sets a and b holds that a=b. Your a and b have no connection to x here, which is a problem.

Also, you say " := (x,y) ". This is a definition, but a definition is not allowed in set builder notation, not even informally.

Finally, assume that your definition is formally correct. Even then it's not what we want. If you use set builder notation, then you will define a unique set $f$ that satisfies some properties. So given $A$ and $B$, you have defined a unique function $f$. But there might be multiple functions from $A$ to $B$!

In short, you can't use set builder notation here because "f is a function from A to B" is a property of a set. And there is no unique set f that satisfies this. If you used set builder, then this would imply a unique f.

So what we do is just give a definition as follows:
A set $f\subseteq A\times B$ is a function if for each $a\in A$ there exists a unique $b\in B$ such that $(a,b)\in f$.

In symbols: $f\subseteq A\times B$ is a function if

\forall a\in A:~\exists ! b\in B:~(a,b)\in f

where $\exists !$ is the notation for "exists unique". If you don't want that, then you can write it as follows too:

\forall a\in A:~\exists b\in B:~(a,b)\in f~\wedge~((\exists a\in A: \exists b,c\in B:~(a,b),(a,c)\in f)~\rightarrow ~b=c )

We read this as: for all $a\in A$, there exists a $b\in B$ such that $(a,b)\in f$. And if there exists an $a\in A$ and $b,c\in B$ such that $(a,b),(a,c)\in f$, then $b=c$.

So although we can't write "f is a function from A to B" as a set (because it is a property and not a set), what we can do is take the set of all functions from A to B. This can be perfectly defined using set builder notation. The set of all functions from A to B is usually denoted as $B^A$ for some reason I'll make clear immediately. We can write

B^A = \{f\subseteq A\times B~\vert~f~\text{is a function}\}

This is not good because of the $f\subseteq A\times B$. The only allowed definition has

\{x\in X~\vert~P(x)\}

so we have to write it as

B^A = \{f\in \mathcal{P}(A\times B)~\vert~f~\text{is a function from A to B}\}

This is perfectly rigorous because we already defined the property "f is a function from A to B". Now, if you only want a definition using logical symbols, then we can of course write:

B^A = \{f\in \mathcal{P}(A\times B)~\vert~\forall a\in A:~\exists ! b\in B:~(a,b)\in f

or the longer version:

B^A = \{f\in \mathcal{P}(A\times B)~\vert~\forall a\in A:~\exists b\in B:~(a,b)\in f~\wedge~((\exists a\in A: \exists b,c\in B:~(a,b),(a,c)\in f)~\rightarrow ~b=c )\}

Of course, what we could also have done is start of by defining the set $B^A$ as the above, and then defining a function as any element in $B^A$.

So, what you should remember here that it is impossible to define a property of a set as a set. So the things "A is a ordered pair", "A is a function", "A has one element" are not sets and can't be defined.

Finally, why the funny notation $B^A$. Well, it turns out that if $B$ and $A$ are finite sets, then it turns out that the number of functions from A to B is exactly $|B^A| = |B|^{|A|}$. For example, if $A$ has 2 elements and if $B$ has 5 elements, then $B^A$ has 25 elements. This is why we denote the set of all functions from A to B like this.

 

[Dods]

There are a couple of things I'm confused about.

In short, you can't use set builder notation here because "f is a function from A to B" is a property of a set. And there is no unique set f that satisfies this. If you used set builder, then this would imply a unique f.

So what we do is just give a definition as follows:
A set $f\subseteq A\times B$ is a function if for each $a\in A$ there exists a unique $b\in B$ such that $(a,b)\in f$.

In symbols: $f\subseteq A\times B$ is a function if

\forall a\in A:~\exists ! b\in B:~(a,b)\in f

where $\exists !$ is the notation for "exists unique". If you don't want that, then you can write it as follows too:

\forall a\in A:~\exists b\in B:~(a,b)\in f~\wedge~((\exists a\in A: \exists b,c\in B:~(a,b),(a,c)\in f)~\rightarrow ~b=c )

I don't understand " "f is a function from A to B" is a property of a set". You seem to say that you can't have a set f defined in set builder notation.

I mean, we know that $f\subseteq A\times B$ and that set-builder notation \{x\in X~\vert~P(x)\} defines a subset of $X$.

Is it possible that my mistake is in thinking about specific functions rather than functions in general? Could define a specific function as a set like -

f = \{t \in \mathbb{R^2}~\vert~\exists x, y \in \mathbb{R}:~ t = (x,y),\ y = x^2\}

as long as you prove the property \forall a\in A:~\exists ! b\in B:~(a,b)\in f holds?

 

[micromass]

I don't understand " "f is a function from A to B" is a property of a set". You seem to say that you can't have a set f defined in set builder notation.

Given a set f, then the statement "f is a function" is a certain property that can be true or that can be false. You can't define properties using set builder notation. You can only define specific sets (and thus: specific functions) using set builder notation.

What you did here, is perfectly fine:

f = \{t \in \mathbb{R^2}~\vert~\exists x, y \in \mathbb{R}:~ t = (x,y),\ y = x^2\}

as long as you prove the property \forall a\in A:~\exists ! b\in B:~(a,b)\in f holds?

This is perfect and it defines a very specific function.

What you wanted to do in your post is to define a general function as a set. But you can't do that.

 

[Dods]

Ok, I think I see. We can't define a general property using set builder notation because then you wouldn't have specific sets - you can apply the property "is a function" to many sets, like the one I just posted, or a similar one with y = 2x instead of y = x^2, but you can't say they are the same set.
If I had defined a general function as "f = the set of all ordered pairs (a,b) in the Cartesian product A x B, so that for every a in A there is a unique b in B", given the ordered pairs (1,1), (1,2), (2,4), either (1,1) or (1,2) would have to go - but then we get into a position where we're excluding either x→x^2 or x→ 2x as a function!

x→b I'm just using intuitively because verbal statements would make the above awkward to read

 

[micromass]

Ok, I think I see. We can't define a general property using set builder notation because then you wouldn't have specific sets - you can apply the property "is a function" to many sets, like the one I just posted, or a similar one with y = 2x instead of y = x^2, but you can't say they are the same set.
If I had defined a general function as "f = the set of all ordered pairs (a,b) in the Cartesian product A x B, so that for every a in A there is a unique b in B", given the ordered pairs (1,1), (1,2), (2,4), either (1,1) or (1,2) would have to go - but then we get into a position where we're excluding either x→x^2 or x→ 2x as a function!

x→b I'm just using intuitively because verbal statements would make the above awkward to read

Yes, exactly. You can write down specific functions and sets, but not general properties.

As another example, consider the property "is a singleton". You can write down many specific singletons, but you can't write down a general one.

 

[Dods]

Ok, but the definition of a function that we've been looking at leaves some things out:

What notation would represent a function from a domain A to a codomain B?

How would you define the range of a function?

Where does the notation f(x) come in?

 

[micromass]

Ok, but the definition of a function that we've been looking at leaves some things out:

What notation would represent a function from a domain A to a codomain B?

A function would be denoted as $f:A\rightarrow B$.

How would you define the range of a function?

The range or image of a function $f:A\rightarrow B$ would be defined as:

$f(A) = \{b\in B~\vert~\exists a \in A:~(a,b)\in f\}$

Where does the notation f(x) come in?

The notation $f(x) = y$ is simply a shorthand for $(x,y) \in f$.

 

[Dods]

Thank you micromass.

So the range is, intuitively speaking, all the elements of the codomain that get "used".

For the function f:\mathbb{R} \rightarrow \mathbb{R} that takes x to x^2 + 1,
0.5 is in the codomain but not the range because there is no a \in \mathbb{R} so that (a, 0.5) \in f, or equivalently if we use the shorthand, no a \in \mathbb{R} such that a^2 + 1 = 0.5.

Is that correct?

 

[micromass]

Thank you micromass.

So the range is, intuitively speaking, all the elements of the codomain that get "used".

For the function f:\mathbb{R} \rightarrow \mathbb{R} that takes x to x^2 + 1,
0.5 is in the codomain but not the range because there is no a \in \mathbb{R} so that (a, 0.5) \in f, or equivalently if we use the shorthand, no a \in \mathbb{R} such that a^2 + 1 = 0.5.

Is that correct?

Yes, that is exactly correct. The codomain is simply a set of elements which may be "used". But the range is the set of elements that actually gets used. So the range does not always need to equal the codomain. If it does (so if all elements in the codomain actually gets used), then we call the map "surjective" or "onto".

 

[Dods]

It depends on how rigorous you want to be. Statements like

\forall \{a,b,c\}

are not formally allowed. So any statement would have to be like

\forall t:~...~t=\{a,b,c\}~...

Of course, in reality this is far too complicated. So in reality, statements like

\forall \{a,b,c\}:~a=0

are perfectly allowed. So you don't need to relate to $t$ every time.

Lemme try this out then.
Lets say I wanted the set of all points (in the cartesian plane) in the rectangle that has vertices at (0,0), (3,0), (0,5), (3,5).

M=\{t \in \mathbb{R^2}~\vert~\exists x,y \in \mathbb{R}:~t=\{\{x\},\{x,y\}\}:~0 \leq x \leq 3 \ \wedge \ 0 \leq y \leq 5\}
Would this be not completely rigorous, but allowed?

Here is an attempt to make it completely rigorous:

M=\{t \in \mathbb{R^2}~\vert~\exists x,y \in \mathbb{R}:~t=\{\{x\},\{x,y\}\}:~ \forall t [(\exists A \in t:~ \exists a \in \mathbb{R}:~ A=\{a,a\}:~0 \leq a \leq 3) \wedge (\exists B \in t:~ \exists a, b \in \mathbb{R}:~B=\{a,b\}:~0 \leq a \leq 3 \wedge 0 \leq b \leq 5)]\}


Also, at first, I tried to make the same set but instead of with 3 and 5, with arbitrary real numbers (say w and n). Would this not work for the same reasons having a general function set does not work?

Thanks for everything :)