What is the connection between set theory and truth-values?

[Gokul43201]

Being logically inept (never took a class, and don't know what Rose and AKG are talking about), I've always imagined there was direct correlation to set theory, so please excuse my ignorance.

Someone tell me where this is wrong.

Let A, B, C be the following sets :

A = {2,4}
B = {2,3}
C = {1,2}

So, B&C = {2}, which is indeed a subset of A
Also, A&C = {2}, which is a subset of B

So, this example satisfies both the conditions of the premise.
However, AvB = {2,3,4}, which is not a superset of C.

A counterexample, wot ?

Or are A,B,C binary valued variables (meaning I don't have a clue what \supset and \subset are in this context) ?

Sorry, for the inconvenience. I do not wish to derail this thread, so feel free to ignore this post for now (but it would be nice to have my ignoramic queries answered in another thread perhaps).

 

[AKG]

That is not the superset symbol (although it looks like it), it is the horseshoe symbol (is that it's official name) and denotes material implication. I'm guessing your more familiar with what mathematicians use: $\Rightarrow$. The black circle is conjunction (&, AND) and the vee is disjunction (OR). Sometimes a wedge (upside-down vee, $\wedge$) is used instead of the ampersand or the black circle.

The vee (OR) would indeed correspond to the cup symbol for union, and the wedge (AND) would correspond to the symbol for intersection. There is a set-theoretic version of DeMorgan's Law which says:

(A^c $\cup$ B^c) = (A $\cap$ B)^c

where A^c is the complement of A. There is the logical equivalent:

(¬A $\vee$ ~B) :: ¬(A $\wedge$ B)

where A and B are sentences, ¬A is the negation of A, and P :: Q means that sentences P and Q are always interchangeable. Implication $A \supset B$ is the same as $\neg A \vee B$, and the set-theoretic equivalent would then be:

$$A^c \cup B$$

which is not like any basic set-theoretic thing. And note that while "superset" is a relation, entirely different from "union" which is an operation, both implication and disjuction are operations, neither are relations.

And yes, I suppose you can think of A, B as being binary-valued variables. They are sentences that can take on values of "True" and "False".

 

[Gokul43201]

Thanks AKG ! This truly is scary stuff

<runs far, far away>

 

[honestrosewater]

Gokul, I may think of other similarities later (maybe you could split this off), but one that comes immediately to mind is syllogistic (categorical, Aristotelian) logic, which uses something equivalent, IMO, to the membership relation and its derived relations and operations. Its most common decision procedure uses Venn diagrams, if that tells you something. It uses only four forms of propositions (A, E, I, and O), which can be translated into first order logic. (The following are pretty obvious if you just think about them.)

A: All P are Q is $$\forall x (Px \rightarrow Qx)$$ could be $$P \cap Q = P$$;

E: No P are Q is $$\forall x (Px \rightarrow \neg Qx)$$ could be $$P \cap Q = \emptyset$$;

I: Some P are Q is $$\exists x (Px \wedge Qx)$$ could be $$P \cap Q \not= \emptyset$$;

O: Some P are not Q is $$\exists x (Px \wedge \neg Qx)$$ could be $$P \cap Q \not= P$$.

I think this works, i.e., that you could rewrite all of syllogistic logic in the language of set theory, but I haven't checked it. The empty set scares me. But having empty terms has been worked out in syllogistic logic, and it could be the same for the set theory version.
I can't see how set theory and propositional logic have much in common. Maybe I'm just thinking about this the wrong way, but they don't seem to have the same kind of structure. In propositional logic, the individuals are assigned truth-values. What would it mean - and how would it work - to assign a truth-value to a set? I did notice in another thread that connectives do behave somewhat like relations in seeming to have something like reflexive, symmetric, and transitive properties. But connectives just don't seem to work as relations; I can't quite put my finger on the reason. Hm, it might be fun to get into this some more if anyone else is interested.

 

[Gokul43201]

I guess I'm going to put some serious time into this whole logic thing (always wanted to do it, but keep putting it off)...just not right now (yeah, right! ).

Rose, I did start off with a venn diagram, but couldn't show that in a post, so I constructed an example out of it...only I was interpreting the symbols incorrectly. Oh, and I didn't know anything about logic

 

[honestrosewater]

I guess I'm going to put some serious time into this whole logic thing (always wanted to do it, but keep putting it off)...just not right now (yeah, right! ).

Heh, that's what I keep saying about other logics, and if Wilfrid Hodges had written books about them, I would. Check out his book Logic. You don't even need to try to learn the material. Read it for the jokes. It feels like you're having a conversation with him, and I love the way he thinks. He's laid back without being sloppy. I wish he could teach others to do the same. He includes answers and explanations to every problem, so you don't even need to do them. Just get the book and read it for fun. It's short - you could cover it easily in a week or, if you were determined to, in a day (probably - it's been quite a while since I read it). A second edition is coming out in December. Everybody seems to have already pulled the first edition, but you can still get it used.

both implication and disjuction are operations, neither are relations.

Doh! How did I miss this? You mean in assigning truth-values? If so, aren't they still different since they assign values that aren't a part of the language or structure or theory or however you want to look at it?

 

[chronon]

Being logically inept (never took a class, and don't know what Rose and AKG are talking about), I've always imagined there was direct correlation to set theory, so please excuse my ignorance.

I think there is a direct correlation to set theory. Its just that implication corresponds to subset rather than superset. So why anyone should choose that $\supset$ in one system corresponds to $\subset$ in the other is beyond me.

 

[AKG]

Actually, here's an interesting relation between set-inclusion and material implication. Both satisfy transitivity and reflexivity. If two sets include each other, then they are equal, and if two sentences materially imply each other, then they are materially equivalent.

Doh! How did I miss this? You mean in assigning truth-values? If so, aren't they still different since they assign values that aren't a part of the language or structure or theory or however you want to look at it?

Any operation * on a set U can be seen as a function:

* : U x U --> U

If S and T are elements of U, then we normally write operations with infix notation so *(S, T) is denoted as S*T, and S*T is an element of U. So if * is the union operation, and U is the set of all sets, then S and T are sets, and S*T is the union of S and T, which is also a set hence also a member of U. If U is the set of propositions and * is conjugation, then S*T is just another proposition. Relations, if you want to treat them as function from U x U to something, it would be to the set of truth values {t, f}.

$$S \subset T$$

is not a set, it's either yes (S is contained in T) or no. A relation then is a map:

R : U x U --> {t, f}

However, it is "standard" to think of relations as sets of ordered pairs. If R is a relation on U, and s and t are elements of U, then we say (s, t) is in R iff sRt. If R is the set-inclusion relation, then

R = {(s, t) : s, t in U; x in s implies x in t}

An operation is a function, and a function can also be thought of as a set of ordered pairs, but it would be completely different kinds of ordered pairs. The ordered pairs would consist of arguments in the first component and the corresponding value of the function in the second component. So a function f : U x U --> U would be of the form:

f = {((s, t), f(s, t)) : s, t in U}

Note that every element of f is an ordered pair, and the first component of each such pair is itself another ordered pair. If U is the set of propositions and f is the implication operation, then

f = {((p,q), (p --> q)) : all propositions p, q}

If you want to look at it as what assigns what, then relations always assign truth values to a pair of objects, and binary operations always assign an object (of the same type) to a pair of objects. Logical-connectives, set union, set intersection, etc. are all binary operations. Set inclusion is a binary relation.

I can't see how set theory and propositional logic have much in common. Maybe I'm just thinking about this the wrong way, but they don't seem to have the same kind of structure. In propositional logic, the individuals are assigned truth-values. What would it mean - and how would it work - to assign a truth-value to a set? I did notice in another thread that connectives do behave somewhat like relations in seeming to have something like reflexive, symmetric, and transitive properties. But connectives just don't seem to work as relations; I can't quite put my finger on the reason. Hm, it might be fun to get into this some more if anyone else is interested.

This would be interesting. A is a set, and on it's own, it's just an expression, not an equation like A = B which could be assigned a natural truth value. Also, relations and operations are different, but as I suggested at the start of my post, set-inclusion does have some similarities to implication.

However, I've thought about it a little, it seems tough. We need to find an analogy to truth, and an analogy to inference. Every sentence in propositional logic can be written using atomic sentences, conjunction, and negation, so if we correlate sets with propositions, then we can make any proposition-set with "atomic" sets, intersection, and complement. But I still can't tell how to associate a truth value with a set (although the universal set should be tautology or logical truth and the empty set should be contradiction or logical falsity) and I can't figure out what type of set-relation would stand for inference. I'll have to think about it some more.

 

[honestrosewater]

Hm, my book doesn't treat connectives as functions. It uses only one type of function, a valuation:

f : P --> V
or
f = {(p, v) : p is in P and v is in V}

where P is the set of propositions and V is the set of truth-values (keeping in mind that f, f(p), and V aren't a part of the object language but part of the metalanguage).
If p is an atomic proposition,

f(p) = T or F.

If p and q are propositions,

f(~p) = {T if f(p) = F; F otherwise}
f(p -> q) = {F if f(p) = T and f(q) = F; T otherwise}

I don't know, maybe I'm not in the right frame of mind to think about this. I know the difference between a relation and an operation, but I couldn't seem to follow what you said. Do you want

~ : P --> P
-> : P x P --> P
or
~ : P --> V
-> : P x P --> V
or
~ : V --> V
-> : V x V --> V

?? Treating connectives as operations on V makes sense, but V isn't part of the language, so I don't know how that would work. Bah, sorry, I think my brain has a cold. I'll try again later.

 

[AKG]

Hm, my book doesn't treat connectives as functions. It uses only one type of function, a valuation:

f : P --> V
or
f = {(p, v) : p is in P and v is in V}

This can't be right. I suspect you're missing some details. As you've written it, f consists of all pairs (p, v) where p is in P and v is in V. If v, w are unique elements of V, then f contains (p, v) and (p, w). f is no longer a function, because a function assigns only one value to anyone argument. f is some subset of {(p, v) : p in P, v in V}.

Do you want

~ : P --> P
-> : P x P --> P
or
~ : P --> V
-> : P x P --> V
or
~ : V --> V
-> : V x V --> V

?? Treating connectives as operations on V makes sense, but V isn't part of the language, so I don't know how that would work. Bah, sorry, I think my brain has a cold. I'll try again later.

The first one.

 

[honestrosewater]

This can't be right. I suspect you're missing some details. As you've written it, f consists of all pairs (p, v) where p is in P and v is in V. If v, w are unique elements of V, then f contains (p, v) and (p, w). f is no longer a function, because a function assigns only one value to anyone argument. f is some subset of {(p, v) : p in P, v in V}.

Right, brain cold. I forgot that I was defining f. I defined it below that. This is the setup that makes the most sense to me. Each f, or valuation, assigns T xor F to each atomic proposition and then assigns T xor F to each compound proposition according to the definition. The connectives only come into play in defining the valuation. Then, for instance, a proposition is a tautology iff it is assigned T by every valuation.

I haven't had a chance yet to think more about the set theory thing. Some versions of set theory have individuals, or urelements, which may work for atomic propositions (urelements are not sets). Maybe they are different enough that assigning them truth-values makes sense. If you did assign them truth-values, the truth-value of sets could perhaps be determined by the urelements it contained. And perhaps, as you said, the empty set is a contradiction.