, iff and differ in finitely many digits. (So for example but ). Then this equivalent relation partitions into different equivalent classes. How many equivalent classes there are?

Printable View

- June 26th 2011, 09:12 AMgodelproofHow many equivalent classes there are?
, iff and differ in finitely many digits. (So for example but ). Then this equivalent relation partitions into different equivalent classes. How many equivalent classes there are?

- June 26th 2011, 12:01 PMFernandoRevillaRe: How many equivalent classes there are?
- June 26th 2011, 07:53 PMgodelproofRe: How many equivalent classes there are?
Thanks for the reply. I knew that. But by my definition . What you have is ,

**NOT**. I don't really see anything inconsistent with the definition...

---------------------------------------------

Well, maybe I was wrong and it IS ill-defined (but I'd like to know why?). If that is the case, let me define it this way: , iff and differ in finitely many digits or a (b) ends in ...999... and b (a) ends in ...000...

-----------------------------------------------

I'd like to hear your opinion. Thanks in advance(Happy)

Edit: Red. sorry for that conspicuous mistake. Corrected in red. - June 26th 2011, 10:41 PMFernandoRevillaRe: How many equivalent classes there are?
- June 26th 2011, 10:42 PMTravellerRe: How many equivalent classes there are?
Try to show that each class contains countably many elements.

- June 26th 2011, 11:17 PMgodelproofRe: How many equivalent classes there are?
- June 26th 2011, 11:38 PMFernandoRevillaRe: How many equivalent classes there are?
I have explained it. The relation is ill defined in . You can define a well defined equivalence relation in in the following way: iff except for a finite number of terms. I suppose this is what you meant. If you have seen the problem in a book, please transcribe it.

- June 27th 2011, 01:58 AMgodelproofRe: How many equivalent classes there are?
Let me use FernandoRevilla's definition in #7. Please check if there's any problem with the following proofs:

**1.**Any equivalent class contains countable elements.

Proof: Let be the set of all equivalent classes of in #7. Choose any and .

and such that . Hence , where and for . Since was arbitary, we have . Since is countable for any , we proved that is countable.

Q.E.D.

-------------------------------------------------------------------------------

**2.**.

Proof:

(1) If , then E contains finite elements . Now because S is uncountable and , some must contain uncountably many elements, i.e., for some i. Contradiction to proof in 1.

(2) If , then . Define , where for all i. Now we derive a contradiction by constructing but , as follows:

define , then clearly is a**bijection**from to . Construct y by choosing for and (Or by the Cantor's diagonal method, if you prefer). Clearly , . Which is a contradiction. Q.E.D.

------------------------------------------------------------------------------

**3.**

Proof: Choose from each element of an . Let the set of all such x's be . Clearly . But . Hence . Hence . Q.E.D.

-------------------------------------------

Edit: all is replaced by - June 27th 2011, 02:04 AMgodelproofRe: How many equivalent classes there are?
It is easy to see that , so:

is all we can say about ?

Can we show that ,**without assuming ?**

----------------------------------------

Edit: Bold font - June 27th 2011, 03:21 AMFernandoRevillaRe: How many equivalent classes there are?
- June 27th 2011, 04:30 AMemakarovRe: How many equivalent classes there are?
In case this is still not clear: If two objects are equal, then one of them can be replaced by the other

*in any proposition*without changing the truth value of this proposition. (Sometimes this is even taken as the definition of equality.) So here we have

1 ~ 1 (*)

and 1 = 0.999... Replacing the second occurrence 1 in (*) by an equal object 0.999... we get

1 ~ 0.999...

which is false, unlike (*).

Ill-defined definitions typically happen when they involve choosing a representative. Some rational numbers have two decimal expansions, and choosing one or the other gives different results with respect to ~; hence ~ is ill-defined.

I agree with Fernando that considering instead of is probably the most reasonable approach here. - June 27th 2011, 04:38 AMgodelproofRe: How many equivalent classes there are?
- June 27th 2011, 09:14 PMgodelproofRe: How many equivalent classes there are?
- June 27th 2011, 11:46 PMFernandoRevillaRe: How many equivalent classes there are?
- June 28th 2011, 12:34 AMgodelproofRe: How many equivalent classes there are?