연습장

Ex. 1

Existence)
Let $w$ be any string over an $\mathrm{\Sigma }$.
By the definition, the domain of $w$ is a finite initial segment of $\mathbb{\mathbb{N}}$.
This means that $\mathrm{\exists }n\in \mathbb{\mathbb{N}}$ s.t. w is defined at $i\leftrightarrow i<n$

Uniquness)
Suppose that $\mathrm{\exists }n,m$ s.t. both satisfy the condition for the string $w$.
That means, w is defined at position $i$ if and only if $(i<n)\wedge (i<m)$.
By definition, $\{i\in \mathbb{\mathbb{N}}|i<n\}$ and $\{i\in \mathbb{\mathbb{N}}|i<m\}$ are both domain of $w$, which means they are same set.
So the only way that $\{i\in \mathbb{\mathbb{N}}|i<n\}$ and $\{i\in \mathbb{\mathbb{N}}|i<m\}$ are same is their endpoints are same. Therefore, $n=m$.

Hence, there exists a unique natural number $n$ with the desired property.

Ex. 2

Existence)
By definition, the domain of $w$ is the finite initial segment of $\mathbb{\mathbb{N}}$.
If the domain is $\mathrm{\varnothing }$, then there is no position $i\in \mathbb{\mathbb{N}}$ where the $w$ is defined.
In this situation, the length of the string $w$ is 0.
Hence, there is a string $w$ s.t. $|w|=0$.

Uniquness)
Suppose that there is two sets $u,v$ s.t. $|u|=0,|v|=0$.
Then $u,v$ are not defined at any index, so both are empty relation, subset of $\mathbb{\mathbb{N}}\times \mathrm{\Sigma }$.
So $u,v$ are both empty, which means $u=v$.

Hence, there is the a unique empty string $w$ s.t. $|w|=0$, and we can define $ϵ$ as the empty string $w$

Ex. 3

Let $w$ be any string over an $\mathrm{\Sigma }$.
Existence)
By the definition of $w$, $w$ is defined at any position i s.t. $(i\in \mathbb{\mathbb{N}})\wedge (i\in |w|)$.
Therefore, if $i<|w|$, then $\mathrm{\exists }x\in \mathrm{\Sigma }.(i,x)\in w$.

Uniquness)
By the definition of $w$, relation $w\subseteq \mathbb{\mathbb{N}}\times \mathrm{\Sigma }$ is partial function.
So there is only one output $x\in \mathrm{\Sigma }$ when i is given s.t. $i<|w|\wedge i\in \mathbb{\mathbb{N}}$.

Hence, For all strings $w$ and for all $i\in \mathbb{\mathbb{N}}$, if $i<|w|$, then there exists a unique $x\in \mathrm{\Sigma }$ s.t. $(i,x)\in w$.

Ex. 4

Existence)
$|w|=1$ means that the domain of $w$ is $\{1\}$.
So, let relation $w$ be $w=\{(1,x)\}\subseteq \mathbb{\mathbb{N}}\times \mathrm{\Sigma }$, s.t. $x\in \mathrm{\Sigma }$.
First, $w$ is a partial function, since for the input 1, there is only one output value.
Second, the domain of $w$ is $\{1\}$, which is the finite initial segment of $\mathbb{\mathbb{N}}$. Hence, there is $w$ which satisfy given proposition.

Uniquness)
Suppose $u,v$ are string, and $(|u|=|v|=1)\wedge (u$@$0=v$@$0=x,s.t.x\in \mathrm{\Sigma })$ Then, the domain of both string is $\{1\}$, and the alphabet corresponding to index 0 is $x$ for both string. Hence, $u=v=\{(1,x)\}$.

Thus, for every $x\in \mathrm{\Sigma }$, there exists a unique string $w$ s.t. $|w|=1$ and $w$@$0=x$.

Ex. 5

$uv=\{(i,x)|(i,x)\in u\}\cup \{($$|$$u$$|$$+j,y)|(j,y)\in v\}$

Ex. 6

(a)
Let $ϵ=\mathrm{\varnothing }$.
By the definition, $uϵ=\{(i,x)|(i,x)\in u\}\cup \{($$|$$u$$|$$+j,y)|(j,y)\in \mathrm{\varnothing }\}=\{(i,x)|(i,x)\in u\}\cup \mathrm{\varnothing }=\{(i,x)|(i,x)\in u\}=u$
In the same way, $ϵu=\{(i,x)|(i,x)\in \mathrm{\varnothing }\}\cup \{($$|$$\mathrm{\varnothing }$$|$$+j,y)|(j,y)\in u\}=\mathrm{\varnothing }\cup \{(j,y)|(j,y)\in u\}=\{(j,y)|(j,y)\in u\}=u$

(b)
$(uv)w=(\{(i,x)|(i,x)\in u\}\cup \{($$|$$u$$|$$+j,y)|(j,y)\in v\})\cup \{($$|$$uv$$|$$+k,z)|(k,z)\in v\}$
$=uvw=\{(i,x)|(i,x)\in u\}\cup \{($$|$$u$$|$$+j,y)|(j,y)\in v\}\cup \{($$|$$uv$$|$$+k,z)|(k,z)\in v\}$
$=u(vw)=\{(i,x)|(i,x)\in u\}\cup (\{($$|$$u$$|$$+j,y)|(j,y)\in v\}\cup \{($$|$$uv$$|$$+k,z)|(k,z)\in v\})$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$ ${\displaystyle }$