by Corry Shores
[Search Blog Here. Index-tags are found on the bottom of the left column.]
[Central Entry Directory]
[Logic & Semantics, Entry Directory]
Partee, Meulen, and Wall
Mathematical Methods in Linguistics
Chapter VIII: Formal Systems, Axiomatization, and Model Theory
8.1: The syntactic side of formal systems
This chapter will examine formal syntactic and semantic systems. In the following we will use recursive definitions to specify sets. With them we will make inductive proofs and form axiomatic systems. We then illustrate the connections between grammars and formals systems.
8.1.1: Recursive Definitions
We will illustrate recursive definitions.
We consider series of letters. We call them "strings."
Now to understand the next term we first ask, what would "a" look like if she looked in the mirror? She would see herself. She and her image would be standing next to each other, as if the mirror were standing between them:
aa
We notice that if we cut this string in half, we get the same thing on both sides,
a and a.
Now consider when string aba sees herself in the mirror. We get
abaaba.
Notice again we may cut this string in half to get two of the same thing:
aba and aba.
This time we see the string
aaabbaaa.
May we cut this string in half to produce mirror images? Yes:
aaab and baaa.
We call these strings "mirror-image strings."
What about
aabaa? This is not a mirror image string, because we cannot divide it into two equally sized pieces, let alone two mirror-image pieces.
Definition:
mirror-image string: a string that may be divided into halves, the right half consisting of the same sequence as the left half but in the reverse order. For example
aaaa, abba, babbab, and bbabbabb
are mirror-image strings, but
babb, aaab, and bab
are not.
We may group things into discrete sets. Then we may give the set as a whole one name. In our cases we will call the set of mirror-image strings:
set M.
We know that
aa
is included in the set of mirror-image strings M. So we will symbolize their inclusion in that set with the symbol ∈ . So to say that
aa
is included in M, we write:
aa ∈ M
Now, we also know that
bb
would be included in M. so
bb ∈ M
But since they are both included, we will use "&" to mean "and."
Together we have:
1) aa ∈ M & bb ∈ M
We will take this as the first line in our formal definition.
Now in algebra we often use variables, such as x and y. These allow us to speak of any possible term that might rightly substitute-in for that variable. In our definition, we will want to speak of all possible terms that could substitute-in for such a variable. This will allow us to show how we may build more complex terms in the set. But note that there are infinitely many possible terms that could be mirror image strings. Just think about the fact that you can keep doubling mirror image strings to produce more that fit the definition:
aabbaa
aabbaaaabbaa
aabbaaaabbaaaabbaaaabbaa
and so on.
This doubling can go on forever. So we cannot actually name every possible term in the set. However, we can still use a "recursive definition" to show how any possible member of the set could be constructed.
So again, we want to talk about variables. And we want to say, "for all possible substitutions for x." Then we would say something about all such substitutions.
We will symbolize "for all possible substitutions for x" as
∀x.
Now finally, we will want to use "if ... , then ..." statements. We wanted to say, "If A, then B" we would use the arrow symbol → and write: "A → B".
Now, returning to our recursive definition, we know that because these are mirror images, the beginning and the end of each have to both be the same letter. So if the string begins with a, it must end with a. And the same for b.
Now, lets consider the variable x. And let's place it between aa and bb. What we get is
axa
and
bxb.
So let's determine the simplest substitutions for x.
Can x be either a or b?
That would produce:
aaa
aba
bab
bbb
All these are odd. So they do not divide evenly into two parts. So instead we need an even number of letters. The smallest even number is 2, so let's look at our options for 2 variables.
aa
ab
ba
bb.
Now let's put them between aa and bb by substituting them for the x in axa and bxb.
aaaa
aaba
abaa
abba
and
baab
babb
bbab
bbbb.
We see that for both axa and bxb, the only two letter substitutions for x that produced mirror images were aa and bb.
These of course are the two we started-with. So the simplest mirror-image strings are aa and bb. And the next simplest are
aaaa
abba
baab
bbbb.
We know that we cannot substitute x with 3 letters, because that would create an odd number, which does not divide equally into two. So what are the possible 6-letter mirror-image strings?
aaaaaa
aabbaa
abbbba
abaaba
baaaab
bbaabb
babbab
bbbbbb
We see then that we still may fit the axa and bxb format. The possible substitutions for x would be:
aaaa
abba
baab
bbbb.
Now in the first case of substitutions for x, we used no more than what we started with: aa and bb. Then we obtained
aaaa
abba
baab
bbbb.
Then in the second case of substitutions for x, we used no more than the above list. We will find that this pattern continues, where to continue to produce new strings, we need only replace xin axa and bxb with whatever we have previously found or constructed in the set.
We also notice in the case of a constructed sequence such as abba, we know that the x for the axa that we used to construct this, which here is bb, also is in the set. And because each internal sequence will have been build from some already in the set, we can say that for sequence in the set, the middle parts (all but the end terms) will also be in the set. For, they are the "building" blocks we used to make that longer sequence.
So we want to define what possible middle parts x belong in set M. So we will say that if middle part x is in set M, then axa and bxb will also be in that set. For this is how we build the sets. We want to say specifically, "First consider all possible substitutions for x. If that substitution for x is in the set of mirror-image strings M, then so too will its next most complex forms, axa andbxb be included in the set." The formal way of writing this is:
2) (∀x) (x ∈ M → (axa ∈ M & bxb ∈ M))
So this will be our second line in our formal definition. The first one was:
1) aa ∈ M & bb ∈ M
This established our "building blocks." These blocks we used to form the basic strings. And, these blocks recur throughout any other possible mirror-image string. So we call this first line the "base" of the recursive definition.
In the second line:
2) (∀x) (x ∈ M → (axa ∈ M & bxb ∈ M))
we showed how we may recurrently instantiate these building blocks so to create more complex strings. So this second step we call the "recursion step" or just the "recursion." It says that "for any string x if x ∊ M is true, then it is also true of the strings formed from x by concatenating an a at both ends or a b at both ends." (182b)
Now, if we only had these two steps, we open possibilities we do not want. For example, we might obtain acca or bllb. But we only want a's and b's. But of course, if we just follow the two steps, we will not have reason to begin to include other letters. Roger Vergauwen explains that really this is a problem in rare cases in mathematics that involve infinite sets. But in the very least, we can say that we want to indicate that there are no more rules that will influence the recursion. This way there can be no doubts.
So we will write a line that restricts these alternate unwanted possibilities. We call it the "restriction":
3. M contains nothing but those members it has by virtue of lines 1 and 2.
All together, we have:
1) aa ∈ M & bb ∈ M
2) (∀x) (x ∈ M → (axa ∈ M & bxb ∈ M))
3) M contains nothingbut those members it has by virtue of lines 1 and 2.
This was enough to give a recursive definition. The basic steps are:
1) base
2) recursion
3) restriction
We find that most recursive steps say that the second clause can only be true under the condition that the first one is true. We calls these if ..., then ... sorts of statements: conditionals. In recursive steps, usually these conditions use the terms being defined in both the antecedent if clause and the consequent then clause. Yet, this makes the definitions seem circular. So consider for example a possible definition for the term "subset":
For any sets A and B, A is a subset of B if and only if every subset of A is also a subset of B.
Now, that is basically what our second line does:
2) (∀x) (x ∈ M → (axa ∈ M & bxb ∈ M))
It says that all the possible substitutions for x belong to M so long as they already belong to M.
However, we avoid this circularity with the base step. The base step provides the conditions for the conditional statement, which makes it no longer conditional in a sense. We already know that the conditions will be fulfilled, and those conditions are already provided. The conditional sentence form just allows us to make more complex forms to re-input back into the conditional sentence, so to produce even more complex sequences.
We know that this definition is not circular, because we can draw inferences from it. So say we want to prove that abaaba and bbaabb are included in the set of mirror-image strings. Let's follow this proof step by step.
We begin with the base step:
1) aa ∈ M & bb ∈ M
Then the recursive step:
2) (∀x) (x ∈ M → (axa ∈ M & bxb ∈ M))
Now, because in step 1 we know that both aa and bb are included in the set of mirror-image strings, we know that individually just aa is included in that set. This is a simplification of step 1 (abbreviated Simp.). So:
3) aa ∈ M 1, Simp
The "1, Simp" means a simplification of line 1.
Now, we will consider aa as a substitution for x in line two, which was:
2) (∀x) (x ∈ M → (axa ∈ M & bxb ∈ M))
So let's plug aa in for x: We can do that, because our second step speaks of "all x's". So this proposition holds universally for any possible instantiation for the variable x. Hence we call the principle allowing us to make this substitution: Universal Instantiation (U.I.)
4) aa ∈ M → (aaaa ∈ M & baab ∈ M) 2, U.I.
The '2, U.I.' means a universal instantiation of line 2.
Now, consider this argument based on a conditional statement.
If it is cloudy, then the sun won't shine.
It is cloudy.
Therefore, the sun won't shine.
When we affirm the if clause antecedent, we thereby affirm the then clause consequent. We call the principle that allows us to make this inference: Modus Ponens (M.P.). So by affirming the antecedent, we obtain no more than the consequent. Thereby we get:
5) aaaa ∈ M & baab ∈ M 3,4 (M.P.)
The "3,4 (M.P.)" means that we used line 3 to affirm the antecedent in line 4, and by Modus Ponens obtained just the consequent.
We again have a conjunction by '&.' So we again like in line 3 simplify line 5 to get:
6) baab ∈ M 5, Simp.
Now, just like in line 4 where we plugged aa into the recursive conditional sentence, we will do so again for baab to obtain:
7) baab ∈ M → (abaaba ∈ M & bbaabb ∈ M) 2, U.I.
Recall that step 4 was
4) aa ∈ M → (aaaa ∈ M & baab ∈ M)
We notice that we took one part of the statement, the baab, and we plugged it back into that very recursive conditional again. So the same step recurred. Hence the recursivity of this definition.
Now, returning to step 7, which was
7) baab ∈ M → (abaaba ∈ M & bbaabb ∈ M) 2, U.I.
We can affirm the antecedent with step 6, this allows us to derive:
8) abaaba ∈ M & bbaabb ∈ M 6,7 M.P
We see that abaaba and bbaabb did not appear in the original definition. However, they resulted from the definition. So we can know that this definition is not circular.
But we need both the base step and the recursive step to make this definition productive.
From:
Partee, Meulen, and Wall. Mathematical Methods in Linguistics. Springer, 1990.
More information at:
No comments:
Post a Comment