# Math Help - Any smart guys here (substitutions)?

1. ## Any smart guys here (substitutions)?

Hi,

I have a question on how to "combine" substitutions in the sense that there is a dependency between two kinds of substitutions. I'll try to concretise this in an example.

I have a structure consisting of a pair:

$\mathcal{X} := \langle \mathcal{L} \times 2^\mathcal{L} \rangle$ where
$\mathcal{L} := \{a,b,c...,z,aa,bb,...,ab,ac,...\}$
$\mathcal{L}$ is merely a set of labels composed from small letters.

Examples of $\mathcal{X}$ are:

$x_1 = \langle a, \{ b, c, d\}\rangle$
$x_2 = \langle e, \{ f, g, h\}\rangle$
$x_3 = \langle i, \{ j, k, l\}\rangle$
$x_1, x_2, x_3 \in \mathcal{X}$

$\mathcal{Y}$ is the power set of $\mathcal{X}$

$\mathcal{Y} := 2^\mathcal{X}$
$y = \{ x_1\} \cup \{ x_2\} \cup \{x_3\}$
$y \in \mathcal{Y}$

Moreover, there are two types of substitutions, A and B:

$a_1 = \{ a \mapsto aa\}$
$a_2 = \{ e \mapsto ee\}$
$a_3 = \{ i \mapsto ii\}$

$a_1, a_2, a_2 \in \mathcal{A}$

$b_1 = \{ b \mapsto bb, c \mapsto cc, d \mapsto dd \}$
$b_2 = \{ f \mapsto ff, g \mapsto gg, h \mapsto hh \}$
$b_3 = \{ j \mapsto jj, k \mapsto kk, l \mapsto ll \}$

$b_1, b_2, b_3 \in \mathcal{B}$

Substitutions of type A work on the first element of an element of $\mathcal{X}$, while substitutions of type B work on the second element of $\mathcal{X}$.

$\mathcal{S} := 2^{\mathcal{A} \times \mathcal{B}}$
$\mathcal{S}$ represents the dependency between substitutions of type A and B. That is, they are grouped in pairs.

$s = \{ \langle a_1, b_1\rangle, \langle a_2, b_2\rangle, \langle a_3, b_3\rangle \} , s \in \mathcal{S}$

What I wonder is how to define and apply these substitutions correctly to achieve the following:

$y | s \equiv \{ \langle aa, \{ bb, cc, dd \} \rangle\ , \langle ee, \{ ff, gg, hh \} \rangle\ , \langle ii, \{ jj, kk, kk \} \rangle\}$
$y \in \mathcal{Y} , s \in \mathcal{S}$

| represents the action\operator that applies the substitutions correctly. That is, the substitutions of type B (second element of S) is only applied if the substitution of type A (first element of S) is applied.

Any ideas?

2. A small typo in the above result. The result should (obviously) be:

$y | s \equiv \{ \langle aa, \{ bb, cc, dd \} \rangle\ , \langle ee, \{ ff, gg, hh \} \rangle\ , \langle ii, \{ jj, kk, ll \} \rangle\}$

3. What do you want to get: a strict mathematical description, code in some programming language or something else?

I would start by defining the result of applying a substitution of type B to a set.

An important issue is when s = {<a1,b1>, <a2,b2>}, y = {x} and both a1 and a2 are applicable to the first element of x. What happens then?

4. Originally Posted by emakarov
What do you want to get: a strict mathematical description, code in some programming language or something else?

I would start by defining the result of applying a substitution of type B to a set.

An important issue is when s = {<a1,b1>, <a2,b2>}, y = {x} and both a1 and a2 are applicable to the first element of x. What happens then?
Thanks very much for your response! Appreciated!

I'm trying to come up with a concise mathematical notation that describes the "combined" action of the substitutions. That said, I'm not sure how to do this in a "proper" way. Obviously, I could write a textual description telling how the desired result should be, but I prefer a pure mathematical notation with less text. For instance, I'm not sure how to define application of several substitutions which are found in a set. That is, if I have a set of substitutions, how can I apply all of these substitutions to a structure. Let's say

$b = \{a \mapsto\ b, c \mapsto d \}$

Could I do something like this:

$l(x), l \in b$

And does this mean that all substitutions of b are "carried out" resulting in x (where labels are changed).

The case you refer to where two A substititons match the first element of X should not be legal.

5. First, I should note that I encountered the term "substitution" only when a variable occurring in a syntactic expression is replaced by another expression. For example, if E = x^2 = x + 1 and ϴ = [x ↦ 2 + 3] is substitution, then Eϴ = (2 + 3)^2 = (2 + 3) + 1. It is customary to denote substitutions by Greek letters and denote the result of the application by Eϴ or ϴ(E).

Let u range over elements of L and w range over subsets of L. We can identify the set of substitutions A with L x L, i.e., the set of pairs of elements of L, and B with the set of functions from L to L. If f ∊ B and w ⊆ L, it is customary to denote {f(u) | u ∊ w} by f[w].

So, let y ∊ Y and s ∊ S. Define y | s, or s(y), to be

{<a', f[w]> | <a, w> ∊ y, <<a, a'>, f> ∊ s} ∪
{<a, w> | <a, w> ∊ y, <<a, a'>, f> ∉ s for all a', f}.

The second set in the union corresponds to those pairs x whose first element is not subject to a substitution from y, if this is possible. To prove that y | s is well-defined one has to show that it is impossible that <a, w> ∊ y and <<a, a'>, f'> ∊ s, <<a, a''>, f''> ∊ s for a' ≠ a'' or f' ≠ f''.

6. Originally Posted by emakarov
First, I should note that I encountered the term "substitution" only when a variable occurring in a syntactic expression is replaced by another expression. For example, if E = x^2 = x + 1 and ϴ = [x ↦ 2 + 3] is substitution, then Eϴ = (2 + 3)^2 = (2 + 3) + 1. It is customary to denote substitutions by Greek letters and denote the result of the application by Eϴ or ϴ(E).

Let u range over elements of L and w range over subsets of L. We can identify the set of substitutions A with L x L, i.e., the set of pairs of elements of L, and B with the set of functions from L to L. If f ∊ B and w ⊆ L, it is customary to denote {f(u) | u ∊ w} by f[w].

So, let y ∊ Y and s ∊ S. Define y | s, or s(y), to be

{<a', f[w]> | <a, w> ∊ y, <<a, a'>, f> ∊ s} ∪
{<a, w> | <a, w> ∊ y, <<a, a'>, f> ∉ s for all a', f}.

The second set in the union corresponds to those pairs x whose first element is not subject to a substitution from y, if this is possible. To prove that y | s is well-defined one has to show that it is impossible that <a, w> ∊ y and <<a, a'>, f'> ∊ s, <<a, a''>, f''> ∊ s for a' ≠ a'' or f' ≠ f''.
Awesome! I'm so glad you took time to elaborate this. This notation is both concise and intuitive!

Thanks very much!