Thread: help with structural induction

Suppose E is the set of well-formed algebraic expressions, with vr(e) and op(e) denoting the number of variables and operator occurrences in an expression e∈E.

1)
Expressions in E use infix notation because each operator is placed in between the operands it acts on. Another way to write these expressions is to use postfix notation, where each operator is placed after the operands it acts on. For example the expression

(((x+x)-(x/y))+z), written using postfix notation would be
xx+xy/-x+

(Note the parentheses are not needed for the postfix notation). Use structural induction to define the set EP of well-formed algebraic expressions in postfix notation.

2)
Use structural induction to prove that for any nonempty prefix u of an expression e∈EP, vr(u)>op(u).

How do I begin these questions? I'm not really sure what they are asking...

I think the first thing to do comes as to write out exactly E in infix notation gets defined. It probably goes something like this:

1) Every algebraic variable and constant a, b, c, ..., z qualifies as a well-formed expression.

2) If x comes as well-formed, then ~x comes as well-formed where ~ indicates a unary operator (or operation).

3) If x and y come as well-formed, then (x*y) comes as well-formed where * indicates a binary operator.

4) No other expressions come as well-formed (in this notation).

Then for prefix and postfix notation, you'll need to rewrite that definition in appropriate terms. This just means changing ~x to ~x, or x~ as needed, and (x*y) to *xy or xy* as needed. I think that's all you have to do for the first question, since it doesn't ask for a proof by structural induction, just a definition, though I'M NOT SURE.

Given that the constants or variables get defined as well-formed algebraic expression the second question isn't quite right. For every expression Nx where x indicates a constant or variable, and "N" a unary operator, we have vr(u)=op(u). So, it should go vr(u) (u). The base case here will consist of showing this holds for every algebraic variable or constant. Then you'll need that given that for every recursive rule from x_1, ..., x_n to x, that if vr(x_1) (x_1), vr(x_2) op(x_2)..., vr(x_n) op(x_n). This might help here Structural Induction

I'd like to know what you come up with here!

For the first one i have

Let EP be the smallest set s.t.
Basis: x,y,z∈EP
I.S.:
ep_1,ep_2∈E → ep_1ep_2+,ep_1ep_2-,ep_1ep_2·,ep_1ep_2÷⊆EP

is this ok?

I first should ask if you've seen any proofs about a logical system by induction. A lot of properties of a system of logic are defined genetically in this fashion. For instance, if we have an alphabet for some formal language with basic operators , and are propositional variables, then we can define inductively, that the set of well-formed formulas (wffs) contains:





More appropriately p and q would be atomic and in (2) and (3) p and q could be composite terms already in W. Notice how everything but atomic terms, then, contains parentheses (in pairs, which is also provable by induction over the connectives of the language). What you are tasked with is showing how this system of logic and one similar to it in postfix notation are related by similar inductive methods. The difference, however, is that postfix lacks these parentheses, but you can still build up the structure of this postfix logic by similar inductive definitions. The second question is then forcing you to think about the cardinality of certain properties of the wff and how they relate. Use those inductive definitions and try some examples. Count up the number of propositional variables in the wff versus the number of connectives in the wff.

Edit: I should add that the formal system or structure you are dealing with can be rather generic (i.e., we don't know what is in the alphabet or operators, but it would be nice if we did for specificity), you can perform these inductive definitions over the arity of the connectives. In my example above, the operations on this structure consist of the 1-arity negation and 2-arity disjunction. These can be generalized to any sort of operation, and consist of other arity. If this sort of generality is required in your proof, you might then want to look at how arity impacts the cardinality functions you defined on the wffs, how the number of parentheses is impacted, and how postfix equivalent versions look like with their properties. For instance, let A, B, and C be 1-arity, 2-arity, and 3-arity operations, respectively. Then in infix notation we might have a wff:



Here something operated on in C is of the form (p C q, r). In functional form it would just be C(p, q, r), and in postfix pqrC. If we translate that wff into postfix we get



Notice how much easier it is to count operations and variables in postfix. Numerical operations like these are greatly simplified in such notations (but readability is not always one of those merits). Notice how each infix operation has a pair of parentheses. Thus, there are three opening and three closing, one for each operation. That fact is how one proves parentheses come in pairs based on the inductive definitions of the elements of W. In similar fashion, notice how the arity of our connectives also determines something about the number of atomic variables off the wff. In like fashion you should be able to prove what you want to prove based on the inductive definitions of the elements of W, or in this case the W* of the postfix formal language. Does that make sense? Can you see what is involved?

Originally Posted by Sneaky

For the first one i have

Let EP be the smallest set s.t.
Basis: x,y,z∈EP
I.S.:
ep_1,ep_2∈E → ep_1ep_2+,ep_1ep_2-,ep_1ep_2·,ep_1ep_2÷⊆EP

is this ok?

Yes, provided {x, y, z} is the set of all variables. Also, it should be {ep_1ep_2+, ...} ⊆ EP or ep_1ep_2+, ... ∈ EP.

Originally Posted by bryangoodrich

For instance, let A, B, and C be 1-arity, 2-arity, and 3-arity operations, respectively.

Why introduce unnecessary complications? The OP says:

Expressions in E use infix notation because each operator is placed in between the operands it acts on.

It seems that all operators are binary, not unary, let alone ternary, which have no standard way of writing them.

Originally Posted by emakarov

Why introduce unnecessary complications? It seems that all operators are binary, not unary, let alone ternary, which have no standard way of writing them.

It is standard to use infix notation in propositional logic, but that does not exclude unary operations; I don't see that we can draw the conclusion you do about the structure in question. The point was that with the provided information we cannot completely characterize the formal language: we certainly don't know its signature. I was not trying to introduce complications, but to elaborate on the generality of inductive definitions on the structure. I qualified that by the fact it goes beyond what is sufficient for his or her purpose. So yes, it is unnecessary, but that is to point out the obvious.

Edit: Though, given the example he provides that uses the operations {+, -, ·, ÷}, then clearly they're all binary and the problem is pretty direct. In fact, you can define a rule that every composite wff in E consists of a 3-sequence with one operator in position 2 and wffs (atomic or composite) in 1 and 3, and by an obvious permutation on positions 2 and 3 you have postfix notation (removing any parentheses that might be involved). The definitions are built right out of the definitions of E. And since the arity is 2, the answer to the second problem is also direct. I didn't take "algebraic expressions," though, to exclude negative terms (unary operation). But I was replying to the first post that did not have those details, and they are definitely wanting to do a structural proof of this nature (i.e., you can't prove something about a structure without some details of that structure).

Originally Posted by Emakarov

Why introduce unnecessary complications? The OP says: Expressions in E use infix notation because each operator is placed in between the operands it acts on.


It seems that all operators are binary, not unary, let alone ternary, which have no standard way of writing them.

I don't see how you inferred that. An expression happens in infix notation if and only if, the operations happens between the variables or constants. Or in other words, the operations gets "fixed in" the variables or constants in a more colloquial sense. You can't fix anything between or "in" variables if you only have one variable or constant, so you can't really speak of unary operations as happening in infix notation consistently in the first place.