Question about proof from a guy with a highschool education

[reenmachine]

This seems to be a good time to point out a pecularity with the definition of a function from X into Y as a special kind of subset of X×Y. Suppose that f is a function from X into Y according to the definition you have studied, and that Y is a proper subset of some set Z. Then f is also a subset of X×Z, and it satisfies both conditions in the definition of a function from X into Z. So Z has an equal right to be called the codomain of f.

Great! Does it means that set W , if Z ⊆ W , also has an equal right to be called the codomain of f?

 

[Fredrik]

Great! Does it means that set W , if Z ⊆ W , also has an equal right to be called the codomain of f?

Yes, the set Z in my statement was an arbitrary set that had Y as a subset, so what I said about Z also applies to W.

An example may make the definition $f(A)=\{y\in B\,|\,\exists x\in A~~ f(x)=y\}$ easier to understand. Define $f:\mathbb R\to\mathbb R$ by $f(x)=x^2$ for all $x\in\mathbb R$. The range $f(\mathbb R)$ is the set of all y in the codomain such that there's an x in the domain such that y=f(x)=x². In other words, $f(\mathbb R)$ is the set of all real numbers that are the square of a real number. This is the set of all non-negative real numbers. The negative ones are not included, because for example -1 doesn't have the property that there's an x in the domain such that $x^2=-1$.

I prefer to write the definition as $f(A)=\{f(x)|x\in A\}$. It's just easier to remember this way. But this right-hand side should be viewed as an abbreviated notation for the right-hand side in the more complicated definition. Actually that too, should be viewed as an abbreviation for an even more complicated expression. For example, the statement $\exists x\in A~~f(x)=y$ is an abbreviation for $$\exists x~\left(x\in A~\land~\{\{x\},\{x,y\}\}\in f\right).$$ The $\land$ should be read as "and".

 

[Fredrik]

1) We will attempt to prove that A∪(B∩Z) = (A∪B)∩(A∪Z).

Let x ∈ A∪(B∩Z) be arbitrary.Since x ∈ A∪(B∩Z) , it implies that x ∈ A.Since x ∈ A , it implies that x ∈ (A∪B) , x ∈ (A∪Z) implying that x ∈ (A∪B)∩(A∪Z).

The first sentence is a good start. The second is weird. It's not clear what it means (what does "it" refer to?), and the conclusion $x\in A$ doesn't follow from the first sentence. x could be a member of B-A. After the first sentence, the proof should continue something like this: Since $x\in A\cup(B\cap Z)$, we have $x\in A$ or $x\in B\cap Z$. This implies that $x\in A$ or $x\in B$ and $x\in Z$. This implies that $x\in A\cup B$ and $x\in A\cup Z$. This implies that $x\in (A\cup B)\cap(A\cup Z)$.

The second part of the proof has similar problems. In particular, x may not be a member of A.

2) We will attempt to prove that A–B = A∩B'.

Let x ∈ A and x ∉ B be arbitrary (x ∈ A-B).Since x ∉ B , it implies that x ∈ B' and since x ∈ A , it implies that x ∈ A∩B'.

Now let x ∈ A∩B' be arbitrary.This implies that x ∈ A and that x ∈ B' , which implies that x ∉ B.Since x ∈ A and x ∉ B , it implies that x ∈ A-B proving that A-B = A∩B'.

The statement

Since x ∉ B , it implies that x ∈ B'​

is weird. What you meant to say was presumably

Since $x\notin B$, we have $x\in B'$​

or equivalently

$x\notin B$ implies that $x\in B'$.​

There are many ways to say it. Your way of saying it is weird, because you're making me wonder what "it" refers to. Also for any two statements P and Q, the sentences "Since P, Q" and "P implies Q" mean the same thing. So you shouldn't include both the words "since" and "implies". One of them is sufficient.

My proof of $A-B\subseteq A\cap B'$: Let $x\in A-B$ be arbitrary. We have $x\in A$ and $x\notin B$. This implies that $x\in A$ and $x\in B'$. This implies that $x\in A\cap B'$.

 

[reenmachine]

The first sentence is a good start. The second is weird. It's not clear what it means (what does "it" refer to?), and the conclusion $x\in A$ doesn't follow from the first sentence. x could be a member of B-A. After the first sentence, the proof should continue something like this: Since $x\in A\cup(B\cap Z)$, we have $x\in A$ or $x\in B\cap Z$. This implies that $x\in A$ or $x\in B$ and $x\in Z$. This implies that $x\in A\cup B$ and $x\in A\cup Z$. This implies that $x\in (A\cup B)\cap(A\cup Z)$.

The second part of the proof has similar problems. In particular, x may not be a member of A.

I hate making mistakes like this.Should have concentrated more than I did.

 

[CompuChip]

So f has to be the exact same function as long as you operate in the same ''universe''?

f has to be defined unambiguously. You are of course allowed to define a function g(y) = y - 5, but you shouldn't call it f if f is defined in another way.
Also note that the names of variables are completely arbitrary. E.g. if f(x) = 3x + 1 then you can not only substitute x = 3 to get f(3) = 3 * 3 + 1 = 10, but also x = y to get f(y) = 3y + 1 or x = a₀ to get f(a₀) = 3a₀ + 1. So the function g(y) = y - 5 can also be written as g(x) = x - 5. Therefore you are not allowed to say

f(x) = 3x + 1 and f(y) = y - 5​

because that would give two different definitions to the same function.

My point was that the 2nd f was just a second different function that was part of another function's mechanism.

So you could define g(x) = x - 5 and then write f(x, y) = g(y) - 3x.

Not sure I understand the logic behind this.

In the notation I just made it explicit that, except on the variable x, the function f also depends on some other object, namely the set B. Of course if you want to be very formal, you could go

Define f: \mathbb{R} \times \mathscr{P}(\mathbb{R}) \to \mathbb{R} as f(x, B) = x + \sum_{b \in B} b.​

So f is a function that takes a number (x) and a subset of the reals (B). However, in some applications the subset is "fixed" in the sense that you pick some specific B and then define f as above for that specific B, so it is really only a function of x. Still, there is some dependency on B of course, if I pick a different B then in general f will evaluate to a different number - for example the value of f(0) will change. So instead of writing f(x, B) we often write f(x; B) or f_B(x) to indicate that x is really the variable, but the definition also depends on some (earlier) choice of - in this case - B.
I hope that makes it clearer.

 

[micromass]

f has to be defined unambiguously. You are of course allowed to define a function g(y) = y - 5, but you shouldn't call it f if f is defined in another way.
Also note that the names of variables are completely arbitrary. E.g. if f(x) = 3x + 1 then you can not only substitute x = 3 to get f(3) = 3 * 3 + 1 = 10, but also x = y to get f(y) = 3y + 1 or x = a₀ to get f(a₀) = 3a₀ + 1. So the function g(y) = y - 5 can also be written as g(x) = x - 5. Therefore you are not allowed to say

f(x) = 3x + 1 and f(y) = y - 5​

because that would give two different definitions to the same function.

This is an interesting point and I want to continue a bit on it. What CompuChip is saying is that the functions f(x)=x+5 and f(y)=y+5 are the same thing. In textbooks you will often encounter the phrase that x is a "dummy variable". This means that you can change x in any other symbol (that's not used already) and that the function won't change.

Now, why is this? Well, remember that a function is essentially a set. What set is the function f(x)=x+5. By definition is a subset of $\mathbb{R}\times \mathbb{R}$. Which subset?

f=\{(x,x+5)~\vert~x\in \mathbb{R}\}\subseteq \mathbb{R}\times \mathbb{R}

When we claim that the variable x and y can be interchanged, then we actually say that we have the following equality of sets:

\{(x,x+5)~\vert~x\in \mathbb{R}\} = \{(y,y+5)~\vert~y\in \mathbb{R}\}

This equality can be checked directly. Indeed, take an element in the left hand side and show it is in the right hand side and vice versa. For example, take an arbitrary element of the left-hand side, this has the form $(x,x+5)$ for a certain $x\in \mathbb{R}$. Define $y=x$, then $y\in \mathbb{R}$. Furthermore, we have that $(y,y+5)$ is in the right-hand side (by definition) and that $(x,x+5) = (y,y+5)$. So $(x,x+5)$ is in the right-hand side too.
Showing that an element on the right-hand side is in the left-hand side is analogous.

Now, the above is a bit imprecise. Take two functions $f:A\rightarrow B$ and $g:C\rightarrow D$ are the same thing if
\{(x,f(x))~\vert~x\in A\}= \{(x,g(x))~\vert~x\in C\}
This is nice and it works suitably well. But usually we also demand that $A=C$ and that $B=D$. This has a few consequences that can look weird at first. For example, take $f:\mathbb{R}\rightarrow \mathbb{R}:x\rightarrow x^2$ and $g:\mathbb{R}\rightarrow \mathbb{R}^+ = \{x\in \mathbb{R}~\vert~x\geq 0\}$.
We can see easily that the following equality holds:
\{(x,f(x))~\vert~x\in \mathbb{R}^2\}= \{(x,g(x))~\vert~x\in \mathbb{R}\}
so the graphs of the function are the same and the functions behave the same way. However, the functions are not the same thing, since the codomains of the functions are different.
I agree that this is very weird when you first encounter this. But it makes the life of the mathematician a lot easier!

 

[micromass]

FINALLY I received my books! Yesss!

Calculus: an intuitive and physical approach by Morris Kline is a brick.Intimidating at first , but I'm not one to back down.That is also without knowing if there's some basic high school concepts I'm unaware of that I would need to understand calculus, but that won't stop me even if that's the case , I'll just pick them up by necessity (it's highly likely that the last high school I've been to had a poor math program).

The book of proof looks very nice and a much easier read , but I won't judge a book by it's cover.

I'm very happy to have them , now I should finish the very last section of the textbook I used during the thread and I'll be ready to start these new adventures.

EDIT: Should I try to do some basic exercises on relations and functions? If so , any suggestions?

I suggest you make different threads for the different books you read. So make another thread specifically for Kline. I think it will be a bit confusing if you're going to use this thread both for calculus and set theory.

 

[Fredrik]

What CompuChip is saying is that the functions f(x)=x+5 and f(y)=y+5 are the same thing.

I will elaborate a bit on this too. When I realized these things, I started to get really annoyed by the fact that my books and teachers referred to f(x) as a "function". It's not a function. $f$ is the function. $x$ is a variable that represents a real number. $f(x)$ is an element of the codomain of f. So if $f:\mathbb R\to\mathbb R$, then $f(x)$ is a number, not a function.

As I studied more math, I discovered that small abuses of terminology and notation like this are pretty common. Some of them are pretty useful, because sometimes it's just too annoying to say everything exactly right. Sentences would get too long and weird. But I don't think any of the other standard abuses of terminology and notation can cause as much confusion as this one, so I still refuse to abuse this terminology and notation 99.9% of the time.

I have noticed that I'm not the only one who's been confused by it. I've seen evidence of this in many posts in this forum.

So I will not (or at least very rarely) say things like "the function f(x)=sin x", "the function x²" or "the derivative of sin x is cos x". Instead of the first of these phrases, I'll say "the function f:ℝ→ℝ defined by f(x)=sin x for all x in ℝ". The most accurate way to rephrase the second is similar to the first. A slightly less accurate option (because it doesn't mention the domain or codomain), is "the function $x\mapsto x^2$". Instead of the third, I'll say "the derivative of sin is cos".

 

[micromass]

I will elaborate a bit on this too. When I realized these things, I started to get really annoyed by the fact that my books and teachers referred to f(x) as a "function". It's not a function. $f$ is the function. $x$ is a variable that represents a real number. $f(x)$ is an element of the codomain of f. So if $f:\mathbb R\to\mathbb R$, then $f(x)$ is a number, not a function.

As I studied more math, I discovered that small abuses of terminology and notation like this are pretty common. Some of them are pretty useful, because sometimes it's just too annoying to say everything exactly right. Sentences would get too long and weird. But I don't think any of the other standard abuses of terminology and notation can cause as much confusion as this one, so I still refuse to abuse this terminology and notation 99.9% of the time.

I have noticed that I'm not the only one who's been confused by it. I've seen evidence of this in many posts in this forum.

So I will not (or at least very rarely) say things like "the function f(x)=sin x", "the function x²" or "the derivative of sin x is cos x". Instead of the first of these phrases, I'll say "the function f:ℝ→ℝ defined by f(x)=sin x for all x in ℝ". The most accurate way to rephrase the second is similar to the first. A slightly less accurate option (because it doesn't mention the domain or codomain), is "the function $x\mapsto x^2$". Instead of the third, I'll say "the derivative of sin is cos".

I absolutely agree with this. I really don't like the f(x)=x notation. I will almost always use the full $f:X\rightarrow Y$ notation.
I guess I used the notation in my post because CompuChip used that notation already. Whenever somebody uses some notation in a thread, I generally try to use the same notation so it's less confusing.

The f(x)=x is not even the worst. We also have notations such as $y=x^2$. Those are truly horrible. I generally also dislike the notation for diffy eq. such as $y^\prime = y$. But those are used so often that I'm forced to use them.

And then there's Leibniz notation $\frac{dy}{dx}$, shudder...

The absolute worst notation I've ever seen is in a book where the author decides that function evaluation should be performed along the other side. So instead of f(x), he always writes (x)f. What was he thinking when he decided to use that?

 

[reenmachine]

Yes, the set Z in my statement was an arbitrary set that had Y as a subset, so what I said about Z also applies to W.

An example may make the definition $f(A)=\{y\in B\,|\,\exists x\in A~~ f(x)=y\}$ easier to understand. Define $f:\mathbb R\to\mathbb R$ by $f(x)=x^2$ for all $x\in\mathbb R$. The range $f(\mathbb R)$ is the set of all y in the codomain such that there's an x in the domain such that y=f(x)=x². In other words, $f(\mathbb R)$ is the set of all real numbers that are the square of a real number. This is the set of all non-negative real numbers. The negative ones are not included, because for example -1 doesn't have the property that there's an x in the domain such that $x^2=-1$.

I prefer to write the definition as $f(A)=\{f(x)|x\in A\}$. It's just easier to remember this way. But this right-hand side should be viewed as an abbreviated notation for the right-hand side in the more complicated definition. Actually that too, should be viewed as an abbreviation for an even more complicated expression. For example, the statement $\exists x\in A~~f(x)=y$ is an abbreviation for $$\exists x~\left(x\in A~\land~\{\{x\},\{x,y\}\}\in f\right).$$ The $\land$ should be read as "and".

Again , in $f(A)=\{y\in B\,|\,\exists x\in A~~ f(x)=y\}$ , why is ''there exist'' necessary?

When you define it as $f(A)=\{f(x)|x\in A\}$ , is it implied that f(x) transforms x into y?

 

[reenmachine]

In the notation I just made it explicit that, except on the variable x, the function f also depends on some other object, namely the set B. Of course if you want to be very formal, you could go

Define f: \mathbb{R} \times \mathscr{P}(\mathbb{R}) \to \mathbb{R} as f(x, B) = x + \sum_{b \in B} b.​

So f is a function that takes a number (x) and a subset of the reals (B). However, in some applications the subset is "fixed" in the sense that you pick some specific B and then define f as above for that specific B, so it is really only a function of x. Still, there is some dependency on B of course, if I pick a different B then in general f will evaluate to a different number - for example the value of f(0) will change. So instead of writing f(x, B) we often write f(x; B) or f_B(x) to indicate that x is really the variable, but the definition also depends on some (earlier) choice of - in this case - B.
I hope that makes it clearer.

When you say

f: \mathbb{R} \times \mathscr{P}(\mathbb{R}) \to \mathbb{R}​

I'm not sure I understand in which context you use ℝ × p(ℝ) ---> ℝ , why ℝ × p(ℝ)?

In

f(x, B) = x + \sum_{b \in B} b​

, why is there a B in f(x,B) , why is it described as if the function had an impact on B while it doesn't since B stays the same and only x receive some kind of ''treatment'' from the function?

 

[reenmachine]

This is an interesting point and I want to continue a bit on it. What CompuChip is saying is that the functions f(x)=x+5 and f(y)=y+5 are the same thing. In textbooks you will often encounter the phrase that x is a "dummy variable". This means that you can change x in any other symbol (that's not used already) and that the function won't change.

Now, why is this? Well, remember that a function is essentially a set. What set is the function f(x)=x+5. By definition is a subset of $\mathbb{R}\times \mathbb{R}$. Which subset?

f=\{(x,x+5)~\vert~x\in \mathbb{R}\}\subseteq \mathbb{R}\times \mathbb{R}

I was aware that x could be replaced by any other letter in theory , sorry if I confused you in some ways.

I feel like there's something that I should understand very clearly right away because it's not the first time I'm scratching my head over something similar , when you say f=\{(x,x+5)~\vert~x\in \mathbb{R}\}\subseteq \mathbb{R}\times \mathbb{R} , why is (x,x+5) written like this beside f?

Let me try to explain it to you to see if I understand it correctly.Here we have a function f which is subset of ℝ × ℝ because the function operates on x (which is an element of ℝ) and produce or generate the result x+5 (which is also an element of ℝ).Is that pretty much it?

When we claim that the variable x and y can be interchanged, then we actually say that we have the following equality of sets:

\{(x,x+5)~\vert~x\in \mathbb{R}\} = \{(y,y+5)~\vert~y\in \mathbb{R}\}

Okay that's clear and pretty sure I understood it.

Now, the above is a bit imprecise. Take two functions $f:A\rightarrow B$ and $g:C\rightarrow D$ are the same thing if
\{(x,f(x))~\vert~x\in A\}= \{(x,g(x))~\vert~x\in C\}

When you say \{(x,f(x))~\vert~x\in A\}= \{(x,g(x))~\vert~x\in C\} , why isn't it mentionned that (f(x)) is an element of B or D?

This is nice and it works suitably well. But usually we also demand that $A=C$ and that $B=D$. This has a few consequences that can look weird at first. For example, take $f:\mathbb{R}\rightarrow \mathbb{R}:x\rightarrow x^2$ and $g:\mathbb{R}\rightarrow \mathbb{R}^+ = \{x\in \mathbb{R}~\vert~x\geq 0\}$.
We can see easily that the following equality holds:
\{(x,f(x))~\vert~x\in \mathbb{R}^2\}= \{(x,g(x))~\vert~x\in \mathbb{R}\}

I'm confused here , in $g:\mathbb{R}\rightarrow \mathbb{R}^+ = \{x\in \mathbb{R}~\vert~x\geq 0\}$ , what does R+ means?

In \{(x,f(x))~\vert~x\in \mathbb{R}^2\}= \{(x,g(x))~\vert~x\in \mathbb{R}\} ,why does it hold if one is ℝ and the other is ℝ^2? I'm a lot confused about this whole part so I'm not sure which question to ask , I feel like I have something missing.Mainly my knowledge or understanding of how to define a function seems to be lacking in precision.

 

[reenmachine]

I suggest you make different threads for the different books you read. So make another thread specifically for Kline. I think it will be a bit confusing if you're going to use this thread both for calculus and set theory.

Sure , I'll do that when I start which should be this week-end or next week.

I'm having a very busy week and it's a real pain for my personal math studies.Hopefully I can clear everything within 2 weeks and start to spend even more time studying set theory and calculus.I noticed that when you had some unrelated worries learning math is at least twice as difficult as it is when you have a clear mind.Stress isn't friendly to mathematical thinking.

 

[reenmachine]

This seems to be a good time to point out a pecularity with the definition of a function from X into Y as a special kind of subset of X×Y. Suppose that f is a function from X into Y according to the definition you have studied, and that Y is a proper subset of some set Z. Then f is also a subset of X×Z, and it satisfies both conditions in the definition of a function from X into Z. So Z has an equal right to be called the codomain of f.

With this definition of "function", the range is simply the smallest set that can be called the codomain of f.

Another question about this.

As I've already asked you , if Z ⊆ W , W also has an equal right to be called the codomain of f.Then I presume that if W ⊆ Q , then Q also has an equal right to be called the codomain of f and so on.My point is since everything is a set , then while the range is the smallest possible set that could be called the codomain of f , if you rise in the hierarchy of set you will eventually reach set U , which would have an equal right to be called the co-domain of f , but since U is the set containing all sets , then it means that the co-domain is also the domain?

 

[Fredrik]

Again , in $f(A)=\{y\in B\,|\,\exists x\in A~~ f(x)=y\}$ , why is ''there exist'' necessary?

I thought the example would make that clear. It wouldn't make sense to write $f(A)=\{y\in B\,|f(x)=y\}$, because it's not clear what x refers to. Consider the f I used as an example. If you say that for this f, f(ℝ) is defined by $f(\mathbb R)=\{y\in B|f(x)=y\}$, then you're saying that f(ℝ) denotes the set of all y in ℝ such that y=x². But this doesn't tell me what set f(ℝ) is. It looks like f(ℝ) is some singleton set (for example if x=2, we have f(ℝ)={4}), but I can't tell which one.

When you define it as $f(A)=\{f(x)|x\in A\}$ , is it implied that f(x) transforms x into y?

What is the y in your question?

The equality is supposed to be the definition of the range of a function from A into B that's denoted by f. That fact alone ensures that for each x, f(x) is an element of B. This follows from the definition of "function from A into B".

 

[reenmachine]

I thought the example would make that clear. It wouldn't make sense to write $f(A)=\{y\in B\,|f(x)=y\}$, because it's not clear what x refers to. Consider the f I used as an example. If you say that for this f, f(ℝ) is defined by $f(\mathbb R)=\{y\in B|f(x)=y\}$, then you're saying that f(ℝ) denotes the set of all y in ℝ such that y=x². But this doesn't tell me what set f(ℝ) is. It looks like f(ℝ) is some singleton set (for example if x=2, we have f(ℝ)={4}), but I can't tell which one.

That's not what I meant , I wasn't speaking about both $\exists$ and $x\in A$ , I was only speaking about $\exists$

What is the y in your question?

The equality is supposed to be the definition of the range of a function from A into B that's denoted by f. That fact alone ensures that for each x, f(x) is an element of B. This follows from the definition of "function from A into B".

Okay , but then where is B in your exemple? Simply implied by f?

thanks a lot!

 

[Fredrik]

Another question about this.

As I've already asked you , if Z ⊆ W , W also has an equal right to be called the codomain of f.Then I presume that if W ⊆ Q , then Q also has an equal right to be called the codomain of f and so on.My point is since everything is a set , then while the range is the smallest possible set that could be called the codomain of f , if you rise in the hierarchy of set you will eventually reach set U , which would have an equal right to be called the co-domain of f , but since U is the set containing all sets , then it means that the co-domain is also the domain?

"Contains" is an ambiguous word in this context. The set {x,y,z} "contains x" in the sense that $x\in\{x,y,z\}$ and "contains $\{y,z\}$" in the sense that $\{y,z\}\subseteq\{x,y,z\}$. So I'm not sure if what you had in mind is that every set is an element of U or that every set is a subset of U. Edit: I corrected the last sentence of this paragraph.

In ZFC set theory, there's no set U such that every set is an element of U. We can prove that there isn't by deriving a contradiction from the assumption that there is. So suppose that U is a set that such that every set is an element of U. By the ZFC axioms, this implies that $\{S\in U|S\notin S\}$ is a set. But if this is a set, and we denote it by R, the definition of R tells us that $R\in R$ if and only if $R\notin R$. This is a contradiction, so we are forced to conclude that there's no set U such that every set is an element of U.

There's also no set U such that every set is a subset of it. Suppose that U is such a set, and let S be an arbitrary set. By the ZFC axioms, {S} is a set. By assumption, this implies that $\{S\}\subset U$. This implies that $S\in U$. Since S is arbitrary, this implies that every set is a member of U. This contradicts the previous result that no such set exists. This contradiction forces us to conclude that there's no set U such that every set is a subset of it.

 

[reenmachine]

In ZFC set theory, there's no set U such that every set is an element of U. We can prove that there isn't by deriving a contradiction from the assumption that there is. So suppose that U is a set that such that every set is an element of U. By the ZFC axioms, this implies that $\{S\in U|S\notin S\}$ is a set. But if this is a set, and we denote it by R, the definition of R tells us that $R\in R$ if and only if $R\notin R$. This is a contradiction, so we are forced to conclude that there's no set U such that every set is an element of U.

Don't know what I have today but my head feels like exploding.Just one of those days

Just for the sake of ultimate clearness , in $\{S\in U|S\notin S\}$ , what does the vertical line in the middle means?

So set S is an element of U if and only if S isn't an element of S is that right?

I don't understand what happened when you switched to R.Why is the definition of R telling us that $R\in R$ iff $R\notin R$? Why isn't it $R\in U$ iff $R\notin R$?

sorry for my troubles today , I can't always be on my A game (I'm at least using this rough day to slowly but surely introduce some LaTeX in my posts).

thanks a lot!

 

[Fredrik]

That's not what I meant , I wasn't speaking about both $\exists$ and $x\in A$ , I was only speaking about $\exists$

OK, so you're suggesting that we define the range of a function $f:A\to B$ as the set $\{y\in B|x\in A~~ f(x)=y\}$. The problem is that it's not clear what the statement $x\in A~~ f(x)=y$ means. Using the same example function again, the set we're talking about would be "the set of all real numbers y such that x is a real number y=x²". This sentence doesn't make sense to me. Even if we interpret the end of the sentence as "... x is a real number and y=x²", we can still ask what real number x is. The sentence seems to be referring to an x that's been defined earlier.

Okay , but then where is B in your exemple? Simply implied by f?

I used the notation $f:\mathbb R\to\mathbb R$, which tells us either that ℝ is the codomain of f (if we use definition 2 of "function") or that ℝ is a codomain of f (if we use definition 1 of "function"). Regardless of whether ℝ is a codomain or the codomain, f(x) is still going to be a member of ℝ for all x.

 

[reenmachine]

OK, so you're suggesting that we define the range of a function $f:A\to B$ as the set $\{y\in Y|x\in A~~ f(x)=y\}$. The problem is that it's not clear what the statement $x\in A~~ f(x)=y$ means. Using the same example function again, the set we're talking about would be "the set of all real numbers y such that x is a real number y=x²". This sentence doesn't make sense to me. Even if we interpret the end of the sentence as "... x is a real number and y=x²", we can still ask what real number x is. The sentence seems to be referring to an x that's been defined earlier.

how does $\exists x\in A$ help define x better than just saying that $x\in A$ ? What supplemental information about x did we acquired by reading that $\exists x\in A$ instead of $x\in A$? If $x\in A$ , isn't it implied that ''there exist'' an x? You're saying we could ask ''what real number x is?'' if we only read $x\in A$ , but isn't it also true with $\exists x\in A$?

Also , didn't you mean $y\in B$?

About the clearness , shouldn't there be some kind of transition symbol or concept from $\exists x\in A$ to $f(x)=y\}$?

thanks man!

 

[Fredrik]

Don't know what I have today but my head feels like exploding.

If that's going to happen, this is a good time for it. Russell's paradox and the closely related liar's paradox has that effect on people.

http://www.youtube.com/watch?v=EzVxsYzXI_Y&t=1m23s

Just for the sake of ultimate clearness , in $\{S\in U|S\notin S\}$ , what does the vertical line in the middle means?

It means that S is not an element of S.

The notation $\{S\in U|S\notin S\}$ should be interpreted as "the set of all S in U such that S is not an element of S".

I don't understand what happened when you switched to R.Why is the definition of R telling us that $R\in R$ iff $R\notin R$? Why isn't it $R\in U$ iff $R\notin R$?

The definition of R is $R=\{S\in U|S\notin S\}$.

Every statement must be either true or false. The statement $R\in R$ is no exception.

Suppose that the statement $R\in R$ is true. Since the elements of R are precisely those sets that are not elements of themselves, the assumption implies that R is not an element of R, i.e. that $R\notin R$. This contradicts the assumption that the statement $R\in R$ is true

Suppose that the statement $R\in R$ is false. This assumption is clearly equivalent to $R\notin R$. (We can see that without using the definition of R). Now R satisfies the condition that ensures that it's an element of R. So $R\in R$. This contradicts the assumption that the statement $R\in R$ is false.

Since we get a contradiction regardless of whether $R\in R$ is true or false, R can't be a set.

 

[reenmachine]

If that's going to happen, this is a good time for it. Russell's paradox and the closely related liar's paradox has that effect on people.

http://www.youtube.com/watch?v=EzVxsYzXI_Y&t=1m23sIt means that S is not an element of S.

The notation $\{S\in U|S\notin S\}$ should be interpreted as "the set of all S in U such that S is not an element of S". The definition of R is $R=\{S\in U|S\notin S\}$.

Every statement must be either true or false. The statement $R\in R$ is no exception.

Suppose that the statement $R\in R$ is true. Since the elements of R are precisely those sets that are not elements of themselves, the assumption implies that R is not an element of R, i.e. that $R\notin R$. This contradicts the assumption that the statement $R\in R$ is true

Suppose that the statement $R\in R$ is false. This assumption is clearly equivalent to $R\notin R$. (We can see that without using the definition of R). Now R satisfies the condition that ensures that it's an element of R. So $R\in R$. This contradicts the assumption that the statement $R\in R$ is false.

Since we get a contradiction regardless of whether $R\in R$ is true or false, R can't be a set.

Quick question and brain cramp , why the bolded?

 

[Fredrik]

how does $\exists x\in A$ help define x better than just saying that $x\in A$ ?

$x\in A$ tells us that "x is an element of A". This is a statement about x and A. That's why we need to know what x is.

$\exists x\in A$ tells us that "there's an x that's an element of A". In other words, "there's a set that's an element of A". This is a statement about A alone. It can clearly be made without even using the symbol x.

$x\in A~~f(x)=y$ would be "x is in A f(x)=y". This doesn't make sense as it stands (no punctuation), and if it's interpreted as "x is in A and f(x)=y", then it's a statement about x,y and A.

$\exists x\in A~~f(x)=y$ tells us that "there's an x in A such that f(x)=y". This is a statement about A and y.

What supplemental information about x did we acquired by reading that $\exists x\in A$ instead of $x\in A$? If $x\in A$ , isn't it implied that ''there exist'' an x?

Obviously $x\in A$ wouldn't make sense if x doesn't exist, but how would you know that x isn't a variable that represents some specific element of A? If I say "micromass is Belgian", you would interpret it as a statement about a specific person for whom I'm using the label "micromass". You wouldn't interpret it as "there exists a Belgian person", which is exactly what $\exists\text{ micromass}\in\text{Belgians}$ would mean.

You're saying we could ask ''what real number x is?'' if we only read $x\in A$ , but isn't it also true with $\exists x\in A$?

Not at all, because $\exists x\in A$ means the same thing as $\exists y\in A$. $\exists x\in A$ is a statement about A alone. $x\in A$ is a statement about x and A.

Also , didn't you mean $y\in B$?

Yes. I will edit that in my post.

About the clearness , shouldn't there be some kind of transition symbol or concept from $\exists x\in A$ to $f(x)=y\}$?

Sometimes a colon is used for clarity. (You probably noticed that CompuChip did that). The colon isn't part of the logical language (and neither are the spaces I added), but it's OK to use it if it improves readability.

 

[Fredrik]

Quick question and brain cramp , why the bolded?

Because that condition is "is not an element of itself". Recall that the definition of R is $\{S\in U|S\notin S\}$. So a set is a member of R if and only if it's not an element of itself. In other words, an arbitrary set x is an element of R if and only if $x\notin x$. Therefore R is an element of R (i.e. $R\in R$) if and only if $R\notin R$. This is the contradiction that forces us to conclude that R is not a set.

 

[reenmachine]

$x\in A$ tells us that "x is an element of A". This is a statement about x and A. That's why we need to know what x is.

$\exists x\in A$ tells us that "there's an x that's an element of A". In other words, "there's a set that's an element of A". This is a statement about A alone. It can clearly be made without even using the symbol x.

$x\in A~~f(x)=y$ would be "x is in A f(x)=y". This doesn't make sense as it stands (no punctuation), and if it's interpreted as "x is in A and f(x)=y", then it's a statement about x,y and A.

wow ok , I see it now.

thanks

 

[reenmachine]

Because that condition is "is not an element of itself". Recall that the definition of R is $\{S\in U|S\notin S\}$. So a set is a member of R if and only if it's not an element of itself. In other words, an arbitrary set x is an element of R if and only if $x\notin x$. Therefore R is an element of R (i.e. $R\in R$) if and only if $R\notin R$. This is the contradiction that forces us to conclude that R is not a set.

Before going further , I have to ask what relation does R have with U or S for them to be included in it's definition? It confuses me a bit.

 

[Fredrik]

R and U are notations for two specific sets. (At the end of the argument, we find that they're not sets at all, but until then, they are to be treated as sets). R is only defined to make it easier to derive a contradiction from the assumption that U is a set.

S isn't some specific set, so it wouldn't make sense to say that it has a relationship with U or R. All the statements involving S can be made using any other letter of the alphabet instead, except maybe U and R, because that could be confusing.

The reason why U is mentioned in the definition of R is that the ZFC axioms do not allow us to just think of any statement $\varphi(x)$ about an arbitrary set x, and then say that $\{x\,|\,\varphi(x)\}$ is a set. But if y is a set, they do allow us to say that $\{x\in y\,|\,\varphi(x)\}$ is a set.

In my proof, $\varphi(x)$ is the statement $x\notin x$. The axioms do not ensure that $\{x\,|\,x\notin x\}$ is a set, but if U is a set, they ensure that $\{x\in U\,|\,x\notin x\}$ is a set. This is the set I denoted by R.

I came across a one of micromass' posts about this when I did a search earlier, so I will quote him:

It is indeed true that
\{x~\vert~x\notin x\}does not exist. But the question is, what sets do exist??

Before Russels paradox, it was said that every "collection of objects" was a good set. That means, if \varphi is a property, then
\{x~\vert~\varphi(x)\}is a set. This is the comprehension principle. Of course, this leads to a contradiction with Russel's paradox. So apparently, not every collection satisfying some property is a set. But the question becomes: what is a set?? Can we make a definition/axioms of a set such that all of mathematics still holds but such that things like Russel's paradox not come up.

One such axiom system are the ZFC axioms. Here, the comprehension axiom is replaced by the separation axiom. That is: for every set A, the set
\{x\in A~\vert~\varphi(x)\}is a set. Then Russels paradox does not occur. But does this absolve us from other paradoxes or contradictions?? We don't know and we will likely never know. Godels incompleteness theorem states that it is impossible to prove that ZFC does not have contradictions. But as of now, no contradiction has been found. So most mathematicians believe that ZFC is consistent (but we are unable to prove it).

 

[Fredrik]

Maybe the following example is useful. If $x_1$ and $x_2$ are variables that represent real numbers, then we can use the notation $\sum_{i=1}^2 x_i$ for the sum $x_1+x_2$. To ask about the properties of the set S in $\{S\in U\,|\,S\notin S\}$ is a lot like asking about the properties of the integer i in $\sum_{i=1}^2x_i$. There is no "integer i" in $\sum_{i=1}^2x_i$, because this is just a notation for $x_1+x_2$. Similarly, there's no "set S" in $\{S\in U\,|\,S\notin S\}$.

The x in an expression of the form $\{x\in y\,|\,\varphi(x)\}$ (where $\varphi(x)$ is a statement about x) is always a dummy variable, just like the i and the S mentioned above. So is every variable that's the target of a "for all" or "there exists".

If I want to say that every non-negative real number has a unique square root, I can say "For all $y\in\mathbb R$ such that $y\geq 0$, there's a unique $x\in\mathbb R$ such that $x^2=y$". Here both x and y are dummy variables. The statement isn't in any way a statement about either of those variables. It's a statement about $\mathbb R$, not about x or y.

 

[Fredrik]

I'm bored, so I'll answer the questions you asked micromass before I go to bed.

I feel like there's something that I should understand very clearly right away because it's not the first time I'm scratching my head over something similar , when you say f=\{(x,x+5)~\vert~x\in \mathbb{R}\}\subseteq \mathbb{R}\times \mathbb{R} , why is (x,x+5) written like this beside f?

The notation means "f is the set of all ordered pairs (x,x+5) such that x is a real number".

Let me try to explain it to you to see if I understand it correctly.Here we have a function f which is subset of ℝ × ℝ because the function operates on x (which is an element of ℝ) and produce or generate the result x+5 (which is also an element of ℝ).Is that pretty much it?

Pretty much, but not exactly. What's missing is a "for all" or "for each" statement. The function $f:\mathbb R\to\mathbb R$ is defined by $f(x)=x+5$ for all $x\in\mathbb R$.

When you say \{(x,f(x))~\vert~x\in A\}= \{(x,g(x))~\vert~x\in C\} , why isn't it mentionned that (f(x)) is an element of B or D?

Micromass used the notation $f:A\to B$ to let you know that B is either a codomain of f, or the codomain of f (depending on which definition of "function" we use). Either way, it implies that for all x in A, f(x) is in B. So there's no need to mention that separately.

I'm confused here , in $g:\mathbb{R}\rightarrow \mathbb{R}^+ = \{x\in \mathbb{R}~\vert~x\geq 0\}$ , what does R+ means?

$\mathbb R^+$ is defined by that equality. Since the right-hand side is the set of all non-negative real numbers, that's what $\mathbb R^+$ is.

In \{(x,f(x))~\vert~x\in \mathbb{R}^2\}= \{(x,g(x))~\vert~x\in \mathbb{R}\} ,why does it hold if one is ℝ and the other is ℝ^2?

That looks like a typo. x is an element of ℝ. (x,f(x)) is an element of ℝ². If we drop the ² from the left-hand side, and define "function" as in definition 1 in my post #122, then this equality says that f=g. But we instead define "function" as in definition 2, then the equality only says that the graphs of f and g are the same. This time we do not have f=g (even though both f and g have domain ℝ, and take every real number to its square), because we have explicitly specified that the codomains are different, and definition 2 ensures that two functions can only be equal if they have the same codomain.

 

[reenmachine]

R and U are notations for two specific sets. (At the end of the argument, we find that they're not sets at all, but until then, they are to be treated as sets). R is only defined to make it easier to derive a contradiction from the assumption that U is a set.

S isn't some specific set, so it wouldn't make sense to say that it has a relationship with U or R. All the statements involving S can be made using any other letter of the alphabet instead, except maybe U and R, because that could be confusing.

The reason why U is mentioned in the definition of R is that the ZFC axioms do not allow us to just think of any statement $\varphi(x)$ about an arbitrary set x, and then say that $\{x\,|\,\varphi(x)\}$ is a set. But if y is a set, they do allow us to say that $\{x\in y\,|\,\varphi(x)\}$ is a set.

In my proof, $\varphi(x)$ is the statement $x\notin x$. The axioms do not ensure that $\{x\,|\,x\notin x\}$ is a set, but if U is a set, they ensure that $\{x\in U\,|\,x\notin x\}$ is a set. This is the set I denoted by R.

I came across a one of micromass' posts about this when I did a search earlier, so I will quote him:

When you say ''that the ZFC axioms do not allow us to just think of any statement $\varphi(x)$ about an arbitrary set x , and then say that $\{x\,|\,\varphi(x)\}$ is a set'' I don't think I understand what you mean exactly.

In the micromass post , he says that p is a property , I thought p was a powerset?

 

[reenmachine]

Maybe the following example is useful. If $x_1$ and $x_2$ are variables that represent real numbers, then we can use the notation $\sum_{i=1}^2 x_i$ for the sum $x_1+x_2$.

I'm afraid I'm unfamiliar with the logic behind the placements of these symbols: $\sum_{i=1}^2 x_i$

Does i = x^1 + x^2?

My unfamiliarity with the concepts makes it difficult for me to follow your arguments in the rest of the post.

Or maybe that's just my current state of mind.I've been confused all day.My best bet is probably to go get some sleep and see what happens tomorrow

 

[micromass]

When you say ''that the ZFC axioms do not allow us to just think of any statement $\varphi(x)$ about an arbitrary set x , and then say that $\{x\,|\,\varphi(x)\}$ is a set'' I don't think I understand what you mean exactly.

It means that a set of the form $\{x~\vert~\varphi(x)\}$ is not guaranteed to exist. It may exist, but then it requires a proof.
So in general, given a property, there is no set which has as elements all the things which have that property.
For example, I can have the property $\varphi(x)$ as "$x$ is a set". The set
$\{x~\vert~\varphi(x)\} = \{x~\vert ~ x~\text{is a set}\}$
would be the set of all set and this doesn't exist.

What the ZFC axioms tell you that a set of the following form: $\{x\in A~\vert~\varphi(x)\}$ is always guaranteed to exist (by axiom). So given a specific set A, we can always form a set of all elements of A that satisfy the property. For example, we can form $\{x\in A~\vert ~ x~\text{is a set}\}$. This is a perfectly well-defined set (and it is equal to A).

So: given a property, we can (in general) not form a set that contains all things satisfying the property.
But, given a property and a set A, we can form a set of that contains all elements of A containing the property.

In the micromass post , he says that p is a property , I thought p was a powerset?

Well, we only have 26 letters at our disposal. p means power set of course. But in other contexts, p can mean something entirely different.
In general, I write power set as $\mathcal{P}$ and a property as P.

 

[micromass]

I'm afraid I'm unfamiliar with the logic behind the placements of these symbols: $\sum_{i=1}^2 x_i$

Does i = x^1 + x^2?

No, i is just a dummy variable. It's part of the notation. It doesn't mean anything.

Given numbers $x_1,...,x_n$, we define

\sum_{i=1}^n x_i = x_1 + ... + x_n

The "i=" is just part of the notation. We can leave it out and write

\sum_1^n x_i

(of course, the moment that you have multiple sums, you can't leave the dummy variable out anymore).
We can (sometimes) even leave out the entire summation signs. This is routinely done in physics and is called Einstein notation.

 

[Fredrik]

When you say ''that the ZFC axioms do not allow us to just think of any statement $\varphi(x)$ about an arbitrary set x , and then say that $\{x\,|\,\varphi(x)\}$ is a set'' I don't think I understand what you mean exactly.

I think micromass said it better, so look at what he said in the quote. $\varphi$ is a property (of a set). That just means that for all x, $\varphi(x)$ is a statement about x. So $\{x\in y\,|\,\varphi(x)\}$ would be "the set of all $x\in y$ such that $\varphi(x)$".

In the micromass post , he says that p is a property

No, he doesn't. It's the greek letter phi, LaTeX code \varphi, $\varphi$.

I thought p was a powerset?

That doesn't mean that the symbol can't be used for anything else. We just need to explain what we mean when we use it.

 

[micromass]

No, he doesn't. It's the greek letter phi, LaTeX code \varphi, $\varphi$.

I think he's referring to this post: https://www.physicsforums.com/showpost.php?p=4344788&postcount=139

 

[reenmachine]

The reason why U is mentioned in the definition of R is that the ZFC axioms do not allow us to just think of any statement $\varphi(x)$ about an arbitrary set x, and then say that $\{x\,|\,\varphi(x)\}$ is a set. But if y is a set, they do allow us to say that $\{x\in y\,|\,\varphi(x)\}$ is a set.

I'm still awake because of insomnia , but I think it's starting to all make sense for some reasons.

Will try to explain it myself and tell me if I understood correctly:

When we say $\varphi(x)$ about an arbitrary set x , we mean to define some kind of characteristic of x.The property is what describes something about x.When write something like $\{x\,|\,\varphi(x)\}$ , it means that a property of x is that it's x , which doesn't make sense , just like saying that a property of the color blue is that's it's blue.Is that right?

If $\{x\in y\,|\,\varphi(x)\}$ , they're saying that the property of x is that it's an element of y.Or are they just saying that x is an element of Y regardless of which property x has , meaning that the crucial point is to relate x to something (y)?

Where I'm still confused is it seemed sometimes we used the left side to ''name'' the set then describe something about it on the right side which is the opposite of what happened there.

Another point I'm confused about is what set is $\{x\in y\,|\,\varphi(x)\}$ ? X?

thanks!

EDIT: I think what I said when I started ''explaining'' doesn't make sense in retrospective.

When I said: ''When write something like $\{x\,|\,\varphi(x)\}$ , it means that a property of x is that it's x.'' I missed the point entirely didn't I? Is the crucial point the fact that it's useless to give a property to x if we don't know where the hell x comes from or where he is or where he stands in relation to anything else?

 

[reenmachine]

we can form $\{x\in A~\vert ~ x~\text{is a set}\}$. This is a perfectly well-defined set (and it is equal to A).

tell me if I'm right: If $\{x\in A~\vert ~ x~\text{is a set}\}$ , then this is equal to set A and perfectly acceptable.But if $\{x\in x~\vert ~ x~\text{is a set}\}$ , then this is a contradiction because a set can't be an element of itself?

thanks

 

[reenmachine]

R = $\{S\in U\,|\,S\notin S\}$

Just another round with this:

Here we want to ''describe'' set R using an element of R , which is S.

We state that an element of R is an element of U , and that the property of this element of R is that it's not an element of itself.So to be an element of R , you need NOT to be an element of yourself.But if you take R , which is a set so not an element of itself , then R is an element of itself based on the property of the elements of R.

It's possible this post cancels most of the questions in my last 2 posts.

This is the paradox?

My brain just exploded guys , see you tomorrow

thanks

edit: the definition of R is ''everything'' that's an element of U that isn't an element of itself correct? So S isn't an element of R per say , but it represent everything that is an element of U and isn't an element of itself , and everything that could be included in this definition will be part of the set R?

 

[Fredrik]

When we say $\varphi(x)$ about an arbitrary set x , we mean to define some kind of characteristic of x.The property is what describes something about x.

So far so good.

When write something like $\{x\,|\,\varphi(x)\}$ , it means that a property of x is that it's x , which doesn't make sense , just like saying that a property of the color blue is that's it's blue.Is that right?

This notation would be useless if it was always like that. Some examples of this notation:

The set of non-negative real numbers: $\{x\in\mathbb R|x\geq 0\}$. We can write this as $\{x\in\mathbb R\,|\, \varphi(x)\}$ if we define $\varphi(x)$ as the statement $x\geq 0$. Here you should think of "being non-negative" as a property that a real number may or may not have. You should think of $\varphi$ as that property. You should think of $\varphi(x)$ as the statement "x has property $\varphi$", i.e. "x is non-negative", which in mathematical notation is written as $x\geq 0$.

The set of even integers: $\{n\in\mathbb Z\,|\,\exists m\in\mathbb Z~~ n=2m\}$. If we write this as $\{n\in\mathbb Z\,|\,\varphi(n)\}$, then $\varphi$ is the property of "being even", and $\varphi(n)$ is the statement "n is even", which in mathematical notation is written as $\exists m\in\mathbb Z~~ n=2m$.

Of course, the $\varphi$ notation isn't needed in these examples, because we can just write out the explicit statement that $\varphi(x)$ or $\varphi(n)$ represents. It's useful when we need a notation for an unspecified statement about a set x.

If $\{x\in y\,|\,\varphi(x)\}$ , they're saying that the property of x is that it's an element of y.Or are they just saying that x is an element of Y regardless of which property x has , meaning that the crucial point is to relate x to something (y)?

This is the set of all x in y such that $\varphi(y)$, i.e. the subset of y that consists of all the members of y that have the property $\varphi$.

EDIT: I think what I said when I started ''explaining'' doesn't make sense in retrospective.

When I said: ''When write something like $\{x\,|\,\varphi(x)\}$ , it means that a property of x is that it's x.'' I missed the point entirely didn't I? Is the crucial point the fact that it's useless to give a property to x if we don't know where the hell x comes from or where he is or where he stands in relation to anything else?

The problem isn't that the notation $\{x\,|\,\varphi(x)\}$ is nonsense. It's not. At least not always. For example, if $\varphi(x)$ is the statement $x\in y$, then $\{x\,|\,\varphi(x)\}$ is just the set y.

The crucial point is that we can't allow this notation to be used with an arbitrary $\varphi$, because when we choose $\varphi(x)$ to be the statement $x\notin x$, then everything turns to nonsense.

However, if y is a set, then the notation $\{x\in y\,|\,\varphi(x)\}$ works just fine with any $\varphi$ we can think of. This is one of the things that the ZFC axioms are telling us.

 

[Fredrik]

tell me if I'm right: If $\{x\in A~\vert ~ x~\text{is a set}\}$ , then this is equal to set A and perfectly acceptable.

Yes. Note however that the statement "x is a set" doesn't actually tell us anything, since all the variables represent sets unless we say otherwise (like when we said that $\varphi$ represents a property). You could replace "x is a set" with any other vacuously true statement like x=x, and the result would be the same.

But if $\{x\in x~\vert ~ x~\text{is a set}\}$ , then this is a contradiction because a set can't be an element of itself?

I actually don't know if a set can be an element of itself, but the notation doesn't make sense, because the the first x is a dummy variable and the second x is some specific set.

 

[micromass]

tell me if I'm right: If $\{x\in A~\vert ~ x~\text{is a set}\}$ , then this is equal to set A and perfectly acceptable.But if $\{x\in x~\vert ~ x~\text{is a set}\}$ , then this is a contradiction because a set can't be an element of itself?

thanks

According to the ZFC axioms, the following set is well-defined:

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

where $A$ is a set that does not depend on x, and where $\varphi(x)$ is a property with $x$ as a variable.

You should interpret the set as "the set of all elements $x$ of $A$ such that $\varphi(x)$ is true.

For example:
$\{x\in \{0,1,2\}~\vert~x=1\}$
Here we have $A=\{0,1,2\}$ and $\varphi(x)$ is the formula $x=1$.
The interpretation of the set is: "the set of all elements $x$ of $\{0,1,2\}$ such that $x=1$. Clearly, the set is just equal to $\{1\}$.

$\{x\in \mathbb{R}~\vert~x^2 = 1\}$
Here the set $A=\mathbb{R}$ and $\varphi(x)$ is $x^2 =1$.
This set is the set of all real numbers $x$ such that $x^2 =1$. Clearly, the set is $\{1,-1\}$.

Some stranger examples that are well-defined sets:
$\{x\in \{0,1,2\}~\vert~x\in x\}$
This is the set of all $x$ in $\{0,1,2\}$ with the proporty that $x$ belongs to itself. There are no such $x$ in $\{0,1,2\}$ with that property. So the set is just the empty set.

$\{x\in \mathbb{R}~\vert~1=1\}$
This is a very pathological example, but it is a well-defined set. The set is the set of all real numbers such that 1=1 is true. To check that an element is in the set, we pick a real number $x\in \mathbb{R}$ and we check that $1=1$ is true. But it is always true. So all $x\in \mathbb{R}$ are in the set. So the set equals entire $\mathbb{R}$.
This is very weird since we have a property $\varphi(x)$ that apparently does not depend on $x$. Such sets are well-defined but never show up in practice.

Some counterexamples:
$\{x~\vert~x~\text{is a set}\}$
This is not a good definition of a set since the set $A$ is missing.

$\{x~\vert~x=1\}$
This is not a good definition of a set, since the set $A$ is again missing.
This is a bit strange, since clearly the set that it would define is just $\{1\}$. So if the above is a set, then it would equal $\{1\}$.
We are not saying that $\{1\}$ is not a set (it is a set). But we are saying that $\{x~\vert~x=1\}$ is not a "well-formed".

$\{x\in x~\vert~x=1\}$
This is not a good definition of a set, since the set $A$ is not independent of $x$. We want a set $A$ that has nothing to do with our dummy variable.

So, the only set builder notation that we accept is:
\{x\in A~\vert~\varphi(x)\}
This is the only well-formed formula.

Now, this implies that the follwing is also not a good definition:

$\{x^3\in \mathbb{R}~\vert~x\geq 0\}$

It is clear what I mean with this set. I want to pick all the elements of $\mathbb{R}$ that have the form $x^3$ for some $x\geq 0$. For example, the element 8 is in the set, because we can pick $x=2$.
The element -8 is not in the set. If we pick $x=-2$, then $-8=x^3$, ,but our $x$ does not satisfy $x\geq 0$.

Anyway, this is not a well-formed formula. Our formula is not in the form
\{x\in A~\vert~\varphi(x)\}
The problem is that we have an $x^3$ instead of an $x$.

We can write rewrite our formula as
$\{x\in \mathbb{R}~\vert ~\exists y\in \mathbb{R}: ~y\geq 0~\text{and}~x=y^3\}$
This is a well-formed formula. Indeed, we can take $A=\mathbb{R}$ and $\varphi(x)$ is the formula $\exists y \in \mathbb{R}:~y\geq 0 ~\text{and}~x=y^3$.
The elements of the set are the real numbers $x$ such that a real number $y$ exists such that $y^3 = x$ and $y\geq 0$.

The problem is that the above set is very difficult to write. I'm sure that people find $\{x^3\in \mathbb{R}~\vert~x\geq 0\}$ much easier to read than $\{x\in \mathbb{R}~\vert ~\exists y\in \mathbb{R}: ~y\geq 0~\text{and}~x=y^3\}$. This is why the notation $\{x^3\in \mathbb{R}~\vert~x\geq 0\}$ is used in math texts and is allowed. Allowing this is an abuse of notation since strictly, the notation wouldn't be allowed.

 

[micromass]

I actually don't know if a set can be an element of itself

There is an axiom in ZFC set theory that forbids a set to be an element of itself. This is called the foundation axiom. Other things that are forbidden are sets such that $x=\{x\}$ or $x=\{x,1\}$.

The foundation axiom is however a non-essential part of ZFC. There is very little that would change in entire mathematics if we allowed $x\in x$ to happen. So many people do not accept the foundation axiom.

So whether there are sets that are elements of themselves. The answer is that you can rule out such sets by axiom. Or you can choose not to rule the sets out.
In light of actual mathematics (except set theory), the axiom is not important at all.

 

[Fredrik]

Regarding the definition $R=\{S\in U\,|\,S\notin S\}$...

We state that an element of R is an element of U , and that the property of this element of R is that it's not an element of itself.So to be an element of R , you need NOT to be an element of yourself.

Yes.

But if you take R , which is a set so not an element of itself

I don't know if a set can be an element of itself. This isn't part of the argument anyway.

, then R is an element of itself based on the property of the elements of R.

Yes, the definition of R ensures that if $R\notin R$, then $R\in R$. That is a contradiction. But the proof doesn't end here, because when an assumption leads to a contradiction, we can conclude that the assumption is a false statement. Our assumption was $R\notin R$, so the conclusion is that this is false, i.e. we have $R\in R$.

But if $R\in R$, then the definition of R tells us that $R\notin R$, so we still get a contradiction. This time our assumption was $R\in R$, so we can conclude that this is false, i.e. that $R\notin R$.

So we have proved that $R\in R$ and (its negation) $R\notin R$ are both false. That is the impossible result that forces us to reject the idea that R is a set.

edit: the definition of R is ''everything'' that's an element of U that isn't an element of itself correct? So S isn't an element of R per say , but it represent everything that is an element of U and isn't an element of itself

Yes.

, and everything that could be included in this definition will be part of the set R?

I don't understand this part of the sentence.

It's clear that one of the reasons why you're having difficulties with this proof is that you had not familiarized yourself with the simple examples $\{x\in y\,|\,\varphi(x)\}$ notation before you attacked the "head explode" example of Russell's paradox. Maybe you understand the proof now, but I think it would still be a good idea to do some exercises from the book that involve this notation. The exercises for section 1.1 on page 7 of the online version contain many simple examples.

 

[reenmachine]

According to the ZFC axioms, the following set is well-defined:

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

where $A$ is a set that does not depend on x, and where $\varphi(x)$ is a property with $x$ as a variable.

You should interpret the set as "the set of all elements $x$ of $A$ such that $\varphi(x)$ is true.

For example:
$\{x\in \{0,1,2\}~\vert~x=1\}$
Here we have $A=\{0,1,2\}$ and $\varphi(x)$ is the formula $x=1$.
The interpretation of the set is: "the set of all elements $x$ of $\{0,1,2\}$ such that $x=1$. Clearly, the set is just equal to $\{1\}$.

$\{x\in \mathbb{R}~\vert~x^2 = 1\}$
Here the set $A=\mathbb{R}$ and $\varphi(x)$ is $x^2 =1$.
This set is the set of all real numbers $x$ such that $x^2 =1$. Clearly, the set is $\{1,-1\}$.

Some stranger examples that are well-defined sets:
$\{x\in \{0,1,2\}~\vert~x\in x\}$
This is the set of all $x$ in $\{0,1,2\}$ with the proporty that $x$ belongs to itself. There are no such $x$ in $\{0,1,2\}$ with that property. So the set is just the empty set.

$\{x\in \mathbb{R}~\vert~1=1\}$
This is a very pathological example, but it is a well-defined set. The set is the set of all real numbers such that 1=1 is true. To check that an element is in the set, we pick a real number $x\in \mathbb{R}$ and we check that $1=1$ is true. But it is always true. So all $x\in \mathbb{R}$ are in the set. So the set equals entire $\mathbb{R}$.
This is very weird since we have a property $\varphi(x)$ that apparently does not depend on $x$. Such sets are well-defined but never show up in practice.

Some counterexamples:
$\{x~\vert~x~\text{is a set}\}$
This is not a good definition of a set since the set $A$ is missing.

$\{x~\vert~x=1\}$
This is not a good definition of a set, since the set $A$ is again missing.
This is a bit strange, since clearly the set that it would define is just $\{1\}$. So if the above is a set, then it would equal $\{1\}$.
We are not saying that $\{1\}$ is not a set (it is a set). But we are saying that $\{x~\vert~x=1\}$ is not a "well-formed".

$\{x\in x~\vert~x=1\}$
This is not a good definition of a set, since the set $A$ is not independent of $x$. We want a set $A$ that has nothing to do with our dummy variable.

So, the only set builder notation that we accept is:
\{x\in A~\vert~\varphi(x)\}
This is the only well-formed formula.

Now, this implies that the follwing is also not a good definition:

$\{x^3\in \mathbb{R}~\vert~x\geq 0\}$

It is clear what I mean with this set. I want to pick all the elements of $\mathbb{R}$ that have the form $x^3$ for some $x\geq 0$. For example, the element 8 is in the set, because we can pick $x=2$.
The element -8 is not in the set. If we pick $x=-2$, then $-8=x^3$, ,but our $x$ does not satisfy $x\geq 0$.

Anyway, this is not a well-formed formula. Our formula is not in the form
\{x\in A~\vert~\varphi(x)\}
The problem is that we have an $x^3$ instead of an $x$.

We can write rewrite our formula as
$\{x\in \mathbb{R}~\vert ~\exists y\in \mathbb{R}: ~y\geq 0~\text{and}~x=y^3\}$
This is a well-formed formula. Indeed, we can take $A=\mathbb{R}$ and $\varphi(x)$ is the formula $\exists y \in \mathbb{R}:~y\geq 0 ~\text{and}~x=y^3$.
The elements of the set are the real numbers $x$ such that a real number $y$ exists such that $y^3 = x$ and $y\geq 0$.

The problem is that the above set is very difficult to write. I'm sure that people find $\{x^3\in \mathbb{R}~\vert~x\geq 0\}$ much easier to read than $\{x\in \mathbb{R}~\vert ~\exists y\in \mathbb{R}: ~y\geq 0~\text{and}~x=y^3\}$. This is why the notation $\{x^3\in \mathbb{R}~\vert~x\geq 0\}$ is used in math texts and is allowed. Allowing this is an abuse of notation since strictly, the notation wouldn't be allowed.

Very clear thank you!

 

[reenmachine]

The set of even integers: $\{n\in\mathbb Z\,|\,\exists m\in\mathbb Z~~ n=2m\}$. If we write this as $\{n\in\mathbb Z\,|\,\varphi(n)\}$, then $\varphi$ is the property of "being even", and $\varphi(n)$ is the statement "n is even", which in mathematical notation is written as $\exists m\in\mathbb Z~~ n=2m$.

So the fact that any m in Z multiplied by two will give us an even number makes it good to define n?

 

[reenmachine]

Regarding the definition $R=\{S\in U\,|\,S\notin S\}$...


Yes.


I don't know if a set can be an element of itself. This isn't part of the argument anyway.


Yes, the definition of R ensures that if $R\notin R$, then $R\in R$. That is a contradiction. But the proof doesn't end here, because when an assumption leads to a contradiction, we can conclude that the assumption is a false statement. Our assumption was $R\notin R$, so the conclusion is that this is false, i.e. we have $R\in R$.

But if $R\in R$, then the definition of R tells us that $R\notin R$, so we still get a contradiction. This time our assumption was $R\in R$, so we can conclude that this is false, i.e. that $R\notin R$.

So we have proved that $R\in R$ and (its negation) $R\notin R$ are both false. That is the impossible result that forces us to reject the idea that R is a set.


Yes.


I don't understand this part of the sentence.

It's clear that one of the reasons why you're having difficulties with this proof is that you had not familiarized yourself with the simple examples $\{x\in y\,|\,\varphi(x)\}$ notation before you attacked the "head explode" example of Russell's paradox. Maybe you understand the proof now, but I think it would still be a good idea to do some exercises from the book that involve this notation. The exercises for section 1.1 on page 7 of the online version contain many simple examples.

Yes I'm pretty sure I get the proof now.I will follow your advice and do some exercises later today from the book.

 

[Fredrik]

So the fact that any m in Z multiplied by two will give us an even number makes it good to define n?

Define n? I just used the definition of "even" to define the set of even integers. (What I wrote down means "the set of all integers that have the property of being even"). The definition of "even" is this: An integer n is said to be even if there's an integer m such that 2m=n.

 

[Fredrik]

There is an axiom in ZFC set theory that forbids a set to be an element of itself. This is called the foundation axiom. Other things that are forbidden are sets such that $x=\{x\}$ or $x=\{x,1\}$.

The foundation axiom is however a non-essential part of ZFC. There is very little that would change in entire mathematics if we allowed $x\in x$ to happen. So many people do not accept the foundation axiom.

So whether there are sets that are elements of themselves. The answer is that you can rule out such sets by axiom. Or you can choose not to rule the sets out.
In light of actual mathematics (except set theory), the axiom is not important at all.

Thanks for the explanation. According to Wikipedia, the axiom of foundation says that every non-empty set x has an element y that's disjoint from x. This clearly rules out x={x}, but it's not obvious how it rules out the existence of disjoint x,y such that x={x,y}.

 

[reenmachine]

I sincerely apologize but I'm still having trouble using LaTeX and it would take me half a day to write all the exercises questions in the post by copy-pasting each symbol.

I will simply give you the link http://www.people.vcu.edu/~rhammack/BookOfProof/Sets.pdf , the exercises are on page 7 in section (1.1).I will randomly pick a couple of them and give it a shot.

If you find it unacceptable not to see the question here , please tell me so and I'll try to come out with a solution.

A.

Write each of the following sets by listing their elements between braces.

solutions:
3. {-2,-1,0,1,2,3,4,5,6}
7. {3}
8. {-2}
9. {0} ?? (having trouble with the sin/cos factor in this context)
15. {5a,2b} ? (again , not sure I get how to proceed)

B.

Write each of the following sets in set-builder notation.

solutions:
17. ${x\in N\,|x is a multiple of 2}$
22. ${x\in N\,|x follows the sequence +3,+5,+7,+9}$ ? Okay I admit I have no clue how to proceed here.
25. ${x\in N\,|1/2x}$

edit: apparently I'm still confused about how to use LaTeX

C.

Find the following cardinalities.

solutions:
31.3
32.1 ?
33.??

I admit I'm struggling quite a bit , some feedback would be of great help for me! No point in continuing this , I'm having too much of a hard time and I feel it's counter-productive until I have further informations.

EDIT: seems I still have massive trouble with latex , this isn't how the notations were suppose to come out This is unfortunate because I feel I spend 50% of my energy trying to actually WRITE what I'm trying to write instead of concentrating on the math.

thanks!

 

[Fredrik]

{ and } are reserved symbols in LaTeX. If you want to display them, you must type \{ and \}. If you want text to be interpreted as text and not as a product of variables, you must write \text{something}. LaTeX Guide. Yes, the first few days of using LaTeX, you may spend as much time on how to write things as on the math, but it's just the first few days.

A

3. That's right.
7. The equation has two solutions in ℝ, and 3 isn't one of them.
8. The equation has three solution in ℝ, and -2 is just one of them.
9. What you need to know is that $\sin 0=0$ and that $\sin(t+2\pi)=\sin t$ for all $t\in\mathbb R$.
15. You seem to have forgotten how to read the notation $\{x\,|\,\varphi(x)\}$. (The author writes a colon where I write a vertical bar). It's read as "the set of all x with property $\varphi$". Can you translate $\{5a+2b\,|\,a,b\in\mathbb Z\}$ to words in this way?

Your answers to 7,8 and 9 suggest that you need to refresh your memory about polynomial equations and the basics of trigonometry. I would guess that Kline covers that. If he doesn't, then you will have to read about it somewhere else.B

17 If N={1,2,...}, your answer means {2,4,6,8,10,...}, so this is incorrect. Hint: 2^n.
22 This one is pretty hard. The sequence is 3+3, 3+3+5, 3+3+5+7, etc. We keep adding larger odd integers to the result of the previous calculation. I don't see a simple formula for it. We can define the sequence in the following way. Define s(0)=3. For each positive integer n, define s(n)=s(n-1)+2n+1. Then we have s(1)=s(0)+2*1+1=3+3=6, s(2)=s(1)+2*2+1=6+5=11, s(3)=s(2)+2*3+1=11+7=18, etc. With this definition of s, we can write the set as $\{s(n)|n\in\mathbb N\}$. Maybe there's a simpler answer that I just don't see.
25 I would recommend that you check your answers by calculating a few members of the set you have just written down. What you wrote would give us {1/2, 1/4, 1/6,...}, which is wrong. Hint: 2^n.

By the way, I think it's slightly more popular these days to define the "natural numbers" as including 0. This author doesn't, and that's fine too. You just need to know that different authors have different conventions.C

31. The question is asking you how many elements the set {{{1},{2,{3,4}},∅}} has.