This tag is for elementary questions on set theory - the sort of material covered in "Chapter 0" of graduate texts and in undergraduate set theory texts. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, countability and uncountability, power sets, ...

learn more… | top users | synonyms

1
vote
2answers
49 views

How is there a bijection between an infinite set and a proper subset?

I understand that there cannot be a bijection between $S$, a finite set, and $S'$, a proper subset of $S$, because $S'$ will contain at least one fewer item than $S$. What I don't understand is the ...
-1
votes
2answers
37 views

Power set of {a,b,c} & {a,b,c,d}

I am having trouble grasping the simple concept of the Power set, especifically of {a,b,c} let A = {a,b,c} P(A) = {0, {a}, {b}, {c}, {a,b}, {a,c}, {b,c} } I know that the power set includes the ...
0
votes
1answer
52 views

Can we operate on the real numbers in calculus?

For a set theory class, I was reading into the definition and properties of real numbers. Real numbers are Archimedean. That means there are no infinitely large real numbers or infinitesimally small ...
3
votes
1answer
47 views

How can we show that $\sigma(\mathcal G)\times\sigma(\mathcal G)\subset \sigma(\mathcal G \times \mathcal G)$?

As a part of a larger proof, I'm trying to show that if $\mathcal G \subset \mathcal P(\Omega)$ then $$\sigma(\mathcal G)\times\sigma(\mathcal G)\subset \sigma(\mathcal G \times \mathcal G).$$ Since ...
0
votes
1answer
32 views

Let the set S be infinite, and the set T countably infinite. Show that S and S U T have the same cardinality

Let the set S be infinite, and the set T countably infinite. S and T are both subsets of R. Show that S and S U T have the same cardinality. I know we can discuss whether S is countable or ...
0
votes
2answers
43 views

Equality of two expressions describing a filter

Let $U$, $W$ be boolean lattices with order $\sqsupseteq$, and $U \supseteq W$. The top element of $U$ is the same as the top element of $W$. The bottom element of $U$ is the same as the bottom ...
0
votes
3answers
35 views

Cardinality of the union of disjoint sets, each of which have a cardinality of reals

What can be the Cardinality of the union of disjoint sets, each of which have a cardinality of reals? How should this be proved. I know using Schroder bernstein theorem, it is easy to see that the ...
1
vote
3answers
45 views

If $f$ is 1-1, prove that $f(A\setminus B) = f(A)\setminus f(B)$

I'm having a tough time with this one. Here's the background: Let $X$ and $Y$ be sets, let $f:X\rightarrow Y$ and let $A,B\subseteq X$. For this proof, we also assume that $f$ is 1-1. I've already ...
2
votes
3answers
51 views

Does there exist this type of sequence of subsets of $\mathbb{R}$?

Let $A_n$ be a sequence of subsets of $\mathbb{R}$ with the following properties. $A_n$ is unbounded for all $n$ The union of all $A_n$ is $\mathbb{R}$ No two $A_n$ share elements For all $n$, given ...
-1
votes
2answers
18 views

One-to-one correspondence of a set within a set

I need to find a one-to-one correspondence between each of the following pairs of sets: (a) {x, y, {a, b, c}} and {14, -3, t} (b) 2Z and 17Z For problem a, I have no idea if the inner set counts as ...
1
vote
2answers
42 views

An injective map between two sets of the same cardinality is bijective.

Let $E$ and $F$ be finite sets. If $card(E)=card(F)\not = 0$ then an injective map from $E$ to $F$ must be bijective. I'm asking why we single out the case of the cardinalities are different from ...
1
vote
3answers
63 views

Why is $\emptyset$ an element of the power set of a set?

Take a set $S$. Why is the empty set part of the power set of $S$? Intuitively speaking, the power set is the collection of all possible subsets of $S$. How is $\emptyset$ such a subset then? Why is ...
0
votes
1answer
28 views

Prove cardinal arithmetic (exponentiation)

Suppose $|K|=\kappa, |L|=\lambda, |M|=\mu$ and $L \cap M=\emptyset$. Prove that $$(\kappa^{\lambda})^{\mu}=\kappa^{\lambda \cdot \mu}$$ My attempt: Suppose $F : K^{ L \times M} \rightarrow (K^L)^M$. ...
1
vote
1answer
18 views

Number of words with a given number of letters.

Let $A$ be the set of the alphabet, $card(A)=26$. The set of all words with three letters has $26^3$ elements, this is just the cardinality of the cartesian product $A\times A\times A$. Now I want to ...
-3
votes
1answer
43 views

If a set contains all even natural numbers, does that mean it cardinality is half of that of $\mathbb{N}$? [closed]

When we define set S as the set of all even numbers, is it true that the cardinality of S is half of the cardinality of $\mathbb{N}$? I don't really know if this is obvious or not; I'm just curious. ...
-3
votes
1answer
27 views

build a bijection h : R\Q → R [duplicate]

I needed to find cardinality of irrationals. I have provedthat R\Q is uncountable. Now I need to build a bijection h : R\Q → R . How to do this?
1
vote
1answer
28 views

How can I form a bijection between these elements?

I am having trouble getting started with this particular problem. Let $A$ be a nonempty set, and let $\mathcal{B}$ be the set of all functions $f:A\to\{0,1\}$. Show that ...
0
votes
2answers
16 views

A question regarding supremum of bounded sets.

I'm clear with the definition of supremum and bounded sets. But for some reason, this statement in my lecture notes given by my Prof, doesnt seem to make sense. Let $X = [0, 1) ∪ (2, 3]$. In this ...
0
votes
3answers
33 views

Show the range of a fuction is (-2,2)

Please help me to solve "show the range of $$h=\frac{-2k}{\sqrt{1+k^{2}}}$$ is $(-2,2)$", thanks! Limit can not be used here!
3
votes
1answer
40 views

Show that a set is uncountable.

Let $B$ be the set of all sequences cosisting of digits $7$, $8$, and $9$. Show that $B$ is uncountable. Here is my attempt. Assume to the contrary that $B$ is countable. Then there exists a ...
1
vote
1answer
30 views

Is the set of functions from $\mathbb N$ to a subset of $\mathbb N$ (and vice versa) countable?

I have two sets of functions, let's call them $X$ and $Y$. $X$ maps $\mathbb N$ to $\{1,2, \ldots , k\}$ and $Y$ does the reverse. I believe both are unaccountable but am unsure of my answer. My ...
0
votes
1answer
29 views

Proving elements of sets

For the first case of the proof, is that considered to be a valid proof? And, for the second case, I am really stuck and I have no idea what to do. Any hints or tips?
1
vote
2answers
21 views

Proving a set-theoretic identity

Context: Measure theory. Reason: Just curious. Question: Given $\{A_k\}$ with $A_k$ not disjoint, $B_1=A_1$ and $B_n = A_n - \bigcup\limits_{k=1}^{n-1} A_k$ for $n \in \mathbb{N}-\{1\}$ and $k \in ...
0
votes
1answer
38 views

Prove the existence of a point not accounted for by mapping from N to R and deduce uncountability of R from this

Let a: $\mathbb{N}\rightarrow\mathbb{R}$ be given. For $a, b \in \mathbb{R}$ such that $a < b$ show that there is a point $c$ in the closed interval $I = [a, b]$ such that $c \notin \{a(n) | n \in ...
0
votes
1answer
54 views

Mistake in ProofWiki: Injection has Surjective Left Inverse Mapping?

The first line of Proof 1 states, "Since S is non-empty, we can choose an element $x\in S$." Did the author mistakenly leave out the fact that S is non-empty in his/her statement of the theorem? ...
2
votes
1answer
57 views

Can someone give me some clue on how to show that rationals are well ordered? Thank you in advance.

I wanted to show that the set of rationals are well ordered. A small hint would be really appreciated.
0
votes
1answer
35 views

Evaluating the limit of a sequence

I'm working my way through some practice problems (no solutions given) for an upcoming exam, and I came across the following problem: Let $A_n = \{s : 0 < s \le \frac{1}{n}\}$. What is the limit ...
0
votes
0answers
18 views

set of all ordered basis has cardinality c

Let $V=\mathbb{R}^{n}$ be a vector space over field $\mathbb{R}$. An ordered basis is a sequence of vectors $(v_1,v_2,...,v_n)$ which forms a basis for $V$. Let $X$ be set of all ordered basis of $V$. ...
0
votes
3answers
85 views

How is the set of all closed intervals countable?

I am trying to figure out the answer to the problem: Show that the set of all closed intervals $[a,b]$ with $a,b \in \mathbb{Q}$ is countable. Now I know that the interval $[0,1)$ for example is ...
-5
votes
3answers
68 views

Is it correct to conclude $x\notin A \implies x\in\bar{A}$?

Am I allowed to do this: $$ x\notin A \implies x\in\bar{A} $$ ($\bar A$ is the set complement) in the context of this proof?
0
votes
1answer
24 views

Working with sets and its laws

Given: $(A \oplus B) \cup C = (A \cap C) \oplus ( B - C )$ Work with algebra of sets to prove the proposition above is true. In order to give a solution to this problem I've done the process ...
0
votes
4answers
41 views

Why is my reasoning wrong in determining how many functions there are from set A to set B?

I am trying to count how many functions there are from a set $A$ to a set $B$. The answer to this (and many textbook explanations) are readily available and accessible; I am not looking for the ...
1
vote
1answer
23 views

Demorgans Law negation on sets.

Let's say I have the sets $D, S, \text{and}, G$ meaning that a certain group is unrepresented. The intersection of the three set $D \cap S \cap G$ means that all of the groups are unrepresented. After ...
1
vote
2answers
80 views

What is $(x ∈ S) ∧(x∉S) $ mean?

I am just wondering what does $(x ∈ S) ∧ (x ∉ S)$ mean. Anyone can explain it to me? I am in the midst of doing my homework, and I get something like this: $((x∈S)∧(x∉S)) ∨ ((x∈S)∧(x∉T))$. I know ...
0
votes
2answers
42 views

Clarification on a proof of sets

I have to proof the statement. Is this proof valid? I am not sure whether Step #4 is right or not. Any help would be highly appreciated. Thanks! ** Oh my bad, what I mean is: prove if S and T are ...
1
vote
3answers
40 views

How to prove $X\subseteq Z,Y\subseteq Z,Z\setminus X\subseteq Y$ implies $ Z\subseteq X\cup Y$

I have no idea to prove $$ X\subseteq Z,Y\subseteq Z,Z\setminus X\subseteq Y\text{, then } Z\subseteq X\cup Y $$ Can anyone help me? Thanks.
1
vote
1answer
35 views

Set Theory notation verification

In set theory, the notation $$\bigcup X$$ means the union of all elements of $X$. For example, $\bigcup\{ a,b \}=a \cup b$. I encounter the following notation $$\bigcup X \subseteq X$$ in the book ...
0
votes
2answers
101 views

Applications of infinite cardinalities in real analysis

What are some topics in real analysis that make use of infinite cardinalities larger than that of the real numbers themselves, preferably [edit: but not necessarily] topics that are widely applied in ...
1
vote
3answers
47 views

A proof that if $S \cap T = S$, then $S \subseteq T$

I have to prove the following: If $S \cap T = S$, then $S \subseteq T$. I have no idea where to start. Here's what I have done so far: Suppose $S$ and $T$ are two sets and assume the fact that ...
-4
votes
4answers
73 views

Is ∅ equivalent to {∅}?

Is ∅ equivalent to {∅}? I think they are, but I am not sure? If anyone could clarify, that would be great. Thank you!
1
vote
1answer
40 views

Proof of the uncountability of reals using the diagonal argument—problem?

Consider a common proof of the uncountability of $(0,1]$, as presented here for example: We assume that the reals can be arranged in a sequence $x_k$, represent every number in $x_k$ by its ...
1
vote
2answers
34 views

Proving a bijection(injection and surjection) over a function

I need some help proving bijections: Suppose f is a function from $$ \mathbb R^2 \rightarrow \mathbb R^2$$ Defined by $$f(x,y) = (ax-by,bx+ay)$$ Where a,b are numbers with $$ a^2 + b^2 \neq 0 $$ ...
0
votes
1answer
35 views

Sets Theory Disproof

I have to disprove the statement: For all sets $S$, if $S$ is a subset of the Natural Numbers, then there must exists some $t ∈ S$ such that $|t|\ge1$ Any hints?
0
votes
1answer
53 views

At Most Countable Sets: Finite vs Countable

Quick question: I understand that finite sets are equivalent to $J_n$ for some n $\in$ N, and that countable sets are equivalent to N. Also, either of these is true if and only if an injective map f ...
0
votes
1answer
37 views

Find a 1-1 function mapping the interval (0,1) to the set of rational numbers

Written another way, $f : (0,1) \to \mathbb{R}$ where $f$ is a bijection. I can't think of a function capable of this. If I just map the input to the same output value the function will never reach ...
2
votes
3answers
52 views

Does the set given by $\{(1/n)\}_{n=1}^\infty$ include $0$?

Is there some sort of consensus on whether or not $$0 \in \{(1/n)\}_{n=1}^\infty?$$
-1
votes
1answer
39 views

How do I create an injection here? [duplicate]

I am trying to show that $|\Bbb {R} \times \Bbb {R}| \leq |\Bbb {R}|$. I don't know how to define $f:\Bbb {R} \times\Bbb {R} \rightarrow \Bbb {R}$ in a way that would make $f$ injective. My ...
-1
votes
1answer
37 views

Let F be a partition of A. Prove there exists unique equivalence relation R such that F=A|R?

Let F be a partition of A. Prove there exists unique equivalence relation R such that F=A|R? I don't even know how to start. I know to be a equivalence relation R must be reflexive, symmetric and ...
0
votes
0answers
19 views

Order on the set of partitions (terminology)

Let $S$ and $T$ be partitions of some set $U$. What is the name for the partition $\{ X\cap Y \mid X\in S, Y\in T, X\cap Y\ne\emptyset \}$? Should it be called the infimum of $S$ and $T$? meet of ...
1
vote
2answers
38 views

If there is a mapping of $B$ onto $A$, then $2^{|A|} \leq 2^{|B|}$

If there is a mapping of $B$ onto $A$, then $2^{|A|} \leq 2^{|B|}$. [Hint: Given $g$ mapping $B$ onto $A$, let $f(X)=g^{-1}(X)$ for all $X \subseteq A$] I follow the hint and obtain the function $f$. ...