Membership Table: A subset B

[hotvette]

TL;DR Summary

Clarification on membership table of A subset B

This isn't hw, just clarification on what I see in the book. I understand how to produce the following table:

\begin{array}{|c|c|c|} \hline A & B & A \subseteq B \\ \hline 0 & 0 & 1\\ \hline 0 & 1 & 1\\ \hline 1 & 0 & 0 \\ \hline 1 & 1 & 1 \\ \hline \end{array} What I don't have is an intuitive feel for the result. Take the first row for example. If $x \notin A$ and $x \notin B$, how can this imply $A \subseteq B$. I'm picturing $A$ and $B$ as disjoint sets with $x$ somewhere outside of both. Clearly I have a conceptual misunderstanding. Can someone explain?

 

[Stephen Tashi]

It isn't clear what your "membership table" represents.

You table resembles a "truth table" for the proposition $A \implies B$. Is that what you intended?

 

[jedishrfu]

The truth table shows the four possible conditions for some element X:

                 Condition                                              Conclusion
                 -------------------------------------      ----------------------------------------------

the 1st line:    Element X is not in A and is not in B      --> 1 --> set A is a subset of B

the 2nd line:    Element X is not in A and is in B          --> 1 --> set A is a subset of B

the 3rd line:    Element X is in A and is not in B          --> 0 --> set A is not a subset of B

the 4th line:    Element X is in A and is in B              --> 1 --> set A is a subset of B

I think this is right. Does it make sense?

 

[Mark44]

This isn't hw, just clarification on what I see in the book.

Take the first row for example. If $x \notin A$ and $x \notin B$, how can this imply $A \subseteq B$.

It doesn't. If for each $x \in A$, it's also true that $x \in B$, then by definition of what set inclusion means, $A \subseteq B$. However, if you start with an object that is neither in A nor B, you can't conclude anything.

This isn't hw, just clarification on what I see in the book.

It might help us understand if you uploaded an image of the relevant page in your book.

 

[Mark44]

The truth table shows the four possible conditions for some element X:

                          Condition                                              Conclusion
                         ------------------------------------------------- ----------------------------------------------
the 1st line:    Element X is not in A and is not in B --> 1 --> set A is a subset of B

I don't think so. For example, consider A = {1, 2, 3} and B = {2, 4, 6}, with x = 5. x is in neither set, but clearly A is not a subset of B.

A counterexample to the fourth line, with the same sets as above, but with x = 2. $x \in A$ and $x \in B$, but again, A is not a subset of B. There might be problems with lines 2 and 3, but I haven't looked at them.

 

[jedishrfu]

I think the truth table is for the boolean implication operator which is mapped to the subset operator.

https://en.wikipedia.org/wiki/Subset

 

[Mark44]

I think the truth table is for the boolean implication operator which is mapped to the subset operator.

https://en.wikipedia.org/wiki/Subset

That's what @Stephen Tashi surmised in post 2. If so, then x can be either true or false.

 

[jedishrfu]

Yes, so basically I think the table is saying if you find an element in A that is not in B then A can't be a subset of B. However in all others cases then A could be a subset of B.

 

[hotvette]

My question came up when the book was showing that $A \subseteq B \implies A \cup B = B$. Here is the actual wording from the book.

Consider the membership table below. If we are given the condition that $A \subseteq B$, then we need to consider only those rows of the table for which this is true -- rows 1,2, and 4. For these rows, the columns for $B$ and $A \cup B$ are exactly the same, so this membership table shows that $A \subseteq B \implies A \cup B = B$.

\begin{array}{|c|c|c|} \hline A & B & A \cup B \\ \hline 0 & 0 & 0\\ \hline 0 & 1 & 1\\ \hline 1 & 0 & 1\\ \hline 1 & 1 & 1 \\ \hline \end{array} What I don't understand is the statement "then we need to consider only those rows of the table where $A \subseteq B$ is true -- rows 1,2, and 4". Thus my original post.

 

[Mark44]

My question came up when the book was showing that $A \subseteq B \implies A \cup B = B$. Here is the actual wording from the book.

Consider the membership table below. If we are given the condition that $A \subseteq B$, then we need to consider only those rows of the table for which this is true -- rows 1,2, and 4. For these rows, the columns for $B$ and $A \cup B$ are exactly the same, so this membership table shows that $A \subseteq B \implies A \cup B = B$.

It's still not clear to me what the table is trying to convey . If A and B are sets, what does it mean that A and B have values of 0 or 1? With the information at hand, this makes no sense.

 

[jedishrfu]

The truth table refers to a given element X that may be in set A and may be in set B. There are four possible combinations as shown in the table.

 

[Mark44]

The truth table refers to a given element X that may be in set A and may be in set B.

Then it should explicitly say that, with the table looking more like this:
\begin{array}{|c|c|c|}
\hline x \in A & x \in B & A \subseteq B \\
\hline 0 & 0 & 1\\
\hline 0 & 1 & 1\\
\hline 1 & 0 & 0 \\
\hline 1 & 1 & 1 \\
\hline
\end{array}

In any case, the OP has not confirmed any of this, so it's all speculation until he does so.

 

[WWGD]

The table used coincides with that for the 'Or' logical operator. $A \cup B$ is true when at least one of them is true.

 

[Stephen Tashi]

I think the first row of the table in post #9 means to convey that when the statements $x \in A$ and $x \in B$ are both false then the statement $x \in A \cup B$ is a False statement.

If $x \notin A$ and $x \notin B$, how can this imply $A \subseteq B$.

You're correct to ask because your text's presentation is unclear. One specific case where $x \notin A$ and $x \notin B$ doesn't imply $A \subseteq B$.

Your text is not presenting a clear proof. It is ignoring the role of logical quantifiers in the definitions of set relations. The definition of $A \subseteq B$ involves the logical quantifier "for each" ($\forall x$).
$A \subseteq B$ means $\forall x , x \in A \implies x\in B$.

However, the particular case $x \notin A$ and $x \notin B$ does make the statement $X \in A \implies x\in B$ True in that particular case. This is due to the mathematical definition of implication. The mathematical definition obviously differs from the use of "implies" in ordinary speech. There are threads on the forum about the fact that a False statement (mathematically ) implies any other statement. We can discuss this point of mathematical logic, it is not special to statements about sets.

What I don't understand is the statement "then we need to consider only those rows of the table where A⊆B is true -- rows 1,2, and 4".

Your text is trying to prove a statement that begins " $A \subseteq B \implies ...$" By the mathematical definition of implication if $A \subseteq B$ is False then the implication to be proved is True, so there is nothing that needs to be proven in this case.

What the writer of the text apparently means is that rows 1, 2, 4 are the cases where $x \in A \implies x \in B$ is True and the writer is trying to make some connection with those cases and the definition of $A \subseteq B$, without mentioning the "$\forall x$" aspect in "$\forall x, x \in A \implies x \in B$".

 

[hotvette]

I think post #12 explains the intention. When the book originally discussed membership tables it said "When $x$ is an element of a given set, we write a 1 in the column representing that set in the membership table; when $x$ is not in the set, we enter a 0."

I still don't get why $x$ is a member of $A \subseteq B$ if $x$ isn't a member of either set $A$ or $B$.

 

[Mark44]

I think post #12 explains the intention. When the book originally discussed membership tables it said "When $x$ is an element of a given set, we write a 1 in the column representing that set in the membership table; when $x$ is not in the set, we enter a 0."

I still don't get why $x$ is a member of $A \subseteq B$ if $x$ isn't a member of either set $A$ or $B$.

Because of how subsets are defined. Namely, $A \subseteq B$ is defined this way: $\forall x(x \in A \Rightarrow x \in B)$. See https://en.wikipedia.org/wiki/Subset#Definitions.

The implication in the definition could use some elaboration. An implication $p \Rightarrow q$ is false only when p is true and q is false. Here p and q are logical expressions that can be either true or false.

Going back to the subset definition, the only case where $A \subseteq B$ is not true (i.e., A is not a subset of B) is when $x \in A$ but $x \notin B$.

So, by definition of $A \subseteq B$, the only row of the truth table that produces a value of 0 is row 3, where $x \in A$ but $x \notin B$. All other rows produce a value in the 3rd column of 1.
\begin{array}{|c|c|c|}
\hline x \in A & x \in B & A \subseteq B \\
\hline 0 & 0 & 1\\
\hline 0 & 1 & 1\\
\hline 1 & 0 & 0 \\
\hline 1 & 1 & 1 \\
\hline
\end{array}

 

[Stephen Tashi]

I still don't get why $x$ is a member of $A \subseteq B$ if $x$ isn't a member of either set $A$ or $B$.

The first thing to get is that writing "x is a member of $A \subseteq B$" is meaningless because "$A \subseteq B$" does not not denote a set consisting of single elements. The notation "$A \subseteq B$" indicates a relation between sets, not a set of consisting of single elements.

A coherent way to interpret that particluar line in the table is:
The existence of an $x \notin A$ and $x \notin B$ does not contradict the relation $A \subseteq B$

That interpretation does not say that the existence of $x \notin A$ and $x \notin B$ implies the relation $A \subseteq B$.

It is a consequence of the mathematical definition of "implies" that the case $x \notin A$ and $x \notin B$
makes the implication $x \in A \implies x \in B$ True. However this implication is not the same as saying $A \subseteq B$. To verify $A \subseteq B$ you must consider the truth of that implication in all cases, not just a single case.

For example, suppose we say "If x is a number greater than 10 then x is greater than 5". Another person says "No, that's not true. Consider the case x = 2". Do we want to allow the case x = 2 to contradict our statement?

In mathematics, we regard the case x = 2 as not contradicting our statement. We assert the case x = 2 makes the implication x > 10 $\implies$ x > 5 True. However the truth of the implication in the case x = 2 does not imply the generality "for all x, if x > 10 then x > 5" To prove the generaliy involves writing some argument that considers all cases.

 

[WWGD]

Or this may have been a misprint/mistake. , where $\subset$ was used instead of $\cup$, which was the intended symbol.

 

[hotvette]

I think I get it. For now I need to just use definitions and not try to inject my (flawed) sense of logic and intuition. Thanks for the explanations!