12 - Set proofs in logic

Exam Details

10 T/F 25%
10 MCQ 25%

5 Free response 50%

At least 2 hours

In class practice

$\mathrm{\forall }S,T,ifS\subseteq T,thenS\subseteq S\cap T$
Proof. Let S and T be sets. We work directly. Assume $S\subseteq T$. Let $x\in S$. Then $x\in T$ since $x\subseteq T$. Thus $x\in S\cap T$. Hence $S\subseteq S\cap T$. $◻$

Proposition. Given sets $S$ and $T$, we have $S\subseteq T$ iff $S=S\cap T$.

(=>) Assume $S\subseteq T$.

($S\subseteq S\cap T$) Let $x\in S$... conclude $x\in S\cap T$

($S\cap T\subseteq S$) Let $x\in S\cap T$... conclude $S\in S$)

<= Assume $S=S\cap T$
($S\subseteq T$) Let $x\in S$... conclude $x\in T$

Proposition. $B\ne A\cup B⟹A\ne B$.

Proof. We work contrapositively. Assume $A=B$. Show $B=A\cup B$.

Proposition. Let $A$ and $B$ be sets. If $A=\mathrm{\varnothing }$ and $B=\mathrm{\varnothing }$, then $A\cup B=\mathrm{\varnothing }$.

Proof. We work contrapositively.

Assume that $A\cup B\ne \mathrm{\varnothing }$.
... conclus

Proposition. Theorem: Given four sets A, B, C, D. If $A\subseteq C$ and $B\subseteq D$, then $A$ x $B$ $\subseteq C$ x $D$.

Proof. Let A, B, C, D be sets. We work directly. Assume $A\subseteq C$ and $B\subseteq D$. Let $(x,y)\in A$ x B. Then $x\in A$ and $y\in B$. Then $x\in C$ and $y\in D$. Thus $(x,y)\in C$ x D. $◻$

HW 12

Ben Finch

E 12.1

Proposition. For sets $A,B,C$, prove that if $A\subseteq B\cap C$, then $A\subseteq B$.

Proof. Assume that $A\subseteq B\cap C$. Therefore, by definition of subset, every element that belongs to $A$ also belongs to $B\cap C$.

Let $x$ be an arbitrary element of $A$. Because $A\subseteq B\cap C$, we know that $x\in B\cap C$. By definition of intersection, $x\in B$ and $x\in C$. Therefore, every element of $A$ is also an element of $B$, so $A\subseteq B$. $◻$

An example of when the converse fails:
Consider the sets A = {1, 2, 3}, B = {1, 2, 3, 4}, C = {5}. Thus we have $A\subseteq B$ but not $A\subseteq B\cap C$.

E 12.4b
Proof.
We work directly. Assume $S$ x $T$ = $T$ x $S$.
Let $(x,n)\in S$ x $T$. Thus, per our assumption, $(x,n)\in T$ x $S$. Then $x\in S$ and $x\in T$. Thus $S\subseteq T$. Then $n\in T$ and $n\in S$. Thus we have $T\subseteq S$. Thus $T=S$. $◻$

E 12.5
Proof.
(=>) We work directly. Assume $S=T$. Then

(<=) We work contrapositively. Assume $S\ne T$.

Case 1: If there exists an $x\in S$ and $x\notin T$, then $x$ will be in $S-T$, but $x\notin (T-S)$. Therefore, $S-T\ne T-S$.

Case 2: If there exists a $y\in T$ and $y\notin S$, then $y$ will be in $T-S$, but y $\notin (S-T).$ Therefore, $S-T\ne T-S$.

In either case, we see that $S-T\ne T-S$.

Thus $S=T$ if and only if $S-T=T-S$.

E 12.6
Disproof.

Fix $S=\{1,2,3\}$ and $T=\{1,2\}$. Then, $S-T=\{3\}$. However, $S\ne T$.

So the initial claim is false. $◻$

E 12.7

Thus, $\varnothing \times S$ = {(a, b) | $a\in \varnothing$ and b ∈ S}.

Assume that there exists an element $x$ in $\varnothing \times S$.

Then, by the definition of the Cartesian product, $x=(a,b)$ for some $a\in \varnothing$ and some $b\in S.$

However, by definition, the empty set $\varnothing$ has no elements. Therefore, there cannot be any element 'a' in the empty set.

Thus, there can be no elements in $\varnothing \times S.$

Hence, $\varnothing \times S=\varnothing$.

E 12.8

Proof.
(=>)

If $S=\mathrm{\varnothing }$, there are no elements in $S$ to form ordered pairs with elements of $T$. Similarly, if $T=\mathrm{\varnothing }$, there are no elements in $T$ to form ordered pairs with elements of $S$. Thus, in either case, $S\times T=\mathrm{\varnothing }$.

(<=)

Assume that neither $S$ nor $T$ are empty. Then there exists at least one element in each set. Denote them as $s\in S$ and $t\in T$. By the definition of Cartesian product, there should be an ordered pair $(s,t)$ in $S\times T$. But we've assumed $S\times T=\mathrm{\varnothing }$, which means there are no such ordered pairs, leading to contradiction. Therefore, if $S\times T=\mathrm{\varnothing }$, then $S=\mathrm{\varnothing }$ or $T=\mathrm{\varnothing }$.

E 12.9

Outline:

1. Start by defining the Cartesian product $A\times B$ and $B\times C$, as well as what it means for $A\times B$ to be a subset of $B\times C$.
2. Assume that $A\times B\subseteq B\times C$ and $B\ne \varnothing$.
3. Show that for any element $a$ in set $A$, there exists an element $b$ in set $B$ such that $(a,b)$ is in $A\times B$.
4. Since $A\times B\subseteq B\times C$, this means $(a,b)$ is also in $B\times C$, implying that $a$ is in $C$.
5. Therefore, $A\subseteq C$.

Proof:

Per the definition of the cartesian product means that $A\times B\subseteq B\times C$ means every pair in $A\times B$ is also in $B\times C$. Suppose that $A\times B\subseteq B\times C$ and $B\ne \varnothing$. For any element $a$ in set $A$, there must exist an element $b$ in set $B$ such that $(a,b)\in A\times B$, since $B\ne \varnothing$. As $A\times B\subseteq B\times C$, this means $(a,b)\in B\times C$, which implies that $a\in C$. Thus, for every $a\in A$, we have shown that $a\in C$. Therefore, $A\subseteq C$.

If we remove the hypothesis that $B\ne \varnothing$:

If $B$ is empty, then $A\times B$ will also be empty (since there are no elements in $B$ to pair with elements in $A$). The empty set is a subset of every set, including $B\times C$. This does not provide any information about the relationship between $A$ and $C$. Therefore, the statement "if $A\times B\subseteq B\times C$, then $A\subseteq C$" would not necessarily hold if $B$ could be empty.

E 12.10

The converse of the statement is: Given four sets A,B,C,D, if $A\times B\subseteq C\times D$, then $A\subseteq C$ and $B\subseteq D$.

Let $a\in A$ and $b\in B$. Assume $A\times B\subseteq C\times D$.

By definition of Cartesian product, $(a,b)\in A\times B$.

Since we have assumed that $A\times B\subseteq C\times D$, it follows that $(a,b)\in C\times D$.

But $(a,b)\in C\times D$ means $a\in C$ and $b\in D$ by definition of Cartesian product.

Thus we have that for all $a\in A$, $a\in C$ and for all $b\in B$, $b\in D$.

This means that $A\subseteq C$ and $B\subseteq D$. $◻$