Hoofdstuk 4:
Predicates: properties which may be true or false of particular elements in a given universe.
Quantifiers: the means by which we refer to elements which satisfy such properties.
We sometimes defined sets by stating using the following notation:
- { x : x > 17}
- { p : p is a prime number}
Or more generally, we write {x : x has the property P}. Such a set consists of all elements that satisfy
the predicate P. In general, we will write P(x) when ‘x has the property P’, or when ‘P holds for x’.
A predicate is not the same as a proposition:
- P(x) = x > 17 ∧ x > 5 defines a predicate on x
- x < 12 defines a proposition.
Predicates differ from propositions in that they do not have a fixed truth value, since we do not
know the value of the object to which it refers.
Example: Let the universe of discourse be the Duck family: DUCKS = {Quackmore, Hortense, Scrooge,
Donald, Della, Huey, Louis, Dewey}, and define the following predicate:
Female(x) = “x is a female”.
Then:
- Female(Hortense) and Female(Della) are both true;
- Female(Quackmore), Female(Scrooge), Female(Donald), Female(Huey), Female( Louis),
Female(Dewey) are all false;
- The truth set of the predicate Female(x) is {Hortense, Della}
Predicates can have more than one argument. In that case, they are typically called a relation. We
have already encountered several different relations when studying sets:
- SubsetOf(A,B) holds if for all x, x ∈ A ⇒ x ∈ B
- EqualSet(A,B) holds if both A ⊆ B and B ⊆ A
- ProperSubset(A,B) holds if A ⊆ B and A ≠ B
Many familiar relations are written using infix operators, such as ⊆ or =, rather than a function
name, such as SubsetOf.
We can ‘define’ a predicate Divides(x, y) to hold when x and y are natural numbers and x divides
evenly y (that is, there is no remainder after performing the division):
- For example, Divides(3, 15) holds.
- But Divides(3, 17) does not.
We can construct a truth-set: {(x, y) : Divides(x, y)} To be the set of all pairs (x, y) such that x divides
evenly into y. Traditionally, mathematicians write x | y when Divides(x, y) holds.
, When defining a predicate of the form: P(x) = ...x... The occurrences of x on the right hand side of the
equality all refer to the x bound by the declaration P(x). If we write: P(x) = ...y... It is not clear what y
is – where it is not bound - we say that the variable y is free. Example: ∀y P (x, y): x is free and y is
bound by the universal quantifier.
We can turn any predicate into a proposition by substituting a value for variable bound in the
predicate’s definition. For example, we can define the following predicate: P(x) = x > 1337
- P(10.000) is the proposition 10.000 > 1337 (which happens to be true)
- P(5) is the proposition 5 > 1337 (which happens to be false).
Example:
How many elements are there in the set { x : x < 17}? It depends! Is it a set of natural numbers,
integers, real numbers, … I prefer to be explicit: { x ∈ N : x < 17 }. This avoids confusion and makes it
clear what the universe of discourse is that I’m assuming. These examples all show that – even in the
study of formal logic – there can be information left implicit in the context, naming conventions,
universe of discourse, etc.
We cannot express infinite conjunctions and disjunctions in propositional logic. Example: The
universe of discourse is the set consisting of the four children: Children = {Joel, Felix, Oskar,
Amanda}. They get into the car and head off to school. One of the children has to sit in the front
passenger’s seat, as there is only room for three
passengers in the back seat. Thus, the predicate:
Front(x) which denotes that child x sits in the front
seat, must be true of some one of them. As there is
only room for one child in the front seat, the
predicate front(x) must be true of exactly one child
that is, it must be true of one and false of all of the
others. This means that the following proposition
must be true:
These propositions are lengthy already when there are only four elements in the universe of
discourse.
Let A be the set {0,1,2,3}. We say A is the subset of some other set B, written A ⊆ B, when all the
elements of A also occur in the set B. Or more precisely: 0 ∈ B ∧ 1 ∈ B ∧ 2 ∈ B ∧ 3 ∈ B.
This may work for a finite set, but what if we want to show that all the even numbers are also
natural numbers? 0 ∈ N ∧ 2 ∈ N ∧ 4 ∈ N ∧ 6 ∈ N ∧ …
Predicates: properties which may be true or false of particular elements in a given universe.
Quantifiers: the means by which we refer to elements which satisfy such properties.
We sometimes defined sets by stating using the following notation:
- { x : x > 17}
- { p : p is a prime number}
Or more generally, we write {x : x has the property P}. Such a set consists of all elements that satisfy
the predicate P. In general, we will write P(x) when ‘x has the property P’, or when ‘P holds for x’.
A predicate is not the same as a proposition:
- P(x) = x > 17 ∧ x > 5 defines a predicate on x
- x < 12 defines a proposition.
Predicates differ from propositions in that they do not have a fixed truth value, since we do not
know the value of the object to which it refers.
Example: Let the universe of discourse be the Duck family: DUCKS = {Quackmore, Hortense, Scrooge,
Donald, Della, Huey, Louis, Dewey}, and define the following predicate:
Female(x) = “x is a female”.
Then:
- Female(Hortense) and Female(Della) are both true;
- Female(Quackmore), Female(Scrooge), Female(Donald), Female(Huey), Female( Louis),
Female(Dewey) are all false;
- The truth set of the predicate Female(x) is {Hortense, Della}
Predicates can have more than one argument. In that case, they are typically called a relation. We
have already encountered several different relations when studying sets:
- SubsetOf(A,B) holds if for all x, x ∈ A ⇒ x ∈ B
- EqualSet(A,B) holds if both A ⊆ B and B ⊆ A
- ProperSubset(A,B) holds if A ⊆ B and A ≠ B
Many familiar relations are written using infix operators, such as ⊆ or =, rather than a function
name, such as SubsetOf.
We can ‘define’ a predicate Divides(x, y) to hold when x and y are natural numbers and x divides
evenly y (that is, there is no remainder after performing the division):
- For example, Divides(3, 15) holds.
- But Divides(3, 17) does not.
We can construct a truth-set: {(x, y) : Divides(x, y)} To be the set of all pairs (x, y) such that x divides
evenly into y. Traditionally, mathematicians write x | y when Divides(x, y) holds.
, When defining a predicate of the form: P(x) = ...x... The occurrences of x on the right hand side of the
equality all refer to the x bound by the declaration P(x). If we write: P(x) = ...y... It is not clear what y
is – where it is not bound - we say that the variable y is free. Example: ∀y P (x, y): x is free and y is
bound by the universal quantifier.
We can turn any predicate into a proposition by substituting a value for variable bound in the
predicate’s definition. For example, we can define the following predicate: P(x) = x > 1337
- P(10.000) is the proposition 10.000 > 1337 (which happens to be true)
- P(5) is the proposition 5 > 1337 (which happens to be false).
Example:
How many elements are there in the set { x : x < 17}? It depends! Is it a set of natural numbers,
integers, real numbers, … I prefer to be explicit: { x ∈ N : x < 17 }. This avoids confusion and makes it
clear what the universe of discourse is that I’m assuming. These examples all show that – even in the
study of formal logic – there can be information left implicit in the context, naming conventions,
universe of discourse, etc.
We cannot express infinite conjunctions and disjunctions in propositional logic. Example: The
universe of discourse is the set consisting of the four children: Children = {Joel, Felix, Oskar,
Amanda}. They get into the car and head off to school. One of the children has to sit in the front
passenger’s seat, as there is only room for three
passengers in the back seat. Thus, the predicate:
Front(x) which denotes that child x sits in the front
seat, must be true of some one of them. As there is
only room for one child in the front seat, the
predicate front(x) must be true of exactly one child
that is, it must be true of one and false of all of the
others. This means that the following proposition
must be true:
These propositions are lengthy already when there are only four elements in the universe of
discourse.
Let A be the set {0,1,2,3}. We say A is the subset of some other set B, written A ⊆ B, when all the
elements of A also occur in the set B. Or more precisely: 0 ∈ B ∧ 1 ∈ B ∧ 2 ∈ B ∧ 3 ∈ B.
This may work for a finite set, but what if we want to show that all the even numbers are also
natural numbers? 0 ∈ N ∧ 2 ∈ N ∧ 4 ∈ N ∧ 6 ∈ N ∧ …
