x Turn on thread page Beta
 You are Here: Home

# Infinite Sets and Equivalence Relations watch

Announcements
1. 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!
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.

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.
3. (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 (or in fact any countably infinite set - take your pick) to the set .

TSR Support Team

We have a brilliant team of more than 60 Support Team members looking after discussions on The Student Room, helping to make it a fun, safe and useful place to hang out.

This forum is supported by:
Updated: November 8, 2015
Today on TSR

### University rankings 2019

Cambridge at number one

### I have imposter syndrome at Cambridge

Poll
Useful resources

The Student Room, Get Revising and Marked by Teachers are trading names of The Student Room Group Ltd.

Register Number: 04666380 (England and Wales), VAT No. 806 8067 22 Registered Office: International House, Queens Road, Brighton, BN1 3XE