4th Sept., 2022

# Settings

• People mountain people sea

• P = {🧕,👩‍⚕️,👷,💂‍♀️,🕵️‍♂️,👨‍🌾,👩‍🍳,…}

• belongs to (∈)

1. 👨‍🔬 ∈ P
2. 🐢 ∉ P

# What is function?   need better words to describes things what about inverse functions?

# Name list

Z M S G
surname given name

Yeung Joe

# Two ways to write sets

Goal: To write a set of all persons with surname “李”

• List:

L = {(李,崔牛), (李,鹵味), (李,老竇), (李,老表), (李,腦細), (李,老友), (李,老板)}

• Condition:

L = {🏃‍♂️ ∈ P | 🏃‍♂️ with surname “李”}

• ordered pair: (a,b)

(歐陽,李) ≠ (李,歐陽)

• subset (⊆/⊂): LP

L is contained in P.
ℹ️ I prefer using ‘⊆’.

• superset (⊇/⊃): PL

• empty set (∅): a set that has no element.

# ETV

• {🐢,🦆,😸,🐷,😸,🐢,🦆} = {🐢,🦆,😸,🐷}

# set operations ## union (∪)

• L₁ = {🏃‍♂️ ∈ P | 🏃‍♂️ with surname “Li”}
• L₂ = {🏃‍♂️ ∈ P | 🏃‍♂️ with surname “Lee”}
• L₁ ∪ L₂ = {🏃‍♂️ ∈ P | 🏃‍♂️ ∈ L₁ or 🏃‍♂️ ∈ L₂} = L
• Observation: L₁ ⊆ L and L₂ ⊆ L
• Exercise: write another set union using the surname “Wong”

## intersection (∩)

• J = {(袁,尼姑), (李,老師), (容,海歸), (李,老板), (李,腦細)}
• L = {🏃‍♂️ ∈ P | 🏃‍♂️ with surname “李”}
• JL = {🏃‍♂️ ∈ P | 🏃‍♂️ ∈ J and 🏃‍♂️ ∈ L} = {(李,老師), (李,老板), (李,腦細)}
• Observation: JLJ and JLL

## complement (c)

• Lc = {🏃‍♂️ ∈ P | 🏃‍♂️ ∉ L} = {🏃‍♂️ ∈ P | 🏃‍♂️ whose surname is NOT “李”}

## difference (\)

• J \ L = {🏃‍♂️ ∈ P | 🏃‍♂️ ∈ J and 🏃‍♂️ ∉ L} = {(袁,尼姑), (容,海歸)}
• Lc = P \ L
• Observation: J = (JL) ∪ (J \ L)

# Cartesian product # Logical AND (∧)

Example: Save (Ctrl + S)

Ctrl S Ctrl + S
p q pq
T T T
T F F
F T F
F F F

# Logical OR (∨)

Example: digit key (e.g. 1 in numpad or above alphabets)

numpad 1 alphabet 1 enter 1
p q pq
T T T
T F T
F T T
F F F

# Implication (⟹)

## Example 1

entered Univ through JUPAS attended secondary school entered Univ through JUPAS ⟹ attended secondary school example
me
who?
IB, GCE A Level

# Implication (⟹)

## Example 2

Promise: win Mark Six (六合彩) ⟹ treat you to dinner in a seafood restaurant

P bought Mark Six? bill on me? promise kept?
👩‍🍳
👮
👨‍🌾
👨‍💻

👨‍💻: I don’t buy Mark Six, so I don’t have to spring for your dinner. 😛

set of persons who kept their promise = {🏃‍♂️ ∈ P | 🏃‍♂️ kept his/her promise} = {👩‍🍳, 👨‍🌾, 👨‍💻}

# Implication (⟹) and subsets

p q pq
T T T
T F F
F T T
F F T

Recall:

• L₁ = {🏃‍♂️ ∈ P | 🏃‍♂️ with surname “Li”}
• L = {🏃‍♂️ ∈ P | 🏃‍♂️ with surname “李”}
• Observation:
• L₁ ⊆ L
• 🏃‍♂️ ∈ L₁ ⟹ 🏃‍♂️ ∈ L
• Exercise: show that for any set A, ∅ ⊆ A.

# Implication (⟹)

## To prove a “⟹” statement

### Direct way

1. Assume the premise p is true.
2. Show that the conclusion q is true.

# Implication (⟹)

## To prove a “⟹” statement

Example: solve Sudoku (數獨) by guessing.

 7 4 6 9 5 2 3 6 9 5 2 7 8 2 3 7 5 6 9 8 2 3 5 7 6 9 5 6 9 2 8 7 1 7 4 6 9 8 2 3 5 3 6 7 4 8 2 4 2 6 7 9 8 7 1 2 6
 7 4 18 18 6 9 5 2 3 6 9 5 2 34 13 7 14 8 2 3 7 5 6 9 14 8 2 3 14 5 7 14 6 9 5 6 9 2 8 7 14 1 7 4 6 9 8 2 3 5 3 6 7 4 8 2 4 2 6 7 9 8 7 1 2 6
 7 4 6 9 5 2 3 6 9 5 2 7 8 2 3 7 5 6 9 8 2 3 5 7 6 9 5 6 9 2 8 7 1 7 4 6 9 8 2 3 5 3 6 7 4 8 2 4 2 6 7 9 8 7 1 2 6
• guess: R1C3 = 8
• →←: R2C6 = ø
1. p True
2. p ∧ ~q False
3. so ~q False (i.e. q True)

Sudoku source

# Wiki’s Function definition

• ∀: for all
• ∃: there exists

A function f: AB is a subset of A × B such that

 right-unique (用情專一) 🧑❤🦸‍♀️ ∧ 🧑❤🦹 ⇒ 🦸‍♀️ = 🦹 ∀ a ∈ A, ∀ b ∈ B, ∀ b’ ∈ B, ((a,b) ∈ f ∧ (a,b’) ∈ f) ⟹ b = b’ total (冇單身狗) ∀ 🧑 ∈ A, ∃ 👩 ∈ B : 🧑❤👩 ∀ a ∈ A, ∃ b ∈ B : (a,b) ∈ f The domain of f is A.

# Domain, codomain and range In the picture,

• the domain of f is A = {👷,👨‍🌾,👨‍💻,👨‍💼,👨‍⚖️}
• the codomain of f is B = {🧕,👮‍♀️,👩‍🎤,👩‍🏫,👩‍✈️,👸}
• the range of f is f[A] = {🧕,👩‍🎤,👩‍🏫,👩‍✈️}.

# Injective functions and Surjective functions

 injective function (女版用情專一) 👩‍💻❤👩 ∧ 👷❤👩 ⇒ 👩‍💻 = 👷 ∀ a ∈ A, ∀ a’ ∈ A, ∀ b ∈ B, ((a,b) ∈ f ∧ (a’,b) ∈ f) ⟹ a = a’ 📝 To prove that a function f is injective, we assume that f(a) = f(a’), then we show that a = a’. surjective function (冇單身狗乸) ∀ 👩 ∈ B, ∃ 🧑 ∈ A : 🧑❤👩 ∀ b ∈ B, ∃ a ∈ A : (a,b) ∈ f 📝 To prove that a function f is surjective, we pick an arbitrary element b in the codomain B, then we try to find an element a in the domain A such that f(a) = b. # Bijective functions and inverse functions

A function is bijective is it is both injective and surjective.

1. surjective function (冇單身狗乸)

Given 👩 ∈ B. You can find a 🧑 ∈ A so that 🧑❤👩.

2. injective function (女版用情專一)

You can’t have two different 🧑 & 👦 such that 🧑❤👩 & 👦❤👩. They must been the same person. (represented by 🧑)

If we have a bijective function f : AB defined by f : 🧑 ↦ 👩, then we can define an inverse function f⁻¹ : 👩 ↦ 🧑.

# Comments and critiques

Field medalist Shing-Tung Yau (丘成桐) has emphasized the importance of asking good questions (not in the textbook).