# equivalence relation證明題

1. Let F be the set of total functions of the form f: {0,1} -> N( functions that map from {0,1} to the natural numbers ). Is the set of such functions countable or uncountable ? Prove your answer.

2. Prove that the binary relation on sets defined by X ≡ Y, if and only if, card(X) = card(Y) is an equivalence relation.

Rating
• Jacob
Lv 6

1. F is countable.

Since f: {0, 1}→N, every f can have at most 2 different values.

i.e. every f is such that f(0)=p, f(1)=q for all p, q in N.

Now we denote the function f where f(0)=p and f(1)=q by [p, q].

then we can arrange them in this form:

[1, 1], [1, 2], [1, 3], [1, 4], ...

[2, 1], [2, 2], [2, 3], [2, 4], ...

[3, 1], [3, 2], [3, 3], [3, 4], ...

[4, 1], [4, 2], [4, 3], [4, 4], ...

...

which is countable just like the rational number Q.

In fact, card(F)=card(N*N)=card(Q), which is countable.

2. You need to prove 3 things:

(1) X≡X

(2) If X≡Y, then Y≡X

(3) If X≡Y and Y≡Z, then X≡Z

where X≡Y if and only if card(X)=card(Y).

(1) Define i: X→X by the identity map i(x)=x,

then clearly i is bijective and so card(X)=card(X).

i.e. X≡X

(2) If X≡Y, then card(X)=card(Y),

thus there is a bijective mapping f: X→Y.

But then f^-1: Y→X is also a bijective mapping,

which maps Y into X, and so card(Y)=card(X).

i.e. Y≡X

(3) If X≡Y and Y≡Z, then card(X)=card(Y) and card(Y)=card(Z),

thus there are two bijective mappings f: X→Y and g: Y→Z.

Now consider the composite mappings g。f: X→Z,

this mapping is also bijective since both f, g are so.

Therefore card(X)=card(Z) and hence X≡Z.

2009-01-31 09:07:43 補充：

Hence, ≡ is an equivalence relation.

Source(s): ME