Announcements:

• Friday, 29 February: Professor John Schlipf (Computer Science) will give a presentation on a recently published paper about probabilistic modal logics.
• A Regular Weekly Schedule is Set! Meetings for this quarter (Winter 2008) will be held on Wednesdays and Fridays, from 3:30-5:00 in 807 Old Chem.
• Email Problems Resolved! If you have been unable to receive emails to the mailing list and you tried to subscribe using an "@uc.edu" email address, please re-subscribe using your real email address (the @uc.edu address is simply an alias).
  See the note in the section on Problem for @uc.edu Emails below for details.
• If you haven't already, please join the mailing list! (see below for information on how to do this)
  

1. Upcoming Presentations

Below is a list of all scheduled upcoming presentations.
Unless otherwise stated, all upcoming presentations will be held in 807 Old Chem.

• Friday, 29 February 2008: "Probabilistic Modal Logic" by Professor John Schlipf (Computer Science, website).
  Abstract: A modal logic is any logic for handling modalities: concepts like possibility, necessity, and knowledge. Artificial intelligence uses modal logics most heavily to represent and reason about knowledge of agents about others' knowledge. This type of reasoning occurs in dialog, collaboration, and competition. In many applications it is also important to be able to reason about the probability of beliefs and events. In this paper we provide a formal system that represents probabilistic knowledge about probabilistic knowledge. We also present exact and approximate algorithms for reasoning about the truth value of queries that are encoded as probabilistic modal logic formulas. We provide an exact algorithm which takes a probabilistic Kripke structure and answers probabilistic modal queries in polynomial-time in the size of the model. Then, we introduce an approximate method for applications in which we have very many or infinitely many states. Exact methods are impractical in these applications and we show that our method returns a close estimate efficiently.
  
  
• To Be Announced. "Port Royal Logic" by Professor John Martin (Philosophy, website).
  Abstract: The Port Royal Logic (16th century), on how logical theory, mainly the semantical interpretation of formulas, had to be re-explained when Cartesian philosophy and physics overtook the learned world with its odd denial that the external world could causally affect the mind. Their solution lead to the concept of intensionality in semantics and logic.
  
  
• Wednesday, 5 March 2008, 3:30-4:30pm in 807 Old Chem: "Buy One Get One Free Scheme" by Renling Jin (College of Charleston, website).
  (Hosted by the UC Department of Mathematics)
  Abstract: We can measure the "size" of an infinite sequence of positive integers using various densities. In the talk, I will present a general scheme that for every theorem about Shnirel'man density or lower asymptotic density one can get a new theorem about upper Banach density for free even though the upper Banach density seems to be very different from Shnirel'man density or lower asymptotic density. The scheme uses nonstandard model of Peano Arithmetic in model theory to establish the connection between these densities.
  References:
  1. R. Jin and P. Bihani, Kneser's Theorem for Upper Banach Density, Journal de theorie des nombres de Bordeaux, vol 18, no 2 (2006), pp. 323 --- 343.
  2. R. Jin, Nonstandard Methods For Upper Banach Density Problems, the Journal of Number Theory, 91 (2001), pp. 20---38.
  
  
  
• Thursday, 6 March 2008, 4-5pm in 801 Old Chem "Nonstandard Power in the Standard World: A New Result for Freiman's Inverse Problems" by Renling Jin (College of Charleston, website).
  (Hosted by the UC Department of Mathematics)
  Abstract: In the talk we will present a theorem in additive/combinatorial number theory about Freiman's inverse problems. Let A be a finite set of integers. The theorem says that if A+A has 3|A|-3+b elements for a small positive b, then A is either a subset of an arithmetic progression of length at most 2|A|-1+2b or a subset of the union of two arithmetic progressions with the same difference and a combined length at most |A|+b. We will also explain how the tools from nonstandard analysis are used and why they are crucial in the proof. The talk is intended for a general audience of mathematicians. The background information on Freiman's inverse problems will be supplied and nonstandard analysis will not be discussed in detail.
  References:
  1. Renling. Jin, Freiman's Inverse Problem with Small Doubling Property, Advances in Mathematics, Vol. 216, No. 2, (2007), pp. 711-752
  2. Melvyn. B. Nathanson, Additive Number Theory--Inverse Problems and the Geometry of Sumsets, Springer, 1996.
  
  
  

2. Past Presentations

Below is a list of all past presentations given by the group.

• Friday, 8 February 2008: "Lukasiewicz's original 3-valued logic" by Professor John Martin (Philosophy, website).
  Abstract: Forthcoming...
  
  
• Wednesday, 6 February 2008: "Neoplatonic Logics" by Professor John Martin (Philosophy, website).
  Abstract: Forthcoming...
  
  
• Friday, 25 January 2008, 4-6pm in 43 McMicken: "Multiple Realization, 40 Years Later" by Thomas Polger (Philosophy, website).
  (Hosted by the UC Department of Philosophy)
  Abstract: In his "The Nature of Mental States," Hilary Putnam (1967) argued that his functionalist hypothesis is preferable to the mind-brain identity theory on the grounds that it better accommodates the fact that mental states like hunger and pain can be had by such neurologically diverse creatures as human beings and octopuses. Hunger and pain are, Putnam argued, multiply realized. Few philosophical theses have been as quickly and widely accepted as the multiple realization of the mental, and the consequent rejection of the identity theory. Yet there remains a good deal of confusion about the nature of the phenomenon of multiple realization, about the structure of the argument for multiple realization, and about the actual evidence of multiple realization. In this talk I address these issues. (This talk draws on a paper forthcoming in Philosophy of Science, along with several other works in preparation.)
  
  
• Wednesday, 16 January, and Friday, 18 January 2008: "McCarthy's Circumscription Logic" by Professor John Schlipf (Computer Science, website).
  Abstract: Various people have proposed methods of modifying formal logic to describe ordinary discourse and ``common sense'' reasoning. One such approach is John McCarthy's circumscription. There, the syntax is the same as for classical logic, but the semantics is changed; only some of the classical models of a formula are considered. We define circumscription, in two of its variants, and discuss its motivation in ``negation as failure.'' McCarthy hoped that his ``common sense reasoning'' would be computationally easier than classical logic. Unfortunately, the opposite turns out normally to be true. We state and sketch the proofs of some results.
  Download: PDF (64KB)
  
  
• Friday 16 November 2007, Wednesday 23 January, and Friday 1 February 2008: "On Various Transition Logics" by Tamisra Sanyal (Computer Science).
  Abstract: An introduction to various transition logics such as LTL, CTL, and CTL*. Their syntax and semantics are covered, as well as various computational properties.
  
  
• Friday, 9 November, and Friday, 16 November, 2007: "Probabilistic Reasoning with Default Knowledge" by Pavel Klinov (Computer Science, website).
  Abstract: The talk will be largely based on few works of Thomas Lukasiewicz who adapted non-standard entailment relations (such as Lehmann lexicographic entailment) to work with probabilistic default theories. I'll start with the propositional probabilistic default logic, its semantics, the problems of satisfiability and consistency. Then, we'll discuss few entailment relations that allow non-monotonic default probabilistic reasoning and compare them.
  
  
• Friday, 2 November 2007: "Randomness of Weakly Computable Real Numbers" by Dr. Xizhong Zheng (Mathematics, website).
  Abstract: We will firstly recall definitions of randomness, relative randomness, and Solovay reduction of real numbers. Then it will be shown that, a real number is weakly computable (or, d-c.e.) iff it is Solovay reducible to a c.e. random real.
  
  
• Friday, 26 October 2007: "On the Weakly Computable Real Numbers" by Dr. Xizhong Zheng (Mathematics, website).
  Abstract: Weakly computable real numbers are defined as the differences of c.e. real numbers and also called d-c.e. We will show that the class of d-c.e. real numbers can be characterized in several equivalent ways and show that this class has very nice mathematical as well as computability-theoretical properties.
  
  
• Friday, 12 October 2007: "A Computability Theory of Real Numbers" by Dr. Xizhong Zheng (Mathematics, website).
  Abstract: The notion of computable real numbers was introduced by Alan Turing in his seminal paper of 1936. To define the computability of real numbers precisely, he developed the famous computation model --- the Turing machines. Although the computability theory mainly concerns the discrete sets in the last 70 years, a computability theory of real numbers is of great interests for theoretical research as well as for practical applications. This talk will give a short overview about the recent development of this theory. Several variants of computability of real numbers will be introduced. We explore their mathematical properties and computability theoretical properties as well. Especially, we will show a finite hierarchy of computable approximable real numbers which corresponds different requirements of computability in applications.
  
  
• Wednesday, 10 October, and Friday, 19 October 2007: "An Introduction to Finite Model Theory" by Ryan Flannery (Computer Science, website).
  Abstract: A simple survey of the field of finite model theory. Focus is on the problems within the field and some of the major proof techniques, specifically Ehrenfeucht-Fraïssé games (EF games). Examples of using EF games are presented, as well as some winning strategies for the duplicator and how to use those.
  Download: PDF (312KB) (Note that each slide is seperated by a horizontal line, and I have removed all material not covered in the presentation itself)
  
  

3. About the Group

The intention of this group is to create a regularly meeting forum for students studying in the areas of logic and foundational mathematics, either pure or applied, to...

• Exchange ideas
• Present topics that some are simply interested in
• Present any current research one may be pursuing
• Provide a regular forum for peer review and discussion
• Have fun

Presentations each week are planned and announced ahead of time and open to anyone interested, student or faculty. Possible topics are anything related to Logic or Foundations of Mathematics, either theoretical or some application. These areas of study are, of course, quite broad and have applications in many areas. Anyone studying or applying these areas is welcomed to attend.

As stated, the weekly seminar is informal, and not worth any course credit for students who attend. The hope is that this seminar would not be a burden to any student or faculty (canceling meetings or presentations for any reason would be acceptable), but rather encourage students to present and exchange ideas freely.

4. The Group Mailing List

The mailing list is the primary method of communication for the group. As such, joining is essential. We are currently using a Google-Groups mailing list, whose address is

   uc-logic⟨at⟩googlegroups⟨dot⟩com

4.1 Subscribing to the Mailing List

To subscribe to the mailing list, simply send an email to

   uc-logic-subscribe⟨at⟩googlegroups⟨dot⟩com

4.1.1 Problem with @uc.edu Emails

If you try to subscribe to the mailing list using your "@uc.edu" email address, it will fail. As UCit has informed me, this is because such addresses are simply aliases that point to your "real" email address (usually something of the form "@email.uc.edu", "@ucmail.uc.edu", or a department-specific address). Google-groups mailing lists require you subscribe using a non-alias email address. See the next section for more details as to why this is.

In order to subscribe, you will need to use your "real" email address. Additionally, you must remember that whenever you send emails to the mailing list, you must send the emails using your real email address as the "from" address.

4.1.2 Problem with Email Aliases

In an effort to prevent the use of GoogleGroups for spamming, GoogleGroups does not allow email aliases to subscribe to mailing lists.

If you are not sure what an email alias is, consider the following example. A certain bearded adviser of mine (we'll call him "Johannes") has a department-specific email account "johannes@ececs.uc.edu", for which "johannes@uc.edu" is an alias. As such, Johannes can both receive email sent to this @uc.edu alias as well as send email as if it came from that alias.

However, when sending email from "johannes@uc.edu", the receiving mail server still records "mail.ececs.uc.edu" as the server that sent the email (since the "@uc.edu" email is simply an alias, and the "@ececs.uc.edu" mail server actually does all the work).

Imagine if GoogleGroups allowed email aliases to subscribe to mailing lists... Anyone could setup their own mail server, create a million email aliases all pointing to the same dummy email account, register the million aliases, and then change each alias to point to a real email account of some unsuspecting victim. Vioala! Instant spam list!

4.2. Unsubscribing from the Mailing List

To unsubscribe, simply send an email to

   uc-logic-unsubscribe⟨at⟩googlegroups⟨dot⟩com

4.3. Posting to the Mailing List

To send emails to the mailing list (and thus all subscribed members), simply send and email to

   uc-logic⟨at⟩googlegroups⟨dot⟩com

• Attachments are allowed, and will be sent to everyone subscribed to the mailing list. Use discretion!
• You must be subscribed to the mailing list in order to send mail to it.

4.4. Browsing/Searching the Mailing List Archives

To browse emails previously posted to the mailing list, simply visit the following website:

   http://groups.google.com/group/uc-logic/topics