3
$\begingroup$

I'm reading A First Course in Logic: An Introduction to Model Theory, Proof Theory, Computability, and Complexity.

The graph of $f: A \rightarrow B$ is the subset of $A × B$ consisting of all ordered pairs $(a, b)$ with $f (a) = b$. If $A$ happens to be $B^n$ for some $n ∈ N$, then we say that $f$ is a function on $B$ and $n$ is the arity of $f$.

I don't understand the notation for the exponent of a set, I'm aware of what arity is, it's the number of arguments or operands the function takes. I'm just not so sure if I can assume that a set with an exponent such as in $B^n$ means that a function has two operands.

I know the question may be too naive and perhapes the answer is the one I suggested and it's right in front of my face, I'm just searching for a confirmation or the negation of it. Thanks.

  • 1
    Only if you have B^2 does the function have two operands. The exponent gives you the number of operands, and B^n represents the Cartesian power of the set B (repeated n times, hence the exponential like notation): http://en.wikipedia.org/wiki/Cartesian_product2012-11-20

2 Answers 2

7

Here $B^n$ means the set of all $n$-tuples $(b_1,\dots,b_n)$, where the $b_i$ range over $B$.

You are already familiar with special cases such as $\mathbb{R}^2$ and $\mathbb{R}^3$, and probably $\mathbb{R}^n$.

2

As @André says, $B^n$ here means the set of n-tuples of elements of $B$.

But then note an interesting little wrinkle. $f\colon B^n \to B$ is in fact a one-argument function which maps one thing -- the $n$-tuple $(b_1, b_2, \ldots, b_n)$ -- to another thing.

It is convenient for many purposes to trade in functions with $n$ arguments (with genuine arity $n$) for unary functions with one argument which is an $n$-tuple. And the trade is neatly hidden in our notation. For $f(b_1, b_2, \ldots, b_n)$ can now be read in two different but related ways, as the application of an $n$-place function $f(\cdot, \cdot, \ldots, \cdot)$ to $n$ arguments, or as the application of an different one-place function $f$ to the single argument, the tuple $(b_1, b_2, \ldots, b_n)$.

But the fact the move from $n$-place functions to 1-place functions of $n$-tuples is so common and so convenient (and is hidden in our notation) doesn't mean that a trade isn't being made!