目錄
簡介
 set表示
 屬於、包含
 power set
交集、聯集、差集 Cartesian product cardinality

簡介

set(集合)是數學上用來放置任何東西的抽象概念
因此set只在乎元素有無，並不紀錄順序、數量

比喻而言，“盒子”(set)放置"物品”(element)
並且"盒子"也是"物品”，所以set也可以放進set裡

Set表示法

set表示法就是紀錄"盒子裡有甚麼"的方法

法I: 列舉法

如其名，直接列舉所有甚麼元素
舉例:
桌上 = {飲料,電腦,檯燈,鍵盤,滑鼠}
S = {a,b,c}

法II: set build notation

依其給定性質造出set
舉例:
桌上 = {東西 | 在我桌上的東西 }
座標平面 = {(x,y)| x,y $\in$ R }
正整數 = {x | x $\in$ N}

特別地，空集合 { }記為 $\phi$

Ex1:  
{1,2,3} = {2,3,1} = {1,1,2,3}   
因為set不在乎數量與順序，上面三個集合都是放著1,2,3的盒子      

Ex2:
S = {{1},{2}}  是一個set 
{S} = {{{1},{2}}}也是一個set

屬於、包含

屬於: 元素-集合

表達某元素是否在set中
記做 $a \in \{a\}$

舉例而言
桌上 = {飲料,電腦,檯燈,鍵盤,滑鼠}
則
飲料 $\in$ 桌上
電腦 $\in$ 桌上
但離散數學課本 $\notin$ 桌上

演算法看世界

def isInSet(object,set):
  for element in set: 
    if element == object :
       return "object is in set"
  return "object is NOT in set"

時間複雜度是O(N)，N是set的cardinality

包含: 集合-集合

表達某個集合的元素是不是都在另一個集合裡
記作 A $\subseteq$ B

比如電腦組 = {電腦、鍵盤、滑鼠}
冰箱 = {飲料、水果}
桌上 = {飲料,電腦,檯燈,鍵盤,滑鼠}
則電腦組 $\subseteq$ 桌上
但冰箱 $\not\subseteq$ 桌上
因為水果這個元素不屬於桌上這個集合

邏輯看世界
$A \subseteq B \leftrightarrow \forall X \in A \Rightarrow X \in B$
證明時邏輯很好用
演算法看世界

def isSubset(setA,setB):
  for elementA in setA: 
	 if isInSet(elementA,setB) == "object is NOT in set":
	 	return "setA is NOT a subset of setB"
  return "setA is a subset of setB"

時間複雜度是O(N*M)，N,M是兩個set的cardinality

Note:

可見"屬於"可以定義"包含”，並且"包含"檢查的時間是"屬於"的N倍
屬於是一種檢查"存在"的感覺，一發現存在就完成運算
相對的，包含是一種檢查"不存在"的感覺
套用上面的演算法可以發現， $\phi$ 包含於任何集合，因為他沒有任何元素可以被發現"不存在”

Ex1

完成以下是非題
$\phi\in\phi$ ?
$\phi\subseteq\phi$ ?
$\phi\in\{\phi\}$ ?
$\phi\subseteq\{\phi\}$ ?
$\{\phi\}\in\{\phi\}$ ?
$\{\phi\}\subseteq\{\phi\}$ ?

答案由上而下為:
False 因為右側集合內沒有空集合
True 因為左側集合內沒有找到不在右側集合內的東西
True 因為右側集合內有空集合
True 因為左側集合內沒有找到不在右側集合內的東西
False 因為右側集合內沒有{空集合}
True 因為左側集合只有一個元素，並且在右側集合內找的到

真子集 (proper subset)

即為子集扣除集合相等的情況，子集與真子集的關係，可以用小於等於與小於來理解
記作 $A \subset B $

集合相等

若要說明兩個集合相等，可以使用下列性質
$ A \subseteq B$ AND $B \subseteq A \Rightarrow A = B $

意即兩者互為對方子集，則兩者相等

舉例說明
桌上 = {電腦,鍵盤,滑鼠}
電腦組 = {鍵盤,滑鼠,鍵盤}

則因為
(=>)
桌上所有元素都在電腦組裡
(<=)
電腦組所有元素都在桌上
所以桌上這個集合與電腦組這個集合相等

power set

定義 P(S) = {S的所有子集} 也就是S的所有子集合，所成的集合

如 A = {1,2,3}
則P(A) = {{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

Some Fact:

空集合一定屬於P(A)，空集合也一定是任意集合的子集合，所以空集合屬於也包含於任意集合的power set
經過power set ，集合數量會暴增成 2的指數^(元素個數)

交集、聯集、差集

交集 (intersection)

聯集 (union)

差集 (difference)

延伸: 對稱差集(symmetric difference)

卡氏積

Cardinality

用於表示set抽象的"大小”
我們用元素個數來定義有限大小set的cardinality

記做|S|

比如 |{飲料,電腦,檯燈,鍵盤,滑鼠}| = 5
但注意， |{ { { 1 },{ 2 } } }| = 1 ，因為裡面只有 { { 1 },{ 2 } }一個東西

並且| $\phi$ |=0 也符合直覺

Ex1:

請用set build notation 表達 D = {1,1,2,2,3,3,4,5} ，並寫出D 的cardinality
Ans:
$D = \{x \in Z^+\ |\ x<6 \}$
|D| = 5 ，因為去重複後只有5個元素

Ex2:

求以下Cardinality
$1.\ \phi $
$2.\{\phi\}$
$3.\{\{\phi\}\}$
答案依序為 0,1,1

Little Cube`s box

Set定義與基本運算

簡介