Monthly Archives: June, 2011

Suslin Trees

Definition 1.  A tree is a strict poset (T,<) such that set P(x)=\{t:t<x\} of predecessors of x is well-ordered for all x\in T.

This motivates the notion of a root.  We can define the root of x as r(x)=\min\{P(x)\}.  In particular we can say an element r\in T is a root if it is the root of some element.  We define the height of x as h(x)=ord(P(x)), where ord(X) is the order-type (or ordinality) of X.  The ordinality of a toset (totally ordered set) X is the unique ordinal number to which X is isomorphic (as tosets).

Note that ord(X)\geq |X|.  For example |\omega|=|\omega+1|=\aleph_0.  But ord(\omega)\neq ord(\omega+1) since in the bijection f:\omega+1\to\omega defined by f(\omega)=0 and f(n)=n+1 for finite ordinals, we have 0\leq\omega, but f(0)=1\not\leq 0=f(\omega).

Correspondingly we define the height of T to be h(T)=\sup_{x\in T}\{h(x)\}.  An \alphatree is a tree of height \alpha.  We also define the \alphath level of a tree T as the set L_\alpha=\{x\in T:h(x)=\alpha\}.

Definition 2.  A branch in T is a maximal toset/chain in T.  That is, it is not properly contained within any chain in T.

Definition 3.  A tree T is normal if

  1. T has a unique root;
  2. each level of T is countable;
  3. if x\in L_\alpha is not maximal, then it has infinitely many successors in L_{\alpha+1};
  4. all branches have the same height;
  5. if \alpha<h(T) is a limit ordinal and x,y\in L_\alpha such that P(x)=P(y), then x=y.

Note that tosets can be endowed with a topology called an order topology.  It is generated by predecessor and successor sets.  A poset X is dense if for any comparable x,y\in X, there is a z\in X such that x<z<y.  A toset X is complete if every bounded subset has an infimum and supremum.  A toset satisfies the countable chain condition if every collection of disjoint open rays (predecessor/successor sets) is countable.

Suslin’s Problem.  Let X be a dense, complete, and unbounded toset that satisfies the countable chain condition.  Is X isomorphic to \mathbb{R}?

Note that \mathbb{R} is the unique toset which is dense, complete, unbounded and separable (has a countable dense subset).  The separability of \mathbb{R} implies that it satisfies the countable chain condition.  Since any interval in \mathbb{R} has a rational number (from denseness), then any collection of disjoint open rays must be countable.  Hence Suslin’s Problem asks if the converse is true on tosets that are dense, complete, and unbounded.  This is not provable in ZFC, ZFC+CH, ZFC+GCH, or ZFC+\lnotCH.

Definition 4.  A Suslin line is a dense, complete, and unbounded toset that satisfies the countable chain condition but is not separable.

Hence Suslin’s Problem asks whether or not a Suslin line exists.  This turns out to be equivalent to the existence of Suslin trees.  While a chain of a poset is any sub toset, an antichain is a subset in which no elements are comparable.

Definition 5.  A Suslin tree is a tree T such that h(T)=\omega_1, every branch is countable, and every antichain is countable.

Note these assumptions are not contradictory, since the height of T is not equivalent to the supremum of heights of branches (where height of a branch is defined by supremum of heights of its elements).

Lemma 6.  If there exists a Suslin tree, then there exists a normal Suslin tree.

Proposition 7.  There exists a Suslin line if and only if there exists a Suslin tree.

If SH (Suslin’s Hypothesis) is the nonexistence of a Suslin line and MA is Martin’s Axiom, then the proof of independence follows from ZFC[V=L]\vdash\lnot SH and ZFC[MA]\vdash SH where V=L is the Axiom of Constructibility.

[1] Jech, Thomas.  Set Theory.  Third Edition.  Springer Monographs in Mathematics.  Springer-Verlag.  2003.

Advertisements

New LAUSD Homework Policy

Los Angeles Unified School District put in place a new policy that limits the impact of homework on a students’ grade to 10%.  This appears to be resultant from complaints from parents and students regarding either a time issue or a hindering home environment issue.  “According to the new policy, ‘Varying degrees of access to academic support at home, for whatever reason, should not penalize a student so severely that it prevents the student from passing a class, nor should it inflate the grade’. It was distributed to schools last month”.  Well, as a hypothetical teacher, this policy for my class would just mean upping the weight of examinations to 90%.  And if the premise is based on possible deficiencies of academic support at home, I’m worried this would make the situation even worse when it came time for tests.  Then again, I may be an anomaly in that my grades would be based solely on tests and homework–in general no projects or make-ups on exams.  I mean, I’d be all for this policy since it would separate those who really know the material from those who don’t, but their basis for implementing it seems to be at odds with this ideology.

[1]  http://www.latimes.com/news/local/la-me-homework-20110627,0,6343074.story

Fundamental Knowledge-Part 2: Models

The next task is to absorb the traditional area of mathematical logic.  One key missing ingredient is a model.  Let us recall the traditional setup (taken from [1]).

Definition 2.1.  Let S be a set (of symbols).  An S-structure is a pair \mathfrak{A}=(A,\mathfrak{a}) where A is a nonempty set, called a universe, and \mathfrak{a} is a map sending symbols to elements, functions, and relations of A.  An assignment of an S-structure (A,\mathfrak{a}) is a map \beta:S\to A.  An S-interpretation is a pair \mathfrak{I}=(\mathfrak{A},\beta) where \mathfrak{A} is an S-structure and \beta is an assignment in \mathfrak{A}.

For shorthand notation, the convention (with some of my modifications) is to write:  c^\mathfrak{A}=\beta(c), (f(t_1,...,t_n))^\mathfrak{A}=\mathfrak{a}(f)(\beta(t_1),...,\beta(t_n)), and (xRy)^\mathfrak{A}=\beta(x)\mathfrak{a}(R)\beta(y).  These are the terms.  Formulas are then built from the terms using traditional (although this can be generalized) logical connectives.

The notion of a model is then defined via induction on formulas.

Definition 2.2.  Let \mathfrak{I}=(\mathfrak{A},\beta) be an S-interpretation.  We say that \mathfrak{I} satisfies a formula \phi (or is a model of \phi), denoted \mathfrak{I}\vDash\phi, if \phi^\mathfrak{A} holds, where \phi^\mathfrak{A} is defined via its components and \beta and \mathfrak{a} where necessary.

Formal languages in convention are built up from the formulas mentioned above, which are nothing more than special cases of Alt Definition 1.3.  A model for a language is hence nothing more than an A-interpretation into a structure, where A is an alphabet (provided it is equipped with a logic system).  This is precisely what I have constructed in Part 1;  the symbols of W\subset A^* are mapped to the universe \mathcal{L}_{F,T,W}.  The next thing to establish is that every model is a language model.  This is trivial since a model by definition satisfies a set of formulas as well as compounds of them (i.e. it must satisfy a language).  Hence we have no need to trouble ourselves with interpretations and may simply stick to the algebra of Part 1.

While we have absorbed model theory, there are a few more critical topics to absorb from mathematical logic. We return to the language of Part 1 (no pun).  Let X be a theory of \mathcal{L}_{F,T,W} and \varphi:F[X]\to V be a binary logic system.  A formula \phi\in\mathcal{L}_{F,T,W} is derivable in X if it is a proposition (i.e. is in F[X]).  We may write X\vdash\phi.  This definition is in complete agreement with the traditional definition (namely, there being a derivation, or finite number of steps, that begin with axioms and use inference rules);  it is nothing more than saying it is in F[X].  Similarly \phi\in\mathcal{L}_{F,T,W} is valid if \varnothing\vdash\phi, or equivalently, it is derivable in any theory.  In our setup this would imply \phi\in F[\varnothing]=\varnothing.  Hence no formula is valid.

Let F have a unary operation \lnot and \varphi:F[X]\to V be a logic system on a theory X.

If we assume \lnot to be idempotent (\lnot\lnot\phi=\phi), then since \varphi is a homomorphism, we have \varphi(\phi)=\varphi(\lnot\lnot\phi)=\lnot\lnot\varphi(\phi).  That is, the corresponding unary operation in V must also be idempotent on ran(\varphi).

Definition 2.3.  A unary operation \lnot (not necessarily idempotent) is consistent in \varphi if for all \phi\in F[X], \varphi(\phi)\neq\varphi(\lnot\phi).

If we assume \lnot is consistent in \varphi and that \varphi is a binary logic system, then the corresponding \lnot in V is idempotent since

\varphi(\phi)=0\Rightarrow\varphi(\lnot\phi)=1\Rightarrow\varphi(\lnot\lnot\phi)=\lnot\lnot\varphi(\phi)=0.

Again, proofs in a binary system are independent of the choice of valence.   If we assume consistency and idempotency, then we have a nonidentity negation which is idempotent on the range.  The case for assuming binary system and idempotency yields either a trivial mapping of propositions (all to 0 or all to 1), or that \lnot is consistent and idempotent on V.  And lastly if we assume all three (idempotency and consistency of \lnot together on a binary system), we obtain a surjective assignment with idempotent negation in V.

Let \varphi:F[X]\to V be a binary logic system where V is a boolean algebra.  Then the completeness and compactness theorems are trivial.  Recall these statements:

Completeness Theorem.  For all formulas \phi and models \mathfrak{I},

\mathfrak{I}\vDash\phi\Rightarrow X\vdash\phi

where \mathfrak{I}\vDash X.

Compactness Theorem.  For all formulas \phi and models \mathfrak{I},

X\vdash\phi\Rightarrow\mathfrak{I}\vDash\phi

where \mathfrak{I}\vDash X.

Traditionally these apply to, what we would call, a binary logic system \varphi:F[X]\to V where V is a boolean algebra (hence F has a consistent, idempotent negation) under traditional operations, and in particular this fixes the operational/relational structures of F, T, and W , but X is arbitrary.  In this setup, all “formulas” (or what we would hence call propositions since they are generated by a theory) are trivially satisfiable since they have a language model.  Hence Compactness is true.  Moreover since they are propositions in a binary logic system, they are in some F[X] for a theory X and are hence derivable; so we have Completeness.

Lastly we wish to address Godel’s Second Incompleteness Theorem;  recall its statement:

Godel’s Second Incompleteness Theorem.  A theory contains a statement of its own consistency if and only if it is inconsistent.

We have only defined what it means for a unary operation in a logical system to be consistent.  Hence we can say that a binary logic system with a unary operation is consistent if its unary operation is consistent.  But all of these traditional theorems of mathematical logic are assuming a binary logic system where V is a boolean algebra , \lnot is idempotent, and the map \varphi:F[X]\to V is surjective.  Hence \lnot is consistent (from above discussion), and the consequence in the theorem is false.

The weakest possible violation of the antecedent of Godel’s theorem is to use a structure to create itself (i.e. that it is self-swallowing), which makes no sense, let alone using it to create a larger structure within which is a statement about the initial structure.  That a binary logic system with unary operation could contain a statement of its own consistency is itself a contradiction, since the theory itself, together with the statement \phi, are in a metalanguage.  It is like saying that one need only the English language to describe the algebraic structure of the English language.  As we previously said at the end of Part 1, one can get arbitrarily close to doing this–using English to construct some degenerate form of English, but you can never have multiple instances of a single language in a language loop.  Another example would be having the class of all sets, then attempting to prove, using only the sets and operations of them, that there is a class containing them.

Hence the antecedent is also false.  So both implications are true.

[1]  Ebbinghaus, H.-D., J. Flum, and W. Thomas.  Mathematical Logic.  Second Edition.  Undergraduate Texts in Mathematics.  New York: Springer-Verlag.  1994.

Fundamental Knowledge-Part 1: The Language Loop

We must start with a language.  A language can be defined in two ways.  First let us begin with the axioms of pairing, union, and powerset and schema of separation.  This gives us a cartesian product of sets, and hence functions.

Definition 1.1.  An nary operation on a set X is a map O:X^n\to X.  A structure is a set X together with an n-ary operation.  The signature of a structure X is the sequence (n_1,...,n_k,...) where n_k is the number of k-ary operations.

Definition 1.2.  Let X and Y be structures with the same signature such that each k-ary operation of X is assigned to a k-ary operation of Y (i.e. f(O_i)=O^i where O_i is the ith k-ary operation of X).  A homomorphism between structures X and Y is a map \varphi:X\to Y such that

\displaystyle \varphi(O_i(x_1,...,x_n))=O^i(\varphi(x_1),...,\varphi(x_n)).

Note that a nullary operation on X is a map O:\varnothing\to X.  That is, it is simply an element of X.  Now let A be a set which we will call an alphabet, and its elements will be called letters.  A monoid X has a nullary operation, 1\in X called a space, and a binary operation, which will simply be denoted by concatenation.  We define the free monoid on A as the monoid A^* consisting of all strings of elements in A.  We now have two definitions of a language, of which the first is traditional and the second is mine:

Definition 1.3.  A language is a subset of A^*.

Alt Definition 1.3.  Let W\subset A^*, T be a relational structure (a set together with an n-ary relation), and F be a structure.  The language \mathcal{L}_{F,T,W} is defined as F[T[W]] where X[Y] is the free X-structure on Y.  In particular elements of W are called words, elements of T[W] are called terms, and elements of \mathcal{L}_{F,T,W} are called formulas.

Definition 1.4.  A theory of \mathcal{L}_{F,T,W} is a subset X\subset\mathcal{L}_{F,T,W}.  Elements of a theory are called axioms.  Elements of F[X] are called propositions.  A theory X of \mathcal{L}_{F,T,W} is called a reduced theory if for all \phi,\psi\in X, \psi\neq O(\phi,x_1,...,x_{n-1}) for all n-ary operations of F and all placements of \phi in evaluation of the operation.  (That is, the theory is reduced if no axiom is in the orbit of another).

For example, the theory \mathcal{L}_{F,T,W} is called the trivial theory.  The theory \varnothing is called the empty (or agnostic) theory.

Definition 1.5.  An nary logic system on a theory X is a homomorphism \varphi:F[X]\to V where F and V have the same signature and V has cardinality n.  We may also say the logic system is normal if \varphi(\phi)=\varphi(\psi) for all \phi,\psi\in X.

In traditional logic V is a two element boolean algebra.  Traditional logic also has a special kind of function on its language.

Definition 1.6.  A quantifier on \mathcal{L}_{F,T,W} is a function \exists:T[W]\times\mathcal{L}_{F,T,W}\to\mathcal{L}_{F,T,W}.  We may write:

\exists(x\in X,\phi)=(\exists x\in X)\phi.

In particular it is a pseudo operation, and gives the language a pseudo structure.  This is similar to modules, where in this case a product of a term and a formula are sent to a formula.

Hence our initial assumption of four axioms (as well as the ability to understand the English language), have in turn given us the ability to create a notion of a language of which a degenerate English can be construed as a special case.  This is certainly circular in some sense, but in foundations we must appeal to some cyclic process.  One subtlety worth noting is that the secondary language created will always be “strictly bounded above” by the initial language;  they aren’t truly equivalent.  (In fact this last statement is similar to the antecedent of Godel’s Second Incompleteness theorem).

The God Theory

The Term:

God is a common yet unclear term.  One definition is “creator of universe”.  We first must clarify what “universe” means.  As far as I can tell, the traditional interpretation of universe is everything (i.e. class of all sets).  In this case, the creator/cause of it (i.e. a larger class, which would hence make the universe a set) makes no sense.

Other common interpretations naively personify the God object as human-like, with notions of benevolence/morality.  Others include concepts of omnipresence, omnipotence, and omniscience.  I’m not really sure how to make use of terms like benevolence or omniscience, but I’d probably go with utilitarianism and omnipresence as respective equivalences.  Now, any object with omnipotence and omnipresence=omniscience is at least as “big” (in the containment/causal sense) as the universe.  But again, since the universe contains everything, by definition, then any object with these qualities is equal to the universe.

So it makes more to sense to “start” with the universe.  Where one can possibly get by using this term is asking what caused variation/lack of uniformity in a hyperfluid with an initially uniform density and 0 velocity gradient.  The universe could then be defined as the interval of nonuniform density/velocity of this fluids’ existence–spurred on by nothing more than some random perturbation.

The Theory:

As a theory, God is simply defined as an initial object in the category of events.  As an initial object it can explain any arbitrary thing, and this is precisely the problem.  Science strives to find a necessary and sufficient theory such that the universe (the set of observable events) models that theory.  While God is clearly a sufficient theory, there is no reason to suggest it is necessary.