Testing LaTeX

$\displaystyle|\mathcal{F}|^k\leq \prod_{i\in I} |\mathcal{F}_i|^k$
That's a corollary to Shearer's Lemma, by the way.
(I haven't told you what $I$, $\mathcal{F}$ and $\mathcal{F}_i$ are; oh well)

Anyway. This is courtesy of Watch Math. It's pretty simple, in fact. And it'll make the math on this site prettier.

I may (read: probably won't) get around to rewriting all my math in $\color{white}\LaTeX$.

Edit: Hmm... it seems the LaTeX sometimes takes a little while to load properly. Please be patient.

Introduction to Logical Languages (2)

In my last post (earlier today), we defined a logical language. But we ended wondering how to give meaning to this language. Since we are looking at mathematical logic, we want a mathematical structure to talk about-- every logical statement fits inside of some logical structure: A group G, ZFC, N, the theory of groups, etc.
So, what is a structure and how does this relate to a logical language? A structure is just a set which has some additional material attached; since we have a language we're not using, we might as well attach it to the set.

For a set A, and a language L, an L-Structure is a non-empty set A, (called the universe of structure for A) such that:

• For each constant symbol c, we have a c^A in A.
• For each k-ary function symbol f, there is an f^A:A^k->A.
• For each k-ary relation symbol R, there is an R^A in A^k

These x^A are called interpretations of x. You can think of an L-structure relating to L as a meaning for L. They just drop these symbols into this universe structured around A, and give them a home. But we still don't actually have a way to get from L to its "meaning" in A! Namely, our structure does not contain any information about variables.

A quick recap: we've taken a set A, and equipped it with a structure by dropping symbols from a logical language into it-- notice that constants are just members of A; this is a good thing. And k-ary functions (relations) are functions (relations) which take k elements of A; also a good thing. But we still haven't done anything with our variables So, what kind of variables do we have if we're looking at a set A? We have elements of A. So, let s be a function s:V->A, and let's call it an evaluation map [remember, V is the set of variables in our language]. So, we have a function which gives each variable a value. Good!

But right now, our function and our L-structure are kind of disjoint. We need a function which can take the value of our variables and push those through the interpretations of our functions and relations. So!
For s, let s':T->A with the following properties:

• s'(x)=s(x) [when x is a variable]
• s'(c)=c^A [when x is a constant]
• s' preserves function application: s'(f(t_1,...,t_k))=f^A(s'(t_1),...,s'(t_k)).

These properties mean that s' preserves the structure we've defined on A (so s' is a homomorphism.) If the structure weren't preserved, then we'd run into the problem that if you evaluated f first, you might get something different than if you evaluated the arguments first. Also, you may be wondering why relations aren't included in this: remember that T is the set of terms, and relations aren't terms.

So far, we've defined a logical language, and we've given our language a set to play in, and given our terms a meaning. Pulling back out, when our terms mean something, then we can ask whether a statement about our terms is true. So, truth:
For an L-structure X on A, and an evaluation map s:V->A (X is easier to write than a new font), a statement a is called true (with evaluation s)-- in symbols X|- a [s] if:

• When a: t=u, then X|- a [s] iff s'(t)=s'(u)
• When a: R(t_1,...,t_k), then X|- a [s] if and only if R^X(s'(t_1),...s'(t_2)) holds.
  
• Similarly for non atomic formulas.

Basically all we are saying is "The statement is true in a structure if and only if it makes sense to call it true in that structure." We've just jumped through some hurdles so that we can say "it makes sense" in a rigorous way.

I hope this was easier to follow than the lectures it came from (to be fair, I've left out some useful material about homomorphisms, which was almost as abstract as the evaluation maps)

Introduction to Logical Languages (1)

This is mostly to clarify in my mind the material from the first 2 lectures of the (mathematical) logic class I'm taking. Hopefully it will also help someone else.

So. We want to be able to look at logic from a formal, rigorous perspective-- which means we need to define logic formally. The guiding question when defining it should be: What does a logic look like? We want variables and all the fun logical connectives, and we want them to mean something, and we want all the meanings (eventually) to boil down to the question "Is this statement true?".

So, let's make each of those happen, one at a time;
First, we need some symbols. We will call S our alphabet-- the set of symbols. This may be tediously formal, but it must be done. Since we want to create a logic, we need the logical symbols: So S contains the connectives and quantifiers, (I'm not going to list them) and just as importantly: variables. These are our logical symbols. Since this is mathematical logic, we need some mathy non-logical symbols; these will be constant symbols, relation symbols and function symbols (these will also "look like" variables, but we want to distinguish between them for reasons we will see shortly). We will also consider '=' to be a logical symbol-- I know it's a relation, but it's a special one, and we want to keep it special.

So, we have a bunch of symbols; that doesn't do us much good, so let's let S* be the set of finite sequences from S. Namely, the empty sequence (I'll use _|_) is in S*, S is a subset of S*, and if a and be are in S, ab (the concatenation of a and b) is in S*.
We want to define a language, L, as a subset of S*, but while any subset is a language, we don't want just any subset: it has to be something that we can "read" in a meaningful way. We have to define our language inductively, and piece by piece. I'll let you know when we get there.

Let the set of L-terms (or just terms) be the smallest T such that:

• V (the set of variables) is in T.
• C (the set of constant symbols) is in T.
• Whenever t_1,...t_k are in T, and f is a k-ary function symbol, f(t_1,...,t_k) is in T.

Notice that this definition is recursive: any t_i in the last condition may have the form f'(t_1',...,t_k').
A term is an object which we can equip with some non-logical value, which may need some sort of context (a value for a variable). But a term does us no good on its own, if we are interested in logical values. So, an atomic formula is:

• if t, u are terms, then "t=u" is an atomic formula.
• if t_1,...,t_k are terms, and R is a k-ary relation symbol, then R(t_1,...,t_k) is an atomic formula

So, like any set of "atoms", atomic formulas are the building blocks for formulas.
The set of L-formulas (or just formulas) is defined inductively:
Base case: Atomic formulas are formulas.
Closure: The set of formulas is closed under logical connectives, and quantifiers.
(What this means is that if you have two formulas, p and q, you can connect them using a logical connective, and you can quantify them, and the sequence of symbols you create will also be a formula.)

So, we now have something that looks like the logic we know. But there is a problem: if x and y are variables, "x=y" is a valid formula. But what are x and y?
In that formula, both x and y are free variables. For a given formula the free variables are :

• (for s, t terms) FV(s=t)= var(s)Union var(t) [var(t) means the variabls in t]
• (for R a k-ary relation) FV(R(t_1,...,t_k))= Union(t_i)(over 1≤i≤k)
• (for ~ a logical connective, a,b formulas) FV(a~b)= FV(a)UnionFV(b)
• (for x a var, b a formula) FV(forall x, b)= FV(there exists x, b)= FV(b)\{x}

(Sorry for the formatting...) All this says is that anytime a variable is introduced, it is "free" until it has been quantified.
So finally, we have: A sentence is a formula with no free variables, and our logical language, L, is the set of all sentences from S*.

Cool! We have a logical language. Looking back at our list of things we want, we've got connectives, and we've got quantifiers and just a little bit more. Unfortunately, this means we're not quite done: this language is meaningless. We haven't once said what these symbols actually mean. And we will learn how to do that next time.

Random Conversation

(Laughter has been removed)

MC: hmm. I'm demoting you
CK: ?
MC: you are no longer Master Commander of Hypothetical Operations.
CK: But if you don't demote me, think about how great everything would be!
MC: Your title is now Chief Executive of Jello Affairs.
CK: But!!! I'm not jiggly enough!
MC: hmm... actually, I don't know if I like that title... Jello Executive, Fruity Faction.
CK :I do, however, know that every conditional with a false antecedent is true... and I am responsible enough to only imagine badass scenarios.
MC: mostly so it abbreviates to JEFF
CK: If I had not been demoted, you would be richer than google.
MC: a googol dollars!!!
CK: If I were currently MC of HO, then yes.
MC: hmm
CK: (Hurray vacuous truths!!!) Allowing mathematicians to make vacuous promises since 1000BC
MC: right, could have doesn't actually imply causal effect, does it?
CK: Well, it's that If x Then y is always logically true when x is false. Because the implication is only broken when x is true and y is false. I had a prof who was in the habit of using vacuously true cases for the base case of an induction. Like, a statement about edges in a graph; his base case would have no edges...
CK: Why did I get demoted, by the way?
MC: glitch in the payroll system.
CK: Ah. Well; can't be helped.
MC: actually, we introduced the glitch after the fact
CK: I can't blame anyone, can I.
MC: there was a glitch in the name placards and they came out wrong.
CK: Well, if the name placard says so, it must be so.
MC: so we demoted/promoted people accordingly. It only made sense.
CK: Of course.
MC: we didn't want to waste the money we spent printing them.
CK: A company needs principles if it's to run smoothly. Principals? I don't know which.
MC: well, it needs both; who else is going to turn the hamster-wheel-power-generator?
CK: Right. This is why you can promote, and I'm only the JEFF. Best conversation ever, by the way.
MC: no, they only let me demote. I don't have authority to promote. They only give that authority to the janitor's secretary.
CK: I see. That seems sensible.
MC: I'm not sure this conversation would make any sense were I to read through it after forgetting the fact itself.
CK: You forget that it makes no sense now.