- 締切済み
離散数学の証明
oodaikoの回答
- oodaiko
- ベストアンサー率67% (126/186)
2.有限集合A上の関数f:A->Aに関して、fが単射であるための必要十分条件はfが全射で あること。 全射→単射：A={a_1,a_2,…,a_n}(Aの要素数はn）とする。 fは全射だから f(A)={f(a_1),f(a_2),…,f(a_n)} = A すなわち f(a_1),f(a_2),…,f(a_n)がそれぞれ a_1,a_2,…,a_n のどれかに 対応している。{f(a_1),f(a_2),…,f(a_n)}も{ a_1,a_2,…,a_n}も要素数は 同じだからその対応は１対１でなくてはならない。 単射→全射： fは単射だからa_i≠a_jならf(a_i)≠f(a_j)。 そこでf(A)はAのn個の異なる要素からなる集合である。そのようなものはA自身しかない。 なおこの問題はAが有限集合であることが本質で、無限集合ではどちらも正しくない。 証明のどこに有限性が効いているのか、また無限集合の場合に成立しない例を 挙げておけばポイントが高いかも知れません。
関連するQ&A
- 大学の数学のことで質問です（ってか問題解けません＞＜；；）
問題 ｆ：A→B ｇ：B→Cとする。次の命題のうち正しいものは証明し、正しくないものには反例を挙げよ。 （１）ｆ、ｇが単射であれば、ｇ○ｆも単射である。 （２）ｆ、ｇが全射であれば、ｇ○ｆも全射である。 （３）ｇ○ｆが単射であれば、ｇも単射である。 （４）ｇ○ｆが単射であれば、ｆも単射である。 （５）ｇ○ｆが全射であれば、ｇも全射である。 （６）ｇ○ｆが全射であれば、ｆも全射である。 （７）ｆ、ｇが全単射なら、g○ｆも全単射で（ｇ○ｆ）の－１＝ｆの－１○ｇの－１ （８）g○fが単射であり、さらにｆが全射ならｇは単射 （９）ｇ○ｆが全射であり、ららにｇが単射ならｆは全射 ただしA,BCは集合を表します の－１っていうのはインバースのことでｆの－１の場合 ｆの右上に小さく－１を書こうとしたのですがPCでは入力できない・・！？みたいな感じだったので やむなく [の－１] と書きました(・・;)
- 締切済み
- 数学・算数
- 写像の単射全射のところの関係式に関する証明について
写像の単射全射のところの証明がわからないので、ご教授ください。 集合AからBへの写像をfとし、a∈A,P⊂A,b∈B,Q⊂Bとする。 １．fが単射のとき、a∈P ⇒ f(a)∈f(P)の逆が成り立つことの証明 2.fが単射のとき、Ｐ1⊂P2 ⇒ f(P1)⊂f(P2)の逆が成り立つことの証明 3.fが単射のとき、f(A-P) ⊃ f(A) - f(P) の逆が成り立つことの証明 4.fが単射のとき、f^(-1)(f(P)) = Pの証明 5.fが全射のとき、∃a'∈f^(-1)(Q), b=f(a') ⇒ b∈Qの逆が成り立つことの証明 6.fが全射のとき、Q1⊂Q2 ⇒ f^(-1)(Q1)⊂f^(-1)(Q2)の逆が成り立つことの証明 7.fが全射のとき、f(f^(-1)(Q)) = Qの証明 以上の7問です。 何個かだけでも構いませんので、回答して頂ければ嬉しいです。 また、はじめての質問ですので、ご迷惑をおかけするかもしれませんが、よろしくお願いいたします。
- 締切済み
- 数学・算数
- 集合 位相 について (数学) 教えてください
位相数学についてです f:A → B g:B→C とするとき g ο f が全射ならば gは全射 g ο f が単射ならば fは単射 であることを示せ なかなか位相について自分で掴むことができず 簡単な証明でも分からなくて困っています 教えていただきたいです。
- 締切済み
- 数学・算数
- 大学数学 全射と単射
次の問いが正しければ証明し、間違っていれば凡例をあげよ。 (1)fが単射ならばg○fは単射 (2)gが全射ならばg○fは全射 (3)fが単射、gが全射ならばg○fは全単射 という問題についてなのですが、 例えば(1)はgが全射か単射かによって場合分けをして考えるのでしょうか。 g,fともに全射ならばg○fは全射 g,fともに単射ならばg○fは単射 ということは証明できたのですが、g,fの片方が全射でもう片方が単射の場合の証明方法がわかりません。 また「凡例をあげる」というのは、どのように書けば良いのでしょうか？具体的な関数(y=x^2等)を書けということなのですか？ ヒントやアドバイスでも良いので、どなたか回答をお願いいたします。
- ベストアンサー
- 数学・算数
- 自身への写像が全単射となることの証明
(1) 写像f:Ａ→Ａとする。Aが有限集合であるとき、写像fが単射ならばfは全単射である事を示せ。 (2) Aが無限集合であるとき、fは全単射か。そうであれば証明せよ。そうでないなら反例を示せ。 上の問題の(1)は以下のように考えました。 f(A) は A の部分集合。 f(A)≠A と仮定すると、A とその真部分集合との間に全単射が存在したことになる。これは、無限集合の定義であるため、有限集合は全単射である。 このような証明で十分なのでしょうか？また、上のように考えたのでAが無限集合であるときはfは全単射ではないと思うのですが、反例が思いつきません。 わかる人がいれば教えてください。よろしくお願いします。
- ベストアンサー
- 数学・算数
- 合成問題の証明教えてください(＞＜)
背理法を使ってみたんですがよくわかりませんでした。 写像f:A→B,g:B→Cとその合成写像g。fについて示せ。 １ f,gともに全単射であればg。fはまた全単射である。またこのとき(g。f)＾-1=f＾-1。ｇ^-1である。 ２ g。fが全単射ならばgは全射である。もしこのとき、さらにgが単射でもあれば、fは全射である。 ３ g。fが単射ならば、fは単射である。もしこのとき、さらにfが全射でもあれば、gは単射である。 わかる方よろしくお願いします。
- ベストアンサー
- 数学・算数
- 写像の証明問題です。よろしくお願いします。
写像の問題です。よろしくお願いします。 (1)２つの写像f:Ｘ→Y、f:Ｙ→Zがある。g・fが全射ならばgは全射であるとする。ここでさらにgが単射であると仮定すればfも全射となることを証明せよ。 (2)自然数Nと零を合わせた集合N∪{0}から整数の集合Zへの写像で、全単射となるものを構成し、その理由を説明せよ。
- 締切済み
- 数学・算数