Set

• อาจจะมีการไปรวมกับ 02 Method of Proofs เช่น Proof By Contradiction พวก Show that ต่าง ๆ

Two Ways of Describing Sets

Extensional Description

1. เขียนแบบแจกแจงสมาชิก ซึ่งเป็นการเขียนแสดงสมาชิกของเซตให้เห็นออกมาเลยว่ามีอะไรบ้าง $$\ce{A}=\{2,4,6,8,10\}$$

Intensional Description

2. เขียนแบบบอกเงื่อนไข เป็นการบรรยาลักษณะ (เงื่อนไข) ของสมาชิกแล้วให้คนอ่านแปลเอาเอง ตัวอย่างเช่น เซต A ด้านบนอาจเขียนแบบบอกเงื่อนไขได้ดังนี้ $$\ce{A}=\{2x \ | \ x\in \mathbb{N} \ , \ 1\le x < 6\}$$ ทั้งนี้ การเขียนเซตแบบบอกเงื่อนไข สามารถเขียนได้หลายแบบขึ้นอยู่กับเงื่อนไขของผู้เขียน

Empty Set

• เซตว่าง คือ เซตที่ไม่มีสมาชิก เขียนแทนด้วยสัญลักษณ์ $\varnothing$
  • เช่น เซตของเลขคู่ที่หารด้วย 2 ไม่ลงตัว

Cardinality

• For any finite set $X$, denote by $|X|$ the number of (distinct) elements of $X$.
  • ทำให้เป็น Set ที่ไม่มีตัวซ้ำกันก่อนนะ! อย่าลืม พลาดตลอดดดดด

Membership

• Write $a\in X$, if and only iff $a$ is a member of set $X$
  • $1\in\{1,2,3\}$
  • $1\notin\{x|\text{ }x\text{ is a positive and even integer\}}$

Equality

• Two set $X$ and $Y$ are equal ($X=Y$), if and only if they have exactly the same elements.
• This is, $X=Y$, if and only if
  1. Every element of $X$ is an element of $Y$
  2. Every element of $Y$ is an element of $X$

Set Inclusion

• A set $X$ is a subset of a set $Y$, denoted by $X\subseteq Y$, if and only if every element of $X$ is an element of $Y$.

Proper Subset

• ก็คือ Subset ธรรมดานี่แหละ (แต่ไม่รวมตัวมันเอง!!) – ซับเซตแท้
• A เป็น สับเซตแท้ (Proper subset) ของ B เมื่อ $\ce{A}\subset\ce{B}$ แต่ $\ce{A}\ne\ce{B}$ (ไม่ใช่เซตตัวมันเอง)
• จำนวนของ Proper Subset เท่ากับ $2^n-1$ (หักตัวมันเองทิ้งไป)

Power Set

• The “power set” of x → The set of all subsets of x
• If $|X|=n$, then $|P(X)|=2^n$

Union, Intersection, Difference

• Let $X,Y$ be sets.
  • $X\cup Y$
    • เซตที่ได้จากการนำสมาชิกจาก A และ B มารวมเข้าด้วยกัน
  • $X\cap Y$
    • เซตของสมาชิกที่มีซ้ำกันทั้งใน A และ B
  • $X - Y$
    • เซตของสมาชิกอยู่ใน A แต่ไม่อยู่ใน B
• อันนี้ก็จินตนาการเป็น Venn diagram เอาก็ได้ ไม่น่ายากอะไร!
  

Disjoint Sets

• $X$ and $Y$ are set to be disjoint, if and only if $X\cap Y=\varnothing$
• Clearly, if $X$ and $Y$ are disjoint, then $X-Y=X$

Universal set (U)

• A universal set ($\mathbb{U}$) is a superset of all the sets we are dealing with. If $\mathbb{U}$ is not explicitly given, it must be inferred from the context.
  • ในการกล่าวถึงเซตใด ๆ จะมีการอ้างอิงกับเซต ๆ หนึ่ง ซึ่งตกลงกันว่าจะไม่กล่าวถึงสมาชิกตัวอื่นที่อยู่นอกเหนือจากเซตนี้ เรียกว่า เอกภพสัมพัทธ์ (Universal Set) เขียนแทนด้วยสัญลักษณ์ $\mathbb{U}$
  • ในกรณีที่ไม่กำหนดเอกภพสัมพัทธ์มาให้ จะถือว่า $\mathbb{U}$ คือ เซตของจำนวนจริง ($\mathbb{R}$)

Set Complement

• $\ce{A'}$ หรือว่า $\ce{A^c}$ คือ เซตของสมาชิกที่ไม่ได้อยู่ใน A (อยู่ข้างนอก A) แต่ยังอยู่ใน Universe อยู่ ดังแผนภาพ
  • หรือจะคิดว่าหมายถึง $\mathbb{U} - \ce{A}$ ก็ได้

Laws

• สามารถใช้ Venn Diagram พิสูจน์ Law เหล่านี้ได้!

Associative Laws (The Grouping is Not Important)

Commutative Laws

• Order in $\cap$ or $\cup$ operations makes no difference.

Distributive Laws

Identity Laws

Complement Laws

Idempotent Laws

Bound Laws

• ถ้าไป $\cup$ กับตัวที่ใหญ่กว่า ก็จะเป็นตัวที่ใหญ่กว่า
• แต่ถ้าไป $\cap$ กับตัวที่เล็กกว่า (อย่างเช่น $\varnothing$) ก็ได้เป็นตัวที่เล็กกว่าทันที

Absorption Laws

Involution Law

De Morgan’s Law for Sets

• อันนี้ก็คล้าย ๆ กับ Break the bar change the sign ($\cap$ → $\cup$)

Cartesian Product

• เป็นเซตของคู่อันดับทั้งหมดที่เป็นไปได้
• จะหาว่ามีกี่คู่อันดับที่เป็นไปได้ ก็ใช้ Probability ง่าย ๆ Choices หน้า $\times$ Choices หลัง
• If $X = \{1, 2, 3\}$ and $Y = \{a, b\}$, then
  • $X \times Y = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}$
  • $Y \times X = {(a, 1), (b, 1), (a, 2), (b, 2), (a, 3), (b, 3)}$
  • $X \times X = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)}$
  • $Y \times Y = {(a, a), (a, b), (b, a), (b, b)}.$
• Tuple is a set of 3 elements

Relation

• A (binary) relation is a set of links that connects elements of two sets.
• Each link is represented as a pair
• Therefore, relation → set of a pair (จริง ๆ ก็คล้าย ๆ Cartesian Product นะ แต่ว่าไม่ได้เอาทุก Possible combination)
  • อาจารย์พูดในห้องจริง ๆ ว่าจะ relate กับ Cartesian Product ยังไง
  • $R_1$ is the subset of $X \times Y$

Formal Definition

A (binary) relation ($R$) from a set $X$ to a set $Y$ is a subset of the Cartesian product $X\times Y$

• ถ้าเต็ม ๆ (Cartesian product) ก็ถือว่าเป็น Relation เหมือนกัน

Notation

If $(x,y) \in {R}$, we write $x\text{ }{R}\text{ }y$

• The domain of $\mathbb{R}$ is the set
  • $\{x \in X | (x,y)\in{R}$ for some $y \in Y\}$
• The range of $\mathbb{R}$ is the set
  • $\{y \in Y | (x,y)\in{R}$ for some $x \in X\}$

A relation from $X$ to $X$ is simply called a relation on $X$

• เวลาโจทย์ถามว่า How many relations from $X$ to $Y$ are there? — คือมันถามประมาณว่า จะมีทั้งหมดกี่ Relation ซึ่ง Relation มันก็เป็น Subset ของ Cartesian product อีกที ดังนั้นก็ตอบจำนวน Subset ไปเลย $=2^n = 2^{|X|\times|Y|}$

Digraph

• Let $R$ be the relation on $X = \{ 1, 2, 3, 4\}$ defined by $(x, y)\in R$ if $x \le y, x, y \in X$. Then
  • $R = \{ (1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4) \}$
    
  • An informative way to picture a relation on a set is to draw its digraph.
    • We’ll discussed in more detail in 07 Graphs
    • For now, we mention digraphs only in connection with relations.)
  • To draw the digraph of a relation on a set $X$, we first draw dots or vertices to represent the elements of $X$.
  • Next, if the element $(x, y)$ is in the relation, we draw an arrow (called a directed edge) from $x$ to $y$.

Basic Types of Relations

Reflexive

• $R$ is called reflexive, iff for each $a \in X, (a,a) \in{R}$
  • if $a\in x$, then $(a,a)\in{R}$

There’s must be a self-loop at every single element.

Symmetric

• $R$ is called symmetric, iff for all $a,b \in X$
  • if $(a,b) \in {R}$, then $(b,a)\in{R}$

Whenever you see a link, you must see reverse of that link!
(Even empty maps is considered symmetric)

Antisymmetric

• $R$ is called antisymmetric, iff for all $a,b \in X$
  • if $(a,b) \in {R}$, and $a\ne b$, then $(b,a)\notin{R}$
  • ที่ต้องมี $a\ne b$ เพราะว่าจะได้ satisfy self-loop is okay

No loop containing two different elements (ทั้งไปและกลับ) → Self-loop is okay
(Even empty maps is considered antisymmetric)

Transitive

• $R$ is called transitive, iff for all $a,b,c \in X$
  • if $(a,b) \in {R}$, and $(b,c)\in {R}$, then $(a,c)\in{R}$
• มันเป็น If-then (Conditional statement) ถ้าไม่มี Link หรือว่าเป็น Empty (maps) relation ไม่ต้อง Check conclusion part แล้ว มันเป็น True เสมอ ถ้างงว่าทำไม Empty maps เป็น Transitive

If there’s a link (from a to b, b to c), there must be a link (from a to c)
(Even empty maps is considered transitive)

• ในข้อสอบอาจจะมีให้ Proof (เวลา True), Disprove (เวลา False)

Partial Order

RAT

• A relation $R$ on a set $X$ is called a partial order*
  • If and only if $R$ is reflexive, antisymmetric, and transitive
  • No cycle other than self-loop!
  • Since a partial order is reflexive, there will be self loop at every element.
• If $x,y\in X$ and either $x \preceq y$ or $y \preceq x$, we say that $x$ and $y$ are comparable.
  • สามารถตอบได้ว่า Element ไหนใหญ่กว่า ถ้ามีลูกศรโยงไป
    • ท้าย ๆ จะใหญ่กว่า ด้านหน้า
• If every pair of elements in $X$ is comparable, we call $R$ a total order.
  

Inverse

• Let $R$ be a relation from $X$ to $Y$. The inverse of R, denoted $R^{-1}$ is the relation from $Y$ to $X$ defined by $$R^{-1}= \{(y, x) | (x, y) \in R \}$$
• $R =\{ (2, 4), (2, 6), (3, 3), (3, 6), (4, 4)\}$ (If $x$ divides $y$)
• $R^{-1} =\{ (4, 2), (6, 2), (3, 3), (6, 3), (4, 4)\}$ (Is divisible by)

Composition

• If we have a relation $R_1$ from $X$ to $Y$ and a relation $R_2$ from $Y$ to $Z$, we can form the composition of the relations by applying first relation $R_1$ and then relation $R_2$.
• Composition of relations generalizes composition of functions. The formal definition follows.
  • Let $R_1$ be a relation from $X$ to $Y$ and $R_2$ be a relation from $Y$ to $Z$. The composition of $R_1$ and $R_2$ , denoted $R_2 ◦ R_1$ , is the relation from $X$ to $Z$ defined by $$R_2 ◦ R_1 = \{ (x, z) | (x, y) \in R_1\text{ and } (y, z) \in R_2 \text{ for some } y \in Y \}$$
• อันนี้ก็คล้าย ๆ Composition ที่เคยเรียนใน Function นั่นแหละ แต่อันนี้มันอยู่ใน Terms ของ Sets เลยงงหน่อย
  • โอเค เข้าใจแล้ว — ก็ถ้าสมมติเราทำ $f ◦ g$ ให้มอง $g$ ก่อน เช่น
    • $g = \{ (1, 2), (1, 6), (2, 4), (3, 4), (3, 6), (3, 8) \}$
    • $f = \{ (2, u), (4, s), (4, t), (6, t), (8, u) \}$
  • ลองมอง $g$ ก่อน $(1,2)$ แล้ว Output คือ 2 มาดู Input ของ $f$ เจอ $(2,u)$ ดังนั้นได้ $(1,u)$ ทำไปเรื่อย ๆ

Pairwise Disjoint Collection of Sets

• Let $S$ be a collection of sets.
  • $S$ is said to be pairwise disjoint, if and only for distinct sets $X,Y$ in $S$, $X$ and $Y$ are disjoint.

Partition

• A partition of a set $X$ is a collection $S$ of subsets of $X$ such that
  1. $S$ is pairwise disjoint, and
  2. $\cup S = X$

Equivalence Relation

RST

• An equivalence relation on a set is a relation that is (เหมือนการเท่ากับ เช่น $3=3$)
  • Reflexive
  • Symmetric
  • Transitive

Equivalence Class