The Student Room Group

Infinite Sets and Equivalence Relations

Firstly:

Show that the set S of square numbers is infinite:

S={n(element)N(naturals) : There exists m(element)N(naturals) such that m=n^2}

I know how to prove that the Naturals are infinite which relies on the pigeonhole principle but I don't know where to begin here.

And:

Is the following relation ~ an equivalence relation on set X.

X=Z(integers), and x~y if xy=1

I can see that the only possibility is x=y=1 or x=y=-1

I also know in order to show equivalence relations you need to show reflexivity, symmetry and transitivity.

The relation is reflexive since x~x means x*x=1 (x=1 or x=-1)
The relation is symmetric since x~y means xy=1 and y~x means yx=1 (x=y=1 or x=y=-1)
The relation is transitive since a~b and b~c then a~c. a~b means ab=1 and b~c means bc=1 so a/c=1 but (a=b=c=1 or a=b=c=-1 so a/c=1 is the same as ac=1 so a~c).

I don't know whether the above reasoning is correct or not since it is only possible for all variables to have the same value of 1 or -1....

Any help would be much appreciated!
Original post by randlemcmurphy
Firstly:

Show that the set S of square numbers is infinite:

S={n(element)N(naturals) : There exists m(element)N(naturals) such that m=n^2}

I know how to prove that the Naturals are infinite which relies on the pigeonhole principle but I don't know where to begin here.



Couple of thoughts: Either create a bijection between the set of natural numbers and the squares. This shows they have the same cardinality.

Or assume the set is finite, so has a largest element, now construct a bigger one, creating a contradiction.



And:

Is the following relation ~ an equivalence relation on set X.

X=Z(integers), and x~y if xy=1

I can see that the only possibility is x=y=1 or x=y=-1

I also know in order to show equivalence relations you need to show reflexivity, symmetry and transitivity.

The relation is reflexive since x~x means x*x=1 (x=1 or x=-1)
The relation is symmetric since x~y means xy=1 and y~x means yx=1 (x=y=1 or x=y=-1)
The relation is transitive since a~b and b~c then a~c. a~b means ab=1 and b~c means bc=1 so a/c=1 but (a=b=c=1 or a=b=c=-1 so a/c=1 is the same as ac=1 so a~c).

I don't know whether the above reasoning is correct or not since it is only possible for all variables to have the same value of 1 or -1....

Any help would be much appreciated!


The reflexive property says x~x for all x in X. Is this true?

PS: Do post in the maths forum in future, rather than this umbrella forum. Not many people look here.
Reply 2
Original post by randlemcmurphy
Firstly:

Show that the set S of square numbers is infinite:

S={n(element)N(naturals) : There exists m(element)N(naturals) such that m=n^2}

I know how to prove that the Naturals are infinite which relies on the pigeonhole principle but I don't know where to begin here.


As ghostwalker says, constructing a bijection from the natural numbers to the squares is a nice way, although a slightly slicker method would be to observe that it is sufficient to show there is an injection from N\mathbb{N} (or in fact any countably infinite set - take your pick) to the set SS.

Quick Reply

Latest

Trending

Trending