inj., surj, bij. Abbildungen < Abbildungen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Es sei X eine a) endliche bzw. b) unendliche Menge und $f: X [mm] \rightarrow [/mm] X$ eine Abbildung. Man beweise oder widerlege:
Die folgenden Aussagen sind äquivalent:
1. $f$ ist bijektiv
2. $f$ ist injektiv
3. $f$ ist surjektiv |
Egal, ob die Menge unendlich oder endlich ist, wenn die Abbildung bijektiv ist, ist sie auch surjektiv und injektiv. Das ist klar. Aber ich vermute, in die andere Richtung muss das ein Unterschied sein, ob die Menge endlich oder unendlich ist. Würde mir jemand das erklären?
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:45 Di 29.04.2008 | | Autor: | Syladriel |
Hat niemand einen Tipp für mich?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:07 Di 29.04.2008 | | Autor: | Alexis |
Hi Syladriel
Als Idee:
Wenn der Körper endlich ist, und deine Abbildung injektiv. Was bedeutet das denn für dich? Genauso wenn sie Surjektiv ist.
Eine Abbildung ist ja erst eine Abbildung, wenn sie jedes Element aus dem Definitionsbereich auch abbildet.
Versuch damit mal auf einen Beweis zu kommen und meld dich nochmal wenn es dir nicht weiterhelfen sollte
MfG
Alexis
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:26 Di 29.04.2008 | | Autor: | Marcel |
Hallo,
> Es sei X eine a) endliche bzw. b) unendliche Menge und [mm]f: X \rightarrow X[/mm]
> eine Abbildung. Man beweise oder widerlege:
> Die folgenden Aussagen sind äquivalent:
>
> 1. [mm]f[/mm] ist bijektiv
> 2. [mm]f[/mm] ist injektiv
> 3. [mm]f[/mm] ist surjektiv
> Egal, ob die Menge unendlich oder endlich ist, wenn die
> Abbildung bijektiv ist, ist sie auch surjektiv und
> injektiv. Das ist klar. Aber ich vermute, in die andere
> Richtung muss das ein Unterschied sein, ob die Menge
> endlich oder unendlich ist. Würde mir jemand das erklären?
im Falle der Endlichkeit von $X$ ist eine Abbildung $X [mm] \to [/mm] X$ genau dann bijektiv, wenn sie injektiv oder surjektiv ist.
Das beweist man z.B. über Induktion. Führe mal den Induktionsbeweis, dass hier aus injektiv auch surjektiv und damit bijektiv folgt. Das ist aber nicht so einfach, das Problem liegt im Induktionsschritt:
Nehmen wir mal an, Du weißt, dass eine jede Abbildung einer 3 elementigen Menge in sich selbst die Eigenschaft hat, dass sie, wenn sie injektiv ist, schon surjektiv ist. Wenn ich nun eine Abbildung $f: [mm] \{1,2,3,4\} \to \{1,2,3,4\}$ [/mm] betrachte mit $f(1)=4$, $f(2)=1$, $f(3)=2$ und $f(4)=3$, so kann ich daraus nicht eine Abbildung einer 3 elementigen Menge in sich selbst machen:
Schränke ich $f$ auf [mm] $\{1,2,3\}$ [/mm] ein, so bildet diese Einschränkung von $f$ dann aber nach [mm] $\{1,2,4\}$ [/mm] ab und es ist [mm] $\{1,2,4\} \not= \{1,2,3\}$
[/mm]
Schränke ich $f$ auf [mm] $\{1,2,4\}$ [/mm] ein, so bildet diese Einschränkung von $f$ dann aber nach [mm] $\{1,3,4\}$ [/mm] ab und es ist [mm] $\{1,2,4\} \not= \{1,3,4\}$
[/mm]
.
.
.
Um es vorweg zu nehmen:
Das vorherrschende Problem tritt also auf, wenn es kein $x [mm] \in [/mm] X$ mit $f(x)=x$ gibt. (Andernfalls wähle man ein solches und entferne es aus $X$, die neue Menge heiße dann [mm] $X\,'$ [/mm] und die Einschränkung von $f$ auf [mm] $X\,'$ [/mm] ist dann eine Abbdilung [mm] $X\,' \to X\,'$, [/mm] so dass dort die I.V. greift.)
Dafür braucht man allerdings eine Lösung. Naheliegend ist es, beim Schritt $n [mm] \mapsto [/mm] n+1$ dann schonmal [mm] $X=\{x_1,...,x_n, x_{n+1}\}$ [/mm] "durchzunumerieren" und dann irgendwie im Induktionsschritt damit zu versuchen, anstatt eine Einschränkung von $f$ ins Spiel zu bringen, zu versuchen, eine Abbildung [mm] $\{1,...,n\} \to \{1,...,n\}$ [/mm] so ins Spiel zu bringen (natürlich wird man irgendwann auch Verknüpfungen davon mit $f$ machen), dass man dafür die Induktionsvoraussetzung anwenden kann (denn wie gesagt: Macht man aus der $n+1$-elementigen Menge $X$ nun eine $n$-elementige Menge [mm] $X\,'$ [/mm] durch entfernen eines Elementes, so wird i.a. die Einschränkung von $f$ auf [mm] $X\,'$ [/mm] keine Abbildung mehr [mm] $X\,' \to X\,'$ [/mm] sein, und i.a. läßt sich auch kein $x [mm] \in [/mm] X$ so finden, dass diese Einschränkung dann doch eine Abbildung von [mm] $X\,'$ [/mm] nach [mm] $X\,'$ [/mm] ist).
Und wenn $X$ unendlich ist: Sei [mm] $X=\IN$ [/mm] (bei mir: $0 [mm] \notin \IN$).
[/mm]
Betrachte mal $f: [mm] \IN \to \IN$ [/mm] mit $f(n):=2*n$. Dann ist $f$ injektiv, nicht aber ... und daher insbesondere auch nicht ...
Betrachte auch mal $g: [mm] \IN \to \IN$ [/mm] mit [mm] $g(n):=\left[\frac{n-1}{2}\right]+1$, [/mm] wobei [mm] $[n]:=\max\{z \in \IZ: z \le n\}$ [/mm] (Gaußklammer).
(Hier ist also $g(1)=1$, $g(2)=1$, $g(3)=2$, $g(4)=2$, $g(5)=3$, ...)
Dann ist $g$ surjektiv, aber nicht ... und daher insbesondere auch nicht ...
P.S.:
Ein noch einfacheres Beispiel einer surjektiven, nicht aber injektiven Abbildung [mm] $\IN \to \IN$:
[/mm]
$g(1):=1$ und $g(n):=n-1$ für alle $n [mm] \in \IN_{\ge 2}$
[/mm]
Und damit Du auch siehst, dass es auch andere Funktionen gibt (also nicht nur mit abzählbarem $X$):
$f: [mm] [0,\infty) \to [0,\infty)$ [/mm] mit [mm] $f(x):=|x*\sin(x)|$ [/mm] ist surjektiv, nicht aber injektiv...
Gruß,
Marcel
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 03:52 Mi 30.04.2008 | | Autor: | MarxK |
a) kann man auch reichlich elementar lösen.
Dazu betrachtest du dir zuerst eine beliebige Abbildung f: X [mm] \to [/mm] Y.
(1*) Ist f NICHT surjektiv, so gilt doch der Definition nach: f(X) [mm] \not= [/mm] Y, dh. es gibt ein [mm] y_0 \in [/mm] Y für das gilt: für jedes x [mm] \in [/mm] X ist [mm] y_0 \not= [/mm] f(x).
Was heißt, das nun für Anzahl der Elemente in f(X) im Vergleich zu der Anzahl der Elemente in Y? - Nämlich, dass Y mind. ein Element mehr hat als f(X) oder anders gesagt: f(X) hat mind. ein Element weniger als Y.
(2*)Ist f NICHT injektiv, dann folgt aus [mm] x_i,x_j \in [/mm] X und [mm] f(x_i) [/mm] = [mm] f(x_j) [/mm] doch [mm] x_i \not= x_j.
[/mm]
Für die Anzahl der Elemente von f(X) gilt dann: f(X) hat mind. 1 Element weniger als die Urbildmenge.
Jetzt nimmst du deine Aufgabe her und beweist sie in dieser Reihenfolge:
(i) f ist injektiv
(ii) f ist surjektiv
(iii) f ist bijektiv
f: X [mm] \to [/mm] X
Dazu bestehe X aus n voneinander veschiedenen Elementen: X={ [mm] x_1,...x_n [/mm] }, n [mm] \in \IN
[/mm]
(i)=>(ii) (Zur Erinnerung A=>B <=> [mm] \neg [/mm] B => [mm] \neg [/mm] A)
Nun zeigt man "nicht surjektiv" => "nicht injektiv". Ist f(X) [mm] \not= [/mm] X, so besteht f(X) aus m<n Elementen (siehe (1*)). Dh. f(X) hat mind. 1 Element weniger als X. Daraus folgt:
es gibt [mm] x_i,x_j \in [/mm] X und [mm] f(x_i) [/mm] = [mm] f(x_j) [/mm] mit [mm] x_i \not= x_j. [/mm] Also ist f nicht injektiv.
(ii)=>(i)
Ist f nicht injektiv, so gibt es [mm] x_i, x_j [/mm] mit [mm] x_i \not=x_j, [/mm] aber [mm] f(x_i) [/mm] = [mm] f(x_j).
[/mm]
f(X) besteht dann aus höchstens n-1 Elementen. Also ist f nicht surjektiv.
Aus (ii)=>(i) folgt (ii)=>(iii), (iii)=>(i) ist klar.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:07 Mi 30.04.2008 | | Autor: | Marcel |
Hallo,
> a) kann man auch reichlich elementar lösen.
> Dazu betrachtest du dir zuerst eine beliebige Abbildung f:
> X [mm]\to[/mm] Y.
>
> (1*) Ist f NICHT surjektiv, so gilt doch der Definition
> nach: f(X) [mm]\not=[/mm] Y, dh. es gibt ein [mm]y_0 \in[/mm] Y für das gilt:
> für jedes x [mm]\in[/mm] X ist [mm]y_0 \not=[/mm] f(x).
> Was heißt, das nun für Anzahl der Elemente in f(X) im
> Vergleich zu der Anzahl der Elemente in Y? - Nämlich, dass
> Y mind. ein Element mehr hat als f(X) oder anders gesagt:
> f(X) hat mind. ein Element weniger als Y.
das ist zwar grundsätzlich nicht falsch, aber da braucht man schon so etwas wie die Anzahl der Elemente. Diese werden meist aber über gewisse Bijektionen (oder siehe unten: Surjektionen bzw., was natürlich auch geht: Injektionen) definiert, und da geht man hin und betrachtet gewisse Abbildungen nach [mm] $\{1,...,n\}$ [/mm] mit einem $n [mm] \in \IN$. [/mm] Schlussendlich nutzt man irgendwann eine Eigenschaft aus, die mit einer Abbildung [mm] $\{1,...,n\} \to \{1,...,n\}$ [/mm] zu tun hat, und hier braucht man dann die obige Eigenschaft für Abbildungen von endlichen Mengen in sich selbst. In diesem Sinne kann es sein, dass, sollte hier kein Induktionsbeweis geführt werden, dieser nicht anerkannt wird, weil er, wenn er es so beweist, etwas benutzt, was er zeigen soll. Da ist sehr viel Vorsicht geboten, wenn man so sagt, wie Du es tust. Und ich kann mich erinnern, dass diese Aufgabe bei uns in WT gestellt wurde und es aufgrund der zur Verfügung stehenden Mitteln kein Weg an einem Induktionsbeweis vorbeiging.
> (2*)Ist f NICHT injektiv, dann folgt aus [mm]x_i,x_j \in[/mm] X und
> [mm]f(x_i)[/mm] = [mm]f(x_j)[/mm] doch [mm]x_i \not= x_j.[/mm]
Das hier ist leider absoluter Unsinn. Wie sollte denn aus $f(x)=f(y)$ folgen, dass $x [mm] \not=y$. [/mm] Was Du meinst, ist folgendes:
Hier folgt aus $f(x)=f(y)$ im Allgemeinen nicht, dass $x=y$. Das heißt: Es gibt $x,y$ mit $x [mm] \not=y$ [/mm] und $f(x)=f(y)$. Das ist etwas vollkommen anderes, als das, was Du oben sagst. Denn bei Dir hieße das auch: Aus $f(x)=f(x)$ folgt $x [mm] \not=x$, [/mm] was niemals sein kann.
Übrigens: Wegen
$A [mm] \Rightarrow [/mm] B $
[mm] $\gdw$ ($\mbox{nicht }B \Rightarrow \mbox{nicht }A$) [/mm]
sind für eine Abbildung $f: X [mm] \to [/mm] Y$ äquivalent:
1.) Für alle $x,y [mm] \in [/mm] X$ gilt: $x [mm] \not=y \Rightarrow [/mm] f(x) [mm] \not=f(y)$
[/mm]
2.) Für alle $x,y [mm] \in [/mm] X$ gilt: $f(x)=f(y) [mm] \Rightarrow [/mm] x=y$
Ich wollte das nur mal ergänzen, damit klar ist, dass sowohl 1.) als auch 2.) zur Definition der Injektivität in Frage kommt.
> Für die Anzahl der
> Elemente von f(X) gilt dann: f(X) hat mind. 1 Element
> weniger als die Urbildmenge.
>
> Jetzt nimmst du deine Aufgabe her und beweist sie in dieser
> Reihenfolge:
>
> (i) f ist injektiv
> (ii) f ist surjektiv
> (iii) f ist bijektiv
>
> f: X [mm]\to[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
X
>
> Dazu bestehe X aus n voneinander veschiedenen Elementen:
> X={ [mm]x_1,...x_n[/mm]Eingabefehler: "{" und "}" müssen immer paarweise auftreten, es wurde aber ein Teil ohne Entsprechung gefunden (siehe rote Markierung)
}, n [mm]\in \IN[/mm]
>
> (i)=>(ii) (Zur Erinnerung A=>B <=> [mm]\neg[/mm] B => [mm]\neg[/mm] A)
> Nun zeigt man "nicht surjektiv" => "nicht injektiv". Ist
> f(X) [mm]\not=[/mm] X, so besteht f(X) aus m<n Elementen (siehe
> (1*)). Dh. f(X) hat mind. 1 Element weniger als X. Daraus
> folgt:
> es gibt [mm]x_i,x_j \in[/mm] X und [mm]f(x_i)[/mm] = [mm]f(x_j)[/mm] mit [mm]x_i \not= x_j.[/mm]
> Also ist f nicht injektiv.
>
> (ii)=>(i)
> Ist f nicht injektiv, so gibt es [mm]x_i, x_j[/mm] mit [mm]x_i \not=x_j,[/mm]
> aber [mm]f(x_i)[/mm] = [mm]f(x_j).[/mm]
> f(X) besteht dann aus höchstens n-1 Elementen. Also ist f
> nicht surjektiv.
> Aus (ii)=>(i) folgt (ii)=>(iii), (iii)=>(i) ist klar.
Wie gesagt: Man muss hier einfach aufpassen, dass man nur das benutzt, was man schon in der Vorlesung zur Verfügung gestellt bekommen hat. Andernfalls stimmen vll. die Aussagen und Argumentationen an und für sich, deren Begründung bedürfte dann aber eigentlich dem, was man zu zeigen hat und damit wird - in diesem Sinne - alles falsch. Ich habe oben nicht umsonst gesagt, dass er einen Induktionsbeweis führen soll und mit Verknüpfungen von Funktionen arbeiten soll, denn mich würde es (aus gewissen Gründen) wundern, wenn er hier schon mit der Anzahl von Elementen einer Menge arbeiten dürfte. Und auch Deine Argumentationen oben:
"Ja, wenn die injektive Abbildung nicht surjektiv ist, dann hat die Zielmenge mindestens ein Element mehr..."
Das hört sich ja auch alles plausibel an, aber: Im Grunde genommen schmeißt Du hier nur so mit Behauptungen um Dich. Ob sich diese überhaupt verwenden lassen, also ob man die verwenden darf:
Das geht nur, wenn es in der Vorlesung bewiesen wurde, oder er es mit einen Mitteln beweisen kann. Dann kann es passieren, dass er am Ende viele kleine zusätzliche Beweise führen muss, um überhaupt mit Deinen Argumenten arbeiten zu dürfen, so dass die ganze Aufgabe "ausartet".
Übrigens, ich hänge mal noch etwas anderes an, nämlich die mir gängige Definition der Endlichkeit einer Menge:
Eine nichtleere Menge $X$ heißt endlich genau dann, wenn es ein $n [mm] \in \IN$ [/mm] gibt, so dass eine surjektive Abbildung $f: [mm] \{1,...,n\} \to [/mm] X$ existiert. Zudem sagen wir auch, dass die leere Menge [mm] $\emptyset$ [/mm] endlich sei.
(In äquivalenter Weise könnte man auch sagen:
...,wenn eine injektive Abbildung $X [mm] \to \{1,...,n\}$ [/mm] existiert.)
Und wenn man das z.B. zur Verfügung hat, dann geht es weiter:
Der Betrag, oder die Anzahl, einer nichtleeren endlichen Menge $X$, im Zeichen $|X|$, werde definiert als das kleinste $n [mm] \in \IN$, [/mm] so dass eine surjektive Abbildung
$f: [mm] \{1,...,n\} \to [/mm] X$
existiert. Zudem setzen wir [mm] $|\emptyset|:=0$.
[/mm]
(Zusätzlich zu dieser Definition sollte die Existenz und Eindeutigkeit dieses $n$'s dann begründet werden, wobei die Existenz recht schnell begründet werden kann. Aber die Eindeutigkeit: Das dauert schon ein bisschen länger...)
Und dann kommt schon die erste Behauptung:
Ist $X$ endlich und $n [mm] \in \IN$, [/mm] dann gilt für eine surjektive Abbildung $f: [mm] \{1,...,n\} \to [/mm] X$, dass sie genau dann bijektiv ist, wenn $n=|X|$.
Und wie würde der Beweis dazu wohl gehen?
Gruß,
Marcel
|
|
|
|
