MATH1081 Discrete Maths (1 Viewer)

InteGrand · Jul 27, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
This bugger.

$\\$Prove the uniqueness of complement: If $A \cup B = U$ and $A \cap B = \emptyset$, then $B = A^C$

$\noindent Well $A^c$ is the set of all things in $U$ (the universal set) that are not in $A$. Let $A \cup B = U$ and $A \cap B = \emptyset$. Suppose $x\in B \subseteq U$. Then since $A\cap B = \emptyset$ (i.e. $A$ and $B$ are disjoint), $x$ is not in $A$, or in other words, $x$ is in $A^{c}$. So $B\subseteq A^{c}$.$

$\noindent Conversely, suppose $x\in A^{c}\subseteq U$. Then $x\notin A$. Since $x\in U$, we have $x\in A\cup B$ (as $U = A\cup B$). So $x\in A$ or $x\in B$. But we already said $x\notin A$, so $x$ must be in $B$. Therefore, $A^{c}\subseteq B$.$

$\noindent It follows that $B=A^{c}$.$

leehuan · Jul 27, 2016

Re: Discrete Maths Sem 2 2016

RenegadeMx said:
if i remember its easier to prove by Venn Diagrams

Sounds right. Jim Franklin seems to prefer to drill us into using slightly more formalised proofs though.

I just wasn't sure how to manipulate my x in. And yet again I forgot that you had to prove they are a mutual subset of each other to be equal sets.

RenegadeMx · Jul 27, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Sounds right. Jim Franklin seems to prefer to drill us into using slightly more formalised proofs though.

I just wasn't sure how to manipulate my x in. And yet again I forgot that you had to prove they are a mutual subset of each other to be equal sets.

havent heard of him before, but had a look at your course outline you lucky fucks will have peter brown

leehuan · Jul 28, 2016

Re: Discrete Maths Sem 2 2016

$\text{Is it true that if }P(A)=P(B)\text{ for two sets }A,B\text{ then }A=B?$

I can see why it is but how would you prove it

InteGrand · Jul 28, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
$\text{Is it true that if }P(A)=P(B)\text{ for two sets }A,B\text{ then }A=B?$

I can see why it is but how would you prove it

$\noindent Note for sets $S$ and $T$ we have $T \in P\left(S\right)$ iff $T \subseteq S$. Also for any set $S$, $S$ is in its power set.$

$\noindent Now, suppose $A$ and $B$ are sets with $P\left(A\right) = P(B)$. Since $A \in P(A)$, we have $A \in P(B)$ (as $P(A)=P(B)$), so $A\subseteq B$. Reversing the roles of $A$ and $B$ shows $B\subseteq A$. So $A=B$.$

leehuan · Jul 29, 2016

Re: Discrete Maths Sem 2 2016

$\\ \text{Prove that for all sets }A,B\text{ and }C\text{, if }A\cap C \subseteq B \cap C\text{ and }\\A \cup C \subseteq B \cup C\\ \text{then }A \subseteq B$

I feel like my proof is inconclusive and achieves nothing because I don't effectively use both criteria.

$\text{Let }A \cap C \subseteq B \cap C\text{ and }A \cup C \subseteq B \cup C\\ \\ \text{Suppose }x \in A\cap C \qquad ---(1)\\ \text{Then }x \in A\text{ and }x \in C\\ \text{so }x \in A\cup C \qquad ---(2)$

$\text{By (1): }x \in B\cap C \because A \cap C \subseteq B \cap C\\ \text{and by (2): }x \in B\cup C \because A \cup C \subseteq B \cup C$

$\therefore x \in B\text{ and }x \in C\\ \text{So }x \in B \therefore A \subseteq B$

InteGrand · Jul 29, 2016

Re: Discrete Maths Sem 2 2016

To show A is a subset of B, you should start off by letting x be an element of A (you did A∩C), and then show it is an element of B. (You may want to consider cases along the way to help use the given info.)

I think what you essentially did is show A∩C is a subset of B.

leehuan · Jul 29, 2016

Re: Discrete Maths Sem 2 2016

Ah right. How's this then?

$\text{Suppose }x \in A\\ \text{Then }x \in A\cup C\\ \therefore x \in B \cup C (A\cup C \subseteq B \cup C)\\ \text{so }x \in B \text{ and/or } x \in C$

$\text{If }x \in B\text{ we have what we need.}$

$\text{If }x\in C\text{, then }x \in A\cap C\\ \therefore x \in B\cap C (A\cap C \subseteq B \cap C)\\ \text{so }x \in B\text{ and }x \in C\\ \therefore x \in B\text{ as well.}$

$\therefore\text{in either case }x \in B\text{ so it follows that }A \subseteq B$

seanieg89 · Jul 29, 2016

Re: Discrete Maths Sem 2 2016

Another way of doing it that doesn't involve taking elements is:

$A=(A\cap C)\cup (A\cap C^c)\subseteq (B\cap C)\cup ((B\cup C)\cap C^c)= (B\cap C) \cup (B\cap C^c) \cup C\cap C^c =B.$

Where the $\subseteq$ step follows from applying the question assumptions to replace $A\cap C,A$ with the supersets $B\cap C,B\cup C$ respectively.

leehuan · Jul 29, 2016

Re: Discrete Maths Sem 2 2016

seanieg89 said:
Another way of doing it that doesn't involve taking elements is:

$A=(A\cap C)\cup (A\cap C^c)\subseteq (B\cap C)\cup ((B\cup C)\cap C^c)= (B\cap C) \cup (B\cap C^c) \cup C\cap C^c =B.$

Where the $\subseteq$ step follows from applying the question assumptions to replace $A\cap C,A$ with the supersets $B\cap C,B\cup C$ respectively.

Nice that makes sense. I'm just used to element wise because the lecturers said so lol.
___________________________

The answers don't even tell me if it's true or false so I assumed it was true (because I could not find any counterexample) but then I got stuck proving the latter part.

$$Prove if true or give a counter example if false:$\\ $For all sets $A, B $ and $C\\ A\times (B\cup C)=(A\times B)\cup (A\times C)$

Basically I got stuck proving the RHS is a subset of the LHS

InteGrand · Jul 29, 2016

Re: Discrete Maths Sem 2 2016

leehuan said:
Nice that makes sense. I'm just used to element wise because the lecturers said so lol.
___________________________

The answers don't even tell me if it's true or false so I assumed it was true (because I could not find any counterexample) but then I got stuck proving the latter part.

$$Prove if true or give a counter example if false:$\\ $For all sets $A, B $ and $C\\ A\times (B\cup C)=(A\times B)\cup (A\times C)$

Basically I got stuck proving the RHS is a subset of the LHS

A way to show RHS is a subset of LHS.

Note the RHS is a set of ordered pairs. Let (x,y) be an element of RHS.

Then (x,y) is in A x B or in A x C.

If it's in A x B, then x is in A and y is in B ==> x is in A and y is in B union C. (As B is a subset of B union C.)

The other case you can similarly show that x is in A and y is in B union C.

So in either case, (x,y) is in A x (B union C).

So RHS is a subset of LHS.

leehuan · Jul 29, 2016

Re: Discrete Maths Sem 2 2016

$$Suppose $A, B$ and $C$ are sets such that $A\oplus C=B\oplus C$. Prove that $A=B$

It means the symmetric difference in this context.

$$Definition given: $A \oplus B = (A-B)\cup (B-A)\\ $Proven earlier: $A \oplus B = (A \cup B) - (A \cap B)$

seanieg89 · Jul 29, 2016

Re: Discrete Maths Sem 2 2016

Have you learned that the symmetric difference is associative? If not, then prove this as an exercise as it is easy and has this claim is a trivial consequence.

Indeed, We have A*C=B*C => (A*C)*C=(B*C)*C => A*(C*C)=B*(C*C) => A*e=B*e => A=B where e denotes the empty set and * denotes the symmetric difference operation.

(In fact we are proving a property of abstract groups here. An algebra of sets endowed with the symmetric difference is an abelian group.)

leehuan · Jul 29, 2016

Re: Discrete Maths Sem 2 2016

I will work on it later. It doesn't look hard if I give it a bit of thought.

We weren't actually taught what symmetric difference is really. It's just a homework question regarding it.

seanieg89 · Jul 29, 2016

Re: Discrete Maths Sem 2 2016

Yep, it really isn't.

As it happens (A*B)*C=A*(B*C)=The set of things that are elements of exactly one of the three sets.

leehuan · Aug 1, 2016

Re: Discrete Maths Sem 2 2016

I think I'm forgetting something.

I understand how a function f is surjective iff the codomain of f is the range. However what's the problem if the codomain was a proper subset of f?

Also, are these supposed to be two notations for the same thing
$f(x)=x^3\qquad f:x \mapsto x^3$

seanieg89 · Aug 1, 2016

Re: Discrete Maths Sem 2 2016

"Codomain was a proper subset of f"? What do you mean by this?

Yes to your second question. Read that kind of arrow as "maps to".

leehuan · Aug 1, 2016

Re: Discrete Maths Sem 2 2016

Alright cool.

My bad on the first qn, meant a subset of the range. So something like

$f:\mathbb{R} \to [0, \infty), \, f(x)=x^3$

Edit: Oh crap, is it because when x=-1 (which is in R), there is no output value?

With that maps-to notation though I have another question. How would you write something like f:R->R, f(x)=x?
$f: \mathbb{R} \to \mathbb{R}, x \mapsto x$

seanieg89 · Aug 1, 2016

Re: Discrete Maths Sem 2 2016

That doesn't make any sense, when you talk about a function, you have to specify a domain and a codomain for that function. Loosely speaking a function is a pair of sets X,Y and a rule that assigns to every element of X an element of Y.

The range is the set of elements of Y that are actually hit, ie the range is always a subset of the codomain.

leehuan · Aug 1, 2016

Re: Discrete Maths Sem 2 2016

Wait what? Now I'm confused.

I resolved my question mainly based off something like this:
$f:\mathbb{R}\to \mathbb{R}, f(x)=\frac{1}{x}\\ \text{is not a function (despite what bull high school says) because when }x=0\text{ there is no defined value for }f(0)$

I was wondering why something like this 'function' is not surjective:
$f:\mathbb{R} \to [0,\infty), f(x)=x^3$

But then I realised that it's not a function because when x<0, there are no output values.

(Edit: Or maybe I do actually. I think I might've abused the term "range")

MATH1081 Discrete Maths (1 Viewer)

Well-Known Member

Well-Known Member

Kosovo is Serbian

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Well-Known Member

Users Who Are Viewing This Thread (Users: 0, Guests: 1)