Results 1 to 6 of 6

Math Help - Any smart guys here (substitutions)?

  1. #1
    Newbie
    Joined
    May 2011
    Posts
    6

    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    May 2011
    Posts
    6
    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\}
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    May 2011
    Posts
    6
    Quote Originally Posted by emakarov View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    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''.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    May 2011
    Posts
    6
    Quote Originally Posted by emakarov View Post
    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!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: May 12th 2009, 05:59 PM
  2. smart car problem.
    Posted in the Math Topics Forum
    Replies: 3
    Last Post: May 30th 2008, 07:53 AM
  3. Come solve this if u think you are smart=)
    Posted in the Algebra Forum
    Replies: 1
    Last Post: February 21st 2008, 03:23 AM
  4. Fermat, computers, and a smart boy
    Posted in the Math Challenge Problems Forum
    Replies: 10
    Last Post: February 2nd 2006, 01:34 PM
  5. Help Smart People
    Posted in the Statistics Forum
    Replies: 0
    Last Post: April 24th 2005, 07:35 AM

Search Tags


/mathhelpforum @mathhelpforum