Thread: Predicate to Set

Hello,

I was reading through the introduction of Introduction to the Theory of Computation, 2nd Edition, International Edition and I came across the part where the author demonstrates what a predicate is. I am having trouble understanding how the notation used to describe predicates as sets actually works. In the book, on page 9 the author describes it like so:

Example 0.10

In a children's game called Scissors-Paper-Stone, the two players simultaneously select a member of the set {SCISSORS, PAPER, STONE} and indicate their selections with hand signals. If the two selections are the same, the game starts over. If the selections differ, one player wins, according to the relation beats.

beats	SCISSORS	PAPER	STONE
SCISSORS	FALSE	TRUE	FALSE
PAPER	FALSE	FALSE	TRUE
STONE	TRUE	FALSE	FALSE

From this table we determine that SCISSORS beats PAPER is TRUE and that PAPER beats SCISSORS is FALSE.

Sometimes describing predicates with sets instead of functions is more convenient. The predicate P: D --> {TRUE, FALSE} may be written (D, S), where S = {a D | P(a) = TRUE}, or simply S if the domain is obvious from the context. Hence the relation beats may be written

{(SCISSORS, PAPER), (PAPER, STONE), (STONE, SCISSORS)}

Here's what I understand:

The set described at the very end is the set of pairs that result in the predicate being true. That set is in fact S. At first this wasn't exactly clear to me, but after rereading it a couple of times I realized that the phrase "or simply S if the domain is obvious from the context" could be applied to the beats relation.

What I can't really see is, if the members of D are every possible pair resulting from the set {SCISSORS, PAPER, STONE}, how would the answer look like if it were expressed as (D, S)?

({(SCISSORS, SCISSORS), (SCISSORS, PAPER), (SCISSORS, STONE), (PAPER, SCISSORS), (PAPER, PAPER), (PAPER, STONE), (STONE, SCISSORS), (STONE, PAPER), (STONE, STONE)}, {(SCISSORS, PAPER), (PAPER, STONE), (STONE, SCISSORS)})?

Originally Posted by jdfm

if the members of D are every possible pair resulting from the set {SCISSORS, PAPER, STONE}, how would the answer look like if it were expressed as (D, S)?

({(SCISSORS, SCISSORS), (SCISSORS, PAPER), (SCISSORS, STONE), (PAPER, SCISSORS), (PAPER, PAPER), (PAPER, STONE), (STONE, SCISSORS), (STONE, PAPER), (STONE, STONE)}, {(SCISSORS, PAPER), (PAPER, STONE), (STONE, SCISSORS)})?

This is correct.

emakarov: Thanks for the reply.

Doesn't that notation seem a bit... unwieldy? What if the domain was the set of k-tuples of some larger set? The text speaks of using the smaller notation when the domain is clear, when would the domain of a predicate not be clear?

Originally Posted by jdfm

Doesn't that notation seem a bit... unwieldy?

Wait until you come across conventions for writing functions. Nowadays it is customary to define a functions as a triple (D, C, f) where D and C are sets called domain and codomain, respectively, and f is a subset D × C satisfying a certain property. When the domain and codomain are clear from the context, one often writes just f. Now, what if f = {(x, x) | x ∈ ℝ)? In this case, it is not only not realistic to write D = ℝ in full, it is impossible because ℝ is uncountable!

Nobody forces anyone to write sets by listing every element. In your example, we can define A = {SCISSORS, PAPER, STONE} and specify D as A² = A × A. Similarly, we can write the set of k-tuples of a set B as . More to the point, when the text says "Sometimes describing predicates with sets instead of functions is more convenient," I don't think it means that in concrete situations writing a predicate as (D, S) is shorter than writing it as a rule mapping D to {TRUE, FALSE}. Rather, it means that viewing it as a pair of sets instead of a function makes it easier to reason about it in some situations and may provide new insights.

For another example, a group is usually defined as a set with a binary operation satisfying certain axioms. However, it can also be viewed as a set of unary functions on the same set. That is, instead of saying that a group is a set A, a function f : A × A -> A and so on, we say that it is a set A where every element is a function A -> A. Indeed, given A and f : A × A -> A, every x ∈ A is associated with a function f(x, ⋅) that maps any y ∈ A into f(x, y). This is a fresh perspective that may turn out useful sometime.

Originally Posted by jdfm

The text speaks of using the smaller notation when the domain is clear, when would the domain of a predicate not be clear?

For example, when one says that x divides y, usually x and y are assumed to be integers. But it also makes sense to say that x divides y when x and y are reals and y = nx for an integer n. For example, x and y are called commensurable if there exists a real z such that z divides both x and y.