Set Builder Notation

Return to Course Outline

Previous Lecture

Questions?

Should one use symbols or English in theorem statements?

The guideline is to avoid symbols that obscure meaning or make it hard to follow, but the actual practice of that is very dependent on audience. For stating a typical theorem about logic and an audience such as this class, I might write something like...

“Theorem: If P and Q are propositions, then ¬(P ∧ Q) is equivalent to ¬P ∨ ¬Q.”

Open Sentences

Which of the following are open sentences (aka predicates)?

• x is greater than 6. This is a classical example of an open sentence.
• x is better than 6. This is not an open sentence, it’s subjective.
• x is less than y. This is an open sentence with 2 variables; multiple variables are no problem.
• Let x be any real number greater than 7. This is not an open sentence, it’s an instruction.

Can open sentences with multiple variables have some of them adequately defined and others not? Technically yes, although that’s a subject of more formal approaches to logic than we’re taking. It would involve defining the predicates as functions that define (or “bind”) the variables via their arguments, for example P(x,y) = x < y vs Q(x) = x < y. All variables in a valid open sentence must be bound, so the first of these examples is valid while the second isn’t.

Set Builder Notation

Use set builder notation to define...

• The set of real numbers greater than 12. { x ∈ ℝ | x > 12 }. This is an example of the first form of set builder notation, where the first part of the notation introduces the variable and the second provides an open sentence that is true of just those values of the variable that are actually in the set.
• The set of Geneseo students who own snakes. Possible answers include the following, all of which bring up the point that the usual universal sets in math (the naturals, reals, etc.) are in some sense just conventions, there’s no reason that people or Geneseo students or snake owners couldn’t be a named, well-recognized, universal set if the need demanded.
  • { x ∈ Geneseo students | x owns a snake }
  • { x | x is a Geneseo student who owns a snake }
  • Let A be the set of Geneseo students; { x ∈ A | x owns a snake }
• The set of even natural numbers. Here again there are several ways to write the set, of which the clearest is { 2p | p ∈ ℕ }. This is an example of the second form of set builder notation, in which the first part provides a function that calculates the members of the set, given each member of the second part’s set as input:
  • { n = 2p | n, p ∈ ℕ }. But one doesn’t usually see “=” in this form of set builder notation, and having 2 variables makes it hard to follow.
  • { n | n/2 ∈ ℕ }. This is still a little harder to follow than the next one
  • { 2p | p ∈ ℕ }.
• The set of even integers whose absolute value is greater than 2. You can use set builder notation inside set builder notation to define this set in stages, although the result might be hard to read: { x ∈ { 2n | n ∈ ℤ } | |x| > 2 }. Notice that this uses both forms of set builder notation.

Key Points

An open sentence is an assertion that becomes a mathematical statement when values are substituted for variables.

The 2 forms of set builder notation, one that picks elements from a universal set to be in the new set, and one that calculates elements of the new sets from elements of a universal set.

Next

Quantifiers.

Read section 2.4.

Next Lecture