Hey there! Sign in to join this conversationNew here? Join for free
x Turn on thread page Beta

Infinite Sets and Equivalence Relations watch

Announcements
    • Thread Starter
    Offline

    10
    ReputationRep:
    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!
    • Study Helper
    Offline

    15
    Study Helper
    (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.
    Offline

    11
    ReputationRep:
    (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 \mathbb{N} (or in fact any countably infinite set - take your pick) to the set S.
 
 
 
Poll
Do you like carrot cake?

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

Write a reply...
Reply
Hide
Reputation gems: You get these gems as you gain rep from other members for making good contributions and giving helpful advice.