# Tagged Questions

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
92 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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: ...
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) ...
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 ...
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 ...
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)$. ...
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 ...
45 views

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 ...
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.] ...
32 views

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)$$ ...
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$ ...
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 \\ ...
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 ...