Summary The Logic Manual - Chapter 1 Notes

1. Sets, Relations and Arguments
1.1: sets
A set is a collection of objects

The objects in the collection are elements in that set

Sets are identical only if they have the same elements
E.g. Set of animals with kidneys is identical to set of animals with heart
Because exactly those animals that have kidneys also have a heart and vice versa

𝑎∈𝑆
A is an element of S

∅
The one set that contains no elements (the empty set)

{London, Munich} = {Munich, London}
A set containing London and Munich
This method of designating sets fails when:
• One lacks names for elements in the set
• There are infinitely or impractically many elements

{x : x is an animal with a heart}
A set containing all animals that have a heart

{x : x is blue all over or x is red all over}
A set containing all objects either blue or red all over

1.2: Binary Relations
Ordered pairs (often referred to as pairs):
<London, Munich>
Unlike a set with two elements the order of the components matters

<d,e> and <f,g> are only identical is d=f, e=g

Definition 1.1
A set is a binary relation if and only if it contains only ordered pairs

∅ is a binary relation because it does not contain anything that is not an ordered pair

'iff' is an abbreviation of 'if and only if'

Definition 1.2
A binary relation R is
1. Reflexive on a set S iff for all elements d of S the pair <d,d> is an element
of R
R is reflexive on a set S if it relates every element of X to itself
E.g. The relation "is equal to" is reflexive over the set of real numbers
E.g. From the set A = {p,q,r,s}, R={<p,p>,<p,r>,<r,r>,<s,s>,<r,s>}

, 2. Symmetric on a set S iff for all elements d, e of S: if <d,e>∈ 𝑹 then <e,d>∈
𝑹
E.g. Set a={a,b,c} R={<a,b>,<a,c>,<b,a>,<c,a>,<a,a>}
iii. Asymmetric on a set s iff for no elements d,e of S: <d,e>∈ R and <e,d>∈ R
This means that it MUST be irreflexive (no element is related to itself) and
antisymmetric
E.g. Sed A={a,b,c} R={<a,b>,<a,c>}
iv. Antisymmetric on a set S iff for no two distinct (that is, different) elements
d,e of S: <d,e>∈ R and <e,d> ∈ R
This means that in an antisymmetric set <d,e>,<e,d> is true iff d=e
Can contain reflexive relations
E.g. A={a,b,c} R={<a,b>,<a,a>,<c,a>}
v. Transitive on a set S iff for all elements d,e,f of S: if <d,e>∈ R and <e,f>∈
R, then also <d,f>∈ R
E.g. A={a,b,c} R={<a,c>,<c,b>,<a,b>}
NOT R={<a,b>,<b,c>) (because <a,c> would be required)
If two elements are indirectly related (through other elements) then they also require a
direct relation

Definition 1.3
A Binary relation R is
i. Symmetric iff it is symmetric on all sets
ii. Asymmetric iff it is asymmetric on all sets
iii. Antisymmetric iff it is antisymmetric on all sets
iv. Transitive iff it is transitive on all sets


Relations and their properties can be visualised by diagrams

Examples:

{<France, Italy>,<Italy, Austria>,<France, France>,<Italy, Italy>,<Austria, Austria>}




Therefore on the set {France, Italy, Austria} the relation is reflexive and antisymmetric,
not transitive (<France, Austria> would be required), not symmetric (there are one-way
arrows), not asymmetric (there are reflexive elements)

{<Eiffel Tower ,Ponte Vecchio>,<Ponte Vecchio, Ponte Vecchio>,<Ponte Vecchio,
Eiffel Tower>}