by Brian Bosse, Copyright July 21, 2008, all rights reserved. 39 views
Some Conventions
1.The capital letters 'P' through 'Z' with or without numerical subscripts will represent symbolic sentences.
2. A variable is a lower-case italicized Latin letter with or without numerical subscripts.
3. The capital letters 'A' through 'E' with or without numerical subscripts represent name letters.
4.The capital letters 'F' through 'O' with or without numerical subscripts represent predicate letters.
5. Variables (2) and name letters (3) will be called symbolic terms.
Proper Substitution - Name Letter
Definition: A symbolic formula φζ comes from a symbolic formula φα by proper substitution of a letter name ζ for a variable α if φζ is like φαexcept for having occurrences of ζ wherever φαhas free occurrences of α.
This is very abstract, and as such I will try and explain this. The first question I will answer is what it means when we speak of φαhaving free occurrences of α. Consider the following symbolic formula:
∀x(F(x) → G(y))
You will notice that the universal quantifier of x ranges over F(x) but does not range over G(y). If the 'y' were an 'x', then it would. But 'y' is not 'x' so '∀x' cannot range over G(y). As such, G(y) is said to be a free occurrence of y; whereas, F(x) contains a bound occurrence of x. In short, if a quanitfier does not range over a variable, then that variable is free. Let's illustrate this with a couple of examples:
Ex. 1 x is an even number.
If we let 'F' stand for the predicate "is an even number," then the statement above can be symbolically represented as F(x). Now, F(x) is not a proposition because "x is an even number" is not a proposition. The reason for this is because we cannot say F(x) is true or false. F(x) contains a free occurrence of x.
Ex. 2 For all x, x is an even number.
This is symbolized by the following formula: ∀x(F(x)). This statement is clearly false. However, 'x' has been ranged over by the quantifier '∀'. As such, 'x' is bound.
Ex. 3 There exists an x such that x is an even number.
This is symbolized by the formula: ∃(x)F(x). This statement is true. 'x' has been ranged over by the quantifier '∃'. As such, 'x' is bound.
We are now ready to tackle name letter substitution. A proper name letter substitution occurs in a formula φα whenever all free occurrences of α (and only free occurrences of α) are substituted with a name letter. Consider Ex.1 above. If we let A be a name letter, then a proper substitution of F(x) for a name letter is F(A). In our definition above we have,
φ is F
ζ is A
α is x
φα is F(x)
φζ is F(A)
Here is how the definition reads with our example 1 above: A symbolic formula F(A) comes from a symbolic formula F(x) by proper substitution of a letter name A for a variable x if F(A) is like F(x) except for having occurrences of A wherever F(x) has free occurrences of (x). As one can see, all of the free occurrences of x in F(x) have been replaced by A in F(A). As such, F(A) comes from a symbolic formula F(x) by proper substitution.
Here is a little more complicated example of name letter substitution. We let our φx stand for the symbolic formula:
∃(z)(F(x) ∧ G(y)) → ∃(x)(H(x)) ∨ G(x)
Now, let's say that I want to do a proper substitution of the variable 'x' for the name letter 'A' in the above formula. The first thing to do is to identify all of the free occurrences of 'x'. They are F(x) and G(x). H(x) is not a free occurrence of 'x' because H(x) is ranged over by the existential quantifier '∃(x)'. The 'x' in F(x) is free because the existential quantifier '∃(z)' ranges only over the variable 'z'. Now, I just replace the 'x' with 'A' in those two places…
∃(z)(F(A) ∧ G(y)) → ∃(x)(H(x)) ∨ G(A)
This formula stands for our φA and φAis in fact a proper substitution.
-----No comments yet.