연습장

Ex. 1

Existence)
Let [math]\displaystyle{ w }[/math] be any string over an [math]\displaystyle{ \Sigma }[/math].
By the definition, the domain of [math]\displaystyle{ w }[/math] is a finite initial segment of [math]\displaystyle{ \mathbb{N} }[/math].
This means that [math]\displaystyle{ \exist n \in \mathbb{N} }[/math] s.t. w is defined at [math]\displaystyle{ i \leftrightarrow i \lt n }[/math]

Uniquness)
Suppose that [math]\displaystyle{ \exist n,\,\, m }[/math] s.t. both satisfy the condition for the string [math]\displaystyle{ w }[/math].
That means, w is defined at position [math]\displaystyle{ i }[/math] if and only if [math]\displaystyle{ (i \lt n) \land (i \lt m) }[/math].
By definition, [math]\displaystyle{ \{i \in \mathbb{N}|i \lt n\} }[/math] and [math]\displaystyle{ \{i \in \mathbb{N}|i \lt m\} }[/math] are both domain of [math]\displaystyle{ w }[/math], which means they are same set.
So the only way that [math]\displaystyle{ \{i \in \mathbb{N}|i \lt n\} }[/math] and [math]\displaystyle{ \{i \in \mathbb{N}|i \lt m\} }[/math] are same is their endpoints are same. Therefore, [math]\displaystyle{ n = m }[/math].

Hence, there exists a unique natural number [math]\displaystyle{ n }[/math] with the desired property.

Ex. 2

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

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

Hence, there is the a unique empty string [math]\displaystyle{ w }[/math] s.t. [math]\displaystyle{ |w| = 0 }[/math], and we can define [math]\displaystyle{ \epsilon }[/math] as the empty string [math]\displaystyle{ w }[/math]

Ex. 3

[math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math] [math]\displaystyle{ }[/math]