小邱 asked in 科學數學 · 1 decade ago

equivalence relation證明題

各位大大~還有兩題證明題~~請看一下~~這次的是total function 跟 cardinality的問題:

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.

希望各位高手大大盡力~~這次出了五題證明~~我只有一題會><"

就是證明偶數是countable....

拜託各位大大了~~Orz

1 Answer

Rating
  • Jacob
    Lv 6
    1 decade ago
    Favorite Answer

    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
    • Login to reply the answers
Still have questions? Get your answers by asking now.