集合論/關係

有序對

為了定義集合上的關係，我們必須有一個有序對的概念，而不是配對公理給出的無序對。為了對有序對有一個嚴格的定義，我們旨在滿足一個重要的性質，即對於集合a,b,c和d中的元素，$(a,b)=(c,d)\iff a=c\ \wedge \ b=d$.

就其本身而言，有許多方法可以定義有序對以滿足此屬性。然後定義是$(a,b)=\{\{a\},\{a,b\}\}$。（這只是一個定義或約定，對於集合論可能有用。）

定理

$(a,b)=(c,d)\iff a=c\ \wedge \ b=d$

證明

如果$a=c$和$b=d$，則$(a,b)=\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}=(c,d)$.
現在，如果$(a,b)=(c,d)$，則$\{\{a\},\{a,b\}\}=\{\{c\},\{c,d\}\}$。然後$\cap \{\{a\},\{a,b\}\}=\cap \{\{c\},\{c,d\}\}$，所以$\{a\}=\{c\}$和$a=c$.
因此，我們有 $(a,b)=(a,d)$。因此，$\cup \{\{a\},\{a,b\}\}=\cup \{\{a\},\{a,d\}\}$，這意味著 $\{a,b\}=\{a,d\}$。

如果 $a=b$，我們有 $\{b\}=\{b,d\}$，因此，$d\in \{b\}$，所以 $b=d$。

如果 $a\neq b$，請注意 $b\in \{a,d\}$，所以 $b=d$

關係

利用有序對的定義，我們現在引入二元關係的概念。兩個集合的笛卡爾積是 $A\times B=\{(a,b)\mid a\in A\wedge b\in B\}$，

二元關係最簡單的定義是有序對的集合。更正式地說，如果 $z\in R\rightarrow z=(x,y)$ 對於某些x,y，則集合 $\ R\$ 是一個關係。我們可以簡化符號並寫成 $(x,y)\in R$ 或者簡單地 $xRy$。

我們給出一些在談論關係時使用的有用集合定義。

• 集合A 是源，B 是目標，其中 $R\subset A\times B.$
• 關係R 的定義域定義為 ${\mbox{dom}}\ R=\{x\in A\mid \exists y,(x,y)\in R\}$，或者包含在R 中的有序對的初始成員的集合。
• 關係R 的值域定義為 ${\mbox{ran}}\ R=\{y\in B\mid \exists x,(x,y)\in R\}$，或者包含在R 中的有序對的所有最終成員的集合。
• 域和值域的並集，${\mbox{field}}\ R={\mbox{dom}}\ R\cup {\mbox{ran}}\ R$，稱為R的域。
• 如果 ${\mbox{field}}\ R\subseteq X$，則關係R是集合X上的關係。
• R的逆或反關係是集合 $R^{T}=\{(y,x)\mid (x,y)\in R\}$
• 集合E在關係R下的像定義為 $R[E]=\{y\in {\mbox{ran}}\ R\mid \exists x\in E,(x,y)\in R\}$。
• 集合F在關係R下的原像是F在R^T下的像，或者 $R^{T}[F]=\{x\in {\mbox{dom}}\ R\mid \exists y\in F,(x,y)\in R\}$。

親屬關係叔叔和阿姨表明，存在關係父親和兄弟姐妹的組合。這樣的組合表達了相對乘法

我們可以組合兩個關係R和S，形成一個關係 $S\circ R=\{(x,z)\mid \exists y,(x,y)\in R\wedge (y,z)\in S\}$。所以 $xS\circ Rz$意味著存在某個y，使得 $xRy\wedge ySz$。

基準二元關係

1. A上的恆等關係，$I_{A}=\{(a,b)\mid a,b\in A,a=b\}$
2. 全關係或集合，其中A的每個元素都與A的每個其他元素相關。符號：，$A\times A$寫為 $A^{2}.$

以下屬性可能對集合X上的關係R成立，也可能不成立

• 如果 $xRx$對X中的所有x成立，則R是自反的。
• 如果 $xRy$意味著 $yRx$對X中的所有x和y成立，則R是對稱的。
• 如果 $xRy$ 和 $yRx$ 同時成立，則意味著對於 X 中的所有 x 和 y，$x=y$。
• 如果 $xRy$ 和 $yRz$ 同時成立，則意味著對於 X 中的所有 x、y 和 z，$xRz$ 成立。
• 如果 R 的定義域是 A，源是
• 如果 xRy 和 xRz 同時成立，則意味著 y = z。
• 既是全關係又是單值關係的關係稱為 函式。

異構關係

當 A 和 B 是不同的集合時，該關係稱為 異構關係。然後，單個集合 A 上的關係稱為 同構關係。

設 U 是給定上下文中的一個論域。根據冪集公理，存在一個包含所有 U 子集的集合，稱為 U 的冪集，記為 ${\mathcal {P}}(U).$

集合成員關係 $x\ \in \ A,\ \ A\subseteq U$ 是一個常用的異構關係，其中定義域是 U，值域是 ${\mathcal {P}}(U).$

集合成員關係的逆關係用反射成員符號表示： $A\ \ni \ x.$

作為一個練習，證明從 A 到 B 的所有關係都是 $A\times B$ 的子集。

函式

定義

函式可以被定義為一種特殊的關聯關係。我們定義一個偏函式 $f:X\rightarrow Y$ 作為從集合 $X$ 到另一個集合 $Y$ 的某種對映，它為每個 $x\in X$ 最多 對映一個 $y\in Y$。或者，f 是函式當且僅當 $f\circ f^{-1}\subseteq I_{Y}$

如果對於每個 $x\in X$，$f$ 正好 對映一個 $y\in Y$，那麼 $f$ 被稱為函式。在討論函式時，通常使用以下定義。

• 如果 $f\subseteq X\times Y$ 並且 $f$ 是一個函式，那麼我們可以用 $f:X\to Y$ 來表示它。集合 $X$ 被稱為定義域，集合 $Y$ 被稱為值域。
• 對於函式 $f:X\to Y$，元素 $x\in X$ 的像是 $y\in Y$，使得 $f(x)=y$。或者，我們可以說 $y$ 是 $f$ 在 $x$ 處取值。
• 對於一個函式 $f:X\to Y$，集合 $A$ 在 $X$ 中的 _像_ 是集合 $\{y\in Y:f(x)=y{\mbox{ for some }}x\in A\}$。這個集合用 $f(A)$ 表示。注意不要把它與 $f(x)$（對於 $x\in X$）混淆，後者是 $Y$ 中的一個元素。
• 函式 $f:X\to Y$ 的 _值域_ 是 $f(X)$，即所有滿足 $f(x)=y$ 的值 $y\in Y$，其中可以找到一個 $x\in X$。
• 對於一個函式 $f:X\to Y$，集合 $B$ 在 $Y$ 中的 _原像_ 是集合 $\{x\in X:f(x)\in B\}$。它用 $f^{-1}(B)$ 表示。

函式的性質

一個函式 $f:X\rightarrow Y$ 被稱為滿射或映上，如果對於每個 $y\in Y$，都存在一個 $x\in X$ 使得 $f(x)=y$。很容易證明一個函式是滿射的充要條件是其陪域等於其值域。它被稱單射或一對一，如果不同的 $X$ 元素被對映到不同的 $Y$ 元素，也就是說 $f(x)=f(y)\Rightarrow x=y$。既是單射又是滿射的函式直觀地稱為雙射。

函式的複合

給定兩個函式 $f:X\rightarrow Y$ 和 $g:Y\rightarrow Z$，我們可能對先對某個 $x\in X$ 求f的值，然後對 $f(x)$ 求g的值感興趣。為此，我們定義這兩個函式的複合，記作 $g\circ f$，定義為

$(g\circ f)(x)=g(f(x))$

注意，這兩個函式的複合將 $X$ 中的元素對映到 $Z$ 中的元素，因此我們會寫成 $g\circ f:X\rightarrow Z$。

函式的反函式

如果存在一個函式 $g:Y\rightarrow X$ 使得對於 $f:X\rightarrow Y$，$g\circ f=I_{X}$，我們稱 $g$ 為 $f$ 的左逆。如果存在一個 $f$ 的左逆，我們說 $f$ 是左可逆的。類似地，如果存在一個函式 $h:Y\rightarrow X$ 使得 $f\circ h=I_{Y}$，那麼我們稱 $h$ 為 $f$ 的右逆。如果存在這樣的 $h$，我們說 $f$ 是右可逆的。如果存在一個既是 $f$ 的左逆又是 $f$ 的右逆的元素，我們稱這樣的元素為 $f$ 的逆，並用 $f^{-1}$ 表示。注意不要將它與 f 的原像混淆；f 的原像總是存在的，而逆可能不存在。以下定理的證明留作習題。

定理： 如果一個函式既有左逆 $g$ 也有右逆 $h$，那麼 $g=h=f^{-1}$。

定理： 一個函式可逆當且僅當它是雙射的。