set theory

Set Theory (and Russell's Paradox) martin Thu, 05/31/2012 - 14:55
Logical System
6/5/12

Tutorial

Set theory is an extensive topic introduced elsewhere. It can be written as a first order theory.

There is one axiom schema, Abstraction (or Comprehension), which can generate infinitely many axioms

∀y(yε{x:Φ[x]}≡Φ[y])

Axiom Schema of Abstraction (or Specification or Comprehension). The Set Builder Axiom Schema.

And a number of other axioms

 (x=y) ≡∀z(zεx≡zεy))      Axiom of Extensionality

Set Theory (and Russell's Paradox)

Logical System

2013

Reading

Colin Howson, [1997] Logic with trees Chapter 11

Tutorial

Set theory is an extensive topic introduced elsewhere. It can be written as a first order theory.

There is one axiom schema, Abstraction (or Comprehension), which can generate infinitely many axioms

∀y(yε{x:Φ[x]}↔Φ[y])

Axiom Schema of Abstraction (or Specification or Comprehension). The Set Builder Axiom Schema.

And a number of other axioms

Help with Ex 3: Moderately Difficult Example martin Tue, 01/13/2009 - 01:55
Topic
Logical System

1/9/09

Help with Ex3 1.

This shows the general technique for proving identities between sets.

The Proof Applet martin Mon, 01/12/2009 - 19:21
Topic
Logical System

1/10/09 13 Software

Some predicate logic proofs or derivations using Gentzen calculus. Try to prove them (click 'Derive It' off the Wizard Menu, if you want help).

Tutorial 10: Set Theory V: Russell's Paradox, Axiomatic Set Theory, and Criticisms martin Sat, 01/10/2009 - 18:13
Topic
Logical System
12/28/20

Russell's Paradox.

Unfortunately (naive) set theory is inconsistent, as was discovered by Bertrand Russell. The problem lies with the Schema of Abstraction, then all that is needed is to consider the set of those objects which are not members of themselves. This seems to be a perfectly good defining property for a set (most sets seem to be not members of themselves; for example, the null set ∅ is not a member of ∅ ie ∅∉ ∅).

Help with Subset Derivation: Short Rewrite Version martin Sat, 01/10/2009 - 12:56
Topic
Logical System

1/9/09

Help with Subset Derivations [Short form example]

There is a shorter and quicker proof using rewrite rules. Ordinarily there is a lot of messing around with instantiating quantifiers, renaming bound variables, etc.. Rewrite rules avoid much of this (and so we can concentrate on Set Theory). You might want to remind yourself of Rewrite Rules and its video.

Help with Subset Derivation martin Sat, 01/10/2009 - 12:37
Topic
Logical System

1/9/09

Help with Subset Derivations [Long form example]

This is a long proof using axioms. There is a shorter and quicker way using rewrite rules.

 

Tutorial 7: Set Theory II: Subsets, Empty Set, Universe Set martin Fri, 01/09/2009 - 22:49
Topic
Logical System
12/25/20

There is the notion that whenever an element is a member of one set then it is also a member of a second set. When this occurs the first set is said to be a subset of the second, and this is denoted by the symbol '⊂' . There is an axiom covering this

(x⊂y) ≡(∀z)(zεx⊃zεy)     Axiom of Subsets

In English this says, 'x is a subset of y if, and only if, All z, if z is a member of x then z is also a member of y' .

Tutorial 9: Set Theory IV: Ordered Pairs, Cross Products martin Fri, 01/09/2009 - 12:50
Topic
Logical System
12/27/20

Order and Ordered pairs

Thus far nothing we have done has order in it. We are definitely going to need the notion order, both for mathematics and everything else. In mathematics, on a simple two dimensional graph the point with x=1 and y=2 is not the same as the point with x=2 and y=1. In the world at large John being taller than Jane is not the same as Jane being taller than John. Set theory is going to need an approach to order.

Tutorial 8: Set Theory III: Union, Intersection, Complement, Unordered Pairs, Power Set martin Thu, 01/08/2009 - 10:55
Topic
Logical System
12/15/20

With two sets, say x and y, there are various ways they can be put together.

There is the union of the two sets, symbolized with ∪, which the set formed when elements are members of one set or the other

zε(x∪y) ≡ (zεx∨zεy)      Axiom of Union

zε(x∪y) :: (zεx∨zεy)       Union Rewrite

There is the intersection of the two sets, symbolized with ∩, which the set formed when elements are members of one set and the other