Tagged Questions
2
votes
3answers
55 views
Set Distributive Property Proof
Prove the distributive property for sets:
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
I'm not good with proofs but my understanding is that I have to prove 2 things:
(1) $A \cup (B ...
0
votes
2answers
50 views
Help with writing proofs
Prove that for any sets A, B and C if A is a subset of B, then A – C is a subset of B – C.
4
votes
2answers
29 views
$S=\{(X,Y) \in \mathcal{P}(A) \times \mathcal{P}(A) \mid \forall x \in X \exists y \in Y(xRy)\}.$ If R is symmetric, must S be symmetric?
I'm working on an exercise from How To Prove It by Velleman, and I'm having a hard time.
Suppose $R$ is a relation on $A$ and define a relation S on $\mathcal{P}(A)$ as follows: $$S=\{(X,Y) \in ...
2
votes
1answer
37 views
Suppose $R$ and $S$ are transitive relations on $A$. Prove that if $S \circ R \subseteq R \circ S$ then $R \circ S$ is transitive.
Suppose $R$ and $S$ are transitive relations on $A$. Prove that if $S \circ R \subseteq R \circ S$ then $R \circ S$ is transitive.
First, I'm wondering if my proof is correct? Second, I'm really ...
5
votes
5answers
92 views
Prove $(A \triangle B) \cap (B\triangle C) \cap (C\triangle A) = \emptyset$
This can be proved by assuming that there exists some $x \in (A \triangle B) \cap (B\triangle C) \cap (C\triangle A) $ and then deriving a contradiction by considering each of the cases that arise.
...
4
votes
4answers
84 views
Prove that $A \mathop \triangle C \subseteq (A \mathop \triangle B)\cup (B \mathop \triangle C)$
Suppose A, B, and C are sets, prove that $A \mathop \triangle C \subseteq (A \mathop \triangle B)\cup (B \mathop \triangle C)$
I'm just wondering if this proof is ok, or if I'm overlooking something, ...
6
votes
3answers
98 views
Prove that if $\mathcal P(A) \cup \mathcal P(B)= \mathcal P(A\cup B)$ then either $A \subseteq B$ or $B \subseteq A$. [duplicate]
Prove that for any sets $A$ or $B$, if $\mathcal P(A) \cup \mathcal P(B)= \mathcal P(A\cup B)$ then either $A \subseteq B$ or $B \subseteq A$. ($\mathcal P$ is the power set.)
I'm having trouble ...
2
votes
2answers
93 views
Prove that $A \subset B$ if and only if $A \cap B = A$
Prove that $A \subset B$ if and only if $A \cap B = A$
I'm having problems writing this proof using formal logic operators. I know the idea behind it: Since $A \subset B$, the only elements A and ...
5
votes
4answers
121 views
Prove that if $A \mathop \triangle B \subseteq A$ then $B\subseteq A$
I'm having trouble with the logic in this proof and was wondering if anyone could point me in the right direction (if I'm wrong)?
Prove that if $A\mathop\triangle B\subseteq A$ then $B\subseteq A$. ...
2
votes
3answers
130 views
Proof: $A \neq \emptyset \implies A \nsubseteq \emptyset $
I proof that, let $A$ a set and $A \neq \emptyset$, then $A \nsubseteq \emptyset$;
Proof by contradiction: if $A \subseteq \emptyset$ then by property I have an absurd , in fact by hypothesis $A ...
4
votes
2answers
176 views
Proof by contradiction: $ \emptyset \subseteq A$
I have to proof by contradiction that: let $ A $ a set and $ \emptyset $ the empty set, then $ \emptyset \subseteq A$; if $ \emptyset \nsubseteq A$ then $\exists x \in \emptyset ( x \notin A ) $ ...
3
votes
3answers
154 views
Discrete Math Proof With Power-sets [duplicate]
The question I am working on is:
Can you conclude that $A=B$ if $A$ and $B$ are two sets with the same power set?
At first, I thought of doing a proof by contraposition; however, that didn't ...
1
vote
2answers
49 views
Is it enough to point the definitions given in the book for proving this relation?
I'm reading Allufi's Algebra, CHAPTER 0:
Prove that if $\sim$ is a relation on a set $S$, then the
corresponding family $P_{\sim}$ is indeed a partition of $S$: That is,
it's elements are ...
4
votes
1answer
47 views
Verification of a proof involving Hausdorff max. principle and collections
I am given this proposition to prove which is a corollary to HMP(Hausdorff maximality principle). My two concerns are:
1. is my attempted proof correct? and 2. Is HMP applicable even when we're ...
1
vote
1answer
35 views
Finding specific sets
I'm trying to calculate these particular sets given that:
$$A=\{a,c,e,h,k\}$$
$$B=\{a,b,d,e,h,i,k,l\}$$
$$C=\{a,c,e,i,m\}$$
$$A \cap B$$
$$A\cap B \cap C$$
$$A \cup B \cup C$$
$$A-B$$
...
-2
votes
2answers
57 views
Prove using induction $(A_1 \cap A_2 \cap … \cap A_k) \cup B = (A_1 \cup B) \cap (A_2 \cup B) \cap … (A_k \cup B)$
Prove that if $A_1, A_2, ... , A_n$ and $B$ are sets, then:
$(A_1 \cap A_2 \cap ... \cap A_n) \cup B = (A_1 \cup B) \cap (A_2 \cup B) \cap ... \cap (A_n \cup B)$
Here's what I have. Could someone ...
1
vote
2answers
46 views
Prove $\bigcup _{j=1}^nA_j \subseteq \bigcup_{j = 1}^n B_j$
Prove using induction that if $A_1, A_2,...,A_n,$ and $B_1, B_2,...,B_n$ are sets such that $A_j \subseteq B_j$ for $j = 1, 2,..., n$ then,
$\bigcup _{j=1}^nA_j \subseteq \bigcup_{j = 1}^n B_j$
I ...
3
votes
3answers
90 views
it is surjective - $f: \mathbb{N} \rightarrow \mathbb{N}: x \rightarrow 2x$
i think, this function is surjective:
$$f: \mathbb{N} \rightarrow \mathbb{N}: x \rightarrow 2x$$
but in my textbook it says, it is not surjective. but no proof there. i am really wondering if it is a ...
3
votes
1answer
94 views
Prove transitivity of $\forall X( X\subseteq A\setminus\{a, b\}\rightarrow(X\cup \{a\}\in\mathcal{F}\rightarrow X\cup\{b\}\in\mathcal{F}))$
This one is from Velleman's "How to Prove It, 2nd Ed.", exercise 4.3.23.
Suppose $A$ is set, and $\mathcal{F}\subseteq\mathcal{P}(A)$. Let $$R=\{(a,b)\in A\times A : \text{for every } X\subseteq ...
3
votes
3answers
118 views
Prove that the sets $(A\cap B)$ \ C and $(A\cap C)$ \ B are disjoint.
Please could someone validate this proof
Prove that the sets $(A\cap B)$ \ C and $(A\cap C)$ \ B are disjoint.
First we want to show that
(1) $(A\cap B)$ \ C $\not \subseteq $ $(A\cap C)$ \ B
...
4
votes
1answer
104 views
How do I show that two sets are equal.
This is an ever so slightly modified version of a question from my book. My teacher went over this with me, but I would like an explanation that I can keep coming back to until I have this method ...
7
votes
2answers
157 views
Feedback on my proof that $(A\setminus B)\cup(B\setminus A)=(A\cup B)\setminus (A\cap B)$
I would like to prove that $(A\setminus B)\cup(B\setminus A)=(A\cup B)\setminus (A\cap B)$. Please could you offer some feedback?
Firstly, I will show that:
$(A\setminus B)\cup(B\setminus ...
3
votes
5answers
142 views
how do you prove this set problem?
I'm trying to teach myself set-theory. I have been unable to prove algebraically that:
$(A \cup B) \cap \overline{(A \cap B)} = (A \cap \overline{B}) \cup (\overline{A} \cap B) $
I know it's ...
2
votes
3answers
72 views
Proving that $\lnot(A \cup B) = \lnot A \cap \lnot B$
I'm working on proving the case above thusly:
Note: I should point out that i'm using the $\lnot$ symbol in place of the complement bar that should go over the letters, as i can't seem to get that ...
1
vote
3answers
94 views
Uniqueness proof for $\forall A\in\mathcal{P}(U)\exists!B\in\mathcal{P}(U)(C\setminus A=C\cap B)$
I managed to prove existence for the following theorem:
$$\forall A\in\mathcal{P}(U)\ \exists!B\in\mathcal{P}(U)\ \forall C\in\mathcal{P}(U)\ (C\setminus A=C\cap B)$$
where U is any set. My ...
0
votes
2answers
74 views
Equinumerous Sets
Suppose $A$ and $B$ are sets and $A$ is finite. Prove that $A \sim B$ iff $B$ is also finite and $|A| = |B|$.
Notes on notation:
$A \sim B$ indicates that $A$ is equinumerous with $B$.
4
votes
3answers
86 views
Prove that $(g \circ f )^{-1} = f^{-1} \circ g^{-1}$
I've already proven that if we assume f is bijective and g is bijective, then $(g \circ f)$ is bijective. I've also proven that$(g \circ f)^{-1}$ exists. I'm stuck on this part, however. Any ...
1
vote
1answer
44 views
Prove that if $n \in \Bbb N$, $f: I_n \to B$, and $f$ is onto, then $B$ is finite and $|B|\leq n$.
Prove that if $n \in \Bbb N$, $f: I_n \to B$, and $f$ is onto, then $B$ is finite and $|B|\leq n$.
Notes on notation:
For each natural number $n$, $I_n = \{i \in \mathbb{Z} \mid i \leq n\}$.
$A ...
1
vote
3answers
54 views
minimum of this simple set
i need again some help here. i am defining the minimum and max and inf and sup of this set
$A:=(]1,2[ \cup ]2,3]) \cup \{2\}$ which is equal to the interval $(1,3]$
i say, max is 3, and sup is also ...
3
votes
2answers
55 views
Stuck with proof for $\forall A\forall B(\mathcal{P}(A)\cup\mathcal{P}(B)=\mathcal{P}(A\cup B)\rightarrow A\subseteq B \vee B\subseteq A)$
I came to point where I suppose for case 1 that $A\subseteq B$ and conclusion is trivial. For case 2 I suppose that $A\not\subseteq B$ and try to prove $B\subseteq A$, but that gets me nowhere. Any ...
2
votes
2answers
102 views
If $f: A \rightarrow B$ is injective, $\exists ! f^{-1}:f(A)\rightarrow A$ such that $f^{-1}f(x) = x$
If $f: A \rightarrow B$ is injective, $\exists ! f^{-1}:f(A)\rightarrow A$ such that $f^{-1}f(x) = x$
I know the proof of this is super simple, like 2 lines (+ some for uniqueness), but I can't ...
1
vote
2answers
86 views
Problem with proving equation. (Sets.)
I would like to ask you for helping me out with this problem. I had to prove this equation.
$$\left(\bigcap_i A_i\cap\bigcup_{i\text{ odd}}A_i\right)\triangle\bigcap_{i\text{ odd}}A_i=\left(\bigcap_i ...
0
votes
2answers
58 views
Maps - question about $f(A \cup B)=f(A) \cup f(B)$ and $ f(A \cap B)=f(A) \cap f(B)$
I am struggling to prove this map statement on sets.
The statement is:
Let $f:X \rightarrow Y$ be a map.
i) $\forall_{A,B \subset X}: f(A \cup B)=f(A) \cup f(B)$
ii) $\forall_{A,B \subset X}: ...
2
votes
3answers
262 views
Set Theory Help
I have a test coming up on set theory, so the basic definitions, set operations, relations and functions.
On the test I will have to do proofs involving all of these (subset, unions, intersections, ...
2
votes
2answers
47 views
how to prove this statement
i am trying to prove this statement, it is obvious, but i just cannot get the clue where and how to start to prove that this statement is true.
the statement is this: $(A \setminus C)\times(B ...
2
votes
1answer
113 views
Sets theory - proving an expression
Given that A, B and C are sets, and that (A ∪ B) \ C ⊆ A \ B
(A cup B) minus C (is contained in) A minus B
Prove that (A \ C) ∩ B = ∅
(A minus C) cap B = Empty set
I tried to prove it this way:
It ...
0
votes
1answer
125 views
Every non-empty subset of $\mathbb{R}$ bounded above has a largest element
I restarted my analysis book from page 1 trying to relearn everything because I feel like my knowledge is too fragmented. This true false question asks exactly what the title says. I don't know 100% ...
0
votes
2answers
78 views
Help with regular expression subset proof
Okay, so basically I'm just showing that two ways to express a regular expression are equal, and to do so, I'm showing they're subsets of each other.
The expression is:
$(A^*B^*)^* \subset ...
0
votes
1answer
91 views
Proof about set Intersection
I am having trouble formalizing two proofs I have to make about an infinite intersection of sets.
Suppose that, for every $k\in\Bbb N$ ($k>0$), we define the set $S_k = \{x\in\Bbb R: 0\le ...
0
votes
1answer
43 views
Set of decision functions are uncountable
Okay, so here's the problem:
A function is a decision function if it maps finite length binary strings {0,1}* into codomain {0,1}. Let D be the set of all possible decision functions. Show that D is ...
2
votes
1answer
64 views
What's wrong with the proof
Result: $(A\times C)-(B\times C)\subseteq (A-B)\times C$
Proof: Let $(x,y)\in (A\times C)-(B\times C)$. Then $(x,y)\in A\times C,\implies x\in A,y\in C$. Since $(x,y)\notin B\times C, x\notin B$. ...
1
vote
1answer
80 views
How can I proceed in proving number theory/set exercise?
The problem states:
Prove that:
In every set of 100 integers, there exists two distinct integers x and y s.t. 89 | (x-y)
So far the only thing I've determined is that 89 is prime, so 89 | (x-y) if ...
0
votes
2answers
49 views
show that {S1,S2}has an infimum.
did i show this right ?
$A \neq \emptyset , $
Pt(A)= the set of all partitions of A
Let $\preceq$ be an partial ordering on Pt(A)
so that
(Pt(A),$\preceq$) is a partially ordered set.
now ...
1
vote
5answers
115 views
Set theory proof $(S_1 \cap S_2') \cup (S_1' \cap S_2) = \emptyset$
Prove $S_1 = S_2$ if and only if
$(S_1 \cap S_2') \cup (S_1' \cap S_2) = \emptyset$
I get why it is, I just don't know how to write formal proofs.
$S_2'$, $S_1'$ in this modified notation means it ...
0
votes
1answer
20 views
let R be an ordering of Aand S be the coresponding strict ordering of A, and R* be the ordering coresponding to S show R=R*
i think i have to use these facts
(a,b)$\in$R* and a$\neq$b
(a,b)$\in$R or a=b
to show they are both subsets of each other .?? but im not sure how.
1
vote
1answer
111 views
Proof that $(x,y)\sim (x',y') \iff x=x' , y-y'=n2\pi$ where $n\in\mathbb Z$ is an equivalence relation?
Have I made any mistakes in the following proof?
THEOREM:
If $P=\{(x,y)\in\mathbb R^2|x>0 \}$ and if there exists a relation $$\sim|(x,y)\sim(x',y') \iff x=x' , y-y'=n2\pi$$ where $n\in\mathbb Z$ ...
3
votes
1answer
354 views
If $F$ and $G$ are one to one, then $G \circ F$ is one to one and $(G \circ F)^\neg = F^\neg \circ G^\neg$
THEOREM: if $F$ and $G$ are one to one then $G \circ F$ is also one to one and $(G \circ F)^\neg$ = $F^\neg \circ G^\neg$
PROOF:
if $F: A\rightarrow B$, $G: B \rightarrow C$ and
$$\forall a, a' ...
4
votes
1answer
73 views
If $\operatorname{ran} F \subseteq \operatorname{dom} G$, then $\operatorname{dom}(G \circ F) = \operatorname{dom} F$.
THEOREM: If $ \text{ran } F \subseteq \text{dom } G $ then $\text{dom }(G \circ F)= \text{dom }F$
PROOF: if $ F\subseteq A \times B$ and $ G\subseteq B\times C$
then by definition
...
0
votes
1answer
78 views
Can I prove that Cardinality of the set of all maximum point (for any function $\mathfrak{f}$) is countable or finite by Reductio ad absurdum
I will write my proof in short words:
If I write that ths set of maximum points is uncountable so if I have a Polynomial function of n degree so the Polynomial function derivative could have a root ...
3
votes
2answers
104 views
Prove whether a relation is an equivalence relation
Define a relation $R$ on $\mathbb{Z}$ by $R = \{(a,b)|a≤b+2\}$.
(a) Prove or disprove: $R$ is reflexive.
(b) Prove or disprove: $R$ is symmetric.
(c) Prove or disprove: $R$ is transitive.
For ...
