1
vote
1answer
37 views

Proving some properties of $\Bbb N$ without using recursion

I will try to prove that if $a, b, c \in \Bbb N$ and $a \in b \in c$, then $a \in c$ (the transitivity property). I will not use recursion or the replacement axiom. Actually we can proove in the same ...
1
vote
2answers
82 views

Prove: If $A \subseteq B$ and $B \subseteq C$, then $A \subseteq C$.

Can someone tell me if this proof is acceptable? Assume $A \not\subseteq C$. This means that there is an $x \in A$ such that $x \not\in C$. But since $\forall x \in A: x \in B$ and $\forall x \in B: ...
2
votes
4answers
87 views

Prove $A \subset \emptyset \iff A = \emptyset$

How does one prove this? Can one prove by contradiction by saying: Let $A$ be any set such that $A$ contains at least one element. Now assume $A \subset \emptyset$. This is clearly absurd by the ...
2
votes
2answers
30 views

Help to prove $f$ is surjective $\Leftrightarrow \forall y \in Y, (X \times \{y\} \cap G_f ) \ne \emptyset $

Let $f:X \rightarrow Y$ be a function with graph $G_f \subseteq X \times Y$. Prove that $f$ is surjective if and only if $\forall y \in Y, (X \times \{y\} \cap G_f ) \ne \emptyset $ I have some ...
1
vote
2answers
52 views

Wondering if proof is proper

so I have been working on learning some new math in order to prepare for next year. I have been trying to learn proofs, and doing practice questions however the only problem is there are not answers. ...
4
votes
1answer
38 views

Proving a Subset Identity

Working on part A of this problem: I worked out the first part like this: 1) If $A$ is a subset of $B$ then $\forall~x~[x\in A \implies x\in B]$ 2) Same goes for $C$ being a subset of $D$ (If ...
23
votes
2answers
1k views

Lamport claims there is an error in Kelley's proof of the Schroeder-Bernstein theorem. What is it?

In section 4.1 of his note How to write a proof, Leslie Lamport mentions an error in Kelley's exposition of the Schroeder-Bernstein theorem: Some twenty years ago, I decided to write a proof of ...
2
votes
2answers
45 views

Proof of $A \subseteq B \Leftrightarrow A \cap B = A$ (Check chain of implications)

Prove $A \subseteq B \Leftrightarrow A \cap B = A$. My attempt: Case $\Rightarrow$: $$\begin{align} A \subseteq B & \Rightarrow & [x\in A \Rightarrow x\in B] \\ &\Rightarrow &[x ...
3
votes
0answers
18 views

Prove that $\operatorname{ran} f \subseteq \operatorname{dom} g \implies\operatorname{dom} (g \circ f)=\operatorname{dom} f$

Some preliminaries: A function $f$ is a binary relation such that $(x,y_1) \in f$ and $(x, y_2) \in f$ implies $y_1 = y_2$. $\operatorname{ran} f = \{y: \exists x$ such that $(x,y) \in f\}$ ...
1
vote
1answer
24 views

Prove that $R[A \cup B] = R[A] \cup R[B]$, where $R$ is a binary relation.

Can someone please verify this? Prove that $R[A \cup B] = R[A] \cup R[B]$, where $R$ is a binary relation. Here, $R[C] = \{y: \exists x \in C $ such that $(x,y) \in R\}$ Let $z \in R[A \cup ...
4
votes
3answers
54 views

Show that $A \subseteq B \iff A \subseteq B-(B-A)$

Can someone please verify this? Show that $A \subseteq B \iff A \subseteq B-(B-A)$ $(\Rightarrow)$ Let $x \in A$. Then, $x \notin B-A$. Also, $x \in B$. Therefore, $x \in B-(B-A)$ So, $A ...
3
votes
1answer
47 views

Show that if $B \subseteq C$, then $\mathcal{P}(B) \subseteq \mathcal{P}(C)$ [duplicate]

Can someone please verify this? Show that if $B \subseteq C$, then $\mathcal{P}(B) \subseteq \mathcal{P}(C)$ let $x \in \mathcal{P}(B)$. Then, $x \subseteq B$ This implies that $$\forall a \in ...
1
vote
1answer
57 views

Is it true , if $|A|=|B|$ and $|C|=|D|$, then $|A \times C| = |B \times D|$?

Check my proof, please. Divide into subsets $A \times C$ and $B \times D$ so that , all pairs with the same element belong to the same subset. Each such subset $|A \times C|$ bijective $C$, $|C|=|D|$ ...
1
vote
2answers
43 views

Is there a direct proof of the following?

I have been warned by my Lecture as well as several other sources that while proof by contradiction is useful and is certainly needed in some cases, it is often overused. In a effort to learn, I ...
1
vote
3answers
147 views

Proposed proof of set theoretic result

I am tasked with proving the following: $$ (A - B)\cap (B-A) = \varnothing $$ My Attempt: Suppose there exist a $x \in (A - B)\cap (B-A) $ then: \begin{align*} x \in (A - B)\cap (B-A) &\iff ...
3
votes
1answer
35 views

Showing that for $s,t\in\mathbb{Q}$, we have $(s+t)^*= s^* + t^*$.

I'm working through the problems of Elementary Analysis Theory of Calculus, and for some reason, this question didn't make the solutions in the back of the book. I did a thorough search on Stack ...
0
votes
1answer
49 views

Is something wrong with a proof of $f(A) \cup f(B) \subseteq f(A \cup B)$?

Claim: $$f(A) \cup f(B) \subseteq f(A \cup B)$$ Suppose $$ y \in f(A) \cup f(B)$$ $$y \in f(A)$$ or $$y \in f(B)$$ $$\exists x_0 \in A (f(x_0) = y)$$ or $$\exists x_0 \in B (f(x_0) = y)$$ ...
1
vote
4answers
39 views

Proof simplification

I am tasked with proving the following: $$\varnothing - A = \varnothing $$ My Attempt : Assume there exist $x \in $$\varnothing - A $ then $$ x \in \varnothing - A \Rightarrow x \in ...
1
vote
3answers
30 views

Verification of Proof strategy

I am tasked with proving the following : $$A \cap B^c \subseteq (A \cap B)^c$$ I came up with the idea of using a combination of De Morgan's laws, rule simplification and rule of addition to prove ...
1
vote
2answers
66 views

Proof makes sense?

$\exists! {A} \subset {Z}$ such that $A \cup B = A$, where $B$ is any subset of $Z$. Proof: Assume two such sets exist, $A_1$ and $A_2$ If $A_1 \cup B = A_1, \forall B \cup Z$, then $A_1 = Z$ If ...
1
vote
1answer
60 views

Prove/disprove questions on isomorphism and embedding between order types

About the notations: Let $\lambda, q, z, \omega$ be the order types of the reals, rationals, integers and natural numbers respectively. The sign $=$ means there's isomorphism and $\le$ means ...
0
votes
1answer
37 views

Showing that two intervals are equivalent.

Complete the proof that any two open intervals $(a, b)$ and $(c, d)$ are equivalent by showing that $f(x) = \frac{d-c}{b-a}(x-a) + c$ maps one to one and onto $(c,d)$. I showed one to one by saying ...
2
votes
0answers
34 views

Velleman's How to prove it. Partial order proof.

Theorem: Suppose that $R$ is a partial order on $A$, $B_1 ⊆ A$, $B_2 ⊆ A$, $x_1$ is the least upper bound of $B_1$, and $x_2$ is the least upper bound of $B_2$. Prove that if $B_1 ⊆ B_2$ then ...
0
votes
1answer
17 views

Prove if $a\in A$ is a maximum then $f(a)\in B$ is maximum and if $(A,\le_A)$ is totally ordered then $(B,\le_B)$ is totally ordered

Two ordered sets $(A,\le_A), (B,\le_B)$ and there's an isomorphic function $f:A\to B$ Prove if $a\in A$ is a maximum then $f(a)\in B$ is maximum. if $(A,\le_A)$ is totally ordered then ...
0
votes
0answers
51 views

Would like to confirm answer (regarding sets)

As you might know from my precious questions, I am pretty weak with quantifiers. Below is my solution to the stated problem, if incorrect, could someone explain why? My attempted solution: ...
2
votes
1answer
55 views

How to Prove it 4.1 ex.10

Prove that for any sets A, B, C, and D, if A × B and C × D are disjoint, then either A and C are disjoint or B and D are disjoint. Proof(someones). Suppose (A X B) and (C X D) are disjoint. Let (x,y) ...
1
vote
0answers
28 views

Prove/disprove questions on equivalence relations and ordered sets

If $R$ is an equivalence relation and a partial order over $A \neq \emptyset$ then every equivalence class contain at least one element. If $(A,\le)$ an ordered set, and $a\in A$ is a single ...
2
votes
1answer
110 views

Proof or find a counterexample:For all sets $A;B;C$ if $A\subseteq B,\ B\subseteq C,$ and $C\subseteq A,$ then $A=B=C.$

Proof or find a counterexample:For all sets $A;B;C$ if $A\subseteq B,\ B\subseteq C,$ and $C\subseteq A,$ then $A=B=C.$ My solution: True. Let $x\in A$, and since $A\subseteq B$ this implies that ...
1
vote
1answer
27 views

Let $A =[a,b,c,f,g,i], B=[b,f,h]$ and $ C = [a,k,l,m]$ Show that $\backslash$ is not associative

Question : Let $A =[a,b,c,f,g,i], B=[b,f,h]$ and $ C = [a,k,l,m]$ Show that $\backslash$ is not associative by comparing $(A \backslash B) \backslash C$ with the set $A \backslash(B \backslash C)$. ...
0
votes
1answer
72 views

Beginner proof of image of functions and functions of sets

This is the third time I got my proofs handed back from my teacher. She won't tell me what's wrong except I have to redo it. I am running out of luck and I need help towards the right direction! The ...
1
vote
1answer
45 views

Proving Limits of f(x) and f(a+h) are equal

The question asks me to prove that the equality of these two expressions $\lim_{x\to a} f(x)$ and $\lim_{h \to 0}f(a+h)$ provided their limits exist. My answer: Let $x=a+h$ so this $\lim_{h \to ...
1
vote
4answers
90 views

$f[A]\cap f[B]\supsetneq f[A\cap B]$ - Where does the string of equivalences fail ? [Chartrand 3E 9.12(b), 9.29]

I only realised that equality may fail in $f[A]\cap f[B]\supseteq f[A\cap B]$ (i.e., that we can have $A,B,f$ for which $f[A]\cap f[B]\neq f[A\cap B]$) after checking the answer. I don't see any ...
0
votes
1answer
29 views

An issue with the usual proof of Cantor's Theorem

It seems to me that the standard proof of Cantor's Theorem also "proves" that $\left|\mathcal{P}(X)\right| < \left|\mathcal{P}(X)\right|$. [The following is adopted from Hrbacek & Jech.] ...
0
votes
0answers
31 views

Proving a set is equal to another set

For all sets $A$ and $B,(B-A)=B\cap A^C$. I would like to know if this proof is correct or if I am on the right track. Here it is: Let $b \in B$ such that $b \notin A$ than $b \in B$ and $b \in ...
3
votes
1answer
54 views

Please check these proofs for sets

I would appreciate the insight again for a couple of proofs since I'm learning. These are homework problems in so much as they are problems from the textbook. They are not required by my professor. ...
2
votes
1answer
102 views

Is the following set stratified (and why not) in New Foundations?

notation: $Id=\{\langle x,y\rangle : x=y\}$ (identity relation) $X[y]$ (image of an element y under a relation X) the set I am asking for is: $Z=\{\langle x,y\rangle : \neg \exists k\; y \in k ...
0
votes
1answer
41 views

set theory, infinite set proof, is it alright?

$\Bbb{N}$ is the natural numbers set (included $0$). let be $n\in\Bbb{N}$, $A_n = \{x\in \Bbb{N}|0\leq x \leq n\}$ prove of disprove: $$\forall n,k \in \Bbb{N},\exists m \in\Bbb{N}(|A_m - A_n|=k)$$ ...
0
votes
1answer
33 views

Set proof (symmetric difference of disjoint set)

The question: Prove this is true: ($A$ $\setminus$ $B$) $\cup $ ($B$ $\setminus$ $A$) = ($A$ $\cup$ $B$) iff ($A$ $\cap$ $B$) = $ \emptyset$ ...
0
votes
4answers
61 views

Prove $(A \cap B) \cup (A \cap B^c) = A$

I need to prove the following statement: $$(A \cup B) \cap (A \cup B^c) = A$$ I did the following steps: \begin{align} &(A \cup B) \cap (A \cup B^c) = A \\ &A \cup B \cap (A \cup A) = A \\ ...
1
vote
1answer
26 views

Weak monotonicity of ordinal addition

I'm trying to prove the weak monotonicity of ordinal addition, i.e. if $\alpha \leq \beta$, then $\alpha + \gamma \leq \beta + \gamma$. The proof is not all that difficult, but I want to make sure I ...
7
votes
5answers
354 views

If $\mathcal{P}(A)=\mathcal{P}(B)$, then $A=B$? [duplicate]

Prove, disprove, or give a counterexample: If $\mathcal{P}(A)=\mathcal{P}(B)$, then $A=B$. Assume $\mathcal{P}(A)=\mathcal{P}(B)$. Since we know $A \subseteq A$, we know $A \in ...
4
votes
1answer
45 views

Problems with a proof that -in a linear order- a minimal element is the smallest element

I have a problem with a proof I found in Velleman's "How to prove it". This is sort of interesting, because it is the very first time I cannot see the structure of a proof presented in the book. The ...
0
votes
0answers
71 views

for n∈N A(n)={x∈N | 0<= x <= n}, prove the following statements

please help me improve this proofes, or find a more formal mathematical version of them. N is the set of natural numbers N = {0,1,2,...,} for all $n∈N$, there is $A(n) = \{x∈N | 0\le x \le n\}$ ...
1
vote
0answers
37 views

Prove the following sets equalities

I'm really struggling with proofes, please tell me if I'm correct and if there is a better way to prove (or disprove) the following: i) $(A \setminus B) \setminus B = A \setminus B$ My answer: ...
3
votes
3answers
102 views

Proof: $a^2 - b^2 = (a-b)(a+b)$ holds $\forall a,b \in R$ iff R is commutative

We want to show that for some ring $R$, the equality $a^2 - b^2 = (a-b)(a+b)$ holds $\forall a,b \in R$ if and only if $R$ is commutative. Here's my proof --- I'm not sure if the first part stands ...
4
votes
2answers
105 views

Prove or disprove $(A + B) \cap C = (A \cap C) +(B \cap C)$

Prove or disprove $(A + B) \cap C = (A \cap C) +(B \cap C)$ I want to disprove this statement. $(A+B)$ is the symmetric difference and has the form of $(A \cup B) \backslash (A \cap B)$ I am ...
3
votes
3answers
104 views

Prove $ (A \cup B) \cap C$ = $(A \cap C) \cup (B \cap C) $

Prove $ (A \cup B) \cap C$ = $(A \cap C) \cup (B \cap C) $ Starting from the left side, $ (A \cup B) \cap C = $ By distributive law, ( distributing the $\cap C$), we have $ (A \cap C ) \cup (B ...
2
votes
1answer
32 views

Some confusion in notation of Bernstein-Schroeder Theorem

Here on page 232-233 the author offers a proof of the Bernstein-Schroeder Theorem. He uses the subset $$\bigcup_{k=0}^\infty(g\circ f)^k(A-g(B))\subseteq A$$ and I'm not exactly sure how to parse ...
0
votes
1answer
61 views

$A=(A \cap B) \cup(A \cap B^\mathsf{c}) $

I would like to know if this proof is correct. If not, what would I have to change to make it rigorous? This set equality seems really obvious, and because of that I am not sure if I have given enough ...
0
votes
1answer
47 views

Is this proof circular? (Proof that the open disk/ball of radius 'r' is an open set)

This is on page 109 of "Vector Calculus" (5th ed.) by Marsden and Tromba. Here's my problem with this proof: We're trying to prove that an Open Disk is, in fact, an open set, but when we use the ...