1
vote
1answer
23 views

Show that if the projection of a set is negligible, then the set is negligible as well

I'd like a hint in the right direction, im drawing a complete blank. let $E \subset \mathbb R^2$. We'll define the projection of $E$ unto the $x$ axis as: $P_x(E)=\{x| \exists y \in \mathbb R s.t ...
-1
votes
1answer
25 views

Symmetric Difference Quesions [on hold]

Let $A$ and $B$ be sets. The symmetric difference of $A$ and $B$ is denoted by $AΔB$. Prove that: (a) $AΔB ⊆ A$ iff $B ⊆ A$ (b) $AΔB ⊆ B$ iff $ A ⊆ B $ (c) If $A$ and $B$ are finite sets, ...
0
votes
1answer
77 views

Show that a particular set is a poset

I would like to know if my understanding of the concept of a poset is correct. From what I've learnt from the class: A poset must be transitive, reflexive, and antisymmetric. Am I right? Therefore, ...
0
votes
2answers
27 views

Cardinality of two sets cross-multiplied

Let $A$ and $B$ be sets. Prove that $ \#(A \times B) = \#(B \times A)$. What I have done: There exist an element $m$ in $A$ such that the element also exists in $B$. If $\#A = \#B$, then $\#B = ...
1
vote
0answers
34 views

Power Set, Bijection Function, Equivalence Relation

Let $S$ be a set and $P(S)$ the power set of $S$. For sets $A,B⊆P(S)$, we say that $A \sim B$ if there exists a bijective function $f: A \rightarrow B$. Show that $\sim $ is an equivalence relation.
1
vote
2answers
53 views

Cardinality, Finite Sets Proof

Let $S$ and $T$ be finite sets. Prove that if $|T-S| = |S-T|$, then $|S| = |T|$.
2
votes
0answers
62 views

Prove $f_\infty: A_\infty \rightarrow B_\infty$ is a bijection

I am using the Cantor-Schroder-Beenstein Theorem to prove $f_\infty: A_\infty \rightarrow B_\infty$ is a bijection. The cases of $f_+: A_+ \rightarrow B_+$ and $f_-: A_- \rightarrow B_-$ being ...
0
votes
1answer
40 views

Basic topology questions with cantor's set

I have 3 questions in toplogy, one of which I managed to solve (but would appreciate input regardless) and 2 which are more difficult. I'd like a push in the right direction. Define $K$ as ternary ...
1
vote
1answer
61 views

What's wrong with my proof?

Let $f:A\to B$ be a function. Let $T_1$ and $T_2$ be subsets of $B$. Show that if $f$ is onto, then $$f^{-1}(T_1)\subset f^{-1}(T_2) \implies T_1\subset T_2$$ I proved it as follows. Let $x\in ...
0
votes
1answer
30 views

Prove that if there exists f: X to a finite set is bijective, then X is finite

I was given that X is finite if any function that maps X to X is surjective and injective. Also, the problem specifies the finite set n as a set with n elements. Now, I only know that there exists ...
0
votes
1answer
45 views

Cardinality of the set of all functions from A to B

Given two sets $A$ and $B$, let $F(A, B)$ denote the set of all functions $f : A → B $ (no assumptions about injectivity or surjectivity – all functions from $A$ to $B$ are included). Let $|S|$ denote ...
2
votes
2answers
78 views

Prove that the cardinality of $\{0,1\}^R$ is not equal to that of $R$

From what I understood $\{0,1\}^R$ is the set of all functions from $\{0,1\}$ to $R$. I would be happy not only for the proof but a good and maybe simplified explanation of the concept of Aleph's and ...
3
votes
1answer
32 views

Union and set notation

I was reading my notes and came across this example... A = {z: z is a number, z is ≤ 20} B = {y: y is an even number} ...
0
votes
1answer
52 views

Can you conclude that A = B if A, B, and C are sets such that…

a. A ∪ C = B ∪ C b. A ∩ C = B ∩ C c. A ∩ C = B ∩ C and A ∪ C = B ∪ C My method of solving this was to convert everything to propositional logic, then to solve it to show that none of the above are ...
-1
votes
1answer
49 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 ...
2
votes
2answers
42 views

Using zorn's lemma to prove aleph 0 is the least infinite cardinal

I understand zorn's lemma, but it is confusing me on how to apply it to an infinite set. I am asked to prove that if A is an infinite set, then there exists an injection from $\mathbb{N}$->A using ...
1
vote
1answer
27 views

explicit choice function without axiom of choice

This is probably quite simple and I am just missing something. I am asked to define a choice function for the collection of all nonempty subsets of $\mathbb{Z}$ without using the axiom of choice. We ...
1
vote
3answers
73 views

Why a unit set is not the same as its element? $\{x\} \ne x$?

I was solving a list of exercises from homework and I answered one question wrong because I thought that a singleton set and its element were the same thing... I found only a few results from a ...
0
votes
0answers
57 views

proving that $f:\mathbb N\to\mathbb N\times\mathbb N$ is countable using Cantor's diagonal method

I need to prove using Cantor's diagonal method that the function $\mathbb N\to\mathbb N\times\mathbb N$ ($\mathbb N$ being all natural numbers) is countable. I have read this question(Does anyone ...
1
vote
2answers
25 views

Counting Venn Diagram problem

"In a survey of 185 university students, 91 were taking a history course, 75 were taking a biology course, and 37 were taking both. How many were taking a course in exactly one of these subjects?" I ...
1
vote
1answer
41 views

What is $\bigcup_{r\in(0,1)}[0,r]$?

Question: for any real number $r$, let $C_r$ be the closed interval $[0,r]$. Let $J$ be the open interval $(0,1)$. what is $\bigcup_{j\in J} C_j$? So far I have attempted a double inclusion proof to ...
1
vote
1answer
40 views

Subtraction of elements from $\mathbb Z$

Let $M_n$ be the set of integers which are integer multiples of $n$. If $\mathbb N = {1,2,3...}$ What would $$ \mathbb Z - \bigcup_{n\in\mathbb N}M_{2n+1} $$ be? I know that $M_{2n+1}$ represents ...
3
votes
2answers
42 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
votes
0answers
65 views

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

(a) If f is onto then g o f is onto. (b) If g is onto then g o f is onto. (c) If f is one-to-one then g o f is one-to-one. (d) If g is one-to-one then g o f is one-to-one This is a question on my ...
1
vote
1answer
32 views

If $cf(\alpha)<cf(\beta)$, how to show that every increasing $h:\alpha \to \beta$ has a range that is bounded in $\beta$?

The problem Let $\alpha$ and $\beta$ be two limit ordinals. Show that $1$. $\implies$ $2$., where $\qquad 1$. $cf( \alpha)$ < $cf(\beta )$ $\qquad 2$. Every increasing $h: \alpha \to \beta $ ...
-1
votes
2answers
36 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
70 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
1answer
31 views

For an $f:\omega_1 \to \omega_1$, how to prove $\alpha = f(\alpha)$ for uncountably many $\alpha$?

My homework question reads: Let $\omega_1$ be the first uncountable ordinal, and let $f:\omega_1 \to \omega_1$ be s.t. If $\alpha < \beta < \omega_1$, then $f(\alpha) < f(\beta)$. ...
3
votes
2answers
53 views

How to show existence and uniqueness of an $f: R(\omega) \to \omega$, where $R(\omega)$ is the cumulative hierarchy?

My questions For part A (see below), is my reasoning correct? Is it enough to just show that $f(x) \in \omega \ \ \forall x \in R(\omega)$? I'm very new to axiomatic set theory, in particular to the ...
0
votes
2answers
30 views

Use of “for all” in definition of reflexive and symmetric relations.

My book says that a relation R on A is reflexive, if $\ (a,a) \in R, \ for\ every \ a \in A$ symmetric, if $\ (a_1,a_2) \in R \implies (a_2,a_1) \in R,\ for\ all\ a_1,a_2 \in A$ Although I ...
-1
votes
4answers
70 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 ...
1
vote
4answers
27 views

How can I prove this relation between the images of these two different sets?

If $f : X \to Y$ is surjective, prove that every $A\subset X$ satisfies $$Y\setminus f(A) \subset f(X\setminus A). $$ Show that the claim is false is $f$ is not surjective. I was able to ...
3
votes
3answers
80 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
0answers
35 views

Recursive seqence of power set, starting with the empty set

Let $A_0$ be the empty set and $A_n := \mathcal{P}(A_{n-1})$ for $n \in \mathbb{N}$. I have to determine $A_n$ and $|A_n|$. Using the definition of the power set I get \begin{align} A_1 & = ...
3
votes
1answer
34 views

Prove that $\bigcup_{n=2}^{\infty} [1/n, 1 - 1/n] = (0, 1)$

This is an exercise for a set theory class. I already managed to prove $\bigcup_{n=2}^{\infty} [\frac{1}{n}, 1 - \frac{1}{n}] \subseteq (0, 1)$: Let $x \in \bigcup_{n=2}^{\infty} [\frac{1}{n}, 1 - ...
-1
votes
1answer
44 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.
0
votes
1answer
23 views

Bijection between sets of functions

Let $\left ( B \times C \right )^A=\{f \in \mathcal{P} \left ( \left ( B \times C \right) \times A \right) \big | f \hspace{2mm} \text{is a function and} \hspace{2mm} \text{dom}(f)=B \times C \}$ ...
0
votes
0answers
27 views

How to prove this equation of composition of binary relations?

We have three binary relations $R,S,T$ all from $A$ to $A$. Prove $(R∘S)\cap T=\emptyset$ iff $(R^{-1}∘T)\cap S=\emptyset$ iff $(T∘S^{-1})\cap R=\emptyset$ I don't quite see what's $(R∘S)^{c}$ is ...
1
vote
0answers
28 views

Binary relation R is symmetric and transitive iff?

This is a homework question and I am stuck. Binary relation R is transitive and symmetric if and only if $R=R^{-1}∘R$ The "only if" way is trivial. On the "if" way, I worked out that given ...
0
votes
1answer
57 views

Let $H=\{2^m: m ∈ Z\}$ Where $m$ is any integer, and $ a\sim b\Leftrightarrow a/b $ is an element of $H$.

Show that is an equivalence relation and describe the elements in the equivalence class $\operatorname{cl}(3)$. We're studying sets and equivalence in my mathematical proofs class. As this is a ...
2
votes
1answer
39 views

Domain when dividing two functions

Let's say we have two function $f(x) = \sqrt{x-3}$ and $g(x) = \sqrt{16-x^2}$, when finding the domain of $\frac{f}{g}$ do you find the domain of $\frac{\sqrt{3-x}}{\sqrt{16-x^2}}$ so that $x$ is an ...
0
votes
1answer
42 views

Let H be a (non-empty) subset of integers. Suppose a-b <=> a~b ∈ H is an equivalence relation.

Show that $0 \in H$. Show that if $a \in H$ then $-a \in H$, and lastly, if $a$ and $b \in H$ then $a + b ∈ H$. Last bonus question on our last unit test on sets, equivalence relations and proofs. I ...
0
votes
1answer
69 views

If $X = \{1, 2, 3, 4\}$ show there are just two equivalence relations on $X$ with $1\sim 2$ and $2 \sim3$

If $X = \{1, 2, 3, 4\}$ and $\sim$ is an equivalence relation on $X$, then if $1 \sim 2$ and $2 \sim 3$ show that there are just two possibilities for the relation $\sim$ and describe both ...
1
vote
1answer
31 views

What is the inverse of this two-case function?

Given the function $f: \mathbb{Z} \to \mathbb{Z}$ defined by $$ f(n) = \begin{cases} n+2 \mbox{ if $n$ is even }\\ 2n+1 \mbox{ if $n$ is odd } \end{cases} $$ find the inverse or show that no ...
1
vote
1answer
25 views

Symmetric Binary relations on N equinumerous to 2^N

I am attempting to establish that the set of all symmetric binary relations on N (a set R is symmetric if (a, b) is in R implies (b, a) is in R) is equinumerous to 2^N and am having some difficulty. ...
0
votes
1answer
45 views

Show that the set is a singleton

Let $f$ be convex, differential function. Consider the set $$X=\left\{x\in \underset{x}{\text{argmin}} f(x):\; \|x\|\leq \|y\|,\;\forall y\in \underset{x}{\text{argmin}} f(x)\right\}$$ Prove that this ...
0
votes
0answers
43 views

Prove that a given set satisfies a condition.

A subset $W $ of $R$ is called a ring if it contains $1$, and for all $ a,b \in W $, $ a - b $ and $ab$ are also in $W$. Let: $$ S = \left\{\frac{m}{2^n} \;\middle\vert\; m,n \in I\right\} ...
1
vote
2answers
65 views

What is the inclusion-exclusion principle for 4 sets?

Proofs class homework question - It doesn't ask for us to prove, derive, or even illustrate the inclusion/exclusion principle - Just to jot it down. We're learning about sets and ...
0
votes
2answers
31 views

Show that if S=a+b√2 : a,b are rational numbers and T=r+s√3 :r,s are rational numbers, then$S \cap T$ = rational

Someone please correct a formatting error in the problem [still a newbie] ; "S&T" (And = upside down U) Here's a bonus question that was on a test we received that I couldn't figure out. I'd ...
-3
votes
1answer
53 views

Find the number of integers between 1 and 100 that are divisible by exactly one of 3 and 4. [closed]

Homework question similar to my previous question but a little more specific. The last one I could follow with the hints but this one seems tougher, proofs class. Our current unit is sets, ...