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

In summary: But even if they can be seen as assignments, how can implication be an operator? In summary, the conversation is discussing set theory and its relationship to logic. The participants are discussing the symbols and operations used in set theory, such as union and intersection, and how they relate to logical operators like implication and disjunction. They also touch on syllogistic logic and its connection to set theory. The conversation concludes with a recommendation to read a book on logic by Wilfrid Hodges.
  • #1
Gokul43201
Staff Emeritus
Science Advisor
Gold Member
7,220
24
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).
 
Last edited:
Physics news on Phys.org
  • #2
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: [itex]\Rightarrow[/itex]. The black circle is conjunction (&, AND) and the vee is disjunction (OR). Sometimes a wedge (upside-down vee, [itex]\wedge[/itex]) 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:

(Ac [itex]\cup[/itex] Bc) = (A [itex]\cap[/itex] B)c

where Ac is the complement of A. There is the logical equivalent:

(¬A [itex]\vee[/itex] ~B) :: ¬(A [itex]\wedge[/itex] 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 [itex]A \supset B[/itex] is the same as [itex]\neg A \vee B[/itex], and the set-theoretic equivalent would then be:

[tex]A^c \cup B[/tex]

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".
 
Last edited:
  • #3
Thanks AKG ! This truly is scary stuff :eek:

<runs far, far away>
 
  • #4
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 [tex]\forall x (Px \rightarrow Qx)[/tex] could be [tex]P \cap Q = P[/tex];

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

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

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

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.
 
Last edited:
  • #5
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! :rolleyes:).

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 :redface:
 
  • #6
Gokul43201 said:
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! :rolleyes:).
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.
AKG said:
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?
 
Last edited:
  • #7
Gokul43201 said:
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 [itex]\supset[/itex] in one system corresponds to [itex]\subset[/itex] in the other is beyond me. :confused:
 
  • #8
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.
honestrosewater said:
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}.

[tex]S \subset T[/tex]

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.
 
  • #9
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. :yuck: I'll try again later.
 
  • #10
honestrosewater said:
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. :yuck: I'll try again later.
The first one.
 
  • #11
AKG said:
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.
 
Last edited:

1. What is the purpose of the "Split from Logic Q&A Game"?

The purpose of the "Split from Logic Q&A Game" is to test a person's ability to think logically and solve problems by splitting a group into smaller subgroups based on specific criteria.

2. How does the game work?

The game presents a group of people with certain characteristics and asks players to split them into smaller groups based on a specific criteria. Players must use logic and deductive reasoning to correctly split the group into the appropriate subgroups.

3. What skills does this game help develop?

This game helps develop skills such as critical thinking, problem-solving, deductive reasoning, and logical thinking. It also promotes teamwork and communication as players work together to solve the puzzles.

4. Is this game suitable for all ages?

Yes, this game is suitable for all ages. It can be played by children and adults alike, and the difficulty level can be adjusted to suit the age and skill level of the players.

5. Can this game be used for educational purposes?

Yes, this game can be used for educational purposes. It is an engaging and interactive way to teach logical thinking and problem-solving skills. It can also be used as a team-building exercise or to improve communication and critical thinking skills in a group setting.

Similar threads

  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
57
Views
5K
  • Calculus and Beyond Homework Help
Replies
7
Views
2K
  • General Math
2
Replies
66
Views
4K
  • Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
  • Special and General Relativity
Replies
2
Views
760
  • Set Theory, Logic, Probability, Statistics
Replies
1
Views
971
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
3K
  • Set Theory, Logic, Probability, Statistics
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
1
Views
2K
Back
Top