Grammatiken & Mengen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo Zusammen,
Ich habe zur Zeit einige Probleme mit zwei Aufgaben.
Eine poste ich jetzt hier und die andere in einem anderen Posting.
| Aufgabe | Zu zwei nichtleeren Mengen [mm]A\![/mm] und [mm]B\![/mm] bezeichne [mm]B^A[/mm] die Menge aller totalen Funktionen und [mm]P(A,B)[/mm] die Menge aller partiellen Funktionen von [mm]A\![/mm] nach [mm]B\![/mm]. Zeigen Sie für nichtleere endliche Mengen [mm]A\![/mm] und [mm]B\![/mm]:
(a) [mm]\left|B^A\right| = \left|B\right|^{\left|A\right|}[/mm] (Hinweis: Induktion nach [mm]\left|A\right|[/mm]).
(b) [mm]\left|P(A,B)\right| = \left(\left|B\right| + 1\right)^{\left|A\right|}[/mm] (Hinweis: Verwenden Sie Teil (a)). |
Bei dieser Aufgabe ist mir besonders unklar, was die Schreibweise [mm]B^A[/mm] bedeutet und was partielle und totale Funktionen sind. Wäre Klasse, wenn ihr mir da etwas helfen könntet.
Vielen Dank!
Viele Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fehlerhaft  | | Datum: | 00:40 So 17.10.2004 | | Autor: | Thomie |
[mm]B^A:= {f}, f:B\rightarrow A[/mm]
So oder ähnlich müsste das euer Prof definiert haben.
In Worten steht da: [mm]A^B[/mm] bezeichne die Menge aller Funktionen, die A nach B abbilden.
Eine totale Funktion (das muss er doch irgendwie definiert haben!) klingt für mich so etwas nach Surjektivität, soll heißen, das jedes [mm]b\in B[/mm] auch "getroffen" wird.
Partiell ist das wahrscheinlich das Gegenteil davon, könnte aber auch bedeuten, dass f nicht auf ganz A definiert ist, also dass nicht jedem [mm]a\in A[/mm] ein [mm]b\in B[/mm] zugeordnet wird.
Mein Tipp an dich: mach eine Definitionensammlung, die du imer griffbereit hast (z.B. ein Vokabelheft), das hilft, wenn es mal schneller gehen soll beim Nachschlagen
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:14 So 17.10.2004 | | Autor: | andreas |
hi Karl
also meines wissens nach sind [m] B^A [/m] die abbildungen von $A$ nch $B$ und nicht andersrum, also [m] B^A := \{f: A \longrightarrow B: f \text{ abbildung} \}[/m].
unter einer partiellen abbildung wurde bei uns eine abbildung verstanden, die nicht notwendigerweise auf dem gesamten urbildbereich definiert ist, eine totale funktion ordnet hingegen jedem element des urbildbereichs ein bild zu.
ansonsten halte dich mal an die angegebenen hinweise.
grüße
andreas
|
|
|
| |
|
Hallo Andreas,
> unter einer partiellen abbildung wurde bei uns eine
> abbildung verstanden, die nicht notwendigerweise auf dem
> gesamten urbildbereich definiert ist,
Tja, irgendwie verstehe ich das nicht. Was ist mit dem "nicht
notwendigerweise" gemeint? Könntest du mir vielleicht
die Definition der Menge aller totaler und partieller Funktionen
mathematisch hinschreiben? Vielleicht wird es mir dann klarer.
Ach ja, was bedeutet eigentlich das "obere Kringel" in Teil b) beim
linken Teil der Gleichung?
Danke!
Viele Grüße
Karl
[P.S. Ich merke gerade, daß sich die PDF-Version des Übungsblattes
von meiner ausgedruckten Version unterscheidet. Auf meiner ausgedruckten Version ist das "Kringel" vorhanden. Ob es wohl nur
ein Zeichnungsfehler ist, und ohne Bedeutung ist? So sieht es aus:
[Dateianhang nicht öffentlich]
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:50 So 17.10.2004 | | Autor: | andreas |
hi
also zb ist [m] f: \mathbb{N} \longrightarrow \mathbb{N} [/m] mit [m] n \longmapsto \begin{cases} 10 & \textrm{für } n \not= 10 \\ \textrm{undefiniert} & \textrm{für } n = 10 \end{cases} [/m] eine partielle abbildung, da sie nicht jedem element aus $n$ ein bild zuordnet. mit dem nicht-notwendigerweise meinte ich, dass insbesondere jede totale abbildung auch eine partielle ist.
such mal bei google nach partieller abbildung da findet sich dann eine korrekte definietion.
grüße
andreas
|
|
|
| |
|
Hallo Andreas,
Also viel habe ich bisher nicht geschafft. Hier ist meine Lösungsidee:
Induktionsanfang:
Sei $A = [mm] \emptyset$, [/mm] dann ist [m]\left|B\right|^{\left|\emptyset\right|} = \left|B\right|^0 = 1[/m]. Und [m]\left|B^\emptyset\right| = \left\{f:\emptyset \rightarrow B\ |\ \text{f ist Funktion}\right\}[/m]. Da
[mm] $\emptyset \in [/mm] B$, gibt es wohl nur eine einzige Funktion, die eine solche
Definitionsmenge haben kann, nämlich [m]f:\emptyset \rightarrow \emptyset[/m]. Damit gilt [m]\left|B^\emptyset\right| = \left|B\right|^{\left|\emptyset\right|} \gdw 1 = 1[/m] und wir haben einen Induktionsanfang.
Induktionsannahme:
Sei [mm] $\left|B^A\right| [/mm] = [mm] \left|B\right|^{\left|A\right|}$. [/mm] 
Induktionsschritt:
Sei $A = [mm] \left\{a_0,...,a_{n-1}\right\}$. [/mm] Es gelte: [m]\left|B^{A\cup\left\{a_n\right\}}\right|[/m], wobei [mm] $a_n$ [/mm] irgendein neues Element für A sein soll. Nach der Induktionsvorraussetzung brauchen wir
offenbar nur den Fall [m]\left|B^{\left\{a_n\right\}}\right| = \left|B\right|^{\left|\left\{a_n\right\}\right|}[/m] zu betrachten. Auf der rechten Seite
erhalten wir [mm] $\left|B\right|^1$ [/mm] also [mm] $\left|B\right|$. [/mm] Auf der linken Seite
wird es komplizierter. Wie viele Funktionen wird es wohl geben, die von einer einelementigen Menge auf eine andere beliebig große Menge abbilden? Da wir es hier aber mit totalen Funktionen zu tun haben,
Funktionen also, die - wie du sagst - jedem Element aus dem Urbildbereich ein Element aus dem Bildbereich zuordnen, können wir
alle Elemente der Menge nacheinander durchlaufen und jeweils Funktionen
auf jedes dieser Elemente setzen. Insgesamt wären das dann
[mm] $\left|B\right|$ [/mm] Funktionen, nicht wahr? Also haben wir die Aussage bewiesen [mm] $\Box$. [/mm] Richtig?
Also wenn's jetzt soweit stimmt, weißt du eventuell, was denn
dieses Kringel bei b) zu bedeuten hat? Und inwiefern nützt mir da der Hinweis auf a)? Der rechte Teil der Gleichung muß wohl etwas damit
zu tun haben.
Vielen Dank!
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:22 So 17.10.2004 | | Autor: | andreas |
hi Karl
schön, dass du einen lösungsanstz postest, das macht mir die arbeit doch etwas leichter.
den induktionsanfang darfst du nicht mit [m] A = \emptyset [/m] machen, da die aussage dafür falsch ist: es gibt keine totale abbildung der leeren menge nach [m] B [/m], da elementen von $A$ elemnete von $B$ zugeordnet werden. bei dir werden mengen mengen zugeordnet (das $A$ nicht-leer sei wurde in der aufgabenstelleung vorausgetzt - schau mal nach). im weiteren sei $B$ stets eine feste endliche menge.
also IA:
sei [m] |A| = 1 [/m] dann gibt es genau [m] |B| =:n [/m] mögliche funktionen (= totale abbildungen) von [m] A = \{ a \} [/m] nach $B$, nämlich für [m] B = \{ b_1, \hdots, b_n \} [/m] die funktionen [m] \{ f \}_{i=1}^n [/m] mit
[m] f_i: A \longrightarrow B; \; a \longmapsto b_i [/m].
IS:
voraussetzung: sei [m] |B^A| = |B|^{|A|} [/m] für alle [m] A [/m] mit [m] |A| \leq n [/m]
betrachte nun [m] A \cup \{a_{n+1}\} [/m]. funktionen $f$ von [m] A \cup \{a_{n+1}\} [/m] nach $B$ lassen sich nun stets auf $A$ einschränken:
[m] f|_A: A \longrightarrow B [/m]
und nach vorausstzung gibt es davon genau [m] |B|^{|A|} [/m] stück (da die menge $A$ $n$-elementig ist). um den gesamten urbild bereich auszuschöpfen, kann nun jede dieser funktionen so fortgestzt werden, das dem dazukommenden element [mm] $a_{n+1}$ [/mm] ein beliebiges element von $B$ zugeordnet wird und davon gibt ja genau $|B|$-stück. macht man dies mit jeder funktion so erhält man also [m] |B|^|A| \cdot |B| = |B|^{|A| + 1} = |B|^{|A \cup \{a_{n+1}\} |}[/m]-viele funktionen. damit ist die aussage bewiesen.
jedoch bin ich mit dem beweis noch nicht so ganz zufrieden - das sollte doch etwas klarer zu formulieren sein.
der kringel bei der aufgabe b) ist wohl nur ein druckfehler - ich kann mir zumindest nicht vorstellen, was der bedeuten soll.
der hinweis auf aufgabe a) bringt dir insofern was, da du weißt wieviele totale funktionen es gibt.
du kannst nun [m] P(A, B) = B^A \cup P(A, B) \setminus B^A [/m] betrachten. bei der ersten menge ist dir die mächtigkeit bekannt. die abbildungen der zweiten menge sind auf mindestens einem element undefiniert. betrachte mal die abbildungen die auf genau einem elemnet undefiniert sind. es gibt ja genau [m] |A| = \binom{|A|}{1} [/m]-möglichkeiten ein element aus der menge zu entfernen. diese abbildungen kann man nun aber wieder als totale abbildungen auf einer [m] |A|-1 [/m]-elemntigen menge betrachten - und wieveile es davon gibt ist ja nach teil a) bekannt. nun überlege dir mal, wieviel möglichkeiten es gibt 2, 3, ... elemnet aus $A$ zu entfernen...
probiere mal ob du damit zu teil b) was zustande bekommst.
grüße
andreas
|
|
|
|
