en>박중현: TeX command correction

2014-01-01T12:26:10Z

TeX command correction

← Older revision		Revision as of 14:26, 1 January 2014
Line 1:		Line 1:
	Hi there! :) ~~My name~~ is ~~Edgar~~, I'm a ~~student studying Medicine from Sittard~~, ~~Netherlands~~.<br><br>~~My page -~~ [http://~~clashofclans~~.~~free-hack~~.~~org~~/ ~~clash~~ of ~~clans hack for gems~~]		{{tone\|date=January 2012}}
			{{inappropriate person\|article\|we\|date=January 2012}}
			In mathematics, the '''Szpilrajn extension theorem''', due to {{harvs\|txt\|authorlink=Edward Szpilrajn\|first=Edward \|last=Szpilrajn\|year=1930}} (later called [[Edward Marczewski]]), is one of many examples of the use of the [[axiom of choice]] (in the form of [[Zorn's lemma]]) to find a maximal set with certain properties.

			The theorem states that, given a [[binary relation]] ''R'' that is [[irreflexive relation\|irreflexive]] and [[transitive relation\|transitive]] it is always possible to find an extension of the relation (i.e. a relation ''T'' that strictly includes ''R'') which is [[asymmetric relation\|asymmetric]], [[negatively transitive]] and [[Connectedness\|connected]].

			First of all, we need some definitions to be clear upon the terminology we will use speaking about relations with particular properties.

			== Definition (negative transitivity) ==
			Given a [[binary relation]] <math>R \subseteq X\times X</math> on a generic [[set (mathematics)\|set]] <math>X</math>, we say that <math>R</math> is '''negatively transitive''' if
			:<math> \forall \ x,y,z\in X \ \ \neg (xRz) \and \neg (zRy) \Rightarrow \neg (xRy),</math>
			:where by <math>\neg(xRy)</math> we mean <math>(x,y)\not \in R.</math>

			Note that [[negative transitivity]] can also be rewritten as :<math> \forall \ x,y,z\in X \ \ (xRy) \Rightarrow (xRz) \or (zRy) </math>, simply using the fact that <math>A \Rightarrow B</math> can be rewritten as <math>\neg A \or B
			</math>

			== Definition (connection) ==
			Given a [[binary relation]] <math>R \subseteq X\times X</math> on a generic [[set (mathematics)\|set]] <math>X</math>, we say that R is ''connected (weakly)'' if :<math>\forall x,y \in X : x\not = y </math> either <math>x R y</math> or <math>y R x</math>.
			:Say that R is ''strictly connected'' or ''complete'' if <math>\forall x,y \in X, xRy \or yRx</math>.

			== Properties ==
			This properties on binary relations can be easily checked by definition:
			:R is ''[[irreflexive]]'' and ''[[transitive relation\|transitive]]'' <math>\Rightarrow </math> R is ''[[asymmetric relation\|asymmetric]]''.<ref>{{cite book\|last1=Flaška\|first1=V.\|last2=Ježek\|first2=J.\|last3=Kepka\|first3=T.\|last4=Kortelainen\|first4=J.\|title=Transitive Closures of Binary Relations I\|year=2007\|publisher=School of Mathematics - Physics Charles University\|location=Prague\|page=1\|url=http://www.karlin.mff.cuni.cz/~jezek/120/transitive1.pdf?}} Lemma 1.1 (iv). Note that this source refers to asymmetric relations as "strictly antisymmetric".</ref>
			:R is ''asymmetric'', ''transitive'' and ''connected'' <math>\Rightarrow </math> R is ''[[negatively transitive]]''.

			To enounce precisely the theorem, we need yet a couple of definitions and a useful, simple lemma.

			==Definition (strict orders)==
			:A binary relation R is said to be a ''[[strict partial order]]'' if it is irreflexive and transitive, and it is a ''[[strict order]]'' if it is ''asymmetric'', ''negatively transitive'' and ''complete''.

			==Lemma==
			Let R be a strict partial order on X. Then there exists another binary relation T on X which is still a strict partial order and extends R, hence:
			:<math>\exists T \subseteq X\times X </math> such that <math> R\subset T </math> and T is another strict partial order on X.

			This lemma can be easily proved, by taking <math>x\not =y \in X</math> such that <math>\neg(xRy) \and \neg(yRx)</math>, which exists since the relation is not connected.

			:Naming:
			:<math>Rx=\{z \in X \| zRx\}</math>
			:<math>yR=\{z \in X \| yRz\}</math>
			we can define another relation:
			:<math>S=\{x\}\cup Rx \times \{y\}\cup yR \subseteq X \times X. </math>
			Finally, set <math>T=R \cup S</math>
			which is trivially an extension of R and another strict partial order on X.

			==Theorem (Szpilrajn's extension theorem)==
			Let ''R'' be a strict partial order on a set ''X''. Then there exists a relation ''T'' that extends ''R'' and is a strict order on ''X''.

			==Proof==
			:Let <math>\mathcal{P}=\{P: R\subset P</math>, P is a strict partial order on X<math>\}</math>.

			We want to show the existence of a maximal element in <math>\mathcal{P}</math> with respect to set inclusion.

			To do this, we will use Zorn's Lemma. First of all we want to verify the hypothesis of the Lemma, hence that any [[Total_order#Chains\|chain]] (respect to inclusion) of <math>\mathcal{P}</math> admits an [[upper bound]] in <math>\mathcal{P}</math>.

			Let <math>\mathcal{C}</math> be a chain in <math>\mathcal{P}</math>.

			Define
			:<math>\mathcal{M}=\bigcup_{C\in \mathcal{C}} C.</math>

			Clearly <math>\mathcal{M}</math> is an upper bound to the chain, but we have to show that <math>\mathcal{M}\in \mathcal{P}</math>, hence that <math>\mathcal{M}</math> is another strict partial order which extends R.

			Obviously it contains R, as all <math>C\in \mathcal{C}</math> contains R, and it is irreflexive, as
			<math>(\bigcup_{C\in \mathcal{C}} C)\cap \Delta_{X} = \bigcup_{C\in \mathcal{C}} (C \cap\Delta_{X})=\empty</math>, since any
			:<math>C\in \mathcal{C}</math> is irreflexive,
			:<math> \Delta_{X}=\{(x,x)\|x \in X\}.</math>

			We have to show that <math>\mathcal{M}</math> is transitive and here we use the chain properties of <math>\mathcal{C}</math>.

			Let <math>x,y,z \in X</math> such that <math>x\mathcal{M}y \and y\mathcal{M}z</math> iff <math>(x,y),(y,z) \in \mathcal{M}</math>.

			As <math>\mathcal{M}</math> is defined as a union of sets, there exists
			:<math>P_1,P_2\in \mathcal{C}</math> such that <math>(x,y)\in P_1, (y,z)\in P_2.</math>.

			But <math>\mathcal{C}</math> is a chain with respect to inclusion, hence it holds that <math>P_1 \subseteq P_2</math>
			or vice versa, so that the two couples of elements of X both belong to the same set in the union, and that set is a transitive relation; then also <math>(x,z)</math> is in that set, hence in <math>\mathcal{M}</math>.

			Applying Zorn's Lemma, we deduce that <math>\mathcal{P}</math> admits an upper bound with respect to set inclusion; let's call T that bound.

			T has to be a complete relation, as if it was not, we could construct (exactly as in the preceding Lemma) another binary relation which strictly extends (strictly includes) T and is a strict partial order, so yet another element of <math>\mathcal{P}</math>, contradicting that T is a maximal of <math>\mathcal{P}</math>.

			So ''T'' is an irreflexive, transitive and complete binary relation on ''X''. But as we observed above, irreflexivity and transitivity give asymmetry that, with transitivity and completeness, give negative transitivity.

			Hence ''T'' is a strict order on ''X'' that extends the partial order ''R''.

			==References==

			<references />
			*{{Citation \| last1=Szpilrajn \| first1=E. \| title=Sur l'extension de l'ordre partiel \| url=http://matwbn.icm.edu.pl/tresc.php?wyd=1&tom=16 \| year=1930 \| journal=[[Fundamenta Mathematicae]] \| issn=0016-2736 \| volume=16 \| pages=386–389}}
			[[Category:Axiom of choice]]
			[[Category:Theorems in the foundations of mathematics]]
			[[Category:Articles containing proofs]]

en>Gadget850: fix math error

2011-11-05T13:06:59Z

fix math error

New page

Hi there! :) My name is Edgar, I'm a student studying Medicine from Sittard, Netherlands.<br><br>My page - [http://clashofclans.free-hack.org/ clash of clans hack for gems]

Soundness (interactive proof) - Revision history

en>박중현: TeX command correction

en>Gadget850: fix math error