# Tagged Questions

44 views

### Suppose $f: X \rightarrow Y$, and is one-to-one, and let $A \subseteq X$, prove that $f^{-1}[f[A]] = A$.

Suppose $f: X \rightarrow Y$, and is one-to-one, and let $A \subseteq X$, prove that $f^{-1}[f[A]] = A$. EDIT: Actually, this identity should hold even if $f$ is not one-to-one (injective), right? ...
27 views

94 views

### If $f \colon A \to B$, $g :\colon B \to C$ and $g\circ f \colon A \to C$ are bijections. Prove that $f$ is 1-1, $g$ is onto.

From what I understand, one-to-oneness means every element in $A$ is mapped to a unique element in $B$. To be onto, means for every $y$ in $B$, there exist at least one $x$ in $A$ from which it can ...
65 views

### Prove that $A \cup B = A$ if and only if $B$ is a subset of $A$

If $A \cup B = A$ then $A$ is a subset of $A$ and $B$ is a subset of $A$. Thus $A \cup B = A$. If $B$ is a subset of $A$ then it follows that $A \cup B$ is a subset of $A$. My solution. It seems ...
98 views

### Prove that the union of two disjoint countable sets is countable

This is a question from my proofs course review list that I have had trouble understanding. I understand the concept of disjoint sets. I'm not sure what they mean by countable. How would one prove ...
55 views

### Assuming that A and B are non-empty, if there is an injective function F : A -> B then there must exist a surjective function g : B -> A

Either give a counter-example, or a proof. A question in my proofs review. From what I understand we must assume each element of A is carried to a unique element of B (i.e. every value of A is ...
35 views

### Suppose that $F : X \longrightarrow Y$ is a function and $A$, $B$ are subsets of $Y$. Prove or disprove the following:

Suppose that $F : X \longrightarrow Y$ is a function and $A$, $B$ are subsets of $Y$. Prove or disprove the following: (a) Prove or Disprove: $F(A \cap B) = F(A) \cap F(B)$. (b) What if $f$ is ...
24 views

### Need help with compositions of relations

Prove that given relations $R_1 \subseteq A \times B$, $R_2 \subseteq B \times C$, $R_3 \subseteq C \times D$ then $(R1 \circ R2) \circ R3 = R1 \circ (R2 \circ R3)$ I don't know where exactly to ...
34 views

### How do I construct a proof showing what the cardinality of the set is:{ p/q such that p,q are elements of Natural Numbers}?

I know that the cardinality of the set of 1/k such that k is an element of Natural numbers is just Aleph-Null because I can prove that there is a bijective function from N-> 1/k for each k. But how do ...
29 views

### What is the cardinality of the subset of [0,1] consisting of infinite decimal expansions with only the digits 2 and 5?

Wouldn't this be uncountably infinite because ie, $$x_1=0.222225..., x_2=0.555555552..., x_3=0.5255...,$$ and if we keep going on...there can be $2^{\aleph_0}$ combinations. Then the cardinality ...
25 views

### Proof by Induction on two languages [duplicate]

I have a question that states - Using proof by induction, prove formally that L(R*) = L((R*)*) -- Where R is a regular expression over a non-empty alphabet. I have am struggling to relate it back to ...
37 views

### How to show a proof for |N|=|N| + 1 (Cardinality) [duplicate]

The problem is |N|=|N|+1, by N being all the natural numbers. The way I had it (which is the wrong way of proving it) was: Because |N| = Aleph-Null, the problem basically becomes Aleph-Null= ...
41 views

### one to one positive integers and positive rationals

How would you go about proving that there is a 1 : 1 correspondence between the set of positive integers and the set of positive rationals. I know there are a lot of ways to do this but I am looking ...
56 views

### Set theory proof question with functions

Let $f:A\rightarrow B$ be a function and let $C_1,C_2\subset A$ Prove that $f(C_1\cap C_2)=f(C_1)\cap f(C_2) \leftrightarrow$ $f$ is injective Attempt: $(\leftarrow)$ Let $f(x)\in f(C_1\cap C_2)$. ...
27 views

### Set theory: equivalence relation proof question

Prove that If $G$ is an equivalence relation in $A$, then $G\circ G=G$ My try Reflexive: $(x,x)\in G \forall x\in A$ Symmetric: If $(x,y)\in G$ then $(y,x)\in A$ Transitive: If $(x,y)\in G$ and ...
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 ...
34 views

### Proving that $S_k = \{A \subset \mathbb{N} : |A| = k\}$ for $k\in\mathbb{N}$ is denumerable. [duplicate]

I am having trouble with this problem for quite some time. I posted this question before but I still can not figure out this problem. So far,from the suggestion of user134824, I have tried to define ...
172 views

### Proof strategy for $(\Leftarrow)$: If $g \circ f = id_A$, then $f$ onto $\Leftrightarrow$ $g$ 1-1. [Chartrand 3Ed P239 9.72]

For nonempty sets $A$ and $B$ and functions $f \colon A \to B$ and $g \colon B \to A$, suppose that $g \circ f =$ the identity function on $A$. $(♦)$ (e) $(\Leftarrow)$ Assume that $g$ is ...
66 views

### Proof strategy for $(=>)$: If $g \circ f = id_A$, then f onto $\iff$ g 1-1. [Chartrand 3Ed P239 9.72]

For nonempty sets A and B and functions f : A → B and g : B → A, suppose that $g \circ f =$ the identity function on A. $(♦)$ (d) $(=>)$ Assume that $f$ is onto. This means there exist ...
46 views

### Proof that $X^C \cap Y^C= \;(X \cup Y)^c$

Proof that if $X \subset S,\; Y\subset S,\;$ then $\;X^C \cap Y^C= \;(X \cup Y)^c:$ It must be shown that the two sets have the same elements, that each element of the set on the left is an element ...
38 views

### Proof over subsets

So I'm currently taking a course for proofs, could you please check my work? Prove if $B \subseteq C$ then $A \cup C^c$ is a subset of $A \cup B^c$. For all $x \in B$, $x$ will be an element of $C$. ...
54 views

### Proving a Bound for Oddtown-Eventown or Clubtown

Suppose we have a town with a set of residents $V$, where $|V| = n$. The residents like forming clubs, and we have clubs $C_1,C_2,\ldots,C_m \subseteq V$. We are interested in the maximum number of ...
40 views

### How do i prove $\omega\times\omega\approx \omega$, **not using prime decomposition nor division**?

Yet there are many ways to prove this, i remember that i saw a proof in a text which proves this without using any decomposition nor division. (I remember the name of the text is "Set theory - ...
18 views

### Are these Cartesian Product equalities true?

Let $A, B, C, D$ be sets. (i): (A x B) $\cup$ (C x D) = (A $\cup$ C) x (B $\cup$ D) (ii): (A x B) $\cap$ (C x D) = (A $\cap$ C) x (B $\cap$ D) I have to prove these later for homework if true, and ...