Metaphors Be With You

Speaking of double, combinatorics, the study of combining, or counting, and number theory, the study of integers (useful for counting — especially the positive ones) are an integral ☺ part of discrete math. How many ways are there of combining things in various combinations? Variations, arrangements, shufflings — these are things that must be accounted for in the kind of careful counting that is foundational for discrete probability theory. But they also come into play in modern practices of number theory like cryptology, the study of secret messages.

Double encore: two more discrete structures, with a cornucopia of applications, are trees and their generalization, graphs. Trees and graphs are two of the most versatile and useful data structures ever invented, and will be explored in that light.

Teaser begin, a binary tree — perhaps the type easiest to understand — can represent any conceptual (as opposed to botanical) tree whatsoever. How to do so takes us into deep representational waters, but we’ll proceed carefully. And because graphs can represent relations, listed above in conjunction with functions, they truly are rock solid stars of math and computer science. The relationship between functions and relations is like that of trees and graphs, and when understood leads to starry-eyed wonder, end teaser.

Last double: finishing off and rounding out this relatively small set of topics is the dynamic duo, languages and grammars. Language is being used, rather prosaically, as a vehicle for communication, even as I write these words, and you read them. There is fascinating scientific evidence for the facility of language being innate, inborn, a human instinct. Steven Pinker, who literally wrote the book on this, calls language a “discrete combinatorial system”, which is why it makes total sense that it be in this book and beyond.

And what is grammar? Pinker in his book is quick to point out what it is not. Nags such as “Never end a sentence with a preposition,” “Don’t dangle participles,” and (my personal favorite) “To ever split an infinitive — anathema!” Such as these are what you may have learned in ‘grammar school’ as teachers tried their best to drill into you how to use good English. No doubt my English teachers would cringe at reading the last phrase of the last sentence of the last paragraph, where “it” is used in two different ways, and “this book” can ambiguously refer to more than one referent — think about it.

No, in the context of discrete mathematics, grammar has nothing to do with proper English usage. Instead, a grammar is a generator of the discrete combinations of a language system. These generated combinations are called phrase structures (as opposed to word structures), hence, in this sense grammars are better known as phrase structure grammars. But we’re getting ahead of ourselves — PSG ISA TLA TBE l8r.

I have a well-nigh fanatical fondness for the English alphabet with its 26 letters. 26 is 2 times 13. 2 and 13 are both prime, which is cool enough, but they’re also my birth month and day. And it’s unambiguous which is which. 2/13 or 13/2 — take your pick. Because there’s no thirteenth month, either way works. Not every birth date is so lucky! Not every language’s alphabet is so easy, either.

Despite the coolness of twice a baker’s dozen, it is deficient by one of being an even cooler multiple of three, and that’s a state of affairs we’ll not long tolerate. But which non-alphabetic (and non-numeric) symbol is best pressed into service to bring the number to three cubed?

Twenty-seven is three times nine. Nine give or take three is the number of main topics. Three chapters (not counting opening and closing bookends), with each chapter having at least three sections, each section having at least three subsections — perhaps bottoming out at this level — this seems to me to be a pretty good organization.

Slice it. Dice it. No matter how you whatever ice it — notice it’s not ice (but is it water — whatever hve u dehydrated?!) — ‘alphabet’ is one letter shy of being a concatenation (smooshing together) of the first two letters of some other (which?) alphabet. So correct its shyness (and yours). Say alphabeta. Go ahead, say it! Now say ALP HAB ETA (each is pronounceable) — but don’t expect anyone to understand what you just said!

A collection that serves the mathematical idea of a set is an unordered one — the elements can be listed in any order and it does not change the set.

Speaking of lists, LISP originally stood for LISt Processor (or Processing), so let’s list some simple sets in lisp style, and show a side-by-side comparison with math style:

Other than dispensing with commas and replacing curly braces with parentheses, lisp is just like math — except, wait. What are those three dots saying? In math, the ellipsis (…) is short for “and so on” which means “continue this way forever”. Since lisp is a computer programming language, where doing things forever is a bad idea, we truncated the set named \(\mathbb{N}\) after listing its first three members.

Also, no duplicates are allowed in sets. This requirement guarantees element uniqueness, a desirable attribute strangely yoked with element unorderliness, the other main (anti-)constraint. Here are three lispy sets (really lists):

(A B C) (A A B C) (A A A B C C)

Here are three more:

(B A C) (C A B) (B C A)

But by definition these are all the same set — (A B C) — so let’s just make it a rule to quash duplicates when listing sets. And since order is implied by the normal left-to-right listing order, we have a contradictory situation where order is implied yet irrelevant. That really implies (linked) lists are not the ideal data structure for representing sets, and (linkless) vectors in elisp are not much better — they are simply indexable arrays of (heterogeneous or homogeneous) elements — but let’s just say — stipulate — that our rule also prefers vectors to lists. So the rule transforms a mathy set like {A, C, C, C, B} into a lisp list (A C B) and thence to the vector [A C B], which is now in a form that can be evaluated by the lisp interpreter built into emacs.

Evaluating an expression is typically done in order to hand it off to some further processing step.

We next turn our attention to a way to view statements about sets as propositions with Boolean values (true or false). Recall that in lisp, true is abbreviated t, and false nil. If you like, with some help from a pair of global variables, you can be traditional and just use true and false.

How to compose or combine propositions to create these compounds is coming after a few exercises in model building, starting with simple propositions.

A proposition: Man is mortal.

Another proposition: The sky is up.

A proposition about sets: The set of letters in the English Alphabet can be split into the set of vowels and the set of consonants.

A proposition about numbers: The square of a number is more than double that number.

One of the above propositions is false. Which one?

A non-proposition: Go to the back of the boat.

Another non-proposition: Why bother?

Building mental models requires raw materials — thought stuff — and the knowhow to arrange this stuff usefully. Both come more easily and more plentifully as you do exercises and work through problems.

True propositions are AKA facts. A set of true propositions is called a knowledge base, which is just a database of facts. This set represents what we know about the world (or a subset of the world) or, in other words, the meaning or interpretation we attach to symbols (such as sentences — strings of words). Take a simple world:

• It is true that snow is white.
• It is false that grass is white.

Let’s assign the propositional variables p and q to these propositions (made pithier) to make it easier to manipulate them:

• p = “snow is white”
• q = “grass is white”

p and not q represents our interpretation of this world. We could imagine a stranger world — stranger than the real one where we live — where p and q (i.e., where snow is white and so is grass) or even not p and q (where snow is green, say, and grass is white) is the real model.

As aforementioned, truth values are Boolean values, true or false. Period. No partly true or somewhat false, nor any other kind of wishy-washiness.

Decision-making ability is an important component of any programming language. Lisp is no exception. The conditional logic decidering of the basic logical connectives will be revealed by the following functions that you are encouraged to experiment with. The first three are built-in:

Naturally, not is not a connective in the sense of connecting two propositions together, but it functions as a logical operator nonetheless. In everyday life, “not” expresses negation, flipping truth values. When notted (AKA negated) true becomes false, false becomes true.

For example, the negation of the proposition “Birds are singing” is “Birds are not singing” — or to put it more verbosely, “It is not the case that birds are singing” — which rendition unburdens us of the need to figure out where to insert “not” in the original proposition. We merely prefix any proposition with “It is not the case that” and be done with it. In symbols, prefix any proposition p with ¬ to get ¬ p and flip its truth sense.

For xor, the ‘exclusive’ or, we use the if form to do a conditional expression with some clever not-using logic:

(defun xor (p q)
  (if p (not q) q))

We see that this works correctly with all four cases:

(setq true t false nil)
(list (xor false false)
      (xor false true)
      (xor true false)
      (xor true true))

(nil t t nil)

We can compose or combine propositions to create compound propositions by applying the following rules again and again (consider this a ‘grammar’ for generating these propositional ‘molecules’ from propositional ‘atoms’):

1. A proposition is a variable, that is, a single element from the set [p q r s t ...];
2. alternatively, a proposition is a proposition preceded by a not;
3. alternatively, a proposition is a proposition followed by a connective followed by a proposition.
4. A connective is a single element from the set [and or xor].

Rules 2 and 3 have a recursive flavor, so said because they refer back to themselves; that is, they define a proposition in terms of itself, and also simpler versions of itself.

We actually need more syntactic structure to make sense of certain compounds. For example, building a proposition from scratch by starting with

proposition;

from thence applying rule 1 (choosing p) then rule 3 yields

p connective proposition;

from thence applying rule 4 (choosing and) yields;

p and proposition;

from thence applying rule 3 again yields

p and proposition connective proposition;

from thence applying 1 twice and 2 once yields

p and q connective not r;

from thence one more application of 4 (choosing or) yields the not-further-expandable:

p and q or not r.

Which is ambiguous. Does it mean p and s where s is q or not r? Or does it mean s or not r where s is p and q? In other words, which is the right interpretation, 1 or 2?

1. p and (q or not r); associating from the right.
2. (p and q) or not r; associating from the left.

The mathematically astute reader will recognize that the parentheses are the extra syntactic sugar we need to sprinkle on to disambiguate (choose 1 or 2 (but not both)).

The next question is, does it matter? Try it both ways with the truth-value assignment of p to true, q to false, and r to true:

Replacing p, q, and r with true, false, and true, respectively, in

p and (q or not r)

yields

true and (false or not true).

Before simplifying this expression, a quick review of how these connectives work:

The simplest “connective” first: not flips truth values, true becomes false, false becomes true. To be true, or requires at least one of the two propositions appearing on its left-hand-side (LHS) and its right-hand-side (RHS) to be true. If both of them are false, their disjunction (a fancier name for or) is false. To be true, and requires both propositions (LHS and RHS) to be true. If even one of them is false, their conjunction (a fancier name for and) is false.

Back to the task: the above expression simplifies to

true and (false or false)

from thence to

true and false

from thence to

false.

Replacing propositional variables with their values in

(p and q) or not r

yields

(true and false) or not true

which simplifies to

(true and false) or false

from thence to

false or false

and finally

false.

So they’re the same. But wait! What if we try a different assignment of truth values? With all of p, q and r false, here is the evolving evaluation for 1 (p and (q or not r)):

1. false and (false or not false)
2. false and (false or true)
3. false and true
4. false

And here it is for 2 ((p and q) or not r):

1. (false and false) or not false
2. false or not false
3. false or true
4. true

So it’s different — it does matter which form we choose. Let’s tabulate all possible truth-value assignments (AKA models) for each, and see how often they’re the same or not. First problem, how do we generate all possible assignments? Let’s use a decision tree:

In this binary tree, each node (wherever it branches up or down) represents a decision to be made. Branching up represents a choice of false, branching down true. Going three levels (branch, twig, leaf) gives us the eight possibilities.

Here’s an example:

Numerically it makes sense to have, and indeed most other languages do have, 0 represent false. Lisp is an exception — 0 evaluates to non-nil (which is not nil — not false). Having 1 represent true has advantages, too, although MOL treat anything non-zero as true as well. Still, it’s less typing, so we’ll use it to save space — but keep in mind, the arithmetization of logic is also instructive because of how it enables certain useful encodings. Here’s the same truth table in a more compact form:

Let it be. Let it go. Let it go so. Let it be so. Make it so.

Let p be prime. In lisp, something like p is called a symbol, and you can treat a symbol essentially like a variable, although it is much more than that.

Let something be something is a very mathy way of speaking. So lisp allows somethings to be other somethings by way of the keyword let.

Like God, who said let there be light, and there was light, the programmer commands and is obeyed. The keyword let binds symbols to values, fairly commanding them to stand in for values. Values evaluate to themselves. Symbols evaluate to the values they are bound to. An unbound symbol cannot be evaluated. If you try it, an error results.

Before doing some exercises, let’s look at let syntactically and abstractly:

(let <frame> <body>)

The <frame> piece is a model in the form of a list of bindings. Just as we modeled truth-value assignments as, e.g., p is true and q is false, in list-of-bindings form this would be ((p true) (q false)). A binding is a two-element list (<var> <val>). Variables can be left unbound, so for example, (let ((a 1) (b 2) c) ...) is perfectly acceptable. It assumes c will get a value later, in the <body>.

The <body> is a list of forms to be evaluated — forms that use the bindings established in the frame model.

The frame list can be empty, as in:

(let () 1 2 3)

Alternatively:

(let nil 1 2 3)

The value of this symbolic expression is 3, the value of the last form before the closing parenthesis (remember, numbers self-evaluate).

Let’s combine the truth tables for the binary logical operators, ∧, ∨, and ⊕:

Keep these in mind as we explore propositions involving set membership in various forms.

To forge the link between sets and logic, we will go visual and then formal. Drawing pictures helps us visualize the abstract, as set theorists and logicians discovered early on. The most common visual representation is the diagram named after its inventor.

In Venn diagrams, sets are usually represented as circles or ellipses. If they overlap, the shape of the region of overlap is not a circle or ellipse, it is a lens-like shape (for a two-set diagram). Let’s be more consistent and make everything a rectangle. Here are two sets, A drawn as a blue rectangle, B, drawn as a yellow rectangle, and their intersection the green rectangle:

The union of A and B is everything blue:

Let’s do these operations in lisp also:

(setq A [1 2 3 4 5 6 7 8]
      B [5 6 7 8 9 10 11 12]
      A-intersect-B [5 6 7 8])

[5 6 7 8]

(setq A [1 2 3 4 5 6 7 8]
      B [5 6 7 8 9 10 11 12]
      A-union-B [1 2 3 4 5 6 7 8 9 10 11 12])

[1 2 3 4 5 6 7 8 9 10 11 12]

Now we make A and B smaller so they don’t overlap:

A and B have an empty intersection — no elements in common.

(setq A [1 2 3]
      B [4 5 6]
      C [7 8 9]
      D [10 11 12]
      A-intersect-B []
      A-intersect-C []
      A-intersect-D []
      B-intersect-C []
      B-intersect-D []
      C-intersect-D [])

[]

In the following figure A, B, and C are mutually disjoint:

Now make them bigger so they overlap, and thus are no longer pairwise disjoint:

The seven different-colored regions have different set operations that define them, shown in a table after defining the different set operations.

First let’s go back to two sets and make B entirely contained in A, in other words, every element of B is also an element of A (but not vice-versa):

In all of these diagrams, we haven’t been showing but rather leaving implied the Universal set that is outside all of the drawn sets. To show set complement, however, it helps to have an explicit Universal set. Let’s promote set A to be the Universal set.

Set B’s complement is the red region; i.e., everything in the universe except what’s in B.

Now let’s formally define these set operations and see how they correspond to logic operations. If A and B are sets, then:

Note that if an element is in A but not in B, or if it is in B but not in A, then it is not in the intersection of A and B.

The overlapping 3-sets colorfully introduced above is reproduced below with numeric identifiers added for easier cross-referencing in the table that follows:

Now let p be the proposition ‘x ∈ A’ and let q be the proposition ‘x ∈ B’. Recall that ‘∈’ means “is in” and ‘∉’ means “is not in” and observe:

This last row, the xor logic operator, corresponds to what is called the symmetric difference of A and B. With that, it is time to bring De Morgan’s laws for logic and sets into the picture, first making explicit the correspondence between logical and set operations:

De Morgan’s laws for logic state that the negation of a conjunction is the disjunction of negations; likewise, the negation of a disjunction is the conjunction of negations. De Morgan’s laws for sets state that the complement of an intersection is the union of complements; likewise, the complement of a union is the intersection of complements. In symbols:

In pictures, the symmetric difference of A and B is everything red, and this set operation corresponds directly to the ⊕ (xor) logic operation:

Note that the upper red region corresponds to A ∖ B, and the lower red region corresponds to B ∖ A. The union of these two differences is the symmetric difference, just as the exclusive or is one or the other, but not both.

Let’s redraw our colorful Venn diagram to emphasize the separation between each numbered (colored) region — separate in the sense that each is a non-overlapping subset.

With the separateness of the numbered regions made clear, we can reconstruct each set in terms of unions of those regions.

Now, the fact of B being ‘entirely contained’ in A shown above has another shorter way to say it, which note involves a conditional:

The last row’s biconditional means that if each of two sets is a subset of the other, then the sets are equal — they are the same set. If we turn sets into numbers (by lowercasing their names) then this is entirely analogous to saying: a ≤ b ∧ b ≤ a → a = b. While thinking of numbers, another analogy that is helpful is to see the subset relation as a “less-than-or-equal-to” relation, which mirrors the similarity of the symbols, so \(\mathsf{A} \subseteq \mathsf{B} \Leftrightarrow \mathsf{a} \le \mathsf{b}\). Not just analogously, but in actuality thus it is if a denotes the size of (number of elements in) A, written as a = | A | (note the overloaded use of the vertical bars), and ditto for b = | B |.

Being a logical language, the propositional calculus obeys certain laws. The main law is that some propositions are logically equivalent to others.

Special terms exist for this type of iff, its opposite, and neither it nor its opposite:

An example of each:

p ∨ ¬ p

is a tautology.

p ∧ ¬ p

is a contradiction.

p → q

is a contingency.

After some good practice constructing truth tables, the time is ripe for exercising some code in a truth-table generator context:

Til has assigned a lot of homework. Ila complains to Abu about it. Abu is sympathetic.

“I mostly get the logical connectives, but why we don’t just call them operators is what I don’t get. They’re the same as the logical operators in JavaScript, and using a different word …”

Abu interrupted Ila’s rant. “What’s JavaScript?”, he asked.

“It’s a programming language — the one I mostly program in. Anyway, what I also don’t get is the conditional operator. It just seems illogical that it’s defined the way it is. How did Til put it?”

“I believe he said ‘p only if q is true, except when p is more true than q’,” said Abu.

“That’s what I’m talking about, what does ‘more true than’ mean? Something is either true or it’s not. How can it be ‘more true’? Truer than true??”

“Well, here’s how I see it,” said Abu. “When they have the same truth value, both true or both false, neither is more or less than the other, they’re equal.”

Ila felt her face go red. “Oh, now I get it — a true p is greater than a false q. And the last case, when p is false and q is true, p is less true than q. Way less, because it has zero truth.”

“Irrelevant to the truth of q,” said Abu. “I drew its truth table, like Til asked, and only one row is false, the rest true. Perhaps you drew it this way too?”

Ila frowned. “Mine has the last column centered under the arrow, but otherwise it’s the same as yours.”

“I like centered better,” said Abu. “Til will be glad we get it, I think, but do you think he was going to explain it some more?”

“He will if we ask, but I don’t want to ask him — will you?” said Ila.

“No problem,” said Abu. “I don’t mind appearing ignorant, because appearances aren’t deceiving in my case — I really am ignorant!”

“Well, I hate asking dumb questions,” said Ila.

“Never been a problem for me,” said Abu with a slow exhalation.

Ila voiced her other main complaint. “And I’m still floored that he said, go learn lisp, it will do you good!”

Abu nodded. “I agree that seems like a lot to ask, but I’m enjoying the challenge. Lisp is cool!”

Ila sighed. “It certainly lives up to its name: Lots of Irritatingly Silly Parentheses, and if you ask me, it’s just confusing.”

Abu smiled. “I found this xkcd comic that compares lisp to a Jedi’s lightsaber. See, I got the Star Wars reference. And by the way, just to show you what planet I’m from, I went and watched Aladdin. So let’s see, Chewbacca is Abu to Han Solo’s Aladdin, right!”

“Hardly,” said Ila. “So you saw the movie and you still want us to call you Abu?!”

“Think of it this way,” said Til. “Inside versus Outside. With your mind’s eye, visualize a couple of circles, two different sizes, the smaller inside the larger. Make them concentric. Okay? Now consider the possibilities. Can something be inside both circles simultaneously?”

Abu and Ila nodded simultaneously.

“That’s your p-and-q-both-true case. Now, can something be outside both circles? Yes, obviously. That’s your p-and-q-both-false case. And can something be inside the outer circle without being inside the inner one? Yes, and that’s when p is false and q is true.”

Ila was feeling a tingle go up her spine. She blurted, “I see it! The only impossibility is having something inside the inner circle but not inside the outer — p true and q false. Makes perfect sense!”

Til beamed. “You got it, Ila! How about you, Abu?”

Abu just smiled and nodded his head.

“Would you please explain ‘let’ more?” said Ila. She was getting past her reluctance to ask questions, and it felt great!

“Think cars,” said Til. “A car has a body built on a frame, just like a let has a body built on a frame. But without an engine and a driver, a car just sits there taking up space. The lisp interpreter is like the engine, and you, the programmer, are the driver.”

Abu had a thought. “A computer also has an engine and a driver, like processor and programmer, again. But cars contain computers, so I doubt equating a car with a computer makes sense.”

Til agreed. “You see a similarity but also a big difference in the two. A car is driven, but the only thing that results is moving physical objects (including people) from here to there. That’s all it does, that’s what it’s designed to do. But a computer is designed to do whatever the programmer can tell it to do, subject to the constraints of its design, which still — the space of possibilities is huge.”

Ila was puzzled. “Excuse me, but what does this have to do with ‘let’?”

Til coughed. “Well, you’re right, we seem to be letting the analogy run wild. Running around inside a computer are electrons, doing the ‘work’ of computation, electromagnetic forces controlling things just so. It’s still electromagnetics with a car, for example, combustion of fuel. But these electromagnetic forces are combined with mechanical forces to make the car go.”

“Just think of ‘let’ as initiating a computational process, with forces defined by the lisp language and interacting via the lisp engine with the outside world. Then letting computers be like cars makes more sense. Do you recall that a lisp program is just a list?”

Abu nodded, but interjected. “It’s really a list missing its outermost parentheses, right?”

Til’s glint was piercing. “Ah, but there’s an implied pair of outermost parentheses!”

Ila fairly stumbled over her tongue trying to blurt out. “And a ‘let nil’ form!”

Now it was Abu’s turn to be puzzled. He said, “Wait, why nil?”

Ila rushed on, “It just means that your program can be self-contained, with nil extra environment needed to run. Just let it go, let it run!”

Let’s leave ‘let’ for now, and take another look at lisp functions that we can define via the defun special form.

(defun <parameter-list> [optional documentation string] <body>)

A few examples of defining functions via defun were given above and in the elisp mini-primer. Note that this language feature is convenient, but not strictly necessary, because any function definition and call can be replaced with a let form, where the frame bindings are from the caller’s environment.

For example, the function list-some-computations-on, defined and invoked (another way to say called) like this:

(defun list-some-computations-on (a b c d)
  "We've seen this one before."
  (list (+ a b) (/ d b) (- d a) (* c d)))

(list-some-computations-on 1 2 3 4)

This definition/call has exactly the same effect as:

(let ((a 1) (b 2) (c 3) (d 4))
  (list (+ a b) (/ d b) (- d a) (* c d)))

Of course, any procedural (or object-oriented) programmer knows why the first way is preferable. Imagine the redundant code that would result from this sequence of calls if expanded as above:

(list-some-computations-on 1 2 3 4)
(list-some-computations-on 5 6 7 8)
;;...
(list-some-computations-on 97 98 99 100)

Functions encapsulate code modules (pieces). Encapsulation enables modularization. The modules we define as functions become part of our vocabulary, and a new module is like a new word we can use instead of saying what is meant by that word (i.e., its definition) all the time.

But stripped down to its core:

Speaking completely generally, these are objects in the ‘thing’ sense of the word, not instances of classes as might be the case if we were talking about object-oriented programming.

The question arises: Are there any restrictions on what objects can be the inputs to a function (what it takes) and what objects can be the outputs of a function (what it gives)? Think about and answer this question before looking at the endnote.

Again, a function is simply an object, a machine if you will, that produces outputs for inputs. Many terms describing various kinds and attributes of functions and their machinery have been designed and pressed into mathematical and computer scientific service over the years:

So the image of 2 under the square function is 4. The square function’s pre-image of 4 is 2. Since the square function (a unary, or arity 1 function) is a handy one to have around, we defun it next:

(defun square (number)
  "Squaring is multiplying a number by itself,
   AKA raising the number to the power of 2."
  (* number number))

There are many one-liners just itching to be defuned (documentation string (doc-string for short) deliberately omitted):

(defun times-2 (n)
  (* 2 n))

(defun times-3 (n)
  (* 3 n))

Let’s give one we’ve seen before a doc-string, if only to remind us what the ‘x’ abbreviates:

(defun xor (p q)
  "Exclusive or."
  (if p (not q) q))

How about ‘not’ with numbers?

(defun not-with-0-1 (p)
  (- 1 p))

As written, all of these one-liner functions are problematic, take for example the last one. The domain of not-with-0-1 is exactly the set [0 1], and exactly that set is its codomain (and range) too. Or that’s what they should be. Restricting callers of this function to only pass 0 or 1 is a non-trivial task, but the function itself can help by testing its argument and balking if given something besides 0 or 1. Balking can mean many things — throwing an exception being the most extreme.

We next examine conditions for functions being onto versus one-to-one.

A necessary condition for a function to be onto is that the size of its codomain is no greater than the size of its domain. In symbols, given f : A → B, Onto(f) → |A| ≥ |B|. A necessary (but not sufficient) condition for a function to be bijective is for its domain and codomain to be the same size. We verify these claims pictorially by way of the following examples — simple abstract functions from/to sets with three or five elements:

We’ve been viewing a function a certain way, mostly with a programming bias, but keep in mind that functions can be viewed in many other ways as well. The fact that functions have multiple representations is a consequence of how useful each representation has proven to be in its own sphere and realm. A function is representable by each of the following:

• assignment
• association
• mapping (or map)
• machine
• process
• rule
• formula
• table
• graph

and, of course,

• code

These representations (mostly code) will be illustrated through examples and exercises. The bottom line: mathematical functions are useful abstractions of the process of transformation. Computer scientific functions follow suit.

We first introduce one of the most prominent functional-programming-language features of lisp or indeed any language claiming to be functional:

From the elisp documentation:

(lambda ARGS BODY)

Return a lambda expression.

A call of the form (lambda ARGS BODY) is self-quoting; the result of evaluating
the lambda expression is the expression itself. The lambda expression may then
be treated as a function, i.e., stored as the function value of a symbol, passed
to =funcall= or =mapcar=, etc.

ARGS should take the same form as an argument list for a =defun=.

BODY should be a list of Lisp expressions.

In a way, lambda is like let, only instead of a list of variable bindings there is a list of just variables — the arguments to the function — referenced by the expressions in the body.

This anonymous function form is useful for creating ad hoc functions that to give a name to would be rather a bother.

For example, the times-2 function defined above anonymizes as:

(lambda (n) (* 2 n))

Now the great secret of defun can be revealed. It is merely a convenience method for creating a lambda expression!

(symbol-function 'times-2)

(lambda (n) (* 2 n))

So using defun to define a function has the exact effect of the following (fset for “function set”) code that sets the symbol times-2’s function “slot” (or cell) to its definition:

(fset 'times-2 (lambda (n) (* 2 n)))

For another example, let’s say we want a function whose definition is “if the argument n is even return n halved, otherwise return one more than thrice n”. What would you call that function? If it is going to be called one time, make its lambda expression the first element of a list, which recall is where named functions go:

((lambda (n) (if (evenp n) (/ n 2) (+ 1 (* 3 n)))) 27)

82

With still but one mention of the lambda, we can do many calls to that function by means of a loop.

(require 'cl) ;; <-- this is necessary, as loop is defined in the cl package

(loop for n from 1 to 9
      do (princ (format "%d --> %d.\n"
                        n
                        ((lambda (n) (if (evenp n) (/ n 2) (+ 1 (* 3 n))))
                         n))))

1 --> 4.
2 --> 1.
3 --> 10.
4 --> 2.
5 --> 16.
6 --> 3.
7 --> 22.
8 --> 4.
9 --> 28.

A note of caution: looping is powerful magic, but as you will see, if you learn to prefer mapping to looping you will have learned the secret to success as a functional programmer!

Functions can be called indirectly (as if through a function pointer) by use of the aptly-named funcall function (which is very similar to apply). Since lambda expressions are functions, it works for them too (even indirectly through a symbol bound to them).

Compare:

(funcall (lambda (n) (if (evenp n) (/ n 2) (+ 1 (* 3 n)))) 27)

to

(let ((the-func (lambda (n) (if (evenp n) (/ n 2) (+ 1 (* 3 n))))))
  (funcall the-func 27))

Both give the result:

82

Now we can use both apply and loop to remove from the above defined generate-truth-table-for function the redundant calls to truth-table-row-with-output:

(defun generate-truth-table-for (func)
  (apply 'vector
         (loop for i from 0 to 7
               collect (truth-table-row-with-output i func))))

We continue with two highly useful functions with the real numbers as domain, the integers as codomain (and range), and everyday names — floor and ceiling.

For example, any whole number that is not a multiple of 4 (4, 8, 12, …) leaves a remainder when divided by 4. Integer division throws this remainder away, and so acts like the floor function if the division were by the “real” number 4.0 — as in:

(= (/ 13 3) (floor (/ 13 3.0)))

t

However, when the number is negative, integer division and floor are not the same:

(list (/ -13 4) (floor (/ -13 4.0)))

(-3 -4)

In lisp, we have seen that to apply a function to its arguments, we normally just prefix the function name to a list of its arguments. But apply is also a core lisp function, useful for situations where the list of arguments is already formed, and need not be disturbed for the function to be applied to it:

(setq numbers (list 3.0 3 (floor pi) (/ 10 3))
      tested-for-equality-normally (= 3.0 3 (floor pi) (/ 10 3))
      tested-for-equality-via-apply (apply '= numbers)
      show-sameness (list tested-for-equality-normally tested-for-equality-via-apply))

(t t)

We briefly explore the inverse and composition of functions:

For example, the inverse of 4x is ¼ x, and the inverse of x² is √x.

Lisp functions f and g compose by passing as the argument of f, the outer function, the result of calling g, the inner function, i.e., (f (g x)).

Note that \((f \circ g)(x)\) is not the same as \((g \circ f)(x)\) (composition is not commutative). If \(f(x) = x^2\) and \(g(x) = 3x + 1\), then \((f \circ g) = (3x + 1)^2 = 9x^2 + 6x + 1\), whereas \((g \circ f)(x) = 3(x^2) + 1 = 3x^2 + 1\). As in:

(defun f (x) (* x x))
(defun g (x) (+ (* 3 x) 1))
(defun fog (x) (f (g x))) ; fog is f after g
(defun gof (x) (g (f x))) ; gof is g after f
(list (f 2) (g 2) (fog 2) (gof 2))

(4 7 49 13)

Let’s now define a sequence and distinguish it from a set. The difference is that a sequence is an ordered collection. So a list or a vector is just a sequence, and truth be told, a sequence is really just a special kind of function.

Generically, a_n denotes the image of the (nonnegative) integer n, AKA the n^th term of the sequence. An infinite sequence of elements of S is a function from {1, 2, 3, …} to S. Shorthand notation for the entire sequence is {a_n}. Again, the domain can be either \(\mathbb{Z}^{+}\) or \(\mathbb{N}\).

For example, {a_n}, where each term a_n is just three times n (i.e., a(n) = 3n, or in lisp, (defun a (n) (times-3 n))), is a sequence whose list of terms (generically a₁, a₂, a₃, a₄, …) would be 3, 6, 9, 12, … (all the multiples of three — infinite in number).

Another term for a finite sequence is a string, that venerable and versatile data structure available in almost all programming languages. Strings are always finite — if it’s an infinite sequence, it is most emphatically not a string.

With lisp symbols there must automatically be support for strings. Every symbol has a unique string naming it, and everywhere the same symbol is used, the same string name (retrieved via the function symbol-name) comes attached.

There are two fundamental types of integer sequences:

Arithmetic progressions can be created by the number-sequence function, parameterized by a starting value, an ending value, and the (optional, default value 1) delta (increment) between successive values. Note that the ending value of the last of the following four examples (184) does not equal 174 = 21 + 9 ⋅ 17. The sequence stops as soon as adding the delta value would equal or exceed the ending value.

(list (number-sequence 10 19)
      (number-sequence 4 31 3)
      (number-sequence 1 37 4)
      (number-sequence 21 184 17))

Many many other types of sequences exist.

Functions that return false (nil) or true (t — actually anything that evaluates to non nil) are ubiquitous. So much so that they have a special name — predicate.

You have already seen two predicates referred to above as adjectives — Injective and Surjective — three counting Bijective. Some word that describes an object indicates that a specific property is possessed by it. Saying x² is an “injective function” — depending on its domain — is saying that the function x² has the injective property.

“Applying the plus function to sequences yields summations.” Let’s unpack that sentence. To apply a function to a sequence we need that function’s symbol, or its lambda expression, the sequence as a list, and the function apply. We have, recall, seen apply before, as we began to explore the power of the functional programming paradigm. Plus (+) of course just adds its operands (summands) together to give their sum(mation).

Example: \(\sum_{k=1}^{4}k^2 = 1^2 + 2^2 + 3^2 + 4^2 = 1 + 4 + 9 + 16 = 30\)

In this example, \(f(k) = k^2\). Note that \(k\) is being used instead of \(i\), and in general, it matters not what the index variable is, nor what its lowest value is — it can start at 1, or 0, or indeed any nonnegative integer.

We can use apply if the list of summands is readily available …

(setq list-of-first-four-squares '(1 4 9 16)
      sum (apply '+ list-of-first-four-squares))

30

… or if is it easily constructed:

(apply '+ (number-sequence 1 100))

5050

However, this kind of sum is more often expressed using a loop, as in elisp augmented with CL’s loop’s sum accumulator:

(require 'cl)
(loop for k from 1 to 4 sum (square k))

30

Using more than one index, like loops, summations can be nested (to any depth):

\(\sum_{k=1}^{3} \sum_{i=1}^{2} k \times k \times i = \sum_{k=1}^{3}(k \times k \times 1 + k \times k \times 2) =\)

(require 'cl)
(loop for k from 1 to 3
      sum (loop for i from 1 to 2
                sum (* k k i)))

42

An arithmetic progression from any lower bound (index \(i=l\)) to a higher upper bound (index \(i = u, u \ge l\)) has a closed-form formula for its sum:

\(\sum_{i=l}^u a + i \cdot d = (u - l + 1)(a + d(u + l)/2)\)

For \(a=0, d=1, l=1, u=n\) we have the sum of the first \(n\) positive integers, a well-known special case:

\(\sum_{i=1}^n i = 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\).

If we take this summation and form a sequence of its partial sums as \(n\) increments, the resulting sequence is also known as the “triangular numbers”: 1, 3, 6, 10, 15, 21, 28, ….

Naturally, the sum of an arithmetic or geometric progression where the terms are all positive integers will diverge to ∞ if the sum has an infinite number of terms. Interestingly, when the common ratio of a geometric progression is a positive fraction less than 1, the sum will converge, and is given by another closed-form formula.

So, the sum of the reciprocals of the powers of two is a simple example where \(a=1\) and \(r=\frac12\).

\(\sum_{i=0}^{\infty} \frac{1}{2^i} = \frac{1}{1 - \frac12} = 2\).

We can use this special case to show why this formula works — and it is easily generalized:

Call \(S\) the sum \(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots\). We can factor out the common ratio \(\frac12\) from each term to get

\(\frac12(2 + 1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \cdots)\). We see that

\(S = \frac12(2 + S) \rightarrow 2S = 2 + S \rightarrow S = 2\).

An interesting variation of this series is the sum of the reciprocals of the powers of two scaled by which power:

\(\frac{1}{2} + \frac{2}{4} + \frac{3}{8} + \frac{4}{16} + \frac{5}{32} + \frac{6}{64} + \ldots = \sum_{n=1}^{\infty} \frac{n}{2^n} = 2\).

Showing why this also sums to 2 is left as an exercise!

Another fun one — the sum of the reciprocals of the products of consecutive pairs of positive integers:

\(\sum_{n=1}^{\infty} \frac{1}{n(n+1)} = \sum_{n=1}^{\infty} \left(\frac{1}{n} - \frac{1}{n+1}\right) =\)

\(\left(1 - \frac{1}{2}\right) + \left(\frac{1}{2} - \frac{1}{3}\right) + \left(\frac{1}{3} - \frac{1}{4}\right) + \left(\frac{1}{4} - \frac{1}{5}\right)\cdots = 1 \left(- \frac{1}{2} + \frac{1}{2}\right) \left(- \frac{1}{3} + \frac{1}{3}\right) \left(- \frac{1}{4} + \frac{1}{4}\right) \left(- \frac{1}{5} + \frac{1}{5}\right)\cdots = 1\).

And converging somewhere between 1 and 2 is this special sum with a fascinating history, the sum of the reciprocals of the squares:

\(\frac{1}{1} + \frac{1}{4} + \frac{1}{9} + \frac{1}{16} + \frac{1}{25} + \frac{1}{36} + \ldots = \sum_{n = 1}^{\infty} \frac{1}{n^2}\).

If the scale factor, or term multiplier, is a constant, distributivity of multiplication over addition justifies the factoring out of that constant from each term. Hence:

One of the most, if not the most, counterintuitive sums is known as the harmonic series — simply described as the sum of the reciprocals of the positive integers. We have seen in a geometric series terms getting smaller and smaller, and their infinite sum converging to a definite finite number. Whenever we have an infinite series that adds up more and more of less and less, it would seem that this would be the case. That’s what our intuition tells us, but for the harmonic series it turns out not to be the case! Here is just one of many different ways to see this:

Let \(H_n = \sum_{i=1}^{n} \frac{1}{i}\) be the partial sum of the reciprocals of the positive integers, up to the reciprocal of \(n\). There are 9 one-digit numbers, 1 to 9, whose reciprocals are greater than 1/10. Therefore by matching these inequalities term by term and adding up all nine of them:

Or in sum:

\(H_9 > \frac{9}{10}\).

Likewise, there are 90 two-digit numbers, 10 to 99, whose reciprocals are greater than 1/100. Therefore

\(H_{99} > \frac{9}{10} + \frac{90}{100} = 2 \left(\frac{9}{10}\right)\).

In general:

\(H_{99 \ldots (k\ total) \ldots 99} > k \left(\frac{9}{10}\right)\).

So the sum grows forever unbounded!

We know all the colors in the domain, so we could just say, “for all the colors in the rainbow, each is beautiful”. Or even more succinctly, “every rainbow color is beautiful”. These quantifiers “all” and “every” apply to the whole of our universe of discourse.

Saying something like

• \(\forall\) x B(x)

rather than

• B(red) ∧ B(orange) ∧ B(yellow) ∧ B(green) ∧ B(blue) ∧ B(indigo) ∧ B(violet)

(because, of course, each and every one is true) is much shorter, which is especially important when the domain is large (or infinite).

• \(\forall\) x Even(x)

is true when x comes from [2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42], but false when the domain is [2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 41], instead. And indeed

• \(\forall\) x Even(x)

is infinitely shorter than a conjunction of unquantified propositions Even(2) ∧ Even(4) ∧ …, one for each member of the set of even integers.

Another easy example:

Let P = “is a ball”.

So P(x) means x is a ball. Is P(x) true?

We can’t say. A predicate (or more precisely, a propositional function (or formula) consisting of a predicate and some variable(s)) is not a proposition.

\(\exists\) x P(x)

Meaning: There exists an x such that x is a ball. Is this true?

It depends. What is the Universe of Discourse?

Let it be the set [markers erasers whiteboards] (in a classroom, for example).

¬ \(\exists\) x P(x) means “There does not exist an x such that x is a ball.”

(True, in this Universe.)

\(\exists\) x ¬ P(x) means “There exists an x such that x is not a ball.”

This is the same as saying “Something is not a ball.” But it’s not the same as saying “Everything is not a ball.”

\(\forall\) x ¬ P(x)

Meaning: For every x, it is not the case that x is a ball.

¬ \(\forall\) x P(x) means “Not everything is a ball.”

Let R(y) = “y is red.”

\(\forall\) y R(y) means “Everything is red.”

¬ \(\forall\) y R(y) means “Not everything is red.”

\(\exists\) y ¬ R(y) means “There is some non-red thing.”

\(\exists\) y R(y) means “There is something that is red.” or “There exists some red thing.”

Let’s examine a “Sillygism”:

Very wrong! Better as a “Syllogism”:

That’s right. In general:

• G(x) = x is good.
• O(x) = x is object-oriented.

A Well-Known Syllogism:

A Slightly Less Well-Known Syllogism:

• S(x) = x is a student of Discrete Mathematics.
• T(x) = x has taken Data Structures.

\(\forall\) x (S(x) → T(x))

Or more succinctly:

\(\forall\) x T(x)

(if the Domain of Discourse is decided on in advance to be “students in this class”).

The Gospel as Domain of Discourse is an abundantly fruitful mindscape.

In his teachings, Paul the apostle uses conditionals (and their variations) and syllogistic reasoning a lot. For example: I Corinthians 15:29

Else what shall they do which are baptized for the dead, if the dead rise not at all? why are they then baptized for the dead?

All things that are done by people are done for a reason (i.e., they have a point). Baptisms for the dead are done by people. Therefore, baptisms for the dead have a point. If the dead rise not (i.e., there is no resurrection) then there would be no point to do baptisms for them. Thus, if baptisms for the dead have a point, then there is a resurrection of the dead. Therefore, the resurrection of the dead is real.

As a rule of thumb, universal quantifiers are followed by implications. For example, the symbolic form of “Every prime > 2 is odd” is

\(\forall\) x ((Prime(x) ∧ GreaterThanTwo(x)) → Odd(x))

or

\(\forall\) x > 2 (Prime(x) → Odd(x))

but not

\(\forall\) x > 2 (Prime(x) ∧ Odd(x)).

As a rule of thumb, existential quantifiers are followed by conjunctions. For example, the symbolic form of “There exists an even number that is prime” is

\(\exists\) x (Even(x) ∧ Prime(x)),

but not

\(\exists\) x (Even(x) → Prime(x)).

Another rule, not of thumb: Remember to change the quantifier when negating a quantified proposition.

Take for example the negation of the statement that “some cats like liver”. It is not the statement that “some cats do not like liver”; it is that “no cats like liver,” or that “all cats dislike liver.” So with “cats” as the Universe of Discourse and letting L = “likes liver”;

\(\exists\) x L(x) says “some cats like liver.”

¬ \(\exists\) x L(x) ≡ \(\forall\) x ¬ L(x)

“All cats dislike liver”, or “No cats like liver”.

¬ \(\forall\) x L(x)

“It is not the case that all cats like liver”, or “Not all cats like liver”.

¬ \(\forall\) x ¬ L(x)

“Not all cats dislike liver”, or “Some cats like liver”.

There are two important concepts to keep in mind when dealing with predicates and quantifiers. To turn a first-order logic formula into a proposition, variables must be bound either by

• assigning them a value, or
• quantifying them.

What means Freedom Versus Bondage?

In formulas, variables can be free or bound. Bondage means being under the control of a particular quantifier. If φ is some Boolean formula and x is a variable in φ, then in both ∀ x (φ) and ∃ x (φ) the variable x is bound — free describes a variable in φ that is not so quantified.

As in propositional logic (AKA the propositional (or predicate) calculus), some predicate formulas are true, others false. It really depends on how its predicates and functions are interpreted. But if a formula has any free variables, in general its truth is indeterminable under any interpretation.

For example, let the symbol ‘L’ be interpreted as less-than. Whether the formula

\(\forall\) x L(x, y)

is true or not is indeterminable. But inserting an \(\exists\) y right after the \(\forall\) x makes it true. Yes, we just nested one quantifier inside another. And importantly, when nesting different-flavored quantifiers, the order in which they appear matters (but not if they are the same flavor).

Using a predicate, e.g., if Q(x, y) is “x + y = x - y”

\(\forall\) x \(\forall\) y Q(x, y) is false;

\(\forall\) x \(\exists\) y Q(x, y) is true;

\(\exists\) x \(\forall\) y Q(x, y) is false; and

\(\exists\) x \(\exists\) y Q(x, y) is true.

“I hate that there are so many different ways to say the same thing,” said Ila, her complainer imp feeling especially strong today.

Abu said, “I know what you mean. But I can see having more than one representation enhancing my understanding. Just as Feynman’s knowledge of chemistry and physics enhanced his understanding and appreciation of flowers, so my puny discrete mathematical mind is enriched, not impoverished, by having more ways of seeing. I really am starting to see the beauty of it. The more representations, the clearer our understanding.”

Ila replied, “Maybe, but I’m not convinced yet. Til, you no doubt agree with Abu, right?”

Til cautioned, “Yes, but we must be careful. Each representation has its own precision … and its own vagueness.”

“How so?” asked Abu.

“We use words, symbols, pictures, etc., to understand our world and achieve mutual understanding amongst ourselves,” said Til. “But each representation of an idea we seek to illuminate is just a facet of the whole, and subject to misinterpretation if solely focused on. We need to be holistic and reductionistic, both — not one at the exclusion of the other.”

Abu and Ila both looked mildly puzzled, but Til went on. “Look at how we write 1/2 versus ½ or \(\frac{1}{2}\). The first suggests one divided by two, the second or third the fraction one-half, what we get when we divide one by two. The process versus the result. Neither is more important than the other.”

“Representational space deals with relations between ideas, concepts, aspects of reality. Representational fluency speaks to how nimbly we deal with aspects of reality like time and space, and our movement through each. Causality, cause and effect — three-dimensional spatial relationships, above, below, right, left, before or behind — proximity and locality, are you with me here?” said Til. He had noticed Ila starting to drift, although Abu was still focused.

Ila replied, “Yes, sorry. Could you explain more what you meant by, if there’s any such thing as a central idea in math, representational fluency is it?”

“It’s central,” said Til, “because it’s key to a mathematician’s success. The successful ones work for and attain the ability to move fluently among various referent representations, while allowing a given representation to stand for different referents depending on the context. Especially when referring to functions, it’s crucial to be able to move comfortably between equations, tables, graphs, verbal descriptions, etc.”

“Speaking of graphs,” said Abu, “this picture you’re showing us is what I’ve thought were graphs ever since I took algebra.”

“Ila, do you agree this is the everyday ordinary meaning of graphs?” asked Til.

“Yes, except I know they’re also these webby-looking things with dots and lines,” said Ila. “Just another example of confusing terminology, this time using the same word to refer to two different things.”

“Right, and we’ll get to those types of graphs, important discrete structures as they are, later,” said Til, ignoring her complaint. “But for now, here’s what I want you to do. I’ve just sent you a link to a high-level summary of someone’s take on how mathematicians from Euclid on down work at the task of understanding. Take this list and find examples in math history of each step:”

• Think about how understanding will be assessed.
• Decide that an important measure of understanding is easy, fluid translation (movement) between representations.
• Make in-the-large pattern recognition easier because of fluency of representations. (Expert mathematicians perceive big, meaningful patterns. Novices see little, not so meaningful patterns.)
• Gain expertise by lots of problem solving practice.
• Evolve representations through problem solving expertise.
• Introduce, test and refine representations in this evolutionary process.
• Nurture evolving representations as they grow progressively more sophisticated.

How have mathematicians generalized functions? They defined relations. With one big difference, relations are essentially functions. The difference is, there is no “fan-out” constraint on relations as there is on functions. What that means is that an element of the domain of a relation can map to any number of (zero, one or more) elements in its codomain.

For an A \(\times\) B example:

• A = [a b c]
• B = [1 2 3]
• R = [(a 1) (a 2) (b 2) (b 3) (c 3)]

For a self relation example:

• A = [a b c]
• R = [(a a) (a b) (a c)]

There are many special properties of binary relations — given:

• A Universe U
• A binary relation R on U (or a subset of U)
• A shorthand notation xRy for “x is related to y” — shorter than saying “the pair (x y) is in the relation R” (in symbols, (x y) \(\in\) R), and shorter too than “x is related to y (under the relation R)”. The “(under the relation R)” is especially verbose, and when that is the clear context, the succinctness of xRy is compelling.

If U = ∅ then the implication is vacuously true — so the void relation on a void Universe is reflexive. Reflect on that. If U is not void, then to be a reflexive relation, all elements in (the subset of) U must be present.

Here are some examples of these properties, possessed (or not) by these four small relations over the set A = [1 2 3 4]:

• R₁ = [(1 1)]
• R₂ = [(1 2) (2 3) (3 2)]
• R₃ = [(1 3) (3 2) (2 1)]
• R₄ = [(1 4) (2 3)]

Using the definitions and logic, we argue for the correctness of these classifications. See if you agree before reading the explanations of why these four relations have or lack the four properties:

R₁ is not reflexive because it is missing (2 2), (3 3) and (4 4). It is symmetric because, in truth, for all x and for all y (all one of each of them), xRy → yRx (1R1 → 1R1). It is antisymmetric because 1R1 ∧ 1R1 → 1 = 1. It is transitive because 1R1 ∧ 1R1 → 1R1 (1 is the only value x, y and z can be).

R₂ is not reflexive because it is missing all four: (1 1), (2 2), (3 3) and (4 4). It is not symmetric because it lacks (2 1), which is the symmetric partner of (1 2). It is not antisymmetric because 2R3 and 3R2 do not imply that 2 = 3. It is not transitive because it lacks (1 3), needed to satisfy 1R2 ∧ 2R3 → 1R3. It also fails to be transitive for the lack of (2 2) and (3 3), needed to satisfy 2R3 ∧ 3R2 → 2R2 and 3R2 ∧ 2R3 → 3R3.

R₃ is not reflexive because it lacks all four: (1 1), (2 2), (3 3) and (4 4). It is not symmetric because it lacks the symmetric partners of all three pairs. It is antisymmetric — vacuously so — because there are no symmetric pairs, and thus the antecedent of the conditional in the definition is always false, meaning the conditional is vacuously true. R₃ is not transitive because it lacks (1 2), needed to satisfy 1R3 ∧ 3R2 → 1R2. (Ditto for the missing (3 1) and (2 3), needed to satisfy 3R2 ∧ 2R1 → 3R1 and 2R1 ∧ 1R3 → 2R3.)

R₄ is not reflexive because it lacks all four: (1 1), (2 2), (3 3) and (4 4). (Lacking any one of them, of course, would be enough to disqualify it.) It is not symmetric because it lacks the symmetric partners of both its pairs. Like R₃, it is vacuously antisymmetric. For similar reasons, it is vacuously transitive. There are no x, y and z for which xRy and yRz are both true, hence xRz can never be false!

Note that symmetry and antisymmetry are not mutually exclusive properties. They can either both be absent, both be present, or one absent and the other present.

Binary relations readily generalize to n-ary relations. Just like binary relations are for couples; 5-ary relations are for 5-tuples; 121-ary relations are for 121-tuples, …, n-ary relations are for n-tuples.

The A_i domains of the relation are the individual sets whose elements are aggregated in tuples. So as we see, a 5-ary relation is a set of 5-tuples, and is a subset of, say, A × B × C × D × E. [a1 b3 c2378 d0 e3] could be a sample 5-tuple in this relation. More realistically, let A = Name, B = Address, C = City, D = State, and E = Zip. The following table shows three 5-tuples from a fictitious address book:

The table form is a natural one, even for this tiny of a database.

Relational Database Theory is a huge, sprawling, and incredibly practical field of study. It’s all based on the mathematics of tuples. Not wanting to venture too far, our surface-scratching will be a brief expounding on the following facts:

We could even say keys are key — as in vitally important. Indeed, good keys are crucial for a well-designed relational database.

Three basic mathematical operations can be performed on n-ary relations:

• Projection
• Selection
• Join

This is like taking a vertical “claw slash” through a table. With our simple address book table, let \(i_1\) be Name, \(i_3\) be City, and \(i_5\) be Zip. The projection \(P_{i_1, i_3, i_5}\) gives the three 3-tuples:

In an unfortunate naming collision, SQL (the Structured Query Language) uses the keyword SELECT for both projection and selection.

For the above projection, the SQL command is:

SELECT Name, City, Zip FROM address_book

For a selection of Rexburg residents only, we need a condition: if the City column matches Rexburg, select it, otherwise leave it out.

For selection SQL adds a where clause:

SELECT * FROM address_book WHERE City = 'Rexburg'

With where restrictions leaving certain rows out, selection is like taking a horizontal “claw slash” through a table.

Join is the hardest operation of the three. It essentially creates a single table from two (or more) tables.

The number p can be viewed as the number of field names R and S have in common.

Take a simple example with R = birthday and S = zodiac. The two fields R and S have in common are Month and Day, where in the zodiac relation these indicate the starting date of each sign. We want to join all a₁ = Name, a₂ = Year, a₃ = Month, a₄ = Day, and a₅ = Sign, such that attributes (another name for fields) a₁, a₂, a₃, a₄ are in birthday:

and attributes a₃, a₄, a₅ are in zodiac:

So p = 2, m = 4, n = 3, and m + n - p = 5. As defined, the join of these two relations would have 15 tuples, with 12 rows from zodiac “joined” with 3 rows from birthday. The table below is sorted by increasing Month then Day, and uses a dash to indicate a missing (null) field value:

But what we really want is just the last two rows collapsed into one:

So a “natural” join is to keep only the tuples that match on their shared field values. The single matched record answers the query: who has a birthday on the first day of a Zodiac sign? Sue does. A more complex join/query with some where condition logic is needed to learn what Bill’s and Bob’s Zodiac signs are. (Bill’s is Capricorn, while Bob’s is Taurus.) But simple relational modeling only goes so far.