0
$\begingroup$

Let's say we have some given schema within a logical system which is such that there are an indefinite number of variables given (whether this is an axiom-schema or a wff-schema or something else is irrelevant).

So, for example, let's say we had a schema, something like: ($x_1$,$x_2$,$x_3$,...,$x_n$) and it was specified that the $x_i$'s are such and such (let's just say they are positive integers).

The question is how does one define what an instance of this schema is/would it even be necessary?

I can't even recall the first time I had seen the use of a letter like 'n' in $x_n$ come into play nor can I recall of any mathematical/logical texts detailing precisely what exactly its role is..even though we all understand it.

The point being that while we understand that (2,82,523,5,32) would be an instance of the schema, we understand this only because we already know that the '...,$x_n$' in the schema tells us that an instance will be such that there are a finite number of positive integers, each of which are separated by a comma...but as to how many there will be, well this is undetermined. (Although, a question could arise of whether the schema says that there must be at least 3 positive integers)

Would this information need to be laid out in the presentation of the particular system and if so, what would be the most rigorous way? Any example texts?

Also, while trying to look up an answer to this question I came across this: https://books.google.com/books?id=aJTTBwAAQBAJ&pg=PA101&lpg=PA101&dq=logic+algorithm+schema&source=bl&ots=Q2W1MA7U_e&sig=yipc1SAAGnGPrPtV9fXA6zV5V0U&hl=en&sa=X&ved=0ahUKEwjW0LaC68HOAhUGbB4KHcsPAzsQ6AEIITAA#v=onepage&q=logic%20algorithm%20schema&f=false

On page 102 the author talks of "schema-variables" and "wff-schemas." Are these common terms/are there any other texts on them anywhere?

Basically, the question can be summed up like this:

Let's assume we have a formal system where a wff will be defined in the following way (note, that these wffs may seem useless is irrelevant, the point has to do with how to define an instance of a particular kind of schema):

"Any instance of the following schema is a wff

($x_1$,$x_2$,$x_3$,...,$x_n$)

where the $x_i$'s are positive integers."

The question is whether that would be an adequate definition of a wff for the system or whether one would need to define "instance" more precisely, and if so how would that be done?

And my reference request has to do with texts dealing with a systemic logical approach to the usage of letters when presenting an undermined number of variables.

Thanks

$\endgroup$
1
$\begingroup$

Good question. The reason you're confused is that many texts do not carefully distinguish between the strings in the formal system itself and the expressions in the meta-system. If you know basic programming, the string literal "x[n]" is not the same as "x["+n+"]". Even if you don't, you still need to understand that analysis of any formal system is always done in some meta-system that understands string manipulation. In the meta-system we can talk about which strings are wffs over the formal system. For example if $α,β$ are wffs then $\def\t{\text}\def\str#1{{``\t{#1}\!"}}$$α \cdot \str{$\land $} \cdot β$ is also a wff, where "$\cdot$" here denotes concatenation and string literals are enclosed in quotes. Note clearly that $α,β$ are objects in the meta-system, and $\str{$\land$}$ also is an object in the meta-system. Technically it is incorrect to say that $α \land β$ is a wff! But texts do that all the time because it is highly inconvenient to have quotation everywhere. $\def\nn{\mathbb{N}}$

But that really is the key issue. For example a lot of texts can even say things like "Let $α = t=u$." where $t,u$ are terms. That is utterly confusing to students. To be technically precise it should be "Let $α = t \cdot \str{=} \cdot u$.". The first equality symbol is the (definitional) equality in the meta-system, while the second equality symbol is merely a symbol in the formal system being studied. Same for schemas. For your example, $\str( \cdot x_1 \cdot \str, \cdot x_2 \cdot \ \cdots \ \cdot \str, \cdot x_n \cdot \str)$ is a wff for any positive integers $x_1,x_2,...,x_n$. Now this should get the point clearly across but is still imprecise.

To make the schema precise we need a recursive definition, but it is precisely your imprecision that makes it impossible for me to know what your base cases are, namely do you allow $\str{()}$ as a wff? I'll omit that special case. Also, we will need some sort of encoding, because positive integers are in the meta-system and are not symbols. In PA for example every natural number can be encoded as a term by using the constant symbol $\str1$ and the function symbol $\str+$ (and bracket symbols if needed). Let $c(x)$ be the string over the formal system that encodes $x$ for any given $x \in \nn$. Then we define that $α$ is a csv-wff iff either $α = c(x)$ for some $x \in \nn_+$ or $α = β \cdot \str, \cdot c(x)$ for some csv-wff $β$ and $x \in \nn_+$, and then define that $α$ is a tuple-wff iff $α = \str( \cdot β \cdot \str)$ for some csv-wff $β$.

Note that the above definition is sufficient to allow you to prove various properties about tuple-wffs, but it does not prevent every string from being a tuple-wff! So to really capture that, you need the following. Let $S_0 = \{ c(x) : x \in \nn_+ \}$. For each $k \in \nn$ let $S_{k+1} = \{ α \cdot \str, \cdot c(x) : α \in S_k \land x \in \nn_+ \}$. Now define that $α$ is a tuple-wff iff $α = \str( \cdot β \cdot \str)$ for some $β \in \bigcup_{k\in\nn} S_k$. This is now a complete rigorous definition of your schema, but as you can see it is also completely ridiculous in complexity, which is one obvious reason why nobody does it explicitly.

Unfortunately, I don't know of any text that makes the distinction described above absolutely clear. Rautenberg in A Concise Introduction to Logic only does so for the equality symbol, stating " Note that the boldface symbol is taken as a basic symbol; simply taking $=$ could lead to unintended mix-ups with the metamathematical use of the equality symbol $=$". Suffice to say that students who don't understand the distinction wouldn't grasp what this is about either.

If all symbols in the meta-system are different from those in the formal system under study, then one could unambiguously parse any given statement, by adding quotes and string concatenation appropriately. The symbols used for objects in the meta-system are called meta-variables. A schema is a list (in the meta-system) of strings (in the formal system). An axiom schema is a schema of axioms, such as the induction schema for PA or another system of arithmetic, or the comprehension schema for ZFC or another set theory. A theorem schema is a schema of theorems, such as the transfinite recursion theorem schema for ZFC. You also see "algorithm schema" in the book you cite, meaning a list of algorithms (as defined in the meta-system). And schema-variables are meta-variables used to define a schema. These terms in bold are indeed common terminology in mathematical logic and set theory.

$\endgroup$
  • $\begingroup$ Having skimmed through this, it seems like a great answer, thanks. Though, I won't be able to spend time on it until later today. I'll respond more then. $\endgroup$ – Boolean_functions Aug 15 '16 at 12:31
  • $\begingroup$ @Boolean_functions: Sure; feel free to ask for clarification on any particular point. $\endgroup$ – user21820 Aug 15 '16 at 12:32
  • $\begingroup$ So, I'm with you until the 3rd paragraph. First, good point in regards to the ambiuguity as to what counts as a wff I was aware that a case of "()" might be interpreted as a wff, but only addressed ambiguity issues like that through the part where i brought up how one might want to argue that there must be at least 3 positive integers to constitute a wff). So to clarify, what I had in mind for this example was that a wff would need at least 1 positive integer. So "()" is no wff, but "(43)" would be. $\endgroup$ – Boolean_functions Aug 15 '16 at 23:45
  • $\begingroup$ I am a bit confused on why you say "also we will need some sort of encoding, because positive integers are in the meta-system and are not symbols." Though I didn't mention it, I was envisioning that the grammar of the example-system was in fact the set of all positive integers, as well as the auxillary symbols consisting of the left-paranthesis, right-paranthesis, and comma. Wouldn't the positive integers be part of the object language and the $x_i$'s in ($x_1$,$x_2$,$x_3$,...,$x_n$) be the meta-variables? $\endgroup$ – Boolean_functions Aug 15 '16 at 23:46
  • $\begingroup$ Unless do you mean that since there are positive integers within the subscripts of the meta-variables, that this might cause some issues, and so we need to use some sort of encoding? But then in regards to this encoding, I am lost a bit. Is what c(x) denotes part of the object langauge? Or does it denote a string which encodes something which is itself part of the object language? The whole encoding part confuses me, actually. And I'm not understanding why it's necessary or even what exactly you're doing. Any clarification would be appreciated. $\endgroup$ – Boolean_functions Aug 15 '16 at 23:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.