This seminar will be a graduate-level survey of topics in logic for philosophers, including propositional logic, modal logic, predicate logic, model theory, completeness, incompleteness, computability theory, set theory and the higher infinite. The material will thus be a mixture of philosophical logic and mathematical logic, and a goal of the course will be to develop the student’s ability to consider these ideas with clarity and precision.

The lectures will be largely self-contained, and some course materials will be distributed during the semester.  On some topics, material will be drawn from:

More Precisely, The Math You Need to do Philosophy, Eric Steinhart, Broadview.

On other topics, students may wish to supplement the lecture notes with other sources, and there are dozens of suitable texts for this purpose, as well as on-line information.

For focused help, students are also directed to the following excellent on-line resources:

1. Math.StackExchange.com, an on-line question/answer forum for mathematics questions, which welcomes questions on logic, and most questions get high quality answers very quickly.
2. MathOverflow.net, a similar site for research-level mathematics questions.

Weekly exercises.  Exercises will be assigned in connection with each lecture, and these are due by the following lecture.  It is fine and even advisable for you to work in groups, but kindly submit only solutions that you yourself have thoroughly mastered.

Final paper.  Students will write a final paper (about 8 pages) on an approved topic chosen in consultation with the instructor.  The instructor’s goal in assigning this paper is to give the students experience both in conducting research on a technical topic, as well as in writing on such a topic.  Suitable topics will be suggested, but they will generally consist not of giving a summary account or criticism of an advanced topic from the literature (this will be discouraged), but rather of considering a modest but novel topic or context—perhaps a variation of a better known theory—and then discovering and working out some interesting aspect of it. The idea is that the paper topic should be a little like undertaking research in logic.  The paper is due by the last day of the semester, and late work will not be accepted.

Grading. Grades will be based on the weekly exercises and the final paper (with a class participation element).  All work for this class, including the final paper, must be submitted by the last day of the semester.  No Incomplete grades will be given—no exceptions.

My intention is to post the weekly problem sets here, by updating this post.  I will make Google+ posts pointing to this page when it is updated, for a circle of subscribed members; send me a message on G+ to join the circle (or you can alternatively just subscribe to this blog, but then you’ll get notified of all my posts).

Lecture 1.  A picture of logic.  Propositional logic. Truth tables; tautologies; logical equivalence; well-formed formulas; induction on formulas; complete sets of connectives; every truth function is represented by a formula in disjunctive normal form; satisfiability; connections with P vs. NP.

Lecture 1 notes by a student

Exercises:$\newcommand\iff{\leftrightarrow}$

1. Make truth tables for $$(p\wedge q\wedge r)\vee((p\wedge q)\to r)$$ $$(p\wedge(t\to q))\wedge((q\iff r)\vee p)$$ $$(((p\vee q)\vee r)\vee(r\to(\neg q\to r)))\to r$$

2. Argue that every well-formed formula of propositional logic has the same number of left as right parentheses.  (According to the rules we gave in class for the formula-building operations.)

3. Argue that every well-formed formula of propositional logic has twice as many parentheses as binary logical connectives.

4. Argue that the collection of tautologies is closed under conjunction, disjunction, implication and biconditional. In other words, if $\varphi$ and $\psi$ are tautologies, then so are $\varphi\wedge\psi$, $\varphi\vee\psi$, $\varphi\to\psi$ and $\varphi\iff\psi$.

5. Which of the converses of these are true? In other words, which of the following are correct:

• If $A\to B$ is a tautology, then $A$ and $B$ are tautologies.
• If $A\iff B$ is a tautology, then $A$ and $B$ are tautologies.
• If $A\wedge B$ is a tautology, then $A$ and $B$ are tautologies.
• If $A\vee B$ is a tautology, then $A$ and $B$ are tautologies.

6. Argue that every propositional assertion is logically equivalent to an assertion in conjunctive normal form (a conjunction of disjunction clauses, each of which is a disjunction of literals).  (Hint:  in class we proved that every propositional assertion is logically equivalent to an assertion in disjunction normal form.  Given $\varphi$, consider $\neg\varphi$ in light of what we did in class.)

7. Determine which of the following sets of logical connectives are complete: $\{\neg,\to\}$,  $\{\neg,\iff\}$.  (The second one is a bit harder, and we’ll cover it in class next time.)

8.  Show that Nand and Nor are the only binary connectives that, by themselves individually, are complete.  (Hint:  if you have a binary connective $A\star B$ that is complete, then consider what the truth table of $\star$ must be. What must it be on the top row? On the bottom row? How many possibilities remain?)

Possible paper topic connected with the Satisfiability problem and P vs. NP.  For example, you could write a paper explaining how the general satisfiability problem reduces to the 3-Sat problem.  (This is a classical result, but one that can be easily rediscovered independently.)

Lecture 2. Discussion of homework problems from last time, including a simple account of the disjunctive normal form theorem and the conjunctive normal form theorem.

New topic:  multi-valued logic; Lukasiewicz/Kleene logic.  Basic truth tables for 3-valued logic.  Discussion of various motivations, such as logic of missing information, logic of possible worlds, logic of unknown truth values, neither true nor false, both true and false; most of these stories are flawed and do not actually capture the logic. Tautologies and complete sets of connectives in 3-valued logic.  Notions of logical equivalence. No strict tautologies. Disjunctive normal form still works.  Weak tautologies are the same as classical tautologies.

Lecture 2 notes by a student

Exercises. 

1. If $\varphi$ is a propositional assertion in the language with $\neg,\wedge,\vee,\to,\leftrightarrow$, and $\varphi(\vec p)=U$. Does there always exist a crispification of $\vec p$ to $\vec p^*$ with $\varphi(\vec p^*)=T$ and another crispification $\vec p^{**}$ with $\varphi(\vec p^{**})=F$? In other words, does the truth value $U$ mean that it could have been $T$ and it could have been $F$, depending on what way the input $U$ values are made crisp?
2. Define a natural analogue of NAND and of NOR for Kleene logic. Does it obey the expected identities? Does it continue to be complete in Kleene logic in the narrow sense? In the wide sense?
3. Verify the De Morgan laws in Lukasiewicz logic, namely, that $\neg(A\vee B)\equiv\neg A\wedge\neg B$ and $\neg(A\wedge B)\equiv\neg A\vee\neg B$, using $\equiv$ to mean logically equivalent in the sense of having the same truth table.
4. Verify the distributivity laws $$P\wedge(Q\vee R)= (P\wedge Q)\vee(P\wedge R)$$ $$P\vee (Q\wedge R) = (P\vee Q)\wedge (P\vee R)$$ in Lukasiewicz logic.  (You probably don’t want to compute the truth table, since it has 27 rows; rather, reason about what must happen if $P$ is true; if $P$ is false; and if $P$ is $U$.)
5. Find an expression in $P$, $Q$ and $R$ that has value $U$, if any of them is $U$, and otherwise has value $F$.
6. Is the truth table of every expression in Lukasiewicz logic determined (as it is in classical logic) by the location of the $T$’s? That is, if you know where the $T$’s are, can you determined whether the others are $F$ or $U$, just from knowing that the expression came from $\wedge,\vee,\neg,\to,\leftrightarrow$?

Possible paper topics.

• Develop the logic of missing information.  The context would be that there is a genuine classical logic world, but we do not know some of the truth values of the atomic facts.  What is a sensible way to develop a logic for this situation? Is it truth-functional? Can we assign truth values to every statement in a sensible multi-valued logic? What are the notions of tautology, validity, completeness, and so on?
• Explore the notion of complete sets of logical connectives in Lukasiewicz logic.  We know the standard set of connectives $\neg,\wedge,\vee,\to,\leftrightarrow$ is not complete, but can we augment it with another connective to make it complete? Is there a single connective in the 3-valued logic that is complete? (I have some good references for research on this topic.)

Lecture 3.  Fuzzy logic. Definitions of the logic. Disjunctive normal form theorem. Traditional connectives are not complete. No finite set  (nor even any countably infinite set, nor even any set of size continuum) is complete for fuzzy logic. Tautologies in fuzzy logic; weak tautologies (truth value $\geq\frac12$); positive assertions (truth value is never $0$). For assertions in traditional logical language, weak tautologies, positive and classical tautologies are the same. The proof uses logical homomorphisms, translating fuzzy logic to Lukasiewicz logic. We discussed various kinds of logical homomorphisms. General treatment of truth-functional logic: a space $\cal L$ of truth values, with logical functions $\neg,\wedge,\vee$ on that space.  Concepts of extensions ${\cal L}_0\subset{\cal L}_1$ and logical homomorphisms $\pi:{\cal L}_1\to {\cal L}_0$. Boolean algebras. Axioms of Boolean algebras. A few examples, including power sets.

Exercises.

1. Verify in fuzzy logic that $$p\iff q\equiv (p\wedge q)\vee (\neg p\wedge \neg q).$$
2. Verify that the de Morgan laws continue to hold in fuzzy logic.$$\neg(A\vee B)\equiv (\neg A)\wedge(\neg B)$$$$\neg(A\wedge B)\equiv(\neg A)\vee(\neg B)$$
3. Verify that the distributivity laws continue to hold in fuzzy logic.$$A\wedge(B\vee C)\equiv (A\wedge B)\vee(A\wedge C)$$$$A\vee(B\wedge C)\equiv(A\vee B)\wedge(A\vee C)$$
4. Argue that in fuzzy logic, just as in Lukasiewicz logic, there are no tautologies in the language having only the traditional five connectives: $\neg,\wedge,\vee,\to,\iff$.
5. Consider the translation from fuzzy logic to Lukasiewicz logic, which takes the center interval $(\frac13,\frac23)$ of fuzzy truth values to the truth value U; the numbers in the interval $[0,\frac13]$ to $F$ and numbers in $[\frac23,1]$ to $T$. Show that this is a logical homomorphism of fuzzy logic to Lukasiewicz logic.
6. Show that there is no logical homomorphism of fuzzy logic to classical logic.
7. Discuss the question of whether fuzzy logic is the logic of probabilistic reasoning. Suppose that we are in a probability space, where the underlying propositional variables are given a probability. Does fuzzy logic then give sensible probabilities for compound logical expressions using those variables? That is, if we know the probabilities of $p$, $q$ and $r$, then does fuzzy logic tell us the probability of compound expressions like $p\to(q\vee r)$?

Suggested Paper topics.

1. Investigate the nature of the fuzzy truth functions that one may define using the standard five connectives. Can one recognize or characterize them? How many binary connectives are realized?
2. Investigate and discuss the issue of continuity of truth functions in fuzzy logic. Under what kind of semantics would one want to make use of or consider discontinuous truth functions?
3. Discuss the issue or ordinal comparision versus cardinal comparison in fuzzy logic truth values.  One might consider logical homomorphisms of fuzzy logic to itself, which preserve the order of truth values, but which greatly magnify small differences or diminish large ones.

Lecture 4 student notes

Exercises.

1. Are all eight combinations of the properties of reflexivity, symmetry and transitivity possible? Provide instances of relations exhibiting each combination that can occur.
2. Criticize the following argument that every relation that is symmetric and transitive is also reflexive: If $E$ is symmetric, then $a\mathrel{E} b$ implies $b\mathrel{E} a$, and so if it is also transitive, it follows that $a\mathrel{E} a$, and so it is reflexive. Is this argument correct? If not, what is a correct statement that a similar argument establishes?
3. How are the concepts of asymmetric, anti-symmetric and “not symmetric” connected to each other? Which imply which others? Which of the eight conceivable combinations actually arise? Provide relations exhibiting each possible combination.
4. How many equivalence relations are there on a 4 element set? It is possible easily to draw a small picture of each one. Organize this chart into the refinement hierarchy.
5. Consider the claim that the living-in-the-same-city-as relation refines the living-in-the-same-country-as relation, on the set of all people.  Discuss the various problematic assumptions underlying this example. For example, if there were a person who lives in more than one country, or no country, or a person who lives in more than one city, or no city; or suppose that there is a city with parts in more than one country. For each of these situations and others you may think of, precisely which parts of the claims that these relations are both equivalence relations on the set of all people and that the first relation refines the second would be affected?
6. Consider the relation of comparability for elements in a partial order.  Is it an equivalence relation? Consider each of the properties of relations that we have considered (reflexive, irreflexive, symmetric, asymmetric, anti-symmetric, etc.) and argue that comparability always has that property or give an example partial order showing that the comparability relation need not have that property.

Exercises.

1. In the language of the structure $\langle\mathbb{N},\leq\rangle$, construct a formula with two free occurrences each of the variable symbols $x$, $y$ and $z$, and with two bound occurrences of $x$ and $y$, but where the bound appearances of $x$ fall under the scope of different quantifications over $x$. Next, construct a second formula with variables $w,x,y,z$ each with one free occurrence and three bound occurrences, but make the bound occurrences of $w,x$, respectively, fall under the scope of different quantifiers of these variables.
2. Distinguish the structure $\langle\mathbb{Z}^+,\mid\rangle$, where $\mathbb{Z}^+$ denotes the positive integers and $n\mid m$ just in case $n$ divides $m$, from the structure $\langle F,\subseteq\rangle$, where $F$ is the collection of finite subsets of the natural numbers $\mathbb{N}$. That is, find a statement in the first-order language with one binary relation, which is true in $\langle\mathbb{Z}^+,\mid\rangle$ and false in $\langle F,\subseteq\rangle$.
3. For each of the following pairs or triples of structures, distinguish them by finding a sentence that is true in the first, but false in the second.  

Lecture 7 students notes

Exercises.

1. Kindly do the rest of problem 3 from lecture 6 above; some of those instances were not mentioned in the previous lecture.
2. Distinguish the following structures in the first-order language having only multiplication, by finding for each structure a sentence true only in that structure:
   $$\langle \mathbb{N},\cdot\rangle\qquad\langle \mathbb{Z},\cdot\rangle\qquad\langle \mathbb{Q},\cdot\rangle$$
3. Show that $\sqrt{3}$ is irrational. (Hint: follow the argument for $\sqrt{2}$ given in lecture, but replace talk of even/odd with talk involving divisibility-by-$3$. After all, a number is even just in case it is divisible by $2$.) What do you think is the general fact concerning whether $\sqrt{n}$ is irrational for natural numbers $n$?
4. Consider the chain of submodels $$\langle\mathbb{Z}^+,\lt\rangle\subset\langle \mathbb{N},\lt\rangle\subset\langle\mathbb{Z},\lt\rangle\subset\langle\mathbb{Q},\lt\rangle$$Are any of these submodels elementary submodels?
5. Argue that $\langle\mathbb{N},<\rangle$ is Leibnizian (any two elements are discernible, that is, they have different types).
6. Let $\langle A,\sim\rangle$ be a relational structure in which $\sim$ is an equivalence relation. Show that if $a\sim b$, then $a$ and $b$ are indiscernible in this structure.
7. Give an example of an infinite pre-order, which is not a partial order, in which any two elements are indiscernible.
8. Using some of the examples from the other exercises, find a structure $\cal M$ and a submodel ${\cal N}\subset {\cal M}$ such that ${\cal N}\equiv{\cal M}$ but ${\cal N}\not\prec{\cal M}$.
9. In the integers, is less-than fundamentally different from greater-than? Compare $\langle\mathbb{Z},<\rangle$ with $\langle\mathbb{Z},>\rangle$. Are there any statements that can tell apart $<$ from $>$? Specifically, argue that the structures $\langle \mathbb{Z},<\rangle$ and $\langle \mathbb{Z},>\rangle$ satisfy exactly the same truths. Conclusion: no first-order assertion can tell apart $<$ from $>$. That is, $\langle \mathbb{Z},<\rangle\equiv \langle \mathbb{Z},>\rangle$.

Paper topics.

1. Indiscernibility and identity.  Objects in a model are indiscernible with respect to a given formal language, if they satisfy all the same formulas in that language. There are numerous examples of structures having indiscernible non-identical elements, or in which all elements are indiscernible or none are, and it would be an interesting project to find examples illustrating the range of possibility.
2. Is every structure characterized by the collection of first-order truths in it? Is this true for finite structures? This is actually a deep topic, and there are many interesting examples and ideas.

Exercises.

1. Which are the definable elements of the following partial orders? For each definable element, provide a definition; if an element is not definable, explain how you know that. 
2. Consider the case of an equivalence relation $\sim$ having exactly one class of size one, exactly one class of size two, exactly one class of size three, etc. Are there any definable elements? What are the definable subsets?
3. Show that every element is definable in $\langle\mathbb{N},+\rangle$. (Hint: it is easy to define $0$; to define $1$, note that $1$ cannot be written as the sum of two other numbers, neither of which are $1$; now use $1$ to define all other numbers.)
4. Show that multiplication is not definable from addition in $\langle\mathbb{Z},+\rangle$. (Hint: If it were, then $1$ would be definable. But argue that $1$ is not definable in $\langle\mathbb{Z},+\rangle$.)
5. Show that “$x$ is even” and “$x$ is odd” are definable in $\langle\mathbb{N},+\rangle$. Using the elimination of quantifiers result from lecture, conclude that $+$ is not definable in the Peano structure $\langle\mathbb{N},S,0\rangle$.
6. Show that “$x$ is prime” is definable in $\langle\mathbb{N},\cdot\rangle$.

Suggested Paper topics.

1. Additional instances of elimination of quantifiers. For example, in $\langle\mathbb{Q},<\rangle$, which is an interesting argument.
2. Argue that in a finite structure, Leibnitzian is the same as every-object-is-definable.
3. Discuss the Leibnitizian axiom of set theory: every two objects are discernible over the ordinals.
4. On the significance of Tarski’s theorem that $\langle\mathbb{R},+,\cdot,0,1,<\rangle$ admits elimination of quantifiers. Discuss significance of having a decision procedure for Cartesian plane geometry.

Exercises.

1. Determine the truth of the following assertions at the various worlds in the following Kripke model. $$\necessary(p\to\necessary p),\quad\qquad \possible\necessary p,\quad\qquad \possible\necessary\neg p,\quad\qquad \necessary p\to\necessary\necessary p,\quad\qquad\possible\necessary(p\iff\neg\possible p)$$
2. Prove that every assertion of propositional modal
   logic is equivalent under the Kripke semantics to an assertion using only
   $\necessary,\wedge,\neg$.
3. Show that $[(\possible\necessary\varphi)\wedge(\possible\necessary\psi)]\implies\possible\necessary(\varphi\wedge\psi)$ is valid on a partial pre-order frame just in case the frame is directed.

Paper topics. We have fewer exercises because it is time to be working on your papers.  Please make an appointment to discuss your topic with me, if you have not done so already.

1. Combine modal logic Kripke semantics with multivalued logic.
2. Investigate predicate modal logic, such as conditions for the Barcan formula and for its converse.
3. Bimodalities obtained by using the accessibility relation and its inverse.
4. Analyze various conceptions of temporal logic using modal logic, and investigate how one’s conception of the nature of possibility through time (such as linear, tree branching, others) arise in the resulting modal logic.

$\newcommand\Mod{\text{Mod}}\newcommand\Th{\text{Th}}$

Lecture 12. Computability theory. Primitive recursive functions; composition; primitive recursion, with examples. Turing machines. Sample programs. Other computational models: register machines, flowchart machines, recursive functions, idealized programming languages. Hierarchy vision of computability vs. threshold vision. Church-Turing thesis (weak and strong). Undecidability of the halting problem.

Lecture 12 student notes

Exercises

1. Write a Turing machine program to compute the function $d(n)=0$, when $n$ is even; otherwise, $d(n)=1$, when $n$ is odd.
2. Extra: Explain how the the class of Turing computable functions avoids the diagonalization argument of Gödel given for the primitive recursive functions. That is, we may still effectively enumerate $f_n$ all computable functions, and still attempt to define $g(n)=f_n(n)+1$. Does this argument show that there are intuitively computable functions that are not Turing computable? Why does it work with primitive recursive functions and not with computable functions?

Paper topics

1. Develop a new model of computability and prove that it is Turing complete.
2. Topics in oracle computation and the Turing degrees.
3. Topics in infinitary computability, such as Blum-Shub-Smale machines, or infinite time Turing machines.

Next week:  Gödel’s incompleteness theorems!

Lecture 13. Gödel’s incompleteness theorems. Hilbert program. Proof of first incompleteness via halting problem (due to Kleene). For any true computably axiomatizable theory $T$, there is a Turing machine program $p$ and input $k$ such that $p$ does not halt on input $k$, but $T$ does not prove this. MRDP theorem. Arithmetization of syntax. Gödel codes. Carnap’s fixed-point lemma. Gödel sentence, “I am not provable.” First incompleteness theorem. Second incompleteness theorem. Derivability conditions. Rosser’s theorem. Tarski’s theorem. Löb’s theorem. Independence phenomenon. Goodstein’s theorem. Kirby-Paris Hydra theorem.

Lecture 13 student notes

Exercises.

1. Show that if $T$ is a computably axiomatizable theory extending PA, then $T$ is inconsistent just in case $T$ proves $\text{Con}_T$.

All students should be working on their final papers, with the topic chosen in consultation with me.  The papers are due by the end of finals week; no late work will be accepted. Please come to my office with drafts for comments and suggestions.

Lecture 14. Set theory and the higher infinite. The googol plex bang stack hierarchy. Hilbert’s hotel. Countable sets. Cantor’s theorem on the uncountability of the reals. Equinumerosity. Cantor-Schröder-Bernstein theorem. Ordinals. How to count. Cantor’s theorem that $X<P(X)$. General Comprehension principle. Russell’s paradox. Rise of ZFC. The continuum hypothesis. Gödel’s theorem on the constructible universe; Cohen’s development of forcing. The independence phenomenon. The singularist/pluralist debate in the philosophy of set theory.

Lecture 14 student notes

This was the last lecture; it was a great time! Final papers are due by the end of finals week. Please drop by my office for comments on a draft version of your paper.

Final Papers The students all wrote final papers on various topics connected with the seminar, and many of them were quite interesting. Let me summarize here several of the resulting titles and topics.

Mala Chatterjee, Łukasiewicz Logic & Strong Completeness.  Mala investigates complete sets of connectives for Łukasiewicz logic, introducing several novel connectives, denoted by $+$, $\Cup$ and $\oplus$, which she shows can form various small complete sets of connectives for this logic.

Hugo Dumoulin, Logic Gates and the Turing Machine. Hugo constructs a subtractor using only logic gates and explains how logic gates can be used be used to simulate Turing machines.

Arden Koehler, Definability and distinguishability in finite and infinite structures.  Arden investigates the difference between Leibnizian structures (where any two objects have different types) and pointwise-definable structures (where every individual is definable) in first-order logic. In finite structures, the concepts are equivalent, but there are infinite structures, even in a finite language, which are Leibnizian, yet have no definable elements.

Annette Martin, A brief look at nonstandard models of true arithmetic. Annette develops the theory of nonstandard models of true arithmetic, establishing the overspill principle, determining the order type of every countable nonstandard model of arithmetic, proving that every nonstandard model of arithmetic has entire $\mathbb{Z}$ chains consisting of composite nonstandard numbers, and proving that there are uncountably many pairwise non-isomorphic countable nonstandard models of true arithmetic.

Nathan Pensler, What is the Logic of Missing Information?  Abstract: Is there a logic of missing information? In this paper, I’ll survey several logics and determine
whether any of them provide an adequate analysis of the concept. I first discuss Kleene and Łukasiewicz Logics. I argue that both systems fail as logics of missing information, due to counterexamples involving classical tautologies. I then discuss several new logics of missing information, all of which assign truth values to formulae relative to an informational background. I define what it is for a logic to be truth functional and prove that several logics of this type are truth functional just in case the informational background is severely restricted. I then explore a truth-functional logic of missing information. I conclude by exploring whether there is reason to prefer the truth functional logic of missing information to the non-truth functional logics.

David Storrs-Fox, The modal logic of a knight in chess.  David investigates the modal logic of a knight’s move, by considering the frame consisting of the squares on a chessboard (in both the finite and infinite cases) as the possible worlds and the knight’s move as the accessibility relation. After settling a large number of validities and invalidities for this chessboard interpretation, David proves that the squares on the 8×8 chessboard are distinguished by their modal validities, unless they are in rotational or reflective symmetry.

Casey Tirschfield, Select limitations of infinitary logic.   In this paper, Casey develops the basic syntax and semantics of the infinitary logics $L_{\kappa,\mu}$ and proved that the compactness theorem and the upward Löwenheim-Skolem theorems can both fail in the infinitary context.

Kameryn J Williams, Complete sets of connectives for generalized Łukasiewicz logics. Abstract: While $\wedge$, $\vee$, $\neg$ form  complete set of connectives for classical propositional logic, this does not hold for Łukasiewicz’s three-valued propositional logic, nor its generalization to $n$-valued logic. We define a unary connective $\frak{c}$ so that $\wedge$, $\vee$, $\neg$, $\frak{c}$ form a complete set of connectives for $n$-valued Lukasiewicz logic. We discuss generalizations of this to infinitary logics. If we allow infinite conjunctions and disjunctions of arbitrary size, this provides a complete set of connectives for real-valued Łukasiewicz logic. Restricting to countable conjunctions and disjunctions, the truth functions expressible with these connectives are precisely the Borel functions.

Jake Zuehl, What group preferences can arise by majority vote?  It is known by the Condorcet paradox that the group preferences determined by majority vote can be non-transitive, even when all individuals have linearly ordered preference relations. But exactly which relations can arise? In this paper, Jake proves that it is all and only the asymmetric irreflexive relations that arise as the majority-vote group preference relation by a group of individuals with linear preferences. He then proceeds to investigate bounds on the minimum number of voters required to realize a given relation.