Question about proof from a guy with a highschool education

[micromass]

To contrast (15), take a look at

\{6x + 2y~\vert~x,y\in \mathbb{Z}\}

This will not equal $\mathbb{Z}$. Do you see which set it will equal instead?

Questions of these kind are solved in abstract algebra. In particuler, the relevant result here is Bezout's theorem which states when

\mathbb{Z}~=~\{ax+by~\vert~x,y\in \mathbb{Z}\}

and what exactly the correct set is if the equality doesn't hold.

 

[reenmachine]

To contrast (15), take a look at

\{6x + 2y~\vert~x\in \mathbb{Z}\}

This will not equal $\mathbb{Z}$. Do you see which set it will equal instead?

ℝ? Because y could be an irrational number?

Questions of these kind are solved in abstract algebra. In particuler, the relevant result here is Bezout's theorem which states when

\mathbb{Z}~=~\{ax+b~\vert~x,y\in \mathbb{Z}\}

and what exactly the correct set is if the equality doesn't hold.

Not sure I understand this part , what is the y doing there?

 

[micromass]

Sorry, typos corrected now.

 

[reenmachine]

\mathbb{Z}~=~\{ax+by~\vert~x,y\in \mathbb{Z}\}

Still not sure I understand.

If a and b are ${\sqrt{2}}$ and x and y are 2 , then it gives us 2.828... + 2.828... = 5.657... which would mean that the set would be ℝ no?

 

[reenmachine]

15.

As I said before, it's the set of all 5a+2b such that a and b are integers. It's pretty obvious that this is the set of all integers, $\mathbb Z$, as you have now concluded. (Edit: Ohh...after reading micromass' reply below, I see it's not as obvious as I thought. It's only obvious that this set will be a subset of $\mathbb Z$). If you want to prove that this "guess" is correct, you need to rely on the axiom that says that two sets are equal if and only if they have the same elements. Define $Z=\{5a+2b\,|\,a,b\in\mathbb Z\}$. We want to prove that $Z=\mathbb Z$.

Let $x\in Z$ be arbitrary. The definition of Z tells us that there exist $a,b\in\mathbb Z$ such that $5a+2b=x$. Since $\mathbb Z$ is closed under addition and multiplication, this implies that $x\in\mathbb Z$.

Let $x\in\mathbb Z$ be arbitrary. Define $a,b\in\mathbb Z$ by $a=x$ and $b=-2x$. We have $a,b\in\mathbb Z$ and $5a+2b=5x+2(-2x)=5x-4x=x$. This implies that $x\in Z$.

wow this is great! Can you elaborate a little bit on what you mean with '' Since $\mathbb Z$ is closed under addition and multiplication, this implies that $x\in\mathbb Z$ ''.

21. Note that your result can be simplified to $\left\{n^2\,|\,n\in\mathbb N\right\}$. The proof of that is similar to the proof of 15. (Most people use n and m for integers rather than x and y, but it's not necessary to do this. n is a dummy variable here, so you can use x instead).
.

Is it important to simplify it?

thanks Fredrik!

Congratulations on becoming a mentor , well deserved promotion!

 

[Fredrik]

Still not sure I understand.

I think micromass is talking about the following issue: For what integer values of a,b is $\left\{ax+by\,|\,x,y\in\mathbb Z\right\}=\mathbb Z$?

Edit: Problem 15 says that this equality holds when a=5 and b=2. micromass says that it doesn't hold when a=6 and b=2. (Note that when we write the set this way, the dummy variables corresponding to a and b in problem 15 are x and y, not a and b).

Can you elaborate a little bit on what you mean with '' Since $\mathbb Z$ is closed under addition and multiplication, this implies that $x\in\mathbb Z$ ''.

Suppose that X is a set on which an addition operation is defined. A subset $S\subseteq X$ is said to be closed under addition if for all $x,y\in S$, we have $x+y\in S$.

"Closed under multiplication" is defined similarly.

Is it important to simplify it?

Not really. But it's important to know that it can be simplified, because you may encounter the other way of writing the set, and when you do, you need to be able to recognize it as the same set.

Congratulations on becoming a mentor , well deserved promotion!

Thank you.

 

[CompuChip]

As an example, the set of even numbers is closed under addition (because the sum of two even numbers is even), but the set of odd numbers is not - any two numbers will provide a counterexample.

The set of all integers except 0 is closed under multiplication, but the set of all integers except 1 is not (do you see why?).

 

[CompuChip]

thanks Fredrik!

Congratulations on becoming a mentor , well deserved promotion!

Congratulations! Do you get the extended Christmas pack now? ;)

 

[Fredrik]

The set of all integers except 0 is closed under multiplication, but the set of all integers except 1 is not (do you see why?).

Edit: What I said here is wrong. See the two posts below this one.

I think you must have meant to say something other than you did in that last example. For all $n,m\in\mathbb Z-\{1\}$, we have $nm\in\mathbb Z$ and it's impossible that nm=1, because this equality is false if one of n and m is 0, and implies n=1/m or m=1/n otherwise.

So $\mathbb Z-\{1\}$ is closed under multiplication (←Wrong.), but $\mathbb Q-\{1\}$ and $\mathbb R-\{1\}$ are not. Also, $\mathbb Z-\{1\}$ is not closed under addition. Maybe that's what you had in mind.

Congratulations! Do you get the extended Christmas pack now? ;)

Thanks. It doesn't have a lot of benefits I'm afraid.

 

[micromass]

I think you must have meant to say something other than you did in that last example. For all $n,m\in\mathbb Z-\{1\}$, we have $nm\in\mathbb Z$ and it's impossible that nm=1, because this equality is false if one of n and m is 0, and implies n=1/m or m=1/n otherwise.

What about $n=m=-1$?

(Feel free to delete this post if you'll delete your comment)

 

[Fredrik]

What about $n=m=-1$?

(Feel free to delete this post if you'll delete your comment)

Lol. No, I'm not going to delete a post just to cover up how dumb I can be sometimes.

(But I have added a comment to the post where I made that silly mistake).

 

[reenmachine]

To contrast (15), take a look at

\{6x + 2y~\vert~x,y\in \mathbb{Z}\}

This will not equal $\mathbb{Z}$. Do you see which set it will equal instead?

Questions of these kind are solved in abstract algebra. In particuler, the relevant result here is Bezout's theorem which states when

\mathbb{Z}~=~\{ax+by~\vert~x,y\in \mathbb{Z}\}

and what exactly the correct set is if the equality doesn't hold.

I just woke up and I think I know why now , \{6x + 2y~\vert~x,y\in \mathbb{Z}\} can't be the set Z because both multiplications will always result in even numbers , which means the addition will always be an even number as well.

So this would be the set of all even integers.

Let's try it out with all possibilities.

6(3)+2(-2) = 14 odd/even
6(2)+2(5) = 22 even/odd
6(-2)+2(4) = -4 even/even
6(5)+2(-7) = 16 odd/odd

The result is always even.

For the set to be Z , we would need an odd number to be able to multiply it by another odd number like for example 7(7) = 49 + 2(2) = 53

 

[CompuChip]

Correct!

Just to test your intuition, what do you think
\{ 6x + 9z \mid x, y \in \mathbb{Z} \}
will be?

 

[reenmachine]

Correct!

Just to test your intuition, what do you think
\{ 6x + 9z \mid x, y \in \mathbb{Z} \}
will be?

as I mentionned at the end of the post , this will be Z because there's an even and odd number.If you replaced the 9 with a 8 , it would be the set of all even integers.

If both would be odd , it would still be Z.

 

[micromass]

as I mentionned at the end of the post , this will be Z because there's an even and odd number.

But the number is always divisible by 3! (! is not a factorial here)

 

[reenmachine]

But the number is always divisible by 3! (! is not a factorial here)

what does it change? what role does division play in that situation?

 

[Number Nine]

as I mentionned at the end of the post , this will be Z because there's an even and odd number.If you replaced the 9 with a 8 , it would be the set of all even integers.

If both would be odd , it would still be Z.

Would a and b not have to be relatively prime? It seems to me that any linear combination of 6 and 9 would get you a multiple of 3.

 

[reenmachine]

okay you got me , give me a chance I just woke up from a pretty rough night

the set would be ( w in Z : there's exist a v in Z such that w = v/3 ) ?

not sure that even works for all , have to verify

 

[Number Nine]

Any pair of relatively prime integers a and b would do it. We know that there is a linear combination

ax + by = 1

But then we have

n(ax + by) = (nx)a + (ny)b = n

So we can express any integer as a linear combination of a and b.

 

[CompuChip]

Yep. You probably don't know what "relatively prime" means (yet), but that's the official term.
The trick is, if you look at the earlier example with a = 5, b = 2, that you can write 1 = 5 - 2 * 2.
So you can write any number n as $n(5 - 2 \cdot 2) = 5n + 2(n - 2)$, i.e. as 5x + 2y with x = n and y = n - 2.
It doesn't work for 4 and 2 or for 6 and 9, because you can't write 1 as 4x + 2y or 6x + 9y, so you can only get multiples of 2 and 3, respectively.

This is what Number Nine tries to tell you in more general terms.

 

[reenmachine]

Another try:

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

I have a feeling this is correct.

 

[Number Nine]

Another try:

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

I have a feeling this is correct.

This would give you the set of all multiples of 3.

 

[reenmachine]

This would give you the set of all multiples of 3.

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

 

[reenmachine]

But in that case isn't it the set R? If x=0 and z=1/9 then 6(0)+9(1/9)=1 and you can generate any number in theory no?

 

[Number Nine]

But in that case isn't it the set R? If x=0 and z=1/9 then 6(0)+9(1/9)=1 and you can generate any number in theory no?

You specified that both x and y are integers, in which case you would only have multiples of 3.

 

[reenmachine]

You specified that both x and y are integers, in which case you would only have multiples of 3.

The exemple was \{ 6x + 9z \mid x, y \in \mathbb{Z} \} in which I confused the z with the y.

If z was replaced by y on the left side (like below), I think every elements of that set would be multiples of 3.Am I wrong?

\{ 6x + 9y \mid x, y \in \mathbb{Z} \}

 

[reenmachine]

Suppose that X is a set on which an addition operation is defined. A subset $S\subseteq X$ is said to be closed under addition if for all $x,y\in S$, we have $x+y\in S$.

"Closed under multiplication" is defined similarly.

Very clear thank you!

 

[reenmachine]

I need to be reminded of something , looking at page 24-25 in the book of proof : http://www.people.vcu.edu/~rhammack/BookOfProof/Sets.pdf

why does i=1 below the notations?

 

[Fredrik]

I need to be reminded of something , looking at page 24-25 in the book of proof : http://www.people.vcu.edu/~rhammack/BookOfProof/Sets.pdf

why does i=1 below the notations?

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

 

[Fredrik]

By the way, the sigma notation for sums can be defined recursively.

For all $n\in\mathbb Z$, we define
$$\sum_{i=n}^n x_i=x_n.$$ For all $n,m\in\mathbb Z$ such that $m>n$, we define
$$\sum_{i=n}^m x_i =\left(\sum_{i=n}^{m-1}x_i\right)+x_m.$$ It's not essential that you understand this now, but you will have to get used to recursive definitions at some point.

Another example (of recursion): For each $n\in\mathbb N$ (where this $\mathbb N$ is defined to include 0), we define $n!$ by
$$n!=
\begin{cases}1 &\text {if }n=0\\
n(n-1)! &\text{if }n>0.
\end{cases}
$$ This definition implies e.g. that
$$5!=5(4!)=5(4(3!))=\cdots =5(4(3(2(1(0!))))) =5\cdot 4\cdot 3\cdot 2\cdot 1.$$