Modelling Space & Time Flashcards
Topological Space
A set X (of things we think of as points)
and
a set of subsets of X (called open sets)
which satisfy certain axioms.
Definition of a Part
Relationship of being a part:
P(x, y) ≡ ∀ z ( C(z,x) → C(z,y) )
Where C(x, y)
means that x
is connected to y
.
The idea of one region being a part of another is that the part is somewhere inside the whole.
Definition of a Proper Part
PP(x,y) ≡ P(x, y) ∧ ¬P(y,x)
Special case: being part but not being equal.
Definition of Overlap
Relationship of regions overlapping
O(x, y) ≡ ∃z ( P(z, x) ∧ ¬P(z, y) )
Overlapping is defined as sharing a region.
Regions that only just touch are not overlapping.
Definition of External Connection
Relationship of regions being externally connected.
EC(x,y) ≡ C(x, y) ∧ ¬O(x, y)
This is the idea of just touching at the boundary and not overlapping.
Definition of Tangential Proper Part
TPP(x,y) ≡ PP(x, y) ∧ ∃z ( EC(z, x) ∧ EC(z, y) )
Special kind of proper part relationship.
Idea of the part being inside the whole but the part does touch the boundary of the whole from the inside.
Definition of Non-tangential proper part
NTPP(x,y) ≡ PP(x, y) ∧ ∃z ( EC(z, x) ∧ EC(z, y) )
Idea of the part being so clearly inside the whole that the part does not touch the boundary of the whole.
RCC axioms: R
R
is a set, the elements of which are the regions
RCC Axioms:u
A special region for the universe, or the whole space.
RCC Axioms:null
An element, which is not a region, for a null element.
RCC Axioms:compl
An operation compl
(complement) gives for each region (except u
) the outside of the region.
RCC Axioms:sum
Gives the union of a pair of regions.
RCC Axioms: prod
Gives the intersection of regions (when it exists), or the null element when the regions do not overlap.
RCC Axioms:C
The binary relation of connection.
8 RCC Axioms
- Every region is connected to itself
- Connection is symmetric
- All regions are connected to the universal region
- Being NTPP of
y
means not being connected to the complement ofy
. And being part ofy
means not overlapping the complement ofy
. - Connected to a sum means connected to a summand.
- Connected to an intersection means connected to a region which is a part of both the intersecting regions.
∀ x, y ∈ R ( prod(x, y) ∈ R ⇔ O(x, y) )
- Every region has a non-tangential proper part.
Axiom R7 was found to be redundant. It can be proved from other ones.
What are the RCC8 Relations?
8 Relationships having the special property that every pair of regions will be in exactly one of these relationships.
They form a Jointly Exhaustive and Pairwise Disjoint set (JEPD).
8 RCC8 Relations
- Tangential Proper Part
- Non-Tangential Proper Part
- Non-Tangential Proper Part Inverse
- Tangential Proper Part Inverse
- Partial Overlap
- Equal
- Externally Connected
- Disconnected
Definition of Self-connectedness
`SCON(X) = ∀y ∀z (( x = sum(y, z)) → C(y, z))
Convex hull
In geometry, the Convex Hull of x
is the smallest region y
including x
and such that any line between points in y
lies entirely in y
.
I.e. the smallest convex region including x.
3 Axioms of a linear order
∀t₁ ∀t₂ ∀t₃ (( t₁ ≤ t₂ ≤ t₃ ) → t₁ ≤ t₃ )
∀t₁ ∀t₂ ( t₁ ≤ t₂ ∨ t₂ ≤ t₁ )
∀t₁ ∀t₂ (( t₁ ≤ t₂ ∧ t₂ ≤ t₁ ) → ( t₁ = t₂ )
Define a strict ordering relation
`t₁ < t₂ iff t₁ ≤ t₂ ∧ ¬ ( t₁ = t₂ )
Axiom: time will continue forever in the future
∀t ∃t' (t < t')
Axiom: time is infinitely divisible
a.k.a. density
`∀t₁ ∀t₂ (( t₁ < t₂ ) → ∃ t₃ (( t₁ < t₃ ) ∧ ( t₃ < t₂ ))
13 Allen relations between two intervals
4 Components of propositional modal logic
- Propositional variables, that stand for atomic propositions just as in ordinary propositional logic
- Logical connectives:
¬
∧
∨
→
↔
- Two additional logical symbols:
- ☐ called box
- ♢ called diamond
- The usual parenthesis to avoid ambiguity.
Formulas of modal logic
Expressions that can be true or false.
Unlike first order logic there are no terms in the language that can refer to individual things.
Rules for construction of a formula
- Every atomic proposition is a formula
- If
⍺
andβ
are formulas then the following are formulas:¬⍺
⍺ ∨. β
⍺ ∧ β
⍺ → β
⍺ ↔ β
☐⍺
♢β
Informal idea of modal logic
In propositional logic, when we give the meaning of an atomic proposition we simply say whether it is true or false.
In model lagic, we can think of propositions not simply being true or false, but being true at some places and false at others.
“Places” might be different times, or objects in the world.
Formal definition:
frame & valuation
A frame is a pair (W, R)
where
- a set W
- a binary relation R ⊆ W x W
a valauation V
provides for each atomic proposition p
, a subset of W
so V(p) ⊆ W
.
Key points on ♢
and ☐
-
♢p
is true atw
whenp
is true somewhere accessible fromw
. -
☐p
is true atw
whenp
is true everywhere accessible fromw
.
Truth, satisfaction and validity
in ordinary propositional logic
A formula ɸ
is satisfiable if it is true under some valuation and valid if it is true under all valuations.
Truth, satisfaction and validity
in propositional modal logic
A formula ɸ
can be:
- True at a particular world in a Frame F
under valuation V
- True at all worlds in a frame F
under valuation V
(satisfied in F
by V
)
- True at all worlds in a frame F
under all valuations (valid in F
)
- Valid in a frames (universally valid)