Difference between revisions of "Ordered pair"
m |
m |
||
| Line 13: | Line 13: | ||
The axioms may be found [[Set theory axioms|here]] | The axioms may be found [[Set theory axioms|here]] | ||
| + | |||
| + | ==Proof of uniqueness== | ||
| + | Before we may write <math>(a,b)</math> we must make sure this is not ambiguous. | ||
| + | |||
| + | {{Begin Theorem}} | ||
| + | Proof that <math>(a,b)=(a',b')\iff[a=a'\wedge b=b']</math> | ||
| + | {{Begin Proof}} | ||
| + | <math>\impliedby</math> | ||
| + | |||
| + | Clearly if <math>a=a'</math> and <math>b=b'</math> then <math>(a,b)=\{\{a\},\{a,b\}\}=\{\{a'\},\{a',b'\}\}=(a',b')</math> and we're done. | ||
| + | |||
| + | <math>\implies</math> | ||
| + | |||
| + | Assume <math>(a,b)=\{\{a\},\{a,b\}\}=\{\{a'\},\{a',b'\}\}=(a',b')</math>. | ||
| + | |||
| + | If <math>a\ne b</math> then we must have <math>\{a\}=\{a'\}</math> and <math>\{a,b\}=\{a',b'\}</math> (as clearly <math>\{a\}=\{a',b'\}</math> is false, there are either 2 or 1 elements not contained in <math>\{a\}</math> that are in <math>\{a',b'\}</math> - namely <math>a'</math> and <math>b'</math>) | ||
| + | |||
| + | Clearly <math>a=a'</math>, then <math>\{a,b\}=\{a',b'\}\implies b=b'</math>. | ||
| + | |||
| + | If <math>a=b</math> then <math>(a,a)=\{\{a\},\{a,a\}\}=\{\{a\}\}</math>, we know <math>\{\{a\}\}=\{\{a'\},\{a',b'\}\}</math> so again using the [[Set theory axioms]] (namely Extensionality) we see <math>a=a'=b'</math> so <math>a=a'</math> and <math>b=b'</math> holds here too. This completes the proof. | ||
| + | {{End Proof}} | ||
| + | {{End Theorem}} | ||
{{Definition|Set Theory}} | {{Definition|Set Theory}} | ||
{{Theorem|Set Theory}} | {{Theorem|Set Theory}} | ||
Revision as of 14:43, 11 March 2015
Kuratowski definition
An ordered pair [math](a,b)=\{\{a\},\{a,b\}\}[/math], this way [math](a,b)\ne(b,a)[/math].
Ordered pairs are vital in the study of relations which leads to functions
Proof of existence
It is easy to prove ordered pairs exist
Suppose we are given [math]a,b[/math] (so we can be sure they exist).
By the axiom of a pair we may create [math]\{a,b\}[/math] and [math]\{a,a\}=\{a\}[/math], then we simply have a pair of these, thus [math]\{\{a\},\{a,b\}\}[/math] exists.
The axioms may be found here
Proof of uniqueness
Before we may write [math](a,b)[/math] we must make sure this is not ambiguous.
Proof that [math](a,b)=(a',b')\iff[a=a'\wedge b=b'][/math]
[math]\impliedby[/math]
Clearly if [math]a=a'[/math] and [math]b=b'[/math] then [math](a,b)=\{\{a\},\{a,b\}\}=\{\{a'\},\{a',b'\}\}=(a',b')[/math] and we're done.
[math]\implies[/math]
Assume [math](a,b)=\{\{a\},\{a,b\}\}=\{\{a'\},\{a',b'\}\}=(a',b')[/math].
If [math]a\ne b[/math] then we must have [math]\{a\}=\{a'\}[/math] and [math]\{a,b\}=\{a',b'\}[/math] (as clearly [math]\{a\}=\{a',b'\}[/math] is false, there are either 2 or 1 elements not contained in [math]\{a\}[/math] that are in [math]\{a',b'\}[/math] - namely [math]a'[/math] and [math]b'[/math])
Clearly [math]a=a'[/math], then [math]\{a,b\}=\{a',b'\}\implies b=b'[/math].
If [math]a=b[/math] then [math](a,a)=\{\{a\},\{a,a\}\}=\{\{a\}\}[/math], we know [math]\{\{a\}\}=\{\{a'\},\{a',b'\}\}[/math] so again using the Set theory axioms (namely Extensionality) we see [math]a=a'=b'[/math] so [math]a=a'[/math] and [math]b=b'[/math] holds here too. This completes the proof.
