Results 1 to 4 of 4
Like Tree2Thanks
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Predicate to Set

  1. #1
    Newbie
    Joined
    Aug 2012
    From
    Lisbon
    Posts
    8

    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 \in 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)})?
    Last edited by jdfm; October 6th 2012 at 03:31 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,418
    Thanks
    718

    Re: Predicate to Set

    Quote Originally Posted by jdfm View Post
    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.
    Thanks from jdfm
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Aug 2012
    From
    Lisbon
    Posts
    8

    Re: Predicate to Set

    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?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,418
    Thanks
    718

    Re: Predicate to Set

    Quote Originally Posted by jdfm View Post
    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 B^k. 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.

    Quote Originally Posted by jdfm View Post
    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.
    Thanks from jdfm
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 23rd 2011, 12:05 PM
  2. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 5th 2010, 07:53 AM
  3. Predicate Logic
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 29th 2010, 03:51 PM
  4. Predicate Calculus
    Posted in the Calculus Forum
    Replies: 1
    Last Post: May 21st 2009, 05:19 PM
  5. Predicate and Quantifier
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: June 17th 2007, 05:49 PM

Search Tags


/mathhelpforum @mathhelpforum