Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Permutation: Beweis Kommutativität f. 2 disjunk. P

Permutation: Beweis Kommutativität f. 2 disjunk. P

Universität / Fachhochschule

Tags: Beweis, Beweisführung, disjunkt, formal, Kommutativität, nicht-disjunkt, permutation

mike-94 aktiv_icon

08:23 Uhr, 27.11.2019

Hallo Leute,

ich muss folgende Aufgaben Formal beweisen:

$a)$ Weisen Sie nach, dass für zwei disjunkte Permutationen $σ 1$ und $σ 2$ stets $σ 1 \circ σ 2 = σ 2 \circ σ 1$ gilt.
$b)$ Überzeugen Sie sich davon, dass obige Eigenschaft für nicht-disjunkte Permutationen nicht gilt.

Mir ist klar wieso die Kommutativität im Fall $a)$ gilt, und kann dies auch an einenm tatsächlichen Beispiel darstellen. Gefragt ist aber ein formaler Beweis, jedoch weiß ich nicht wo/wie ich hier ansetzen soll.

Kann mir hier jemand vielleicht einen Tipp geben?

Vielen Dank.
SG
Mike

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

Hierzu passend bei OnlineMathe:

Zu diesem Thema passende Musteraufgaben einblenden

anonymous

10:02 Uhr, 27.11.2019

Hallo,
aus der Hüfte geschossen ist es vielleicht einen Versuch wert, es mit einem Widerspruchsbeweis zu versuchen. $σ 1 \circ σ 2 \neq σ 2 \circ σ 1$

michaL aktiv_icon

12:04 Uhr, 27.11.2019

Hallo,

etwas länger gezielt (aber mit dem Hinweis, oft nicht sofort die kürzeste Formalisierung zu wählen):

Wir nehmen zwei Permutationen $σ, τ \in S_{n}$ her mit elementfremden Nichtfixpunktmengen:
$F_{σ} := {i \in {1, \dots, n} ∣ σ (i) = i}$ sei die Fixpunktmenge von $σ$ , $F_{τ}$ die von $τ$ .

Weiter definieren wir $N_{σ} := {1, \dots, n} \ F_{σ}$ , die Menge aller Nichtfixpunkte von $σ$ , $N_{τ}$ die von $τ$ .
$σ$ und $τ$ disjunkt heißt, dass $N_{σ} \cap N_{τ} = \emptyset$ gilt, d.h. es gelten $N_{σ} \subseteq F_{τ}$ und $N_{τ} \subseteq F_{σ}$ , oder konkret auf $σ$ bzw. $τ$ herunter gebrochen:
$σ (x) \neq x \Rightarrow τ (x) = x$ und $τ (x) \neq x \Rightarrow σ (x) = x$

Ich finde, du solltest dir klar machen, warum aus $x \in N_{σ}$ folgt:
* $σ (x) \in N_{σ}$
* $x, σ (x) \in F_{τ}$

Leite daraus her, dass im Falle $x \in N_{σ}$ die Gleichung $τ \circ σ (x) = σ \circ τ (x) = σ (x)$ gilt.

Im anderen Fall ( $x \notin N_{σ} \overset{}{\Leftrightarrow} x \in F_{σ}$ ) unterscheiden wir wieder zwei Fälle: $x \in F_{τ}$ und $x \in N_{τ}$ , wobei der erste Fall trivial ist.
Wenden wir uns also $x \in N_{τ}$ zu.
Aus den oberen Überlegungen folgt (vertauschen der Rollen von $σ$ und $τ$ ), dass auch $τ (x) \in F_{σ}$ .
Damit folgen $τ \circ σ (x) = τ (x)$ und $σ \circ τ (x) = τ (x)$ , also auch in diesem Fall $τ \circ σ (x) = σ \circ τ (x) = σ (x)$ .

Mfg Michael

mike-94 aktiv_icon

17:32 Uhr, 05.12.2019

Vielen Dank für eure Antworten. Konnte $a)$ formal und $b)$ durch ein Beispiel lösen.

1489217

1488011

	Status: nicht eingeloggt	Noch nicht registriert?