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
1answer
27 views

Uncountably infinite set between 1-2 and 1-10?

Just a quick question: Is the size of the set of real numbers from 1 to 2 greater, or equal in size to the number of real numbers between 1 and 10? I'm a Physicist so I'm not totally clued up on ...
0
votes
1answer
32 views

Is the relation on integers, defined by $(a,b)\in R\iff a=5q+b$, a function? [on hold]

Let $A=B=\mathbb N$. Relation $R$ is: $(a,b)\in R$ iff for some $q \in \mathbb Z$ we have $a=5q+b$ Given a relation, show that it's a function. To Show: $\forall a \in A \ \exists b \in B$ such ...
4
votes
3answers
33 views

Subsets of $\{1,2,3,4,5,6,7,8\}$ with at least 1 odd and 1 even number

How can I formally write the number of subsets of $S=\{1,2,3,4,5,6,7,8\}$ with at least 1 odd and 1 even number? I know if I take the subset with even numbers, $E =\{2,4,6,8\}$, there are $2^4-1$ ...
1
vote
0answers
12 views

Inner Measure: Measurability

Reference This problem grew out from: Inner Measure vs. Outer Measure Setting Given a plain space $\Omega$ and a possibly empty semiring $\mathcal{S}$. Consider a premeasure ...
0
votes
1answer
21 views

Image, preimage and set operation in mappings

Not the best title but I don't know how to better describe it. So the image of a set is usually written as $f(B)$, my question is, can I use sets in the place of variables in the expression of my ...
0
votes
1answer
15 views

find image and inverse image of function

I have function $f:R\to R^2 , \ \ f(x)=<\cos 3x, \sin 3x>$ and I have to find image on the interval $(0, \pi]$ and inverse image $[0, +\infty) \times[0, +\infty)$ I think the image will be ...
0
votes
0answers
22 views

Finding a equinumerous set.

Let $A$ and $B$ any sets. How can I show that there are $A^{'} \approx A$ and $B^{'} \approx B$ such that $A^{'}\cap B^{'}=\emptyset$? ($X \approx Y \Leftrightarrow$ $X$ and $Y$ are equinumerous) ...
0
votes
5answers
56 views

Composition of two functions is not commutative

I have been always shown that the composition of two functions is, in general, not commutative with a counterexample. But can you give a more general proof of this statement (that is to say, one that ...
5
votes
0answers
41 views

Is there a linear order with this property

I was trying and failing to construct a linear order L each of whose uncountable subsets contains an uncountable well ordered subset but L is not a countable union of well ordered subsets. Is this ...
-1
votes
2answers
39 views

Basic set theory proof [on hold]

How to prove $(A \times B = B \times A) \Leftrightarrow (A = \varnothing \ or \ B = \varnothing \ or \ B = A)$ ? I'm not sure about my solution.
2
votes
1answer
25 views

Find a bijection, check if a given set is a function

I have problems with two exercises: $1)$ Find a bijection between $A$ and $B$. $$A=[0,1) \times[0,1)$$ $$B=\{{<x,y>}\in \mathbb R^2: x,y>0,\ x+y<1\}$$ $2)$ Decide if the given set is a ...
1
vote
1answer
22 views

Premeasures: Inner Measure vs. Outer Measure

Problem Given a plain space $\Omega$ and a ring $\mathcal{R}$. (In fact, a semiring would do the job, too.) Consider a premeasure $\mu:\mathcal{R}\to\overline{\mathbb{R}}_+$. For simplicity, ...
2
votes
1answer
25 views

$\langle \mathfrak{c},\mathfrak{c}\rangle$-Independent Matrix

Given cardinals $\lambda,\kappa$, an $\langle \lambda,\kappa\rangle$-independent matrix on $X$ is a colection $\mathcal{A} = \{A_{\alpha}^{\beta}:\alpha<\lambda\wedge \beta<\kappa\}$ sattisfying ...
0
votes
2answers
50 views

“Subset of above not equal to” $ \subsetneqq $ Symbol

I was reviewing my Algebra diary, and I noticed a symbol that I was not familiar to: $ \subsetneqq $. After some reseach on the internet I eventualy found it (through UNICODE), and found that the ...
1
vote
4answers
34 views

Select one or zero elements from a set

I am far from a mathematician. Still. I want to formally express that only 0 or 1 element of a series of sets (1...n) is selectet to form a new set. Example: I have three sets $S_1 = \{1,2,3\}$, $S_2 ...
0
votes
2answers
50 views

An isomorphic map from natural numbers to positive rational numbers that preserves addition, multiplication and order

Since $\mathbb{Q}^{+}$ is countable, there is a bijection between $\mathbb{Q}^{+}$ and $\mathbb{N}$ (0 included). Then the question now is, can we go further by constructing an isomorphic map between ...
2
votes
1answer
29 views

Very basic question about set theory: unions and intersection

Let $\{ E_n \}_{n=1}^{\infty} $be a collection of countable sets and let $$ F_k = E_k \setminus ( \bigcup_{j=1}^{k-1} E_j ) $$ Then $F_k$ are pairwise disjoint and $\bigcup^{\infty} F_k = ...
0
votes
1answer
16 views

number of antisymmetric and not irreflexive relations

What is the number of relations on a n element set that are antisymmetric and not irreflexive? I have tried doing this as fallows- no of antisymmetric relations having atleast one self pair[like ...
0
votes
1answer
30 views

What is $r^n$ where $r \subseteq P(\Bbb{N} \times \Bbb{N})$ and $n$ is natural number?

I've got a set theory problem in which I examine the following function: $$\rho : P(\Bbb{N} \times \Bbb{N}) \rightarrow P(\Bbb{N} \times \Bbb{N})$$ $$\rho(r) = \bigcup\{ r^{2^n}|n\in\Bbb{N}\}$$ ...
1
vote
2answers
27 views

How to specify each digit of a real number in decimal representation in set theory?

So real numbers have decimal representations. If you want to say the $n$th digit of some real number, how do you say this formally in set theory?
1
vote
2answers
18 views

Find the image of $A=(-2,1) \times [-2,2)$ under the function $f(x,y)=x^2y$

I have function $f(x,y)=x^2y$ and I have to find image $f[A]$ where $A=(-2,1) \times [-2,2)$ we have that $-2 < x < 1$ and $-2\le y<2$ $0 \le x^2 < 4 $ I claim that the image of ...
1
vote
1answer
26 views

Prove $B−C \subseteq A'$ implies $A \cap B \subseteq C$

Prove that if $B−C \subseteq A'$ then $A \cap B \subseteq C$. Is it perfectly reasonable to show that $A \cap B \not\subset C$, (assuming $B−C \subseteq A'$ holds) leads to a contradiction ? ...
0
votes
1answer
32 views

Number of relations on a set

What is the number of relations on a $n$ element set that are antisymmetric and not symmetric? I have soved this question using the fact that 'antisymmetric and not symmetric' means asymmetric... ...
0
votes
1answer
26 views

Algebra with set notation and set properties

Suppose that $S$ and $T$ are sets with $S \cap T = \emptyset$ Let $C \subseteq S \cup T$ and let $A = C \cap S$ and $B = C \cap T$. Show that $A \subseteq S$, and $B \subseteq T$. I said, let ...
0
votes
0answers
35 views

Why does Power Set represented by $2^x$ takes only $0$ or $1$ as values for $x$

While I was studying about Function Spaces I've seen an example of Function Space from function space of Power Set that tells that it(power set) maps from $X$ to $\{0,1\}$. I couldn't get how that ...
2
votes
1answer
38 views

How would you draw $(A\setminus B)\times (A\setminus B) = (A\times A)\setminus (B\times B)$?

I know it's useful to prove set equalities to make a quick sketch of the sets described. How can I draw this one? $$(A\setminus B)\times (A\setminus B) = (A\times A)\setminus (B\times B)$$
0
votes
2answers
33 views

Set theory questions - Subsets from Zorich Mathematical Analysis I

I am doing a text that my big brother gave me: Mathematical Analysis I - Zorich. This stuff is pretty hard for me, since in class we don't do sets. I can see why they are true with pictures, but i ...
2
votes
2answers
37 views

very short and basic question, is $(1,1]$ empty or is it $\{1\}$

Title says it all really. I was asked what is the union and intersection of all the sets $A_n=(1/n,1]$ where $n$ is natural. Right off the bat, $A_1=(1,1]$. is this an empty set? or is it $\{1\}$. I ...
0
votes
0answers
23 views

Help with logical equivalence proof regarding a lemma for equivalence relations.

So the question is this: Suppose A is a set. Let ~ be an equivalence relation on A and let a,b be elements of A. Then Ta = Tb if and only if a ~ b. I need to prove this statement to be true. I know ...
1
vote
1answer
48 views

Are there any sets that cannot be constructed using the symbols $\{$ and $\}$?

It seems to me all sets in mathematics can be constructed via these two symbols only. For instance, the natural numbers are defined as $0 = \varnothing = \{\}, 1 = \{0\}$, $2 = \{0, 1\}, 3 = \{0, 1, ...
1
vote
1answer
22 views

Logic and set theory proof help

Question: Prove the statement below for the sets $A$,$B$, and the universal set $U$. $$A-B=A \cap B^c $$ My attempt: Converting $A-B$ to set notation: $$A-B = \left\{ {x:x \in A, x \notin ...
-2
votes
1answer
32 views

What means $A \subsetneq X$ with A ~ X? [on hold]

How it is possible to have a subset A, which is $\neq$ to X and at the same time they have an equivalence relation ~? When $A \subset X$ therefore a $\in$ A is also a $\in$ X. With A ~ X ...
0
votes
0answers
17 views

How can a function with asymptotes be defined as a mapping?

A mapping takes each element of a set S and associates it with an element t in some other set T. I believe functions to be mappings. Yet we happily call such as $\frac {x^2}{x+1}$ a function, even ...
1
vote
5answers
275 views

How to prove there is no bijection between a set and its second power set?

Let $X$ be a set. How can I show that there is no bijection between $X$ and $P(P(X))$, the powerset of the powerset of $X$. I know that there is no bijection between $X$ an $P(X)$, due to Cantor's ...
5
votes
2answers
179 views

Let : $X \to Y$ be a function. Show that if $f$ is injective then $f(A \cap B) = f(A) \cap f(B)$ for sets $A \subseteq X$ and $B \subseteq X$.

Let : $X \to Y$ be a function. Show that if $f$ is injective then $f(A \cap B) = f(A) \cap f(B)$ for sets $A \subseteq X$ and $B \subseteq X$. My answer : Suppose $f$ is injective and $f(x) \in ...
0
votes
2answers
17 views

Does $A$ is equipollent to $B$ $\implies $ $P(A)$ is equipollent to $P(B)$?

Let $A, B$ be sets and let $P(A)$ and $P(B)$ denote their powersets. Suppose there is a bijection $f: A\to B$. Is there a bijection $g:P(A)\to P(B)$? I feel like it is true, but I have trouble ...
0
votes
1answer
13 views

Is a relation transitieve if and only if $R\circ R \subset R$?

Let $X,Y, Z$ be sets and call $R\subset X\times Y$ a relation from $X$ to $Y$. Let $R$ be a relation from $X$ to $Y$ and S a relation from $Y$ to $Z$. Then composition relation is given by $S\circ ...
0
votes
1answer
32 views

Counting sets and adding an element

Let $A$ be a set with $n$ elements, where $n \in \mathbb{\omega}$. Suppose $s \notin A$, prove that $A \cup \{s\}$ has $n+1$ elements. Here is what I have done so far: By induction, let $P(n):$ if ...
1
vote
3answers
45 views

How to prove $h\circ f$ injective implies $h$ is injective

Let $X, Y, Z$ be set and $f\colon X\to Y$ and $h\colon Y\to Z$. Suppose $h\circ f$ is injective. How can I prove that $h$ is injective? I have been able to show that $f$ is injective, but I dont know ...
6
votes
0answers
84 views

Is there really anything wrong with Bourbaki's Set Theory?

Recently I have started reading Bourbaki's Theory of Sets on my own. Regarding one of the explanations of a concept when I went to a Professor of our college, he asked me why I was wasting my time ...
0
votes
1answer
18 views

inductively defined group statements

If A is a set, and $B_{1}, B_{2}\subseteq A$ subsets of $A$. Also, $f_{1}:A\rightarrow A$ and $f_{2}:A\rightarrow A$ we will mark: $F1={f1} , F2={f2}$ How do I prove the following: $X_{B1\cap ...
0
votes
1answer
37 views

If $B \subset A$ why is $B \in\mathscr P(A)$?

Can someone explain why it is true that $B \in\mathscr P(A)$ when $B \subset A$ It should be simple for some but I can't wrap my head around it for some reason. Thanks!
19
votes
10answers
3k views

Defeating Russell's paradox

I am not very big in mathematics yet(will be hopefully), naive set theory has a problem with Russell's paradox, how do they defeat this sort of problem in mathematics? Is there a greater form of set ...
-1
votes
1answer
26 views

Prove $|A| \le|C|$ for injection and surjective functions

$A$, $B$ and $C$ are finite sets with $F: A \to B$ a surjection and $G: B \to C$ an injection. Prove $|A| \le |C|$ I could prove it using examples, but not sure how to generally.
3
votes
2answers
41 views
+50

Is there a specific name for this set of square-rooted primes?

Consider the set of all the primes numbers (± square rooted) and all the irrational numbers that can be formed under their addition (only the addition of finitely many elements is allowed, i.e. no ...
1
vote
1answer
39 views

What is this symbol used for?

I have seen the symbol $\subsetneqq$ in a Probability exercise. What is it used for? In the exercise it seemed to mean "proper subset of", but then in what is it different from $\subsetneq$?
0
votes
2answers
36 views

Let $A$ and $B$ be countable sets. Is there any function $f$ such that a certain condition holds for an uncountable number of functions $g$?

Let $A$ and $B$ be countable sets. Is there any function $f:A\to B$ such that there exists uncountably many functions $g:B\to A$ such that $g\circ f=\operatorname{id}$ but $f\circ ...
1
vote
1answer
15 views

Show that $S= \{p:\exists x,y (p=\langle x,y\rangle) \wedge (x \subset y )\}$ is a proper class.

Show that $S= \{p:\exists x,y (p=\langle x,y\rangle) \wedge (x \subset y )\}$ is a proper class. I believe that $x \subset y$ implies $\{\{x \},\{x,y \} \} = \{\{x \} , \{y \} \} =\{\{y \} \} $ ...
5
votes
2answers
109 views

Prisoners Problem

We have an infinite number of prisoners enumerated $\{1, 2, \dots\}$, and on each prisoner there is a hat of either blue or red color. The $n$th prisoner sees the hats of prisoners $\{n+1, n+2, ...
2
votes
1answer
43 views

Show that, using the axiom of choice, that the cardinality of the sets of all countable subsets of $\mathbb{R}$ have cardinality $2^{\aleph_0}$

Show that, using the axiom of choice, that the cardinality of the sets of all countable subsets of $\mathbb{R}$ have cardinality $2^{\aleph_0}$ and show where it was used the axiom of choice. ...