# Tagged Questions

23 views

### Math challenge(Infinite sets): Bottles of Beer

Imagine a counter with stools that stretch across the room(infinite). All the stools are occupied. Two drunks come in and want to squeeze in to sit down. Drunk #1 walks in and tells the person on the ...
25 views

### Having trouble showing the cardinality of two infinite sets is the same

We just learned about Aleph-naught today and I read about it on wikipedia but I do not know how to go about solving this problem in my homework: Prove that N(natural numbers) has the same ...
24 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 ...
50 views

### Proving that these two sets are denumerable.

(a) $S_k=\{A\subset\mathbb{N}: |A|=k\}$ for $k\in\mathbb{N}$ (b) $S = \bigcup_{k=1}^\infty S_k$ Work: For (a), I am not too sure about what approach I should use. I think finding a bijective ...
27 views

### Prove a statement for the infinite matrix

We are given infinite two dimensional matrix $\{a_{i,j}\}_{i,j=1}^\infty$. And we know that matrix contain only natural values and each number appears in the matrix exactly 8 times. Task is to prove ...
28 views

### Prove that for every 2 elements in the set F of all functions from N to N, there's an element in F that's bigger than both

let there be $\ F$ the set of all functions from $\ N \rightarrow N$. K is a relation on F, for every f,g$\in$F , (f,g)$\in$K $\leftrightarrow$ for all $\ n\in N$, $\ f(n)\leq g(n)$ Prove that for ...
50 views

### Proving a relation is transitive

I am trying to understand transitive relations. I understand given that a set may have $\{(a,b)(b,c)\}$ it must contain $(a,c)$ for it to be transitive. But for longer sets I am getting confused in ...
49 views

46 views

### Symmetric Difference Quesions [closed]

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, ...
125 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, ...
37 views

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 ...
46 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 ...
80 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 ...
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} ...
53 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 ...
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 ...
43 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 ...
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 ...
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 ...
58 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 ...
26 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 ...
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 ...
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 ...
46 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 ...
76 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 ...
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$ ...
38 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 ...
72 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 ...
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)$. ...
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 ...
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 ...
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 ...
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 ...
84 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 ...
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 & = ...