Question about proof from a guy with a highschool education

[CompuChip]

Another try:

set = {x ∈ Z : ∃y ∈ Z x = 3y} ?

I have a feeling this is correct.

Isn't all 6x + 9y sums (if x and y are members of Z) a multiple of 3?

EDIT: woah , I just noticed that the z isn't an element of Z , that's just a brain cramp there

Yep, you are correct in both instances (I just made your Z boldface, which is alternative notation for the set of integers \mathbb{Z}, rather than some unspecified set Z).

A common shortcut is just to write 3\mathbb{Z} by the way, so if you see that written the above set is meant.

 

[reenmachine]

Yep, you are correct in both instances (I just made your Z boldface, which is alternative notation for the set of integers \mathbb{Z}, rather than some unspecified set Z).

A common shortcut is just to write 3\mathbb{Z} by the way, so if you see that written the above set is meant.

I might have been correct , but in your exemple \{ 6x + 9z \mid x, y \in \mathbb{Z} \} , the small z isn't an element of Z , so isn't it incorrect?

 

[CompuChip]

Ah, yes, that is a typo. The z should have been a y. My apologies for the confusion that may have caused.

 

[reenmachine]

It's just the conventional notation. For example, the sum of all the real numbers in the set $\{x_1,x_2,\dots,x_n\}\subseteq\mathbb R$ can be written as
$$\sum_{i=1}^n x_i.$$ The alternative is to define $I=\left\{i\in\mathbb Z\,|\,1\leq i\leq n\right\}$ and write
$$\sum_{i\in I} x_i.$$

okay so i isn't really 1 , it's just a notation for a dummy variable.

when they write x1 , x2 and so on until xn , does it represent real numbers?

thanks

 

[micromass]

when they write x1 , x2 and so on until xn , does it represent real numbers?

In Fredrik's example: yes, since he detailed that $\{x_1,...,x_n\}\subseteq \mathbb{R}$. But in principle, it could be something entirely different.

For example, we could have $x_1 = 1$, $x_2 = 2$ and $x_3 = 13$, then

\sum_{i=1}^3 x_i = 1 + 2 + 13 = 16

 

[reenmachine]

Little bit of a rewind here , from the textbook I used at the beginning:

Some terminology.
Functions from A to B in the general case are said to be into B.If the range of the function equals B, then the function is onto B(or surjection). A function F: A → B is called one-to-one function (or injection) just in case no member of B is assigned to more than one member of A (so if a ≠ b, then F(a) ≠ F(b)). A function which is both one-to-one and onto is called a one-to-one correspondence (or bijection). It is easy to see that if a function F is one-to-one correspondence, then the relation F–1 is a function and one-to-one correspondence

Just to use an example , suppose A= {1 , 2 , 3} and B= {4 , 5 , 6}.

If F: A → B , then R ⊆ A × B right? (R being the relation)

If F(1)= 4 , F(2)= 5 and F(3)= 6 , then this is a surjection is that right? (and a bijection).This would also be a one-to-one function correct? Is this a one-to-one correspondance?

But if F(1)= 5 , F(2)= 5 and F(3)= 5 , then this is an injection?

About F-1 , is that the same concept as with relations -1? So in the last case above , F-1 would be what? It can't be F(5) = 1 , 2 , 3 can it?

thanks!

 

[reenmachine]

In Fredrik's example: yes, since he detailed that $\{x_1,...,x_n\}\subseteq \mathbb{R}$. But in principle, it could be something entirely different.

For example, we could have $x_1 = 1$, $x_2 = 2$ and $x_3 = 13$, then

\sum_{i=1}^3 x_i = 1 + 2 + 13 = 16

Very clear thank you!

 

[Fredrik]

okay so i isn't really 1 , it's just a notation for a dummy variable.

It's the start of the range of values for the dummy variable i. In the sum $x_1+\cdots+x_n$, the i has a different value in each term. The first is written below the sigma, the last above it. $$\sum_{i=1}^n x_i$$.

 

[Fredrik]

Just to use an example , suppose A= {1 , 2 , 3} and B= {4 , 5 , 6}.

If F: A → B , then R ⊆ A × B right? (R being the relation)

If F: A → B , then F ⊆ A × B. (This is if we use the definition of "function" from the pdf, which is equivalent to my definition 1). There's no need to introduce another symbol for "the relation", since functions are relations.

If F(1)= 4 , F(2)= 5 and F(3)= 6 , then this is a surjection is that right? (and a bijection).This would also be a one-to-one function correct? Is this a one-to-one correspondance?

Yes, to all questions.

But if F(1)= 5 , F(2)= 5 and F(3)= 5 , then this is an injection?

No, because here F(x)=F(y) doesn't imply x=y. F takes two elements of A to the same element of B.

About F-1 , is that the same concept as with relations -1? So in the last case above , F-1 would be what? It can't be F(5) = 1 , 2 , 3 can it?

F^-1 is only defined when F is bijective. So if we use your example bijection above, then $F^{-1}(4)=1$ and so on.

However, the set $F^{-1}(C)$ (called the preimage of C under f) is defined for all sets C, even if F is not surjective or injective. It's defined by $F^{-1}(C)=\{x\in A\,|\,F(x)\in C\}$.

 

[reenmachine]

It's the start of the range of values for the dummy variable i. In the sum $x_1+\cdots+x_n$, the i has a different value in each term. The first is written below the sigma, the last above it. $$\sum_{i=1}^n x_i$$.

very clear thank you !

 

[reenmachine]

If F: A → B , then F ⊆ A × B. (This is if we use the definition of "function" from the pdf, which is equivalent to my definition 1). There's no need to introduce another symbol for "the relation", since functions are relations.

good , so a function is always a relation but a relation is not always a function.

Yes, to all questions.

No, because here F(x)=F(y) doesn't imply x=y. F takes two elements of A to the same element of B.

In that case , F(1)=4 , F(2)=5 and F(3)=6 would be an injection?

F^-1 is only defined when F is bijective. So if we use your example bijection above, then $F^{-1}(4)=1$ and so on.

However, the set $F^{-1}(C)$ (called the preimage of C under f) is defined for all sets C, even if F is not surjective or injective. It's defined by $F^{-1}(C)=\{x\in A\,|\,F(x)\in C\}$.

Not sure I understand the last paragraph.First of all , in your last set notation , wouldn't x be an element of B instead of A since 4 , to use your exemple above , is an element of B? About set C , isn't C like the range since with F-1 we'll always have the inverse of a function and therefore will have elements of B inside the function?

thank you very much , your feedbacks are always greatly appreciated!

 

[Fredrik]

good , so a function is always a relation but a relation is not always a function.

Yes.

In that case , F(1)=4 , F(2)=5 and F(3)=6 would be an injection?

The F defined by these three equalities is an injection, yes. It's also a surjection. Since it's both, it's a bijection.

Not sure I understand the last paragraph.First of all , in your last set notation , wouldn't x be an element of B instead of A since 4 , to use your exemple above , is an element of B?

I don't see any typos in my notation. $F^{-1}(C)$ is a subset of A, for all sets C. I don't see what 4 has to do with it.

 

[reenmachine]

I don't see any typos in my notation. $F^{-1}(C)$ is a subset of A, for all sets C. I don't see what 4 has to do with it.

I'm having a hard time understanding this for some reasons.

$F^{-1}(C)=\{x\in A\,|\,F(x)\in C\}$

What happened to the $F^{-1}$ in the definition? If we are in the universe A×B , so the function is from A to B , suppose F(1)=4 and $F^{-1}$ (4)=1 , then since 4 is in B , why should $F^{-1}$ (C)=m = element of A? That's what I was wondering.

edit: I think I understand now , since x is in A , then function x = x in B , so this is what F-1(C) is made of?

 

[Fredrik]

It's just a definition, so it doesn't really require explanation. However, if $C\subseteq B$, and $F:A\to B$ is bijective onto B, so that $F^{-1}:B\to A$ is defined, then the preimage of C under F (the left-hand side below) is equal to the image of C under $F^{-1}$ (the right-hand side below). So it makes sense to use the notation $F^{-1}(C)$ for both.
$$\left\{x\in A\,|\,F(x)\in C\right\} =\left\{F^{-1}(x)\in A\,|\,x\in C\right\}.$$

 

[reenmachine]

It's just a definition, so it doesn't really require explanation. However, if $C\subseteq B$, and $F:A\to B$ is bijective onto B, so that $F^{-1}:B\to A$ is defined, then the preimage of C under F (the left-hand side below) is equal to the image of C under $F^{-1}$ (the right-hand side below). So it makes sense to use the notation $F^{-1}(C)$ for both.
$$\left\{x\in A\,|\,F(x)\in C\right\} =\left\{F^{-1}(x)\in A\,|\,x\in C\right\}.$$

Ok I get it now

thanks a lot for the patience!

 

[reenmachine]

Pretty tired today so just going to ask a few quick questions:

http://people.umass.edu/partee/NZ_2006/Set Theory Basics.pdf

The function F: A→A such that F= {<x,x> : x ∈ A} is called the identity function on A, written idA (or 1A).

Given a function F: A→B that is a one-to-one correspondence, we have the following equations:

F–1 °F= idA,
F° F–1 = ?

Is the answer to ? = idA-1 ?

Given two functions F: A→B and G: B→C, we may form a new function from A to C, called the composition of F and G, written G°F.

Function composition is defined as G°F = def{<x,z> for some y, <x,y> ∈ F and <y,z> ∈ G}

I think I understand the concept (except for why they decided to switch the letters in the notation but I guess that's not really important) but there's one thing I would like to be sure about.

Since it's G°F in the first place , why is it ''<x,z> for some y(?) , <x,y> ∈ F and <y,z> ∈ G'' , why isn't it for all y?

thanks a lot!

Now time to attack the book of proof with more consistancy.Will probably re-read the entire thread in the following week , I think it would be a good idea.

cheers!

 

[Office_Shredder]

Is the answer to ? = idA-1 ?

Nope. Think about what set the values you plug in and get out are going to be in.

Since it's G°F in the first place , why is it ''<x,z> for some y(?) , <x,y> ∈ F and <y,z> ∈ G'' , why isn't it for all y?

thanks a lot!

What this is saying is that G(F(x)) = z if F(x) = y and G(y) = z. y here is representing the specific value that F(x) takes - the statement that <x,y> ∈ F and <y,z> ∈ G isn't going to be true for EVERY y because there can only be one value of y with <x,y> ∈ F to begin with!

For a concrete example, let F and G be functions on the real numbers. F(x) = x+1 and G(x) = x².

Then G(F(x)) = (x+1)². Claim: G(F(2)) = 9. Reading off the definition, the reason why this is true is because there exists some real number y, in particular y=3, with F(2) = y and G(y) = 9. Obviously it's not going to be true that F(2) = y and G(y) = 9 for every real number

 

[Fredrik]

I see that Office_Shredder has already written a good answer, but I wrote half of this before I saw it, so I might as well post it.

Is the answer to ? = idA-1 ?

If you mean what I think you mean, then no, it's not. (Could you at least use sub/sup tags?)

why is it ''<x,z> for some y(?) , <x,y> ∈ F and <y,z> ∈ G'' , why isn't it for all y?

I would define $G\circ F:A\to C$ by saying that
$$(G\circ F)(x)=G(F(x))$$ for all $x\in A$. I have never thought about other ways to define it until now, but let's see. $G\circ F$ is the set of all the ordered pairs $(x,G(F(x)))$ with $x\in A$. So
$$G\circ F=\left\{(x,G(F(x)))|\, x\in A\right\} =\left\{(x,z)\,|\, x\in A\text{ and } z=G(F(x))\right\}.$$ Now consider the equality z=G(F(x)). If we define y by y=F(x), then we can write z=G(y). So $G\circ F$ is the set of all (x,z) such that $x\in A$ and $z=G(y)$, where y is an alternative notation for F(x).

You know that the equalities $y=F(x)$ and $z=G(y)$ can be written as $(x,y)\in F$ and $(y,z)\in G$ respectively. Suppose that we say that there exists a $y\in B$ such that $(x,y)\in F$. This statement is true if and only if x is in the domain of F. So it's a way of saying that $x\in A$, and at the same time reserve the symbol y for F(x).

This means that $G\circ F$ is the set of all (x,z) such that there exists a y in B such that (x,y) is in F and (y,z) is in G.
$$G\circ F=\left\{(x,z)\,|\,\exists y\in B~~ \left((x,y)\in F~\land~(y,z)\in G\right)\right\}.$$

 

[reenmachine]

If you mean what I think you mean, then no, it's not. (Could you at least use sub/sup tags?)

Very sorry for this , I pushed my luck long enough , I'll try to have some kind of ''LaTeX session'' this week where I will try to write different equations or formulas in LaTeX without worrying about the meaning just to get used to it.

I would define $G\circ F:A\to C$ by saying that
$$(G\circ F)(x)=G(F(x))$$ for all $x\in A$. I have never thought about other ways to define it until now, but let's see. $G\circ F$ is the set of all the ordered pairs $(x,G(F(x)))$ with $x\in A$. So
$$G\circ F=\left\{(x,G(F(x)))|\, x\in A\right\} =\left\{(x,z)\,|\, x\in A\text{ and } z=G(F(x))\right\}.$$ Now consider the equality z=G(F(x)). If we define y by y=F(x), then we can write z=G(y). So $G\circ F$ is the set of all (x,z) such that $x\in A$ and $z=G(y)$, where y is an alternative notation for F(x).

You know that the equalities $y=F(x)$ and $z=G(y)$ can be written as $(x,y)\in F$ and $(y,z)\in G$ respectively.

Very clear! Feel much better today and it shows in my understanding.

Suppose that we say that there exists a $y\in B$ such that $(x,y)\in F$. This statement is true if and only if x is in the domain of F. So it's a way of saying that $x\in A$, and at the same time reserve the symbol y for F(x).

Very clear again! Though it's pretty obvious that x is in the domain of F from where we come from with this.

This means that $G\circ F$ is the set of all (x,z) such that there exists a y in B such that (x,y) is in F and (y,z) is in G.
$$G\circ F=\left\{(x,z)\,|\,\exists y\in B~~ \left((x,y)\in F~\land~(y,z)\in G\right)\right\}.$$

Crystal clear! Loving it!

Thank you very much Fredrik , once again!

edit: Just for the sake of ultimate clearness , and I know we already talked about this , but in the last set notation , ''for each'' (x,z) is implied on the left side correct? Don't need to write the symbol?

edit2:We can see with your post that there's many many ways to write a notation for the same set.

 

[reenmachine]

Nope. Think about what set the values you plug in and get out are going to be in.




What this is saying is that G(F(x)) = z if F(x) = y and G(y) = z. y here is representing the specific value that F(x) takes - the statement that <x,y> ∈ F and <y,z> ∈ G isn't going to be true for EVERY y because there can only be one value of y with <x,y> ∈ F to begin with!

For a concrete example, let F and G be functions on the real numbers. F(x) = x+1 and G(x) = x².

Then G(F(x)) = (x+1)². Claim: G(F(2)) = 9. Reading off the definition, the reason why this is true is because there exists some real number y, in particular y=3, with F(2) = y and G(y) = 9. Obviously it's not going to be true that F(2) = y and G(y) = 9 for every real number

Also very clear! Thanks guys this really made me understood the concept perfectly!

 

[reenmachine]

$$G\circ F=\left\{(x,z)\,|\,\exists y\in B~~ \left((x,y)\in F~\land~(y,z)\in G\right)\right\}.$$

What do you think of this alternative statement?

∀x,y,z ( (¬(F(x)∧ ¬y)∧¬(G(y)∧ ¬z)) ∧ (¬(G(F(x)) ∧ ¬z) )

Edit second try:

∀x,y,z ( (¬(x ∈ F ∧ ¬y ∈ F)∧ ¬(y ∈ G ∧ ¬z ∈ G)) ∧ (¬(x ∈ F ∧ ¬z ∈ G) )

 

[Fredrik]

edit: Just for the sake of ultimate clearness , and I know we already talked about this , but in the last set notation , ''for each'' (x,z) is implied on the left side correct? Don't need to write the symbol?

Right. You just need to keep in mind that for all properties P, the notation $\{x\,|\,P(x)\}$ is read as "the set of all all x such that P(x)" or (equivalently) "the set of all x with property P".

What do you think of this alternative statement?

∀x,y,z ( (¬(F(x)∧ ¬y)∧¬(G(y)∧ ¬z)) ∧ (¬(G(F(x)) ∧ ¬z) )

Edit second try:

∀x,y,z ( (¬(x ∈ F ∧ ¬y ∈ F)∧ ¬(y ∈ G ∧ ¬z ∈ G)) ∧ (¬(x ∈ F ∧ ¬z ∈ G) )

In the first one, "$\lnot y$" doesn't make sense, since y is a set, not a statement about sets.

The second one is equivalent to
$$\forall x,y,z~\left((x\in F\Rightarrow y\notin F)\land\dots\right).$$ It's clearly not true for all sets x and y that if x is in F, then y is not. Edit: This is wrong. It should be $y\in F$ where I said $y\notin F$. So the sentence above should be "It's clearly not true for all sets x and y that if x is in F, then so is y.".

If you meant $$\{(x,z)\,|\, \text{your statement}\},$$ then you missed the fact that variables that are targets of a "for all" are dummy variables, so your x,y,z don't have anything to do with the x and z before the | symbol.

 

[reenmachine]

Right. You just need to keep in mind that for all properties P, the notation $\{x\,|\,P(x)\}$ is read as "the set of all all x such that P(x)" or (equivalently) "the set of all x with property P".

This is what I thought thank you!

In the first one, "$\lnot y$" doesn't make sense, since y is a set, not a statement about sets.

Make sense.

The second one is equivalent to
$$\forall x,y,z~\left((x\in F\Rightarrow y\notin F)\land\dots\right).$$ It's clearly not true for all sets x and y that if x is in F, then y is not.

In the second one I wrote ¬(x ∈ F ∧ ¬y ∈ F) which should have been ¬(x ∈ F ∧ ¬(y ∈ F)) , so I'm not sure why you're saying that x in F implies that y isn't in F.What I meant by this is that:

It's not true that: x is in F AND that it's not true that y is in F.Therefore if x is in F then so is y (at least that's what make sense in my mind based on how I operated using these symbols earlier in the thread).

If you meant $$\{(x,z)\,|\, \text{your statement}\},$$ then you missed the fact that variables that are targets of a "for all" are dummy variables, so your x,y,z don't have anything to do with the x and z before the | symbol.

oops

So my statements using the true/false method wouldn't actually require dummy variables? I understand now that there's a difference between dummy variables and the precise x which is in A and so on...but I fail to see how to use these dummy variable to make a notation using the true/false logic method.

thanks again

 

[Fredrik]

In the second one I wrote ¬(x ∈ F ∧ ¬y ∈ F) which should have been ¬(x ∈ F ∧ ¬(y ∈ F)) , so I'm not sure why you're saying that x in F implies that y isn't in F.

$p\rightarrow q$ has the same truth table as $\lnot (p\land\lnot q)$. (This is a good exercise). So these statements are equivalent.

So my statements using the true/false method wouldn't actually require dummy variables? I understand now that there's a difference between dummy variables and the precise x which is in A but f(x)=y and so on...but I fail to see how to use these dummy variable to make a notation using the true/false logic method.

It's hard to explain, since I don't see what you're trying to do.

Note by the way that none of the x,y,z in my notation can be a member of F. They are elements of A,B,C respectively, and F is a subset of A×B.

 

[reenmachine]

$p\rightarrow q$ has the same truth table as $\lnot (p\land\lnot q)$. (This is a good exercise). So these statements are equivalent.It's hard to explain, since I don't see what you're trying to do.

OKay , but in that case if

p= x ∈ F and q= y ∈ F

then x ∈ F → y ∈ F = ¬(x ∈ F ∧ ¬y ∈ F)?

I'm a little bit confused where my statement indicate that if x is in F then y isn't in F based on your following statement:

$$\forall x,y,z~\left((x\in F\Rightarrow y\notin F)\land\dots\right).$$

Note by the way that none of the x,y,z in my notation can be a member of F. They are elements of A,B,C respectively, and F is a subset of A×B.

So G is a subset of B×C and G°F is a subset of A×C?

 

[Fredrik]

OKay , but in that case if

p= x ∈ F and q= y ∈ F

then x ∈ F → y ∈ F = ¬(x ∈ F ∧ ¬y ∈ F)?

Yes, $p\rightarrow q$ is equivalent to $\lnot (p\land\lnot q)$ for all p and q (as proved by their truth tables). This specific choice of p and q is not an exception.

(I would however write $\leftrightarrow$ or $\Leftrightarrow$ instead of =).

I'm a little bit confused where my statement indicate that if x is in F then y isn't in F

You said $\lnot (x\in F\land\lnot y\in F)$, which is equivalent to $x\in F\rightarrow y\in F$. So I should have said "if x is in F, then y is in F".

So G is a subset of B×C and G°F is a subset of A×C?

Yes.

 

[reenmachine]

Let me try it one more time.

∀x,y,z ( ¬(x ∈ A ∧ ¬y ∈ B) ∧ ¬(y ∈ B ∧ ¬z ∈ C) )

I am trying to describe or define G°F.

Yes, $p\rightarrow q$ is equivalent to $\lnot (p\land\lnot q)$ for all p and q (as proved by their truth tables). This specific choice of p and q is not an exception.

(I would however write $\leftrightarrow$ or $\Leftrightarrow$ instead of =).

very clear

You said $\lnot (x\in F\land\lnot y\in F)$, which is equivalent to $x\in F\rightarrow y\in F$. So I should have said "if x is in F, then y is in F".

good

thanks a lot !

 

[CompuChip]

I would define $G\circ F:A\to C$ by saying that
$$(G\circ F)(x)=G(F(x))$$ for all $x\in A$. I have never thought about other ways to define it until now, but let's see.

Can't you just use the definition of a function we have been using all the time to define
(x, z) \in G \circ F \subseteq A \times C \iff x \in A \land \exists y \in B \text{ s.t. } ( (x, y) \in F \land (y, z) \in G)
where F \subseteq A \times B and G \subseteq B \times C
(note that I'm using numerous notational "shortcuts" here to make it readable).

 

[Fredrik]

Let me try it one more time.

∀x,y,z ( ¬(x ∈ A ∧ ¬y ∈ B) ∧ ¬(y ∈ B ∧ ¬z ∈ C) )

I am trying to describe or define G°F.

And this is only part of the notation? The whole thing is $\{(x,z)\,|\,\text{your statement}\}$? In that case, it still has the problem that the x,y,z have nothing to do with the (x,z). If your statement is true, the set will be "the set of all ordered pairs" (taken from any two sets), which I'm sure is too large to even exist in ZFC set theory. If your statement is false, the set will be ∅.

The part

¬(x ∈ A ∧ ¬y ∈ B) ∧ ¬(y ∈ B ∧ ¬z ∈ C)​

says that if x is in A then y is in B, and if y is in B then z is in C. This is not true for all x,y,z.

 

[Fredrik]

Can't you just use the definition of a function we have been using all the time to define
(x, z) \in G \circ F \subseteq A \times C \iff x \in A \land \exists y \in B \text{ s.t. } ( (x, y) \in F \land (y, z) \in G)
where F \subseteq A \times B and G \subseteq B \times C
(note that I'm using numerous notational "shortcuts" here to make it readable).

Yes, but I was trying to explain why the more familiar definition of $G\circ F$ implies that $G\circ F$ is the set specified in the text.