0
votes
5answers
158 views

The set of all finite subsets of the natural numbers is countable

Could someone verify my proofs? Proposition: the set of all finite subsets of $\mathbb{N}$ is countable Proof 1: Define a set $ X=\{A\subseteq\mathbb{N}\mid \text{$A$ is finite} \}$. We can have a ...
0
votes
3answers
122 views

Proof that the set of all functions from $\mathbb N$ to $\mathbb N$ is not enumerable

I'm trying to show that the set of all functions from $\mathbb N$ to $\mathbb N$ is not enumerable. Can someone verify my proof below? Proof: Let $\mathcal{F}(\mathbb{N}; \mathbb{N})$ be the set of ...
2
votes
3answers
36 views

What is the set with characteristic function $\chi_A(x) + \chi_B(x)-\chi_A(x)\chi_B(x)$?

Suppose that $A$ and $B$ are subsets of $X$ Find the subset $C$ whose characteristic function is given by: $\chi_C(x)=\chi_A(x) + \chi_B(x)-\chi_A(x)\chi_B(x)$ The answer given is ...
1
vote
1answer
57 views

Is my proof on showing that the set of monotone functions on $[a,b]$ has cardinality of continum correct?

I was given an exercise problem to show that the cardinality of the set of all monotone functions on $[a,b]$ is $\aleph$. I came out with a proof which I am not sure if it is correct. My proof: Let ...
1
vote
3answers
115 views

My proof of the recursion principle (without the axiom of replacement)

(The proof in my book uses the axiom of replacement. My proof doesn't use it. Any hints and recommendations are welcomed.) The recursion principle Let $y_0$ be any element of a set $Y$ and ...
1
vote
1answer
46 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
92 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
90 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
31 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
56 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
41 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 ...
25
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
3answers
62 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
20 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
25 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
61 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
50 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
44 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
150 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
43 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
36 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 ...
0
votes
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
61 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
42 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
39 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
68 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
29 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 ...
1
vote
1answer
115 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
73 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 ...
0
votes
1answer
49 views

Prove or give a counterexample: if $A\cap B=B\cap C=A\cap C = \varnothing$ then $A\cap B\cap C \ne \varnothing$

Prove or find a counter-example to the claim that for all sets $A,B,C$ if $A\cap B=B\cap C=A\cap C = \varnothing$ then $A\cap B\cap C \ne \varnothing$. Solution False. Let $A=\{1,4,6\}, ...
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
31 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
32 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
106 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
39 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
63 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
367 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
50 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
38 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: ...