3
votes
2answers
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? ...
0
votes
3answers
27 views

Help to prove $(A \times B)\cup (C \times D) \subseteq (A\cup C) \times (B\cup D)$

Prove $(A \times B)\cup (C \times D) \subseteq (A\cup C) \times (B\cup D)$ My attempt: $\begin{align} (x,y) \in (A \times B) \cup (C \times D) & \Rightarrow & (x,y) \in (A \times B) \vee ...
0
votes
2answers
59 views

Proof by contradiction for a set question

I have a statement I need to prove by contradiction: If A and B are sets then A intersect (B-A) = {} (empty set). None of the questions I've ever done for this class are like this so im not really ...
1
vote
2answers
18 views

Solution verfication and two small cardinality questions

I'm studying to my final exam due to tomorrow, and I encountered several small problems. Determine the cardinality of the following sets: 1). $A$ is the set of all injective functions from ...
0
votes
0answers
39 views

How do we prove that, if $\mathcal{P}(A) \sim \mathcal{P}(B)$, then $A \sim B$? [duplicate]

The converse--if $\ A \sim B$ then $ \mathcal{P}(A) \sim \mathcal{P}(B)$--is very easy to prove. I can't see an immediate, simple proof for the converse case. It seems like a potentially good strategy ...
2
votes
1answer
33 views

Set difference between power sets

Show that if $A$ and $B$ are sets then $\varnothing \notin \mathcal P(A) − \mathcal P(B)$ . My Attempt: If $A$ and $B$ are sets, then $ \varnothing \subseteq A $ since the empty set is subset of ...
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 ...
0
votes
4answers
146 views

Singleton sets are a subset

I am tasked with prove the following elementary result. I am concerned about being rigours enough in my proof: $$a\in S \iff \{a\} \subseteq S $$ My Attempt: Suppose $\{a\} \subseteq S $ . Then ...
2
votes
0answers
31 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
2answers
45 views

Suppose $F$ and $G$ are families of sets.

Suppose $F$ and $G$ are families of sets. Prove that $\bigcup F$ and $\bigcup G$ and are disjoint iff for all $A∈F$ and $B∈G$ , $A$ and $B$ are disjoint. It has been suggested to use contrapositive ...
2
votes
1answer
54 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) ...
2
votes
1answer
76 views

A proof in naive set theory.

I am trying to use naive set theory to figure out a proof of the following statement: $$(x = u \land y = v) \to 〈x, y〉 = 〈u, v〉$$. What propositions should i use to prove this?
0
votes
2answers
28 views

Let A, B and C be sets. Prove that $A \cap (B-C) = (A \cap B) - (A \cap C)$

Someone please edit so the & symbol is the intersect (reverse of U). This is a recent question on proofs homework. From what I understand, intersect and minus symbols used in equations for sets ...
-1
votes
1answer
44 views

Countability of Different Sets [duplicate]

(a) Prove that $N \times N$ is a countable set (b) Let T be the set of two element subsets of N. Prove that T is countable. This is a question in my exam review package. I missed the lesson on ...
1
vote
2answers
26 views

Bijection and it's inverse

Given $f: X \to Y$ such that $f$ is a bijection prove the existence of a $g:Y\to X$ such that: $f \circ g = 1_Y $ and $g \circ f = 1_X $ Now since $f$ is bijective $\forall y \in Y: \exists!x ...
1
vote
4answers
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 ...
1
vote
3answers
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 ...
1
vote
3answers
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 ...
4
votes
2answers
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 ...
0
votes
3answers
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 ...
0
votes
1answer
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 ...
0
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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= ...
1
vote
2answers
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 ...
1
vote
2answers
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)$. ...
0
votes
1answer
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 ...
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 ...
0
votes
2answers
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 ...
2
votes
5answers
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 ...
1
vote
2answers
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 ...
0
votes
3answers
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 ...
1
vote
2answers
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$. ...
1
vote
1answer
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 ...
0
votes
1answer
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 - ...
0
votes
1answer
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 ...
0
votes
1answer
51 views

Let $X \neq \emptyset$, define the relation$A\sim B$ if there exists a bijection $f : A \to B$, Show that $\sim$ is an equivalence relation on $X$.

A question on my last proofs midterm, I know I must prove injectivity and surjectivity, but there aren't really any obvious conditions or descriptions on S that helped me to manipulate it to try and ...
0
votes
2answers
17 views

$A^c$ and $B^c$ are independent

I am trying to prove that, $A^c$ and $B^c$ are independent. My approach: $P(A^c \cap B^c)=P(A \cap B) - P(A \cap B)=P(A \cap B) \times (1-P(A \cap B) = P(A)P(B) \times ...
3
votes
2answers
52 views

Proof that a given projection map restricted to a subset is closed.

$\pi_{1}:\mathbb{R}^2\rightarrow\mathbb{R}, (x,y)\mapsto x$ is a projection map from $\mathbb{R}^2$ with the standard eulcidean topology, $\mathscr{T}_E$ to $\mathbb{R}$ with it's usual euclidean ...
1
vote
0answers
115 views

For the non-empty sets A, B and C, let $f : A \to B$ and $\,g : B \to C$. Prove or disprove the following statements:

(a) If $f$ is onto then $g\circ f$ is onto. (b) If $g$ is onto then $g\circ f$ is onto. (c) If $f$ is one-to-one then $g\circ f$is one-to-one. (d) If $g$ is one-to-one then ...
0
votes
2answers
48 views

Consider the function h where $h(x,y) = (x+y,x-y)$, $h : \mathbb N\times \mathbb N\to \mathbb N\times\mathbb N$ [duplicate]

Is the function h onto and one to one? Prove this. Online bonus question on a recent proofs quiz on the topic of one-to-one and onto functions. Gave me a bit of grief (the mapping stuff). Also ...
1
vote
3answers
86 views

Let X and Y be finite non empty sets such that $|X| = |Y|$. Show that a function $f : X \to Y$ is onto if it is one to one.

Hello this is a recent question posted on my course website for bonus marks. I am not exactly an expert at proving bijection (our current topic of study) and the definitions of onto and one-to-one are ...
0
votes
4answers
73 views

Let $g : \Bbb N \times \Bbb N \to\Bbb N \times \Bbb N$ defined as $g(m,n) = (m + n,m - n)$

Determine if $g$ is injective; surjective; bijective. Question on a recent test regarding one-to-one and onto functions. Was very difficult for me, could not even begin to answer either. This is ...
0
votes
1answer
17 views

Diagonal Relation as a poset I - establishing the result by vacous truth

I have a problem with the logic behind the fact that, given a nonempty set X, the diagonal relation $D_X := \{ (x,x) : x \in X \}$ is a partial order on $X$. More specifically, my problem is with ...
0
votes
2answers
26 views

Prove that $A \cup C \sim A$ when $C$ is countable and $A$ is infinite.

First of all, if $A$ is countable, the result is true because the union of countable sets is countable. If $A$ is uncountable, and I have no idea how to prove this part. Can it be useful? is there a ...
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 ...
3
votes
2answers
100 views

Let $S$ and $T$ be finite non-empty sets such that $|S| = |T|$. Show that the function $f : S\to T$ is onto if and only if it is one-to-one.

This is a recent homework bonus question assigned in my Proofs and Conjectures class. It (evidently) includes and evaluates our understanding of elementary-set theory and how to determine and prove ...
0
votes
3answers
91 views

Proofs Homework Help

I have been struggling with my proofs homework this week and would greatly appreciate any help. Prove, disprove, or give a counterexample: Suppose $f:X\to Y$, $A\subseteq Y$, $B\subseteq Y$ and ...
0
votes
1answer
59 views

Prove or Disprove the following statement. For any sets $A$, $ B$, and $C$, we have $A \cup (B \& C) = (A\cup B) \cup (A\&C)$

Trying to figure this question out in my proofs class (tried venn-diagram the multiple set-notation signs are confusing me). Homework question in the fundamental sets unit.