What Are the Equivalence Classes of the Smallest Relation Containing R?

[jacktsoi]

Homework Statement

Let R denote the following relation in the set N of natural numbers:
R = {(x, y) | x = 2y}.
Let E be the “smallest” equivalence relation containing R. Give a complete description of the equivalence classes of E.

How can I describe it containing infinite set?

Homework Equations

[An example of smallest equivalence relation can be given as follows::
Let S = {a, b, c, d} and R = {(a, b), (b, c)}, the smallest equivalence relation containing R is {(a, a), (b, b), (c, c), (d, d), (a, b), (b, a), (a, c), (b, c), (c, a), (c, b)}. ]

The Attempt at a Solution

 

[LCKurtz]

Well, you know you need all pairs (a,a) for reflexivity and all pairs (2a,b) and (a,2b) for symmetry. So the question becomes if you do have all those, is that enough to get transitivity or do you need more?

 

[Mene]

In this homework problem, we are given a relation R in the set of natural numbers N, where R is defined as {(x, y) | x = 2y}. This means that for any pair of numbers (x, y) in R, the first number is always twice the second number. For example, (4, 2) and (10, 5) are both in R because 4 = 2*2 and 10 = 2*5. However, (3, 5) is not in R because 3 is not twice 5.

Next, we are asked to find the smallest equivalence relation E containing R. An equivalence relation is a relation that is reflexive, symmetric, and transitive. This means that for any element a in a set, (a, a) must be in the relation, for any elements a and b in the set, (a, b) and (b, a) must be in the relation, and for any elements a, b, and c in the set, if (a, b) and (b, c) are in the relation, then (a, c) must also be in the relation.

In the given example, the smallest equivalence relation E containing R is {(x, y) | x = y}. This is because it satisfies all three properties of an equivalence relation. For any number x in N, (x, x) is in E, satisfying reflexivity. For any numbers x and y in N, if (x, y) is in E, then (y, x) is also in E, satisfying symmetry. And for any numbers x, y, and z in N, if (x, y) and (y, z) are in E, then (x, z) is also in E, satisfying transitivity.

Now, to describe the equivalence classes of E, we can think of them as sets of numbers that are equivalent to each other under the relation E. In other words, for any element x in N, the equivalence class [x] is the set of all numbers y in N such that (x, y) is in E. In this case, since E is defined as {(x, y) | x = y}, the equivalence classes are simply singletons, or sets containing only one element. For example, the equivalence class [2] would contain only the number 2, as it is the