Or think about when ¬(r ∧ s) is true, that is, about when r ∧ s is false. What refutes r ∧ s?

@EliahKagan either of them being false

Can you express that with "∨"?

¬r v ¬s

Yes. :)

:)

While were at it, suppose you had ¬(r ∨ s). Can you express that with "∧" and "¬"?

I think that is only true when ¬r ∧ ¬s

Yes.

\o/ haha

These are called De Morgan's laws. Specifically they are De Morgan's laws for propositional logic (because there are analogous De Morgan's laws about something in set theory).

oooh

Notice that it works with conjunctions and disjunctions of more than two sentences.

I should explain what I mean by that.

∧ is conjunction.

∨ is disjunction, also called alternation.

But what I really need to explain is what I mean by "of more than two sentences," since they are binary sentential connectives!

well, one of them can only stick two sentences together, probably

What I mean is, (r ∧ s) ∧ t is logically equivalent to r ∧ (s ∧ t), so there's no ambiguity when one omits the parentheses and writes r ∧ s ∧ t.

Similarly, (r ∨ s) ∨ t is logically equivalent to r ∨ (s ∨ t), so there's no ambiguity when one omits the parentheses and writes r ∨ s ∨ t.

You'll notice that De Morgan's laws extend readily to the situation where one wishes to negate (¬ is negation) a conjunction with arbitrarily many conjuncts, or when one wishes to negate a disjunction with arbitrarily many disjuncts.

what exactly are these laws? which part of what we were saying, specifically?

De Morgan's laws for propositional logic say:

(1) ¬(r ∧ s) is logically equivalent to ¬r ∨ ¬s.

(2) ¬(r ∨ s) is logically equivalent to ¬r ∧ ¬s.

oh, right :)

@EliahKagan yes

So you see why:

(1') ¬(r ∧ s ∧ t ∧ u ∧ ...) is logically equivalent to ¬r ∨ ¬s ∨ ¬t ∨ ¬u ∨ ....

(2') ¬(r ∨ s ∨ t ∨ u ∨ ...) is logically equivalent to ¬r ∧ ¬s ∧ ¬t ∧ ¬u ∧ ....

?

yes, because if it's false that all these things are true, then only one of them has to be false, and if it's false that any of these things are true, then they must all be false

Yes.

So, I want to mention an important connection between De Morgan's laws and the rules for passage for ¬ across quantifiers.

With a unary predicate F, consider the sentence:

∀x Fx

Suppose further that our universe of discourse is finite. Not only is it finite, we can name all the objects in it. There are five of them, a, b, c, d, and e.

Then that sentence, ∀x Fx, expresses:

Fa ∧ Fb ∧ Fc ∧ Fd ∧ Fe

You may recall that the rule of passage for ¬ across ∀ is that it turns the ∀ into an ∃. Stated less syntactically and more semantically: to deny that something is true for everything is to affirm that it is false for something.

So ¬∀x Fx is logically equivalent to:

∃x ¬Fx

yes

In our universe of discourse consisting of a, b, c, d, and e, we can expand ∃x ¬Fx to:

¬Fa ∨ ¬Fb ∨ ¬Fc ∨ ¬Fd ∨ ¬Fe

That's the result of applying a De Morgan's law to Fa ∧ Fb ∧ Fc ∧ Fd ∧ Fe.

Similarly, consider the sentence:

∃x Fx

:)

In our finite universe with five things all of which we can name, that can be expanded to:

Fa ∨ Fb ∨ Fc ∨ Fd ∨ Fe

indeed

You may recall that the rule of passage for ¬ across ∃ is that it turns the ∃ into an ∀. States less syntactically and more semantically: to deny that something is true for something is to affirm that it is false for everything. (I'm sure you notice the similarity to that.)

So ¬∃x Fx is logically equivalent to:

∀x ¬Fx

In our particular finite universe, that can be expanded to:

¬Fa ∧ ¬Fb ∧ ¬Fc ∧ ¬Fd ∧ ¬Fe

this is nice

I know! :)

Even when one's universe of discourse is infinite of when it is finite but one has no way of naming (or definitely describing) each of its object separately, the conceptual connections between conjunction ("∧") and universal quantification ("∀"), and between disjunction ("∨") and existential quantification ("∃"), remain.

Are you familiar with the mathematical notation for the sum of sequences (i.e., summation, with a big capital sigma) and for the product of sequences (with a big capital pi)?

only the first one

The second one is analogous but for products.

from learning spreadsheets in school!

@EliahKagan ok! that is a useful thing to know :D

Back in the day--at some point in the 19th century I believe--and to a lesser extent still, "+" was used for "∨", and "×" was used for "∧".

They were used with their usual arithmetic meanings too, of course. They had their arithmetic meanings first.

that sounds a bit confusing

There are a few ways to say why this makes sense, but one is to consider the combinatoric meanings of addition and multiplication.

ooh

Suppose I have two piles (often one says "sets" now) of different things. One pile has a things in it. The other pile has b things in it. (So a and b are nonnegative integers.) If I select a thing that was in the first pile or the second pile (i.e., it is true, of that thing, that it was in the first pile or it was in the second pile) then there are a + b possibilities.

Note that this or is, perhaps surprisingly, still an inclusive or. I've just set up the scenario so the piles are disjoint, so it turns out that the thing I pick will not have been in both of them.

In contrast, if I pick something from the first pile and I pick something from the second pile (for this it doesn't matter if the piles are disjoint, so long as I'm permitted to pick the same thing from both when they're not), then there are a × b possibilities.

Also, you can do arithmetic on truth values by taking 0 to mean false and 1 to mean true. Then the effect of conjunction on truth values is perfectly captured by ordinary multiplication. The effect of disjunction on truth value is not quite captured by ordinary addition, though; we have to define addition differently so 1 is an absorbing element, i.e., so 1 + 1 = 1.

Or just consider all nonzero values to mean true and use ordinary addition.

@EliahKagan this is helpful

@EliahKagan O.O

There is also a probabilistic interpretation. I'll use the usual notation P(...) to "mean the probability of ...". Then for mutually exclusive events x and y, the probability of either happening is their sum of their individual probabilities, P(x or y) = P(x) + P(y). And for independent events x and y, the probability of both happening is the product of their individual probabilities, P(x and y) = P(x)P(y).

@EliahKagan this is what I thought about when you were picking things from those piles as well

:)

I bring this up to illustrate how existential quantification is like the sum of a sequence (like summation) and how universal quantification is like the product of a sequence.

When quantification was first being developed, the big capital sigma (which means summation, i.e., the sum of a sequence of numbers) was used to represent existential quantification, and the big capital pi (which means the product of a sequence of numbers) was used to represent universal quantification.

I don't know how long that notation was used but I believe it was the first formal notation for existential and universal quantification, used by Charles Sanders Pierce.

So, regarding the relationship between conjunction ("∧") and universal quantification ("∀") and the relationship between disjunction ("∨") and existential quantification ("∃")...

...this should enable you to infer (or, strictly speaking, make a really good guess that turns out to be accurate) what the truth values are considered to be, of the empty conjunction and the empty disjunction.

empty conjunction? like, with no things to join together?

Yes. Informally:

> All the following are true:

(and then nothing)

oh :D

The truth values of the empty conjunction and the empty disjunction--when they have truth values, because unlike empty sums and products, there is some reason to doubt that empty conjunctions and disjunctions are always meaningful--can also be figured out by contemplating what the situations are where you would want to be able to ∧ together zero sentences as conjuncts or ∨ together zero sentences as disjuncts.

I wouldn't normally bring this up, but I'm already talking about the relationships between disjunction and addition and between conjunction and multiplication.

To clarify what I mean when I say there is some reason to doubt they are meaningful: conjuncts and disjunctions are syntactic in nature. Sums and products are not.

But you can think of what happens when, instead of our system having the 5 constants (i.e., primitive names) a, b, c, d and e and nothing else in its universe of discourse, it has no constants (common) and also its universe of discourse is empty (uncommon, and even prohibited by some logics, but permitted by others).

This is similar to, but syntactically simpler than, but conceptually weirder than, the scenario we discussed earlier where one quantifies over a conditional p → q whose antecedent p is never satisfied.

Am I making sense?

@EliahKagan I think the conclusion there was that it was neither (or both) true nor (or and) false that every state has a state bird if there are no states, but I'm not sure.

When there are no things, everything is true of all of them.

so "all of the following are true" is true when nothing is following

Yes.

∀x Fx is logically equivalent to ¬¬∀x Fx which is logically equivalent to ¬∃x ¬Fx. With an empty universe of discourse, there are no things, so there are no things that satisfy any particular condition (like ¬Fx), so ¬∃x ¬Fx, so ∀x Fx. You can put anything expressible about x for Fx, no matter how absurd. After all, you're only claiming it's true for zero things.

One need not accept that there is any such thing as an empty conjunction, but if one does, it should be compatible with that.

@EliahKagan :)

(I had an extra "so there are no things" in there, which was still a correct inference, but not useful. I've trimmed it. I don't know if that's what you're smiling at.)

I'm smiling that we can say whatever we like about zero things

:)

So the empty conjunction, if you recognize it, is true.

but if we say there is some thing... and there aren't any things

@EliahKagan After all, a conjunction is true exactly whenever all its conjuncts are true.

@Zanna Right, you're not going to be able to show a counterexample to a claim that some claim holds for all of zero things. Not even in principle.

...Now, how about the empty disjunction?

Can you see how that, if you decide to recognize it, must work?

what does it say, this empty disjunction?

Informally:

> Some of the following are true:

(and then nothing)

it seems wrong

Do you mean the empty disjunction is false?

if at least one thing has to be false, then it is false, because everything is true if there are no things

Can you elaborate?

A disjunction, to be true, does not require any of its disjuncts to be false.

yeah

so I don't know

You may be on the right track.

Suppose you apply De Morgan's laws to a disjunction. You get the negation of a conjunction of negations. At least one of those negations must be false, so the whole conjunction of them is false, so the negation of the conjunction of them is true.

So that does work. You can reason about the empty disjunction that way. But I don't especially recommend it. The results don't feel especially compelling, even though they are correct.

Instead... I am recommending you examine the relationship between (a) the empty disjunction and (b) existential quantification in an empty universe of discourse.

I am thinking about it and I think we can't say that there exists some thing such that if there aren't any things

What do you mean by "we can't say"?

That's expressible.

Do you mean it is always false?

I mean, if we say that it will be false

Yes, it is always false.

I'm not sure that directly helps you though.

XD

The sentence being existentially quantified over can be anything.

Though I've been using the simple case of Fx (whatever F means), which is adequate for this purpose.

So when I say "existential quantification in an empty universe of discourse" I just mean:

∃x Fx

...where the universe of discourse happens to be empty.

What do you know about the truth value of a sentence like ∃x Fx when the universe of discourse is empty (i.e., when there are no things)?

it's false

Indeed.

Does the connection between that and the empty disjunction make sense?

The empty disjunction is what you get when you expand ∃x Fx like Fa ∨ Fb ∨ Fc ∨ Fd ∨ Fe except, instead of having five things in your universe of discourse (and conveniently being able to refer specifically to each one of them) and thus five disjuncts, you have zero things in your universe of discourse (and conveniently can refer specifically to each one of them) and thus zero disjuncts.

hmm

I am going to go to bed

thank you for being soooo patient XD

No problem! This empty conjunction and empty disjunction business is ridiculous. I am not sure I should have brought it up. But the empty product and empty sum are conceptually sound and very clear, and I was talking about how conjunctions and disjunctions are like products and sums, respectively. So I figured I should go into that too.

For completeness, but please don't feel obligated to read this now: The way existential quantification over an empty universe of discourse can motivate speculation about what an empty disjuncton would mean mirrors the way universal quantification over an empty universe of discourse can motivate speculation about what an empty conjunction would mean.

The thing to say like that but about the empty conjunction rather than the empty disjunction is:

The empty conjunction is what you get when you expand ∀x Fx like Fa ∧ Fb ∧ Fc ∧ Fd ∧ Fe except, instead of having five things in your universe of discourse (and conveniently being able to refer specifically to each one of them) and thus five conjuncts, you have zero things in your universe of discourse (and conveniently can refer specifically to each one of them) and thus zero conjuncts.

Are you familiar, and comfortable, with empty sums and empty products?

Unlike the empty disjunction and conjunction that are sometimes but not always recognized in logic, empty sums and products in mathematics make excellent sense. In particular, in the case of discrete arithmetic where a combinatoric interpretation can be used directly, the combinatoric interpretation of sums and products covers the empty case of each automatically--it does not even make require them to be treated specially.

* does not even require

Anyways, good night!

@EliahKagan I have never encountered such things!

Oh! They're cool and useful. Do you want me to describe them now? I could instead wait until tomorrow (or whenever we pick this conversation back up).

But also, perhaps you've encountered them but are just not familiar with the phrases "empty sum" and "empty product." I'm talking about how the sum of zero numbers is 0 and the product of zero numbers is 1.

You can describe them any time you feel like doing that and I will read it soon or not-so-good after that

@EliahKagan I hadn't realised that the product of zero numbers is 1

I don't think it has previously been pointed out to me

@Zanna not so soon (autocucumbered)

It's handy that the product of zero numbers is 1 because it means nothing special has to be done to make it so that, given a fraction x / (xy), you can cancel out the xes by simply removing them as factors from their respective products, yielding 1 / y.

I'm not saying that really why the empty sum is 1. But it's a case where you may have benefited from it.

In discrete arithmetic, which admits to a combinatoric interpretation, the sum a + b is the number of ways to select an item taken either from a pile of a things or a separate pile of b things. More generally, a sum of arbitrarily many (or few) addends is the number of ways to select an item taken from one of separate piles with those addends as their sizes. If there are no piles, there are no ways to select an item from one of them, so the empty sum is 0.

Also in discrete arithmetic and with the combinatoric interpretation, the product a × b is the number of ways to pick from a things and then, independently, from b things. More generally, a product of arbitrarily many (or few) factors is the number of ways to pick one item independently from each of separate piles with those factors as their sizes.

If there are no piles, there is one way to pick one item from each of them (in that you're immediately done, having already made all zero choices).

In case that's not clear or is not sufficiently compelling, consider that a × b × c is the number of lists of length 3 where there are a possibilities for the first item, b possibilities for the second item, and c possibilities for the third item;

that a × b is the number of lists of length 2 where there are a possibilities for the first item and b possibilities for the second item; that a is the number of lists of length 1 where there are a possibilities for the first (and only) item. There is exactly one length 0 list. If you write the length 3 lists like ⟨u,v,w⟩ and the length 2 lists like ⟨u,v⟩ and the length 1 lists like ⟨u⟩, then the length 0 list is written like ⟨⟩.

(It also explains the behavior of 0 exponents, but the combinatoric meaning of exponentiation is hard to elucidate without first being very familiar with functions, i.e., with the sort of mathematical object that is called a function. IIRC you'd said you were shaky on that, so I'll wait to give that example.)

@EliahKagan I think that's one of the things I vaguely alluded to not being sure I was allowed to do!

@EliahKagan ooohhh

While I was taking a shower (a good place for diffuse mode thinking) I thought I might mention that I probably felt ok about the number 7 being a set because of my previous meeting with set theory, which I now remember more clearly

My student had some exercises based on things like Venn diagrams with some things in them. She had to complete or evaluate or make some statements relating to the things in the diagrams and she had a glossary of symbols, so it was not difficult to solve the exercises. What I remember noticing was the obvious arbitrariness of the things in the diagrams

I feel like mentioning that this particular student was, in addition to being dyslexic and dyspraxic and totally awesome, was "dyscalculic" and had never been able to learn number bonds or times tables (no doubt despite wasting huge amounts of time repetitively trying to do that) but she had no difficulty with this set theory thing (actually she was good at lots of things in math, just not the ones other people find relatively easy)

@EliahKagan I know that anything^0 is 1 but I don't know why that should be so