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

0
votes
1answer
19 views

Does (f(0)=g(0) or f(1)=g(1)) define a transitive relation on function?

I need is to check if a relation is an equivalence or not. I can see that it is reflexive and symmetric but I'm not able to find out if it is transitive. The relation is defined on the set of all ...
0
votes
1answer
34 views

Are any two uncountable sets similar to each other?

Two sets $A$ and $B$ are called similar $\iff$ thee exists a one to one function $F$ whose domain is the set $A$ and whose range is the set $B$. We know that two countably infinite sets should be ...
2
votes
2answers
27 views

Proving sets implication using the method of contradiction

Suppose S and T are sets. Consider the following implication: If $A∩B=∅$ and $A ∪B = B$, then $A = ∅$. Prove the given implication by contradiction. So I have started by coming up with the negation: ...
0
votes
1answer
32 views

The number of $p$-subsets of an $n$-set is $n$ choose $p$

I want to show that the number of subsets of cardinality $p$ of a set $E$ of cardinality $n$ is ${n \choose p}$. I've read a proof that I couldn't understand it basically says that for any injection ...
2
votes
2answers
62 views

A standard Operations on sets.

I am trying to show the following property of sets: $$ A \cap ( \bigcup A_{\alpha} ) = \bigcup (A \cap A_{\alpha}) $$ My attempt: Let $x \in A \cap ( \bigcup A_{\alpha} )$. This occurs iff $x \in ...
0
votes
1answer
30 views

Maximum and Minimum in Set Theory

In a group of 100 students, each student has to opt for one or more of the three subjects among Physics, Chemistry and Mathematics. The number of students who opted for Mathematics is more than the ...
0
votes
1answer
25 views

Could someone explain this conditional probability problem?

This is an example in my textbook but I do not understand it. A news magazine publishes three columns entitled “Art” ($A$), “Books” ($B$), and “Cinema” ($C$). Reading habits of a randomly selected ...
1
vote
2answers
23 views

Cardinality of a line and a half plane

intuitively it seems like the cardinality of the set of points that make up a line should be different than the cardinality of the set of points that make up a half plane but I couldn't come up with a ...
1
vote
1answer
24 views

Infinite sets: $|a| < |b|$ implies $|c^a| < |c^b|$

If $a,b,c$ are infinite sets, is it true that $|a| < |b|$ implies $|c^a| < |c^b|$? Obviously $|a| < |b|$ implies $|c^a| \leq |c^b|$, but I want to show $c^a$ does not biject with $c^b$...
0
votes
1answer
23 views

proof of set operation discrete math

if $$a=\{3n \mid n \in \mathbb{Z}^+\}$$ and $$b=\{3^{2m}\mid m \in \mathbb{Z}^+\},$$ prove that $b$ is a subset of $a$. I think the question is wrong. I think $a$ should be a subset of $b$.
0
votes
1answer
46 views

Infinite Set confusion

Given an infinite set $A$, I want to show that there exists some subset $B$ of $A$ such that $|A| = |B|$. This is the definition of an infinite set. I can create examples of this, but I am confused ...
0
votes
1answer
64 views

F be the smallest subfield of the real numbers which contains irrational a. Prove that F is countable.

Let a be an irrational number and let F be the smallest subfield of the real numbers which contains a. Prove that F is countable.
0
votes
3answers
57 views

A is an infinite set and $S$ is a countable subset of $A$. $B$ is another countable set, then prove that $A \cup B$ is bijective with $A$

A is an infinite set and $S$ is a countable subset of $A$. $B$ is another countable set, then prove that $A \cup B$ is bijective with $A$ I have started like this: Since $S$ is countable, $B ...
1
vote
2answers
45 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
33 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
51 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
44 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
30 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
40 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
34 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 ...
0
votes
3answers
42 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
49 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
16 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
41 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
61 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
25 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
37 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
26 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?
-2
votes
1answer
45 views

Cardinality of irrationals [closed]

What I have done: Since cardinality of R=c and and cardinality of N is = N0(aleph naught) and R=Q+I (I represents set of irrationals.) So, cardinality (R)=cardinality(Q)+cardinality(I) which implies, ...
1
vote
1answer
27 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
15 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
39 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
26 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
18 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
51 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
54 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
31 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
82 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
65 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
37 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
21 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
73 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
38 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.