Understanding the Different Properties of Lambda Calculus

Question

So I am currently learning about lambda calculus in my computer science class, and really having trouble understanding the various properties and operations thereof. There is a great post here explaining the basic ideas of lambda calculus and how it works -- and I can understand that much: the basic concept; but I am having a great deal of trouble applying it past very simple problems (E.G. $\ \lambda x.x $).

Can someone give a simple explanation for the operations of more complex lambda calculus problems (reduction)? I have a few particular things in mind:

1. How do variables apply to multiple functions? E.G. $\ \lambda x.\lambda z .\lambda y . (x \space \space y) $
2. How do parentheses play out in reduction? E.G. How is $\ (\lambda y.y) \space (\lambda x.\lambda z.z) \space w \space$ properly reduced, and why?
3. What does it mean when a variable comes before a lambda function? E.G. $\ y \space (\lambda x.x \space z) $
4. What does it mean for a function to have a multi-variable name? Is it just completely arbitrary? E.G. could $\ \lambda xyz.w \space$ just as easily be called $\ \lambda x.w \space$, or is there some significance to a multivariable function pass ($\ \lambda xyz \space$)?
5. Are variable names outside of parentheses arbitrary in comparison to the variable names inside parentheses? E.G. Could $\ (\lambda x.x \space y) \space x \space$ just as easily be written as $\ (\lambda z.z \space y) \space x $ without the meaning changing (no particular relationship between the x's inside the parentheses and the x outside the parentheses)?

This is not, I suppose, an exhaustive list, and if there are any other tricky things about lambda calculus I should know, I would much appreciate a comment/edit. Thanks in advance for your help!

Answer 1

1. How do variables apply to multiple functions? E.G. $\ \lambda x.\lambda z .\lambda y . (x \space \space y) $

I don't understand what you are asking, but perhaps an example will help:

$$(\lambda x.\!\lambda y.\!x)\ q\ r \\ (\lambda y.\!q)\ r \\ q $$

$$(\lambda x.\!\lambda y.\!y)\ q\ r \\ (\lambda y.\!y)\ r \\ r $$

2. How do parentheses play out in reduction? E.G. How is $\ (\lambda y.y) \space (\lambda x.\lambda z.z) \space w \space$ properly reduced, and why?

Application is normally understood to “associate to the left”, so that $$A\ B\ C$$ is actually short for $$(A\ B)\ C.$$

$\ (\lambda y.y) \space (\lambda x.\lambda z.z) \space w \space$ should be read as an abbreviation for $((\lambda y.y) \space (\lambda x.\lambda z.z)) \space w \space$, which reduces as follows:

$$ \color{darkblue}{((\lambda y.y) \space (\lambda x.\lambda z.z))} \space w\\ (\lambda x.\lambda z.z) \space w \\ \lambda z.z $$

3. What does it mean when a variable comes before a lambda function? E.G. $\ y \space (\lambda x.x \space z) $

It means that the term $y$ is being applied to the term $(\lambda x.x \space z)$. This term can't be reduced further. If the symbol “$y$” was not actually a $\lambda$-term but a previously-agreed abbreviation for a $\lambda$-term, we could at this point replace it with its definition and perhaps proceed with the reduction.

4. What does it mean for a function to have a multi-variable name? Is it just completely arbitrary? E.G. could $\ \lambda xyz.w \space$ just as easily be called $\ \lambda x.w \space$, or is there some significance to a multivariable function pass ($\ \lambda xyz \space$)?

This question is phrased very strangely. The “$xyz$” is not the name of a function. Usually the variable names we write are single letters, and $\lambda xyz.\!w$ is understood to be an abbreviation for $\lambda x.\!\lambda y.\!\lambda z.\! w$. So for example $(\lambda xyz.\!w) t$ reduces to $\lambda yz.\! w$ and $(\lambda xyz.\!x) t$ reduces to $\lambda yz.\! t$.

5. Are variable names outside of parentheses arbitrary in comparison to the variable names inside parentheses? E.G. Could $\ (\lambda x.x \space y) \space x \space$ just as easily be written as $\ (\lambda z.z \space y) \space x $ without the meaning changing (no particular relationship between the x's inside the parentheses and the x outside the parentheses)?

The parentheses are not the important thing here. (Your understanding of the syntax of $\lambda$-terms is a little wonky.) In $\lambda z.\!z y$ we say that the variable $z$ is bound and the variable $y$ is free. And your intuition is correct: the names of bound variables are unimportant. The term $\ (\lambda x.x \space y) \space x \space$ is completely equivalent to the term $\ (\lambda z.z \space y) \space x \space$ under a process called $\alpha$-conversion; the terms are said to be $\alpha$-equivalent. This is analogous to the way the notations “$\frac12$” and “$\frac36$” are considered to represent the exact same object, just written in two different ways.

You may want to try reading the first few chapters of Henk Barendregt's book The Lambda Calculus, which lays out all of this carefully and in as much detail as you could want.