Question about proof from a guy with a highschool education

[reenmachine]

I think this is conceptual , so I will post it here.

I'm thinking about the difference between $\exists \forall$ and $\forall \exists$.

I just wanted to know if I'm on the right track.

With $\exists \forall$ , you could say $\exists y \in Z$ such that $\forall x \in Z$ , $y - 1 = x$.That would mean that a single $y \in Z$ minus one would result in all $x \in Z$ , which is obviously false.

With $\forall \exists$ , you could say $\forall x \in Z$ , $\exists y \in Z$ such that $y - 1 = x$.This means that for all the $x \in Z$ , there is a $y \in Z$ that equals x if you substract one to it.This is true.

thanks!

 

[CompuChip]

Correct!
Usually \exists\forall describes a special element of your set, e.g. a more sensible use would be something like:
\exists y \in \mathbb{Z} \text{ such that } \forall x \in \mathbb{Z}, x + y = x
(This statement asserts the existence of an additive identity, otherwise known as 0).

 

[reenmachine]

Correct!
Usually \exists\forall describes a special element of your set, e.g. a more sensible use would be something like:
\exists y \in \mathbb{Z} \text{ such that } \forall x \in \mathbb{Z}, x + y = x
(This statement asserts the existence of an additive identity, otherwise known as 0).

Thank you!

 

[CompuChip]

And as a practical example of the other possibility, consider

\forall y \in \mathbb{Z}, \exists x \in \mathbb{Z}, x + y = 0

which claims the existence of an additive inverse to all y.

 

[reenmachine]

And as a practical example of the other possibility, consider

\forall y \in \mathbb{Z}, \exists x \in \mathbb{Z}, x + y = 0

which claims the existence of an additive inverse to all y.

Okay so to demonstrate that there's a -1 for 1 and etc...

thank you!

 

[CompuChip]

Exactly, but without fixing the notation.
As long as we're talking about the integers, -1, -2, ... is great notation but it doesn't always work.
For example, the statement also holds in the set { 0, 1, 2 } with addition defined modulo 3. It does not contain any negative numbers, but still 0 + 0 = 0, 1 + 2 = 0 and 2 + 1 = 0.

So the statement really says something about (an operation on) our set. I stated it here for $\mathbb{Z}$, but I can state it for any set and then it may be an axiom, or it may be provable from axioms, or it may be false.

 

[reenmachine]

For example, the statement also holds in the set { 0, 1, 2 } with addition defined modulo 3. It does not contain any negative numbers, but still 0 + 0 = 0, 1 + 2 = 0 and 2 + 1 = 0.

I don't understand what you're saying :(

Why 1+2=0 and 2+1=0 in this set?

 

[Fredrik]

I don't understand what you're saying :(

Why 1+2=0 and 2+1=0 in this set?

He's talking about letting the + symbol denote "addition modulo 3" instead of the usual addition operation. The dumbed down explanation of the definition is that when we "should" get to 3, we start over with 0 instead. So e.g. 2+1=0 and 2+2=1.

 

[reenmachine]

He's talking about letting the + symbol denote "addition modulo 3" instead of the usual addition operation. The dumbed down explanation of the definition is that when we "should" get to 3, we start over with 0 instead. So e.g. 2+1=0 and 2+2=2.

I'm not sure I understand , why isn't it 2+2 = 1?

If you restart at 0 when you reach 3 , then why isn't 4 = 1 and 5 = 2 and 6 = 0 and so on?

 

[Fredrik]

I'm not sure I understand , why isn't it 2+2 = 1?

If you restart at 0 when you reach 3 , then why isn't 4 = 1 and 5 = 2 and 6 = 0 and so on?

It is. I typed that wrong. I fixed it in an edit after you posted this, but somehow I didn't see that you had made this post.

 

[reenmachine]

It is. I typed that wrong. I fixed it in an edit after you posted this, but somehow I didn't see that you had made this post.

No problem :)

thanks a lot!

 

[reenmachine]

Just for fun , from the set $\{0,1,2\}$ with "addition modulo 3" just trying to describe the set 0 , 1 and 2 based on all possible sums of elements of $\mathbb{N}$.

$\mathbb{N}=\{0,1,2,3...\}$ here (zero included)

0 = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 3(y) = x\}$
1 = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 1 + 3(y) = x\}$
2 = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 2 + 3(y) = x \}$

0+0=0 (0)
0+1=1 (1)
1+1=2 (2)
1+2=0 (3)
2+2=1 (4)
2+3=2 (5)
3+3=0 (6)
3+4=1 (7)
4+4=2 (8)
4+5=0 (9)
5+5=1 (10)
5+6=2 (11)
6+6=0 (12)

 

[CompuChip]

He's talking about letting the + symbol denote "addition modulo 3" instead of the usual addition operation. The dumbed down explanation of the definition is that when we "should" get to 3, we start over with 0 instead. So e.g. 2+1=0 and 2+2=1.

Actually the dumbed down explanation would be "I just defined it that way".

However, the idea is basically that of division with remainder, except we are only interested in the remainder. E.g. instead of "11 / 3 = 3 with remainder 2" we just say "11 mod 3 = 2".

An everyday life example (yes, there are not many of those in maths :-)): if it is now 11 am and you will meet someone in 3 hours, you never say "I'll see you at 14", do you? Instead, you will say "I'll see you at 2". In physics, and the bits of mathematics related to it, modulo calculus is pretty important - perhaps to ones surprise when one encounters it.

 

[Fredrik]

Just for fun , from the set $\{0,1,2\}$ with "addition modulo 3" just trying to describe the set 0 , 1 and 2 based on all possible sums of elements of $\mathbb{N}$.

$\mathbb{N}=\{0,1,2,3...\}$ here (zero included)

0 = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 3(y) = x\}$
1 = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 1 + 3(y) = x\}$
2 = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 2 + 3(y) = x \}$

0+0=0 (0)
0+1=1 (1)
1+1=2 (2)
1+2=0 (3)
2+2=1 (4)
2+3=2 (5)
3+3=0 (6)
3+4=1 (7)
4+4=2 (8)
4+5=0 (9)
5+5=1 (10)
5+6=2 (11)
6+6=0 (12)

I'm not sure how you go from those definitions of 0,1,2 to the results in that list.

The fancy way of doing what I think you want to do here goes like this:

Define a relation ~ on $\mathbb Z$ by saying that for all $n,m\in\mathbb Z$, $n\sim m$ if and only if n-m is an integer multiple of 3. Show that ~ is an equivalence relation. For each $n\in\mathbb Z$, define $[n]=\{m\in\mathbb Z:m\sim n\}$. The sets [n] with $n\in\mathbb Z$ are called equivalence classes. Show that since ~ is an equivalence relation, each integer belongs to exactly one equivalence class. The set of equivalence classes is denoted by $\mathbb Z/\sim$. So $Z/\!\sim\, =\{[n]:n\in\mathbb Z\}$. Now we define an "addition" operation on $\mathbb Z/\sim$ by saying that for all $n,m\in\mathbb Z$, we have $[n]+[m]=[n+m]$. (Some work is required to see that this definition makes sense).

Now we can define "addition modulo 3" on the set S={0,1,2} as the + operation such that for all $n,m\in S$, we have $n+m=\left([n]+[m]\right)\cap S$. Edit: This is wrong. See post #681.

For example, to compute 2+2, we first note that $[2]+[2]=[2+2]=[4]=\{\dots,-2,1,4,7,10,\dots\}$ (where the + in [2+2] is the standard addition operation), and then we note that the only member of this set that's also in S is 1.

If all you want to accomplish is to define addition modulo 3 on the set {0,1,2}, this approach is of course unnecessarily complicated. But it's pretty useful to understand equivalence classes. (Not in your first year at the university, but probably in the third).

 

[AnTiFreeze3]

Oh my goodness this thread is still alive.

 

[reenmachine]

I'm not sure how you go from those definitions of 0,1,2 to the results in that list.

The fancy way of doing what I think you want to do here goes like this:
.

I just woke up so give me an hour to eat and wake up before digesting the rest of your post , but I'm not sure why my version is wrong if you take for granted I didn't include the negative integers.Just to be sure , in your post , ~ means negative/not true?

This is what I wanted to do in clearer terms:

$\mathbb{N} = \{0,1,2,3,4,5,6...\}$

0 = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 3(y) = x\}$ = $\{0,3,6,9,12,15,18,21...\}$ = The set of all sums of elements of $\mathbb{N}$ that would result in 0 in the set with addition modulo 3.

1 = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 1 + 3(y) = x\}$ = $\{1,4,7,10,13,16,19...\}$ = The set of all sums of elements of $\mathbb{N}$ that would result in 1 in the set with addition modulo 3.

2 = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 2 + 3(y) = x \}$ = $\{2,5,8,11,14,17,20,23...\}$ = The set of all sums of elements of $\mathbb{N}$ that would result in 2 in the set with addition modulo 3.

Of course this exclude the negative integers from this set's universe , but not zero since I included it in my version of $\mathbb{N}$ which I understood was accepted (even if uncommon) from some conversations we had.

Is excluding the negative integers a mistake? I thought we could basically decide what we wanted the set to really mean from that context.

 

[reenmachine]

Oh my goodness this thread is still alive.

Of course

 

[Fredrik]

Just to be sure , in your post , ~ means negative/not true?

Not at all. It's a binary relation that I defined in the post.

This is what I wanted to do in clearer terms:

$\mathbb{N} = \{0,1,2,3,4,5,6...\}$

0 = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 3(y) = x\}$ = $\{0,3,6,9,12,15,18,21...\}$ = The set of all sums of elements of $\mathbb{N}$ that would result in 0 in the set with addition modulo 3.

1 = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 1 + 3(y) = x\}$ = $\{1,4,7,10,13,16,19...\}$ = The set of all sums of elements of $\mathbb{N}$ that would result in 1 in the set with addition modulo 3.

2 = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 2 + 3(y) = x \}$ = $\{2,5,8,11,14,17,20,23...\}$ = The set of all sums of elements of $\mathbb{N}$ that would result in 2 in the set with addition modulo 3.

I don't have any objections to these definitions, except maybe that I would use a notation other than 0,1,2. The part that looked weird in your post was that you seemed to think that addition of such sets doesn't need to be defined

 

[CompuChip]

Am I allowed to nitpick? Because 1 + 3(y) = x also looks a bit strange. x = 1 + 3y or x = 3y + 1 is a more standard way of writing it, the brackets around (y) are redundant.

 

[reenmachine]

How about this?

$A$ = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 3(y) = x\}$ = $\{0,3,6,9,12,15,18,21...\}$

$B$ = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 1 + 3(y) = x\}$ = $\{1,4,7,10,13,16,19...\}$

$C$ = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 2 + 3(y) = x \}$ = $\{2,5,8,11,14,17,20,23...\}$

Set $\{0,1,2\}$ with addition modulo 3 (only for positive integers) =

$\{ t , v ,w \in \mathbb{N} \ | \ \forall x \in A , \ \forall y \in B , \ \forall z \in C \ \ \ x - x = t \ , y - y + 1 = v \ , z - z + 2 = w \ \}$

 

[reenmachine]

Not at all. It's a binary relation that I defined in the post.

The book or proof use this symbol for negation and I'm reading the chapter , this is where the confusion came from.

I don't have any objections to these definitions, except maybe that I would use a notation other than 0,1,2. The part that looked weird in your post was that you seemed to think that addition of such sets doesn't need to be defined

I tried that with the post above

thank you!

 

[reenmachine]

Am I allowed to nitpick? Because 1 + 3(y) = x also looks a bit strange. x = 1 + 3y or x = 3y + 1 is a more standard way of writing it, the brackets around (y) are redundant.

Of course you can nitpick all you want , I encourage everybody to do so , as for the notation , I don't even know why I wrote it like this

thank you!

 

[reenmachine]

Maybe I should use functions? Like functions $r$ , $s$ and $f$ with $r(n) = n - n$ , $s(n) = n - n + 1$ and $f(n) = n - n + 2$ with $n \in \mathbb{N}$.

$r(A) \cup s(B) \cup f(C)$ = $\{0,1,2\}$ (with addition modulo 3) , basically the union of the three sets $r(A)$ = $\{r(x) | x \in A\}$ , $s(B)$ = $\{s(y) | y \in B\}$ and $f(C)$ = $\{ f(z) | z \in C\}$.

The part I'm losing myself with is whether or not I need to explain why or how the set {0,1,2} has three elements , 0 , 1 and 2 , or if I just have to define it as the set containing these three elements , regardless of the road I took to create that set.

 

[Fredrik]

How about this?

$A$ = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 3(y) = x\}$ = $\{0,3,6,9,12,15,18,21...\}$

$B$ = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 1 + 3(y) = x\}$ = $\{1,4,7,10,13,16,19...\}$

$C$ = $\{x \in \mathbb{N} \ | \ \exists y \in \mathbb{N} \ \ 2 + 3(y) = x \}$ = $\{2,5,8,11,14,17,20,23...\}$

Set $\{0,1,2\}$ with addition modulo 3 (only for positive integers) =

$\{ t , v ,w \in \mathbb{N} \ | \ \forall x \in A , \ \forall y \in B , \ \forall z \in C \ \ \ x - x = t \ , y - y + 1 = v \ , z - z + 2 = w \ \}$

You could use a notation like $0',1',2'$ or $\mathbf 0,\mathbf 1,\mathbf 2$ if you want the notation to remind you of 0,1,2.

The definition of that last set doesn't make sense.

Maybe I should use functions? Like functions $r$ , $s$ and $f$ with $r(n) = n - n$ , $s(n) = n - n + 1$ and $f(n) = n - n + 2$ with $n \in \mathbb{N}$.

This would make r(n)=0, s(n)=1 and f(n)=2 for all natural numbers n. Constant functions aren't much fun.

The part I'm losing myself with is whether or not I need to explain why or how the set {0,1,2} has three elements

If a set can be written in the form {x,y,z} and we have x≠y, y≠z and z≠x, then the set has 3 elements.

 

[reenmachine]

Okay , I'll take this post piece by piece

Define a relation ~ on $\mathbb Z$...

So ~ is an undefined relation at this very moment in the sentence?

...by saying that for all $n,m\in\mathbb Z$, $n\sim m$ if and only if n-m is an integer multiple of 3

.

What does "-" mean in the part I bolded (n-m)?

By saying $n\sim m \leftrightarrow n-m = \{x \in Z | 3x\}$ , are we trying to create a ~ relation that would mean "equals" between n and m , which in that case would something 0=3?

Show that ~ is an equivalence relation. For each $n\in\mathbb Z$, define $[n]=\{m\in\mathbb Z:m\sim n\}$. The sets [n] with $n\in\mathbb Z$ are called equivalence classes

So I need to show that m~n means m=n if and only if n-m is an integer multiple of 3?

If $[7] = \{m\in\mathbb Z:m\sim 7\}$ , what is happening? What can $m$ be?

Show that since ~ is an equivalence relation, each integer belongs to exactly one equivalence class. The set of equivalence classes is denoted by $\mathbb Z/\sim$

.

I don't understand that each integer belongs to exactly one equivalence class.Is the number of equivalence class infinite like the integer? So 7 belongs to [7]? I'm a little bit lost.

So $Z/\!\sim\, =\{[n]:n\in\mathbb Z\}$. Now we define an "addition" operation on $\mathbb Z/\sim$ by saying that for all $n,m\in\mathbb Z$, we have $[n]+[m]=[n+m]$. (Some work is required to see that this definition makes sense).

So basically here we demonstrate that by adding a relation between two different classes , you actually get the sums of the number of these two classes , so for exemple [2]+[3] = [2+3] = [5].So this is the equivalent class [5]? Where I'm lost is from there how do I ''transform'' him into 1?

Now we can define "addition modulo 3" on the set S={0,1,2} as the + operation such that for all $n,m\in S$, we have $n+m=\left([n]+[m]\right)\cap S$.

Following from my previous question , if $n=2$ and $m=3$ , then $2+3 = ([2]+[3]) = [2+3] = [5] \cap S$.This is another key part where I'm confused , why is there an intersection between [5] and {0,1,2}?

For example, to compute 2+2, we first note that $[2]+[2]=[2+2]=[4]=\{\dots,-2,1,4,7,10,\dots\}$ (where the + in [2+2] is the standard addition operation), and then we note that the only member of this set that's also in S is 1.

Is this whole concept simply trying to say that all integer will share an equivalence relation if and only if they share some common characteristics?

The part where you jump from [4] to the set {...1,4,7...} confuses me.Basically [4] = [1] , but when did we proved or suggested that? At the beginning> Sorry , little bit of confusion :X

From the other post:

This would make r(n)=0, s(n)=1 and f(n)=2 for all natural numbers n. Constant functions aren't much fun.

Yes , but if we use them as $r(A) \cup s(B) \cup f(C)$ , then it describes the set $\{0,1,2\}$ that transformed each elements of A into 0 , each elements of B into 1 and each elements of C into 2 no?

thanks a lot!

 

[Fredrik]

So ~ is an undefined relation at this very moment in the sentence?

Yes.

What does "-" mean in the part I bolded (n-m)?

It's the usual subtraction operation on the set of integers.

By saying $n\sim m \leftrightarrow n-m = \{x \in Z | 3x\}$ , are we trying to create a ~ relation that would mean "equals" between n and m , which in that case would something 0=3?

We wouldn't use the word "equals", but we are trying to define an equivalence relation, and those have a lot in common with equality. Instead of equals, we could say something like "is equivalent to". In this case, there is however a better option, "is congruent modulo 3". So, the definition tells us that two integers are said to be congruent modulo 3 if and only if their difference is an integer multiple of 3.

Wikipedia uses the notation $\equiv$ instead of $\sim$ (on this page), so maybe I should have used that.

So I need to show that m~n means m=n if and only if n-m is an integer multiple of 3?

No, that's the definition of m~n, and you don't need to prove a definition. What needs to be proved here is that ~ is symmetric (x~y if and only if y~x), reflexive (x~x) and transitive (if x~y and y~z, then x~z).

If $[7] = \{m\in\mathbb Z:m\sim 7\}$ , what is happening? What can $m$ be?

[7]={...,-2,1,4,7,10,13,...}.

I don't understand that each integer belongs to exactly one equivalence class.Is the number of equivalence class infinite like the integer? So 7 belongs to [7]? I'm a little bit lost.

There are only three equivalence classes, [0],[1],[2]. Yes, 7 belongs to [7], but [7]=[1].

It's a good exercise to prove the following theorem: Let X be an arbitrary set, and let ~ be an arbitrary equivalence relation on X. For each x in X, define [x] by $[x]=\{y\in X:x\sim y\}$.

(a) For all $x,y\in X$, either $[x]\cap[y]=\varnothing$ or $[x]=[y]$.
(b) For all $x\in X$, there's a $y\in X$ such that $x\in[y]$.

Note that (a) ensures that each element of X belongs to at most one equivalence class, and that (b) ensures that each element of X belongs to at least one equivalence class. So together they imply that each element of X belongs to exactly one equivalence class.

So basically here we demonstrate that by adding a relation between two different classes , you actually get the sums of the number of these two classes

No, the relation partitions the set into equivalence classes. Then we focus on the set of equivalence classes $\mathbb Z/\!\sim\,=\{[0],[1],[3]\}$ instead. Since we just defined this set, there's no addition operation defined on it yet. So we define one like this: For all $n,m\in\{0,1,2\}$, we define [n+m] by $[n]+[m]=[n+m]$.

, so for exemple [2]+[3] = [2+3] = [5].So this is the equivalent class [5]? Where I'm lost is from there how do I ''transform'' him into 1?

[5]={...,2,5,8,...}=[2].

Following from my previous question , if $n=2$ and $m=3$ , then $2+3 = ([2]+[3]) = [2+3] = [5] \cap S$.This is another key part where I'm confused , why is there an intersection between [5] and {0,1,2}?

We want the result to be a number in S. We have [5]={...,-1,2,5,8,...}. If we intersect this with S, we get...uhh...we get {2}, not 2 as I wanted. So my definition doesn't quite make sense. Let me try again:

We can define addition modulo 3 on the set S={0,1,2} by saying that n+m (where + denotes the operation we're trying to define) is the unique k in S such that [k]=[n+m] (where + denotes the usual addition operation on the integers).

So we don't need the addition operation that I defined on the set of equivalence classes. Not just to define "addition modulo 3" on the set {0,1,2} anyway. That's not surprising , since there are perfectly adequate ways to define that operation without mentioning equivalence classes at all.

However, there's an interesting observation to be made here. The addition operation we defined on the set {[0],[1],[2]} is such that e.g. [2]+[2]=[4]=[1]. So this set with its addition operation "behaves" exactly like {0,1,2} with its addition operation. It's like we're doing exactly the same thing when we're working with {[0],[1],[2]} and its addition operation, as when we're working with {0,1,2} and its addition operation. The notations are different, but everything else is the same.

We have found a "thing" that, except for notation, is "just like" some other thing. There are some fancy mathematical terms for this. You don't have to learn them now, but I guess it can't hurt if I mention them. The "things" we're working with here are called groups, and the technical way to say that the first one is "just like" the other one is to say that these groups are isomorphic.

Basically [4] = [1] , but when did we proved or suggested that?

It follows from the definitions of [n] and ~. [4] is the set of all integers that differ from 4 by an integer multiple of 3. [1] is the set of all integers that differ from 1 by an integer multiple of 3. It's pretty obvious that they are the same, and it's easy to prove it.

Yes , but if we use them as $r(A) \cup s(B) \cup f(C)$ , then it describes the set $\{0,1,2\}$ that transformed each elements of A into 0 , each elements of B into 1 and each elements of C into 2 no?

We have $r(A)\cup s(B)\cup f(C)=\{0\}\cup\{1\}\cup\{2\}=\{0,1,2\}$, but I don't see the point of introducing these functions.

 

[reenmachine]

It's the usual subtraction operation on the set of integers.

Ahhh ok , sorry for the confusion.I've learn quite a bit of new notations since we started this thread and I prefer to always be sure because sometimes old notations of my past have a different meaning depending on context.

We wouldn't use the word "equals", but we are trying to define an equivalence relation, and those have a lot in common with equality. Instead of equals, we could say something like "is equivalent to". In this case, there is however a better option, "is congruent modulo 3". So, the definition tells us that two integers are said to be congruent modulo 3 if and only if their difference is an integer multiple of 3.

I am not sure what the difference between "equals" and "is equivalent to" is.

Attempt to understand with an analogy: "Equals" means Mathematic = Mathematic while "is equivalent to" would be Mathematic is equivalent to Mathematique in french.So you could say it's "basically" the same thing within a different context?

(I understand the analogy is limited)

?

Wikipedia uses the notation $\equiv$ instead of $\sim$ (on this page), so maybe I should have used that.

No problem , the only reason for the confusion was that this symbol was used in the book of proof in the exact chapter I'm reading as the notation for negation of a statement.

No, that's the definition of m~n, and you don't need to prove a definition. What needs to be proved here is that ~ is symmetric (x~y if and only if y~x), reflexive (x~x) and transitive (if x~y and y~z, then x~z).

Okay for a minute I thought ~ couldn't be reflexive , but it's always the case because of $3(0)=0$.

Proving this seems tricky at least from my current perspective.

Let me try to deconstruct the situation a little bit:

We have relation ~ that relates two elements if and only if the result of substracting one element to another is a multiple of 3.

We already accept the definition of ~ and that x , y are arbitrary elements of $\mathbb Z$.

We want to prove that x~y if and only if y~x.

Assume x~y.Our assumption implies that $x - y =\{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.This means that the difference of value between $x$ and $y$ will always be a multiple of 3.This implies that $y - x = \{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.This proves that x~y $\rightarrow$ y~x.

Now assume y~x.Our assumption implies that $y - x =\{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.This means that the difference of value between $y$ and $x$ will always be a multiple of 3.This implies that $x - y = \{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.This proves that y~x $\rightarrow$ x~y.

The last two paragraphs proves that x~y $\leftrightarrow$ y~x.

Frankly I'm not sure how to proceed here.I have a strong feeling I'm taking shortcuts once again.I have to go so I'll finish with the rest of the post in depth later.

 

[Fredrik]

I am not sure what the difference between "equals" and "is equivalent to" is.

You know what "equals" means. "x is equivalent to y" is just a convenient way to say that x~y, where ~ is the equivalence relation we're currently working with. (We can use this terminology no matter what equivalence relation ~ is. When we're working with the specific equivalence relation discussed here, we have the option to say "x is congruent modulo 3 to y").

We want to prove that x~y if and only if y~x.

Assume x~y.Our assumption implies that $x - y =\{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.This means that the difference of value between $x$ and $y$ will always be a multiple of 3.This implies that $y - x = \{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.This proves that x~y $\rightarrow$ y~x.

This is fine, except that you wrote = in two places where you meant $\in$.

Now assume y~x.Our assumption implies that $y - x =\{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.This means that the difference of value between $y$ and $x$ will always be a multiple of 3.This implies that $x - y = \{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.This proves that y~x $\rightarrow$ x~y.

Since x and y were arbitrary when you proved the first part, you don't actually have to repeat the proof with x and y swapped.

Frankly I'm not sure how to proceed here.I have a strong feeling I'm taking shortcuts once again.

The result that ~ is symmetric is so obvious that one could argue that you took a longer route than necessary, but I see what you mean about the shortcut.

To prove that ~ is symmetric, I think this is sufficient: Let $x,y\in\mathbb Z$ be abitrary. Clearly x-y is an integer multiple of 3 if and only if y-x is an integer multiple of 3.

If you don't think that this is obvious, or fear that your readers won't think it's obvious, you can do it like this: Let $x,y\in\mathbb Z$ be abitrary. Suppose that x~y. By definition of ~, this implies that there's an integer z such that x-y=3z. Let z be such an integer. We have y-x=3(-z). Since -z is an integer, this implies that y~x.

The part that you left out, that made you feel like you took a shortcut, was to not mention explicitly that there's an integer z such that x-y=3z, and that such a z satisfies y-x=3(-z) and $-z\in\mathbb Z$.

 

[reenmachine]

No, that's the definition of m~n, and you don't need to prove a definition. What needs to be proved here is that ~ is symmetric (x~y if and only if y~x), reflexive (x~x) and transitive (if x~y and y~z, then x~z).

Let me first finish what I started yesterday about this section of your post.

We want to prove that x~y $\leftrightarrow$ y~x.

Assume x~y.Our assumption implies that $x - y \in \{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.This means that the difference of value between $x$ and $y$ will always be a multiple of 3.This implies that $y - x \in \{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.This proves that x~y $\leftrightarrow$ y~x.

We will now attempt to prove that x~x.Let x be an arbitrary element of $\mathbb Z$.From the definition of ~ we know that x~x is possible if and only if $x - x \in \{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.Since we intuitively assume that we always get the integer 0 if we substract an integer to the same integer , then $\forall x \in \mathbb Z \ \ x - x = 0$ .Since 0 $\in \{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$ because of $3(0)=0$, it proves that x~x.

Next we want to prove that if x~y and y~z, then x~z.Let x,y,z be arbitrary elements of $\mathbb Z$.Assume x~y and y~z.From our assumption we know that $x - y \in \{s \in \mathbb Z | \exists t \in \mathbb Z \ \ 3t = s \ \}$ and that $y - z \in \{s \in \mathbb Z | \exists t \in \mathbb Z \ \ 3t = s \ \}$.This means that both x and y belongs to the same equivalence class , and that both y and z belongs to the same equivalence class.This implies that x belongs to the same equivalence class as z.This implies that if x~y and y~z, then x~z.

I had trouble especially with the last one.I got stuck in the middle of it and decided to use equivalence class , but I'm thinking it's not legit.

There are only three equivalence classes, [0],[1],[2]. Yes, 7 belongs to [7], but [7]=[1].

It's a good exercise to prove the following theorem: Let X be an arbitrary set, and let ~ be an arbitrary equivalence relation on X. For each x in X, define [x] by $[x]=\{y\in X:x\sim y\}$.

(a) For all $x,y\in X$, either $[x]\cap[y]=\varnothing$ or $[x]=[y]$.
(b) For all $x\in X$, there's a $y\in X$ such that $x\in[y]$.

This looks difficult.Let me give it a try:

(a) For all $x,y\in X$, either $[x]\cap[y]=\varnothing$ or $[x]=[y]$.

Let $x$ and $y$ be arbitrary elements of $X$.

From it's definition , we know that all elements of $[x]$ will result in multiples of 3 if we substract one element out of any other.Assume $[x]\cap[y]=\varnothing$.If $z \in [x]$ and $v \in [y]$ , then $z - v \notin \{s \in \mathbb Z | \exists t \in \mathbb Z \ \ 3t = s \ \}$ , and therefore they aren't in the same equivalence class.This implies that $[x] ≠ [y]$.

Now let's assume $[x] ≠ [y]$.This means that x and y arent in the same equivalence class.This means that if If $z \in [x]$ and $v \in [y]$ , then $z - v \notin \{s \in \mathbb Z | \exists t \in \mathbb Z \ \ 3t = s \ \}$.This implies that $[x]\cap[y]=\varnothing$.

This proves that $[x]\cap[y]=\varnothing \leftrightarrow [x] ≠ [y]$ and therefore that if $[x]\cap[y]=\varnothing$ , then $[x] = [y]$ is impossible , and if $[x] = [y]$ , then $[x]\cap[y]=\varnothing$ is impossible.

(b) For all $x\in X$, there's a $y\in X$ such that $x\in[y]$.

I'm really not sure how to prove that one since it's so obvious.I can try to use the reflexive argument:

Let $x$ and $y$ be arbitrary elements of $X$.We will attempt to prove that for all $x \in X$ , there's a $y \in X$ such that $x \in [y]$.We intuitively accept that for any $x \in X$ , $x - x = 0$ and that $0 \in \{s \in \mathbb Z | \exists t \in \mathbb Z \ \ 3t = s \ \}$.This proves that for all $x \in X$ , there's a $y \in X$ such that $x \in [y]$.

I will take a break to eat and come back after.

 

[Fredrik]

We want to prove that x~y $\leftrightarrow$ y~x.

Assume x~y.Our assumption implies that $x - y \in \{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.This means that the difference of value between $x$ and $y$ will always be a multiple of 3.This implies that $y - x \in \{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.This proves that x~y $\leftrightarrow$ y~x.

This is OK, but I think the best way to do it is the way I did it in my previous post. Here it is again:

Let $x,y\in\mathbb Z$ be abitrary. Suppose that x~y. By definition of ~, this implies that there's an integer z such that x-y=3z. Let z be such an integer. We have y-x=3(-z). Since -z is an integer, this implies that y~x.

We will now attempt to prove that x~x.Let x be an arbitrary element of $\mathbb Z$.From the definition of ~ we know that x~x is possible if and only if $x - x \in \{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$.Since we intuitively assume that we always get the integer 0 if we substract an integer to the same integer , then $\forall x \in \mathbb Z \ \ x - x = 0$ .Since 0 $\in \{z \in \mathbb Z | \exists w \in \mathbb Z \ \ 3w = z \ \}$ because of $3(0)=0$, it proves that x~x.

Don't mention intuition. That makes the proof look suspicious. The reason why x-x=0 for all x is that for all x, -x is defined to be the integer such that x-x=(-x)+x=0.

You're making it too complicated. This is all you need to say: Let $x\in\mathbb Z$ be arbitrary. We have x-x=0=0·3. Since $0\in\mathbb Z$, this implies that x~x.

Next we want to prove that if x~y and y~z, then x~z.Let x,y,z be arbitrary elements of $\mathbb Z$.Assume x~y and y~z.From our assumption we know that $x - y \in \{s \in \mathbb Z | \exists t \in \mathbb Z \ \ 3t = s \ \}$ and that $y - z \in \{s \in \mathbb Z | \exists t \in \mathbb Z \ \ 3t = s \ \}$. This means that both x and y belongs to the same equivalence class , and that both y and z belongs to the same equivalence class.This implies that x belongs to the same equivalence class as z.This implies that if x~y and y~z, then x~z.

I had trouble especially with the last one.I got stuck in the middle of it and decided to use equivalence class , but I'm thinking it's not legit.

This started out good, but you're right that you can't talk about equivalence classes here. That concept only makes sense when we're dealing with an equivalence relation, and we haven't proved that ~ is an equivalence relation. In fact, that's what we're trying to do right now.

After the assumption that x~y and y~z, I recommend that you continue like this: This implies that there are integers s,t such that x-y=3s and y-z=3t. Can you finish it from here?

(a) For all $x,y\in X$, either $[x]\cap[y]=\varnothing$ or $[x]=[y]$.

Let $x$ and $y$ be arbitrary elements of $X$.

From it's definition , we know that all elements of $[x]$ will result in multiples of 3 if we substract one element out of any other.

When I stated this theorem, I said that ~ is an arbitrary equivalence relation, not that it's specifically the "congruent modulo 3" relation. So you should only use that ~ is an equivalence relation. You shouldn't mention integers at all.

(b) For all $x\in X$, there's a $y\in X$ such that $x\in[y]$.

I'm really not sure how to prove that one since it's so obvious.

This is all you have to say: Let $x\in X$ be arbitrary. Since x~x, we have $x\in[x]$.

 

[reenmachine]

Don't mention intuition. That makes the proof look suspicious. The reason why x-x=0 for all x is that for all x, -x is defined to be the integer such that x-x=(-x)+x=0.You're making it too complicated. This is all you need to say: Let $x\in\mathbb Z$ be arbitrary. We have x-x=0=0·3. Since $0\in\mathbb Z$, this implies that x~x.

You see this is where I never know at which level of assumptions to stop.Here we pretty much assume any integer x minus x will equal to 0.Of course it's obvious , but I'm never sure if I have to prove it inside the other proof.

This started out good, but you're right that you can't talk about equivalence classes here. That concept only makes sense when we're dealing with an equivalence relation, and we haven't proved that ~ is an equivalence relation. In fact, that's what we're trying to do right now.

After the assumption that x~y and y~z, I recommend that you continue like this: This implies that there are integers s,t such that x-y=3s and y-z=3t. Can you finish it from here?

We want to prove that if x~y and y~z, then x~z.Assume x~y and y~z.This implies that there are integers $s,t$ such that $x-y=3s$ and $y-z=3t$.This implies that $x-3s=y$ and that $z+3t=y$.This implies that $x-3s=z+3t$.This implies that $x-z=3s+3t$.This implies that $x-z=3(t+s)$.This implies that there's an integer $w$ such that $t+s=w$.This implies that $x-z=3w$ and this proves that if x~y and y~z, then x~z.

When I stated this theorem, I said that ~ is an arbitrary equivalence relation, not that it's specifically the "congruent modulo 3" relation. So you should only use that ~ is an equivalence relation. You shouldn't mention integers at all.

(a) For all $x,y\in X$, either $[x]\cap[y]=\varnothing$ or $[x]=[y]$.

Suppose $[x]\cap[y]=\varnothing$.Our assumption implies that no elements of [x] is an element of [y] and vice versa.This implies that if $[x]\cap[y]=\varnothing$ , then $[x]≠[y]$.

Suppose $[x]≠[y]$.From the definition of [x] we know that all z in [x] has an equivalence relation with x.We also know that all v in [y] have an equivalence relation with y.From transitivity we know that all elements of one class has an equivalent relation with all elements of the same class.This implies that if $[x]≠[y]$ , then $[x]\cap[y]=\varnothing$.

This implies that $[x]\cap[y]=\varnothing \ \leftrightarrow \ [x]≠[y]$.This proves that for $x,y \in X$ , either $[x]\cap[y]=\varnothing$ or $[x]=[y]$.

Hmm that was kind of difficult to be honest.Maybe I just don't have it today :X.

Thanks a lot man! Will continue with your earlier post later again , thought I could finish it but I end up overthinking myself on each issue

edit: one last question , what happens if [∅] $\cap$ [∅] = ∅ and [∅] = [∅]? Is that even legit anyway?

 

[Fredrik]

You see this is where I never know at which level of assumptions to stop.Here we pretty much assume any integer x minus x will equal to 0.Of course it's obvious , but I'm never sure if I have to prove it inside the other proof.

Unfortunately, you won't really get past this issue until you have studied some abstract algebra. That's where you find out things like that -x is defined such that x-x=0.

We want to prove that if x~y and y~z, then x~z.Assume x~y and y~z.This implies that there are integers $s,t$ such that $x-y=3s$ and $y-z=3t$.This implies that $x-3s=y$ and that $z+3t=y$.This implies that $x-3s=z+3t$.This implies that $x-z=3s+3t$.This implies that $x-z=3(t+s)$.This implies that there's an integer $w$ such that $t+s=w$.This implies that $x-z=3w$ and this proves that if x~y and y~z, then x~z.

The statement that follows x-z=3(t+s) is a bit strange. The existence of an integer w such that t+s=w isn't an obvious consequence of x-z=3(t+s), unless we have already deduced that x~z. It would be more natural at this stage to just point out that t+s is an integer, since t and s are integers, and the sum of two integers is always an integer. If we combine this result with x-z=3(t+s), we see that x~z.

The middle part can be simplified a bit too. After the "...such that $x-y=3s$ and $y-z=3t$", I would just continue like this: This implies that $x-z=x-y+y-z=3s+3t=3(s+t)$. Since s+t is an integer, this implies that x~z.

(a) For all $x,y\in X$, either $[x]\cap[y]=\varnothing$ or $[x]=[y]$.

Suppose $[x]\cap[y]=\varnothing$.Our assumption implies that no elements of [x] is an element of [y] and vice versa.This implies that if $[x]\cap[y]=\varnothing$ , then $[x]≠[y]$.

...or that [x]=[y]=∅. So you also have to rule this out. I should probably have reversed the order of (a) and (b) in the statement of the theorem, because what is now part (b) immediately rules this out.

Suppose $[x]≠[y]$.From the definition of [x] we know that all z in [x] has an equivalence relation with x.We also know that all v in [y] have an equivalence relation with y.From transitivity we know that all elements of one class has an equivalent relation with all elements of the same class.This implies that if $[x]≠[y]$ , then $[x]\cap[y]=\varnothing$.

I don't understand this argument. Were you trying to do something like this?

Suppose that $[x]\neq[y]$. We will try to prove that $[x]\cap[y]=\varnothing$ by deriving a contradiction from the asumption that $[x]\cap[y]\neq\varnothing$. So suppose that $[x]\cap[y]\neq\varnothing$. Let $z\in[x]\cap[y]$ be arbitrary. Since $z\in[x]$, we have $z\sim x$. Since $z\in[y]$, we have $z\sim y$. Since ~ is symmetric and transitive, these results imply that $x\sim y$.

There's no obvious contradiction here, so I don't immediately see how to proceed.

Edit: I have thought about how to do this proof now. It seems easier to prove $[x]\cap[y]\neq\varnothing\Rightarrow[x]=[y]$ than to prove $[x]\neq [y]\Rightarrow[x]\cap[y]=\varnothing$. So I suggest that you do that instead. (Note that $p\Rightarrow q$ has the same truth table as $\lnot q\Rightarrow\lnot p$).

edit: one last question , what happens if [∅] $\cap$ [∅] = ∅ and [∅] = [∅]? Is that even legit anyway?

This can't happen, since no equivalence class is empty. If ~ is an equivalence relation on a set that has ∅ as an element, we would have $\varnothing\in[\varnothing]$ and therefore $[\varnothing]\neq\varnothing$.

 

[reenmachine]

Unfortunately, you won't really get past this issue until you have studied some abstract algebra. That's where you find out things like that -x is defined such that x-x=0.

Is it too early for me to learn that?

The statement that follows x-z=3(t+s) is a bit strange. The existence of an integer w such that t+s=w isn't an obvious consequence of x-z=3(t+s), unless we have already deduced that x~z. It would be more natural at this stage to just point out that t+s is an integer, since t and s are integers, and the sum of two integers is always an integer. If we combine this result with x-z=3(t+s), we see that x~z.

The middle part can be simplified a bit too. After the "...such that $x-y=3s$ and $y-z=3t$", I would just continue like this: This implies that $x-z=x-y+y-z=3s+3t=3(s+t)$. Since s+t is an integer, this implies that x~z.

I understand now where it didn't make sense.Thanks!

I don't understand this argument. Were you trying to do something like this?

Suppose that $[x]\neq[y]$. We will try to prove that $[x]\cap[y]=\varnothing$ by deriving a contradiction from the assumption that $[x]\cap[y]\neq\varnothing$. So suppose that $[x]\cap[y]\neq\varnothing$. Let $z\in[x]\cap[y]$ be arbitrary. Since $z\in[x]$, we have $z\sim x$. Since $z\in[y]$, we have $z\sim y$. Since ~ is symmetric and transitive, these results imply that $x\sim y$.

There's no obvious contradiction here, so I don't immediately see how to proceed.

Edit: I have thought about how to do this proof now. It seems easier to prove $[x]\cap[y]\neq\varnothing\Rightarrow[x]=[y]$ than to prove $[x]\neq [y]\Rightarrow[x]\cap[y]=\varnothing$. So I suggest that you do that instead. (Note that $p\Rightarrow q$ has the same truth table as $\lnot q\Rightarrow\lnot p$).

We will attempt to prove that for all $x,y \in X$ , either $[x] \cap [y] = \varnothing$ or $[x] = [y]$.

We want to prove that $[x]=[y]\rightarrow [x]\cap[y]≠\varnothing$.Assume $[x]=[y]$.Let $z \in [x]$ and $v \in [y]$ be arbitrary.We have $z \sim x$ , $v \sim y$.From our assumption we have that $x \sim y$.Since $\sim$ is symmetric and transitive , we have that $z \sim v$ and therefore that $z \sim y$ and $v \sim x$.This implies that $z \in [y]$ and that $v \in [x]$.This implies that $[x]=[y]\rightarrow [x]\cap[y]≠\varnothing$ and that $[x]\cap[y]=\varnothing\rightarrow [x]≠[y]$.

We now want to prove that $[x]\cap[y]\neq\varnothing\rightarrow[x]=[y]$.Suppose $[x]\cap[y]\neq\varnothing$.Let $z \in [x]\cap[y]$ be arbitrary.Here $z \in [x]$ implies that $z \sim x$ and $z \in [y]$ implies that $z \sim y$.Since $\sim$ is symmetric and transitive , we have $x \sim y$.This implies that $[x] = [y]$.This proves that $[x]\cap[y]\neq\varnothing\rightarrow[x]=[y]$ and that $[x]≠[y]\rightarrow [x]\cap[y] = \varnothing$.

The last two proofs above prove that $[x]=[y]\leftrightarrow [x]\cap[y]≠\varnothing$ and that $[x]≠[y]\leftrightarrow [x]\cap[y]=\varnothing$.This proves that for all $x,y \in X$ , either $[x] \cap [y] = \varnothing$ or $[x] = [y]$.

thoughts?

(My intuition is telling me that I didn't need to mention both $\leftrightarrow$ statements since one implies another , but it can't hurt I guess?)

This can't happen, since no equivalence class is empty. If ~ is an equivalence relation on a set that has ∅ as an element, we would have $\varnothing\in[\varnothing]$ and therefore $[\varnothing]\neq\varnothing$.

Thank you!

 

[Fredrik]

Is it too early for me to learn that?

I think you need a little bit more experience with proofs first. Not much more, but a little more.

We will attempt to prove that for all $x,y \in X$ , either $[x] \cap [y] = \varnothing$ or $[x] = [y]$.

We want to prove that $[x]=[y]\rightarrow [x]\cap[y]≠\varnothing$.Assume $[x]=[y]$.Let $z \in [x]$ and $v \in [y]$ be arbitrary.We have $z \sim x$ , $v \sim y$.From our assumption we have that $x \sim y$.

You could elaborate a bit here. The definition of [x] and the reflexivity of ~ imply that $x\in[x]$, and the assumption tells us that $[x]=[y]$. So $x\in[y]$. This implies that x~y.

Since $\sim$ is symmetric and transitive , we have that $z \sim v$ and therefore that $z \sim y$ and $v \sim x$.

This choice of words suggests that we need to use z~v to find z~y and v~x. We don't.

We know that z~x, v~y and x~y. Since ~ is symmetric and transitive, these three statements imply that z~v, z~y and v~x.

This implies that $z \in [y]$ and that $v \in [x]$.This implies that $[x]=[y]\rightarrow [x]\cap[y]≠\varnothing$

It doesn't imply the implication. What it implies (together with the assumptions $z\in[x]$ and $v\in[y]$) is that z and v are both elements of $[x]\cap[y]$. This implies that $[x]\cap[y]\neq\varnothing$. This completes the proof of the implication $[x]=[y]\rightarrow [x]\cap[y]≠\varnothing$, which is equivalent to $[x]\cap[y]=\varnothing\rightarrow [x]≠[y]$

The final step in a proof of an implication $p\to q$ doesn't imply $p\to q$. It just implies $q$, and completes the proof of the implication.

You proved that an arbitrary $z\in[x]$ and an arbitrary $v\in[y]$ are both in $[x]\cap[y]$. This is an unnecessarily complicated way to prove that $[x]\cap [y]\neq\varnothing$. All you had to do is to prove that there exists a w such that $w\in[x]\cap[y]$. So it's sufficient to (for example) prove that $x\in[x]\cap[y]$.

We now want to prove that $[x]\cap[y]\neq\varnothing\rightarrow[x]=[y]$.Suppose $[x]\cap[y]\neq\varnothing$.Let $z \in [x]\cap[y]$ be arbitrary.Here $z \in [x]$ implies that $z \sim x$ and $z \in [y]$ implies that $z \sim y$.Since $\sim$ is symmetric and transitive , we have $x \sim y$.This implies that $[x] = [y]$.

You're getting ahead of yourself here. How does that last statement follow from the one before it? (What is the method to prove an equality A=B, where A and B are sets?)

 

[reenmachine]

I think you need a little bit more experience with proofs first. Not much more, but a little more.

Cool , I should probably learn calculus before anyway.This is overdue.

You could elaborate a bit here. The definition of [x] and the reflexivity of ~ imply that $x\in[x]$, and the assumption tells us that $[x]=[y]$. So $x\in[y]$. This implies that x~y.

Hmm you see this is a part where I thought it was enough.So sometimes I say too many things , and sometimes I take some shortcuts.

This choice of words suggests that we need to use z~v to find z~y and v~x. We don't.

We know that z~x, v~y and x~y. Since ~ is symmetric and transitive, these three statements imply that z~v, z~y and v~x.

Understood.

It doesn't imply the implication. What it implies (together with the assumptions $z\in[x]$ and $v\in[y]$) is that z and v are both elements of $[x]\cap[y]$. This implies that $[x]\cap[y]\neq\varnothing$. This completes the proof of the implication $[x]=[y]\rightarrow [x]\cap[y]≠\varnothing$, which is equivalent to $[x]\cap[y]=\varnothing\rightarrow [x]≠[y]$

The final step in a proof of an implication $p\to q$ doesn't imply $p\to q$. It just implies $q$, and completes the proof of the implication.

I often make that mistake so that's good to know that the last statement should imply $q$.

You're getting ahead of yourself here. How does that last statement follow from the one before it? (What is the method to prove an equality A=B, where A and B are sets?)

I am? I thought if $x \sim y$ , then $[x]=[y]$.

On top of my head , the method of proving an equality is to prove that all elements of A are elements of B and that all elements of B are elements of A.

I thought $x \sim y$ implied that with $[x]$ and $[y]$.

How am I suppose to say that in this context? $x\sim y$ implies that $\forall x \in [x] \ \ x \in [y]$ and that $\forall y \in [y] \ \ y \in [x]$. This implies that $[x] = [y]$ ?

 

[Fredrik]

I am? I thought if $x \sim y$ , then $[x]=[y]$.

That statement is true, but we haven't proved it yet.

On top of my head , the method of proving an equality is to prove that all elements of A are elements of B and that all elements of B are elements of A.

Yes, that's what I had in mind.

How am I suppose to say that in this context? $x\sim y$ implies that $\forall x \in [x] \ \ x \in [y]$ and that $\forall y \in [y] \ \ y \in [x]$. This implies that $[x] = [y]$ ?

The notation $\forall x\in[x]$ is pretty bad. It only makes sense if it's interpreted as $\forall z\in[x]$. But yes, you could say that $x\sim y$ implies that $\forall z\in[x]~~z\in[y]$ (because z~x and x~y imply that z~y, which implies $z\in[y]$). But it's better to just start with "Let $z\in[x]$ be arbitrary". Then prove that $z\in[y]$. Since x and y are arbitrary, you don't even have to bother with what would normally be the second half of the equality proof, which would start with "Now let $z\in[y]$ be arbitrary." and end with $z\in[x]$.

 

[reenmachine]

The notation $\forall x\in[x]$ is pretty bad. It only makes sense if it's interpreted as $\forall z\in[x]$. But yes, you could say that $x\sim y$ implies that $\forall z\in[x]~~z\in[y]$ (because z~x and x~y imply that z~y, which implies $z\in[y]$). But it's better to just start with "Let $z\in[x]$ be arbitrary". Then prove that $z\in[y]$. Since x and y are arbitrary, you don't even have to bother with what would normally be the second half of the equality proof, which would start with "Now let $z\in[y]$ be arbitrary." and end with $z\in[x]$.

I'm not sure I get it , if I say that all $z \in [x]$ are $\in [y]$ , why is it proven that all $z \in [y]$ are $\in [x]$...

 

[Fredrik]

I'm not sure I get it , if I say that all $z \in [x]$ are $\in [y]$ , why is it proven that all $z \in [y]$ are $\in [x]$...

It's not. But we said more than that. Earlier in the proof, we declared x and y to be arbitrary elements of X such that $[x]\cap[y]\neq\varnothing$. $[x]\subseteq[y]$ doesn't imply $[y]\subseteq[x]$, but we haven't just proved $[x]\subseteq[y]$. We have proved
$$\forall x\forall y~\left([x]\cap[y]\neq\varnothing\to[x]\subseteq[y]\right).$$ x and y are dummy variables here, so this implies that $$\forall y\forall x~\left([y]\cap[x]\neq\varnothing\to[y]\subseteq[x]\right).$$ Since $[y]\cap[x]=[x]\cap[y]$ for all x and y, this implies that
$$\forall y\forall x~\left([x]\cap[y]\neq\varnothing\to[y]\subseteq[x]\right).$$ It's also pretty obvious that $\forall y\forall x$ can be replaced by $\forall x\forall y$ (I think this is an axiom of logic). So the above implies that
$$\forall x\forall y~\left([x]\cap[y]\neq\varnothing\to[y]\subseteq[x]\right).$$
This is not the sort of thing you would be expected to explain, since people with more experience of proofs will find it obvious. They don't immediately see this argument, but they realize that an argument like this can be made.

 

[reenmachine]

The notation $\forall x\in[x]$ is pretty bad. It only makes sense if it's interpreted as $\forall z\in[x]$. But yes, you could say that $x\sim y$ implies that $\forall z\in[x]~~z\in[y]$ (because z~x and x~y imply that z~y, which implies $z\in[y]$). But it's better to just start with "Let $z\in[x]$ be arbitrary". Then prove that $z\in[y]$. Since x and y are arbitrary, you don't even have to bother with what would normally be the second half of the equality proof, which would start with "Now let $z\in[y]$ be arbitrary." and end with $z\in[x]$.

Just to finish with this part of the proof...

We now want to prove that $[x]\cap[y]\neq\varnothing\rightarrow[x]=[y]$.Suppose $[x]\cap[y]\neq\varnothing$.Let $z \in [x]$ be arbitrary.This implies that $z \sim x$.From our assumption we know that $\exists m \in [y]$ such that $m \in [x]$.This implies that $m \sim x$ and $m \sim y$.Since $\sim$ is symmetric and transitive , we have that $x \sim y$ and $z \sim y$.This implies that $z \in [y]$.This implies that $[x] = [y]$.

thoughts on that?

thank you!

 

[reenmachine]

It's not. But we said more than that. Earlier in the proof, we declared x and y to be arbitrary elements of X such that $[x]\cap[y]\neq\varnothing$. $[x]\subseteq[y]$ doesn't imply $[y]\subseteq[x]$, but we haven't just proved $[x]\subseteq[y]$. We have proved
$$\forall x\forall y~\left([x]\cap[y]\neq\varnothing\to[x]\subseteq[y]\right).$$ x and y are dummy variables here, so this implies that $$\forall y\forall x~\left([y]\cap[x]\neq\varnothing\to[y]\subseteq[x]\right).$$ Since $[y]\cap[x]=[x]\cap[y]$ for all x and y, this implies that
$$\forall y\forall x~\left([x]\cap[y]\neq\varnothing\to[y]\subseteq[x]\right).$$ It's also pretty obvious that $\forall y\forall x$ can be replaced by $\forall x\forall y$ (I think this is an axiom of logic). So the above implies that
$$\forall x\forall y~\left([x]\cap[y]\neq\varnothing\to[y]\subseteq[x]\right).$$
This is not the sort of thing you would be expected to explain, since people with more experience of proofs will find it obvious. They don't immediately see this argument, but they realize that an argument like this can be made.

Very clear! Always good to read posts like this even as a reminder.

thank you!

 

[reenmachine]

To continue with post 681.

No, the relation partitions the set into equivalence classes. Then we focus on the set of equivalence classes $\mathbb Z/\!\sim\,=\{[0],[1],[3]\}$ instead. Since we just defined this set, there's no addition operation defined on it yet. So we define one like this: For all $n,m\in\{0,1,2\}$, we define [n+m] by $[n]+[m]=[n+m]$.

Did you meant 0,1,2 instead of 0,1,3 at the beginning of this part?

You say that you define an addition operation with $\forall n , m \in \{0,1,2\}$ we define [n+m] by $[n]+[m]=[n+m]$.

suppose [3]+[7]=[3+7]=[10].How did we define that [10]=[7]=[4]=[1] here? Is it with our already defined $\sim$?

For clearness here , can $\sim$ means different kind of equivalence relations?

We can define addition modulo 3 on the set S={0,1,2} by saying that n+m (where + denotes the operation we're trying to define) is the unique k in S such that [k]=[n+m] (where + denotes the usual addition operation on the integers).

You say n+m is the unique k in S.This confuses me because 3+4 (with + being unknown) would be the unique k in S such that [k]=[7] since the second + means addition.How is there any 7 in k? Yes I understand that [1]=[7] because [1] = $\{...-2,1,4,7,10...\}$ , but I don't understand how our definition of this whole thing implied that you had to make a connection between the three sets of integers that gives multiple of 3 if you substract one to another and equivalence class such as [1].

We have found a "thing" that, except for notation, is "just like" some other thing. There are some fancy mathematical terms for this. You don't have to learn them now, but I guess it can't hurt if I mention them. The "things" we're working with here are called groups, and the technical way to say that the first one is "just like" the other one is to say that these groups are isomorphic.

Very interesting.I guess isomorphic groups are part of the beauty of math :D

It follows from the definitions of [n] and ~. [4] is the set of all integers that differ from 4 by an integer multiple of 3. [1] is the set of all integers that differ from 1 by an integer multiple of 3. It's pretty obvious that they are the same, and it's easy to prove it.

This part might answer some of my previous questions , but I'm not sure.So the definition of $\sim$ is one of the first assumptions we have in all of this right?

thank you once again man!

 

[Fredrik]

We now want to prove that $[x]\cap[y]\neq\varnothing\rightarrow[x]=[y]$.Suppose $[x]\cap[y]\neq\varnothing$.Let $z \in [x]$ be arbitrary.This implies that $z \sim x$.From our assumption we know that $\exists m \in [y]$ such that $m \in [x]$.This implies that $m \sim x$ and $m \sim y$.Since $\sim$ is symmetric and transitive , we have that $x \sim y$ and $z \sim y$.This implies that $z \in [y]$.This implies that $[x] = [y]$.

Looks good. I know I said that you don't have to explain why it's sufficient to prove $[x]\subseteq[y]$, but you should mention that it's sufficient, so that your readers know that this is the argument you're making. So the final sentence should be replaced with something like this: This implies that $[x]\subseteq [y]$. Since x and y are arbitrary elements of X such that $[x]\cap[y]\neq\varnothing$, it also follows that $[y]\subseteq [x]$, and therefore that $[x]=[y]$.

Alternatively: This implies that $[x]\subseteq [y]$. Similarly, we can prove that $[y]\subseteq [x]$. These results imply that $[x]=[y]$.

That "similarly" comment should be enough to get the reader to look at what you just did and notice that the proof still holds if we swap x and y.

 

[Fredrik]

Did you meant 0,1,2 instead of 0,1,3 at the beginning of this part?

Yes. (How did I manage to type a 3 there? )

You say that you define an addition operation with $\forall n , m \in \{0,1,2\}$ we define [n+m] by $[n]+[m]=[n+m]$.

I meant to say that we define [n]+[m] this way. [n+m] is already defined, and we're using that to define [n]+[m].

suppose [3]+[7]=[3+7]=[10].How did we define that [10]=[7]=[4]=[1] here? Is it with our already defined $\sim$?

For clearness here , can $\sim$ means different kind of equivalence relations?

All of this is with ~ meaning "is congruent modulo 3". To see that [10]=[1] for example, let $n\in[10]$ be arbitrary. Let m be an integer such that n-10=3m. We have n-1 = n-10+9 = 3m+3·3 = 3(m+3). Since m+3 is an integer, this implies that n~1. This implies that $n\in[1]$. And we can prove that every element of [1] is an element of [10] in a similar way.

You say n+m is the unique k in S.This confuses me because 3+4 (with + being unknown) would be the unique k in S such that [k]=[7] since the second + means addition.How is there any 7 in k? Yes I understand that [1]=[7] because [1] = $\{...-2,1,4,7,10...\}$ ,

First of all, I should mention again that this is an unnecessarily complicated way to define addition modulo 3 on S. This stuff with equivalence classes is a good way to define the other group {[0],[1],[2]}, which is isomorphic to S. But it's certainly not necessary to use that group to define the addition operation on S. I'm saying that we can do it this way, not that it's one of the easier ways.

Now, regarding what I said about how to do it. I said that for all n,m in S, we define n+m (where + is the addition operation we're trying to define) as the unique k in S such that [k]=[n+m] (where + is the usual addition operation on the integers). Since neither 3 nor 4 is in S, this does not define 3+4. It does however define 2+1 for example. 2+1 is the unique k in S such that [k]=[2+1]=[3]. Since [0]=[3], [1]≠[3] and [2]≠[3], that k is 0. So the definition tells us that 2+1=0.

This part might answer some of my previous questions , but I'm not sure.So the definition of $\sim$ is one of the first assumptions we have in all of this right?

It does, and yes it is.

 

[reenmachine]

Looks good. I know I said that you don't have to explain why it's sufficient to prove $[x]\subseteq[y]$, but you should mention that it's sufficient, so that your readers know that this is the argument you're making. So the final sentence should be replaced with something like this: This implies that $[x]\subseteq [y]$. Since x and y are arbitrary elements of X such that $[x]\cap[y]\neq\varnothing$, it also follows that $[y]\subseteq [x]$, and therefore that $[x]=[y]$.

Alternatively: This implies that $[x]\subseteq [y]$. Similarly, we can prove that $[y]\subseteq [x]$. These results imply that $[x]=[y]$.

That "similarly" comment should be enough to get the reader to look at what you just did and notice that the proof still holds if we swap x and y.

Ok understood.So while I don't have to completely write the proof in both directions (in 2 paragraphs) because the dummy variables are interchangeable , it's good to remind it to the reader.

Just a curiosity question , when you are reaching the level where only good mathematicians will be able to read your proofs , is those kind of "reminders" necessary?

 

[Fredrik]

Just a curiosity question , when you are reaching the level where only good mathematicians will be able to read your proofs , is those kind of "reminders" necessary?

They're probably not necessary then, but I think it's never a bad idea to include them.

 

[reenmachine]

I meant to say that we define [n]+[m] this way. [n+m] is already defined, and we're using that to define [n]+[m].

Understood.

All of this is with ~ meaning "is congruent modulo 3". To see that [10]=[1] for example, let $n\in[10]$ be arbitrary. Let m be an integer such that n-10=3m. We have n-1 = n-10+9 = 3m+3·3 = 3(m+3). Since m+3 is an integer, this implies that n~1. This implies that $n\in[1]$. And we can prove that every element of [1] is an element of [10] in a similar way.

That's awesome.

It seems my doubts about when to assume the definition of $\sim$ was a recurrent problem so I'm glad to understand it now.

Now, regarding what I said about how to do it. I said that for all n,m in S, we define n+m (where + is the addition operation we're trying to define) as the unique k in S such that [k]=[n+m] (where + is the usual addition operation on the integers). Since neither 3 nor 4 is in S, this does not define 3+4. It does however define 2+1 for example. 2+1 is the unique k in S such that [k]=[2+1]=[3]. Since [0]=[3], [1]≠[3] and [2]≠[3], that k is 0. So the definition tells us that 2+1=0.

Ok ok ok , so we use the equivalent classes to single out which $k \in S$ will have a $\sim$ with the integer n+m.

So if [2+2]=[4] , then by using the definition of the equivalence class we know that [4] = [1].So $1=k$.

thank you!

 

[Dmobb Jr.]

Yes it is important to write a lot of proofs for proactice. It is also, important, however to read a lot of proofs. Go to the library (preferably of a college if you can) and check out a book on algebra or set theory (or anything else). Just reading the proofs in the book will teach you farely well.

Edit: Did not reallize there was another 41 pages that I did not read so sorry if this is totally off topic.

 

[reenmachine]

Couples of comments about lists.

"Elements" of lists are called entries.List , contrary to sets , have to be in a particular order and can have repeated entries (if repetition is allowed).

If we have to create a length 3 list from the set $\{1,2,3,4\}$ with repetitions allowed , then to calculate the number of possible lists we just do $4(4)(4) = 64$.If repetition aren't allowed , then we do $4(3)(2) = 24$.If we want to know the number of possible lists containing a single 3 with repetition NOT allowed , then we do $3(2)(3)=18$ the last $(3)$ being the number of spots 3 can have in the order.If we want to know how many lists you can create using 1 (with repetition allowed) , then you calculate the number of list without 1 with $3(3)(3) =27$ and you subtract that result from all possible list $4(4)(4)=64$ , so $64-27=37$.So 37 possible lists using 1 as an entry.

Does that sound about right?

thank you!

 

[Fredrik]

Sounds good to me.

 

[reenmachine]

Sounds good to me.

Thank you!