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
36 views

Confused about images, reverse images.

I am confused over a seemingly simple practice question which I will post below. I am confused over the concept as well, but this question just helps to show what it is I am not understanding. ...
1
vote
1answer
54 views

Showing $ (R ∪ R^{-1})^∗ = R^∗ ∪ R^{−1∗} $ is false by giving a counterexample.

Show that $$ (R ∪ R^{-1})^∗ = R^∗ ∪ R^{−1∗} $$ is false by giving a counterexample. I tried the following, but every time it keeps coming out as true (instead of false): If $R = \{(a,b), ...
4
votes
3answers
54 views

Show that $A \subseteq B \iff A \subseteq B-(B-A)$

Can someone please verify this? Show that $A \subseteq B \iff A \subseteq B-(B-A)$ $(\Rightarrow)$ Let $x \in A$. Then, $x \notin B-A$. Also, $x \in B$. Therefore, $x \in B-(B-A)$ So, $A ...
3
votes
1answer
49 views

$A \setminus B \cup C = A \setminus (B \cup C)$? [duplicate]

$A \setminus B \cup C$ or $A \setminus (B \cup C)$? Sorry as this is a very soft question, but I couldn't find the answer anywhere. Are these two things generally considered the same?
1
vote
0answers
94 views

Inequality with size of sets

Let $ k$ be an integer, $ k \geq 2$, and let $ p_{1},\ p_{2},\ \ldots,\ p_{k}$ be positive reals with $ p_{1}+p_2+\cdots+p_k= 1$. Suppose we have a collection $ \left(A_{1,1},\ A_{1,2},\ \ldots,\ ...
2
votes
2answers
199 views

The union of well-ordered sets is a well-ordered set

In Halmos's Naive Set Theory about well-ordering set, it states that if a collecton $\mathbb{C}$ of well-ordered set is a chain w.r.t continuation, then the union of these sets is a well-ordered set. ...
1
vote
1answer
41 views

Axiom of extension

I am learning Set Theory from the book Naive Set Theory by Halmos as part of my course. The first chapter is on the Axiom of Extension. I understand what it is but what I don't understand is why it ...
0
votes
2answers
47 views

Converting a set to a tuple?

Okay, so, let's say I have a set: $\{0,1,2,3\}$ And I want to convert it to a tuple: $(0,1,2,3)$ How would I do this? Would it be as simple as: $f(\{0,1,2,3\}) = (0,1,2,3)$ ??
1
vote
2answers
33 views

Proving Two sets have same cardinality

I'm studying on my own over the summer and I'm having a bit of trouble with this question. Also, I don't have any background in this, I haven't taken any classes in this yet so, if you choose to help, ...
-2
votes
0answers
27 views

Question of set theory [duplicate]

Suppose That A is a set that at least have 2 element prove that exist a function form A to A that f is 1-1 and onto that for any x is an element of A,f(x) is not equal with x.
0
votes
2answers
30 views

Showing that $A \cap X = A$ for all $A$ if and only if $X = S$.

I have the following task: Let $S$ be a nonempty set. All capital letters will denote subsets of $S$. Show that $A \cap X = A$ for all $A$ if and only if $X = S$. This does not seem to true. ...
-1
votes
2answers
35 views

What is a preimage of domain's subset? [closed]

Let f: A->B be a function. Now let D be subset of A. What is a preimage of D? Is it empty set? There is no typo. The actual question has D as subset of A and E as subset of B. Then you need to ...
0
votes
2answers
82 views

Russell's paradox with bounded comprehension

Consider the set $S = \{A, \varnothing\}$ and define $A = \{x \in S|x \not\in x\}$; this is the same as Russell's paradox except with bounded comprehension, ie $A\in A\iff A\not\in A$. I think the ...
2
votes
2answers
36 views

The set of $x$ where a sequence convergences in terms of set operations

I'm befuddled by this. Suppose $f:\mathbb{R}\to\mathbb{R}$, $f_n:\mathbb{R}\to\mathbb{R}$, $n=1,2,\dots$, and consider the set $$\bigcap_{k\geq 1}\bigcup_{p\geq 1}\bigcap_{m\geq p}\{x\in\mathbb{R} \ ...
4
votes
1answer
201 views

Cantor's diagonal argument meets logic

(I'm not normally dealing much with set theory and logic, so excuse me if my choice of words below seems a bit off the traditional terminology.) Where does the following Cantor-inspired argument go ...
1
vote
0answers
15 views

set theory question in ZF [duplicate]

Let A and B infinite sets and |A|<=|B|. Is that equivalent to |P(A)|<=|P(B)| in ZF? P denotes the powerset. I think it is equivalent, but I dont know exactly how to prove it.
3
votes
1answer
35 views

Well ordered sets, set theory

Define a relation $R$ among ordered pairs of ordinals by $(\gamma,\delta)R(\lambda,\kappa)$ if $\gamma +\delta<\lambda +\kappa$ or $\gamma +\delta=\lambda +\kappa$ and $\gamma<\lambda$ (1) ...
1
vote
2answers
42 views

The proof of Zorn's Lemma

In the book Halmos's proof of Zorn's Lemma. it says that if $C$ is a chain in $\mathbb{X}$(the collection of chain in $X$), then the union of the sets in $C$ belongs to $\mathbb{X}$. I don't ...
3
votes
2answers
29 views

cardinality of infinite sets with cartesian product

claim: $A,B,C,D$ are infinite if $|A\times B|=|C\times D|$ then $|A|=|C|$, $|B|=|D|$ , prove or give a counter example. So imo, the claim is false, using $A=D=\mathbb{R}$ , $B=C=\mathbb{N}$ , is it ...
0
votes
2answers
236 views

Why it is always circle to represent a Set?

When we draw a Venn diagram, we use circle to represent a Set. We can use any closed plane figure but most of the time it is a circle. Why? are there any specialty about that?
1
vote
3answers
26 views

Using set theory to count the possible paths on an XY plane

I'm taking an introductory discrete math course, and we're studying set theory. It's going okay, but I read an example problem which gave me some difficulty. I've included a screenshot of the problem. ...
2
votes
1answer
56 views

How to prove that $max(\aleph_{0}, card(X)) = max(\aleph_{0}, card(L(X)))$?

I struggle with the following problem. Let $X$ be a set of elementary sentences and $L(X)$ be the smallest elementary language in which we can express all the sentences from $X$. How to prove that ...
0
votes
1answer
39 views

Condition for Axiom of Specification

In set theory,the Axiom of Specification claims the existence of the subset under the condition $P(x)$, I am wondering under what kind of condition, we can directly say that this set is not empty ...
3
votes
1answer
14 views

Combination of supermodular and submodular functions

Suppose the production function $v(x,y)$ is increasing and submodular in both arguments, and the production function $c(x,y)$ is increasing and supermodular in both arguments ($x,y \geq 0$). Is the ...
3
votes
1answer
47 views

Show that if $B \subseteq C$, then $\mathcal{P}(B) \subseteq \mathcal{P}(C)$ [duplicate]

Can someone please verify this? Show that if $B \subseteq C$, then $\mathcal{P}(B) \subseteq \mathcal{P}(C)$ let $x \in \mathcal{P}(B)$. Then, $x \subseteq B$ This implies that $$\forall a \in ...
0
votes
1answer
31 views

Which of the following becomes true when $\in$ is inserted in place of the blank? Which become true when $\subseteq$ is inserted?

Can someone please verify my answers? Which of the following becomes true when $\in$ is inserted in place of the blank? Which become true when $\subseteq$ is inserted? (a) $\{\phi\}$ __ ...
1
vote
3answers
58 views

Help understanding Cantor's Theorem

I am having trouble understanding the proof of Cantor's Theorem: https://proofwiki.org/wiki/Cantor%27s_Theorem http://www.whitman.edu/mathematics/higher_math_online/section04.10.html The part that ...
1
vote
1answer
29 views

Ill-Founded Sets in ZFC

Let $\mathbb{N}$ be the set of all finite ordinals defined as the intersection of all ordinals including the empty set and closed under successor. Consider the following set: $S_0 = \mathbb{N}$ ...
0
votes
0answers
26 views

Right continuous but not left continuous function and cardinality

I have been given the following question, Let $f:\mathbb{R}\to\mathbb{R}$ be an arbitrary function and $L=\left\{x:\text{f is right continuous but not left continuous at }x \right\}$. Prove that $L$ ...
0
votes
2answers
60 views

Proof by contradiction for a set question

I have a statement I need to prove by contradiction: If A and B are sets then A intersect (B-A) = {} (empty set). None of the questions I've ever done for this class are like this so im not really ...
0
votes
2answers
28 views

Discrete Math and Sets and subsets question

Let Universe be {1,2,3,4,5,6} If A = {1,2,3,4} then |A| = 4, and from this we can see that A is an element of U(universe), but can someone explain to me why {A} is NOT an element of U? I'snt the ...
0
votes
1answer
22 views

Do the following properties characterize the set membership?

Given a set $S$, a relation $R \subseteq S \times \mathcal P(S)$ has the following properties: $\forall x \in S, \forall A, B \in \mathcal P(S)$, $(x, \emptyset) \notin R$ if $x \in A$, then $(x,A) ...
2
votes
3answers
48 views

Lifting an equivalence relation on elements to a relation on sets

If every element of $A$ is equivalent (by an equivalence relation $R$) to some element of $B$ $\forall x\in A\ldotp \exists y \in B\ldotp x\,R\,y$ and vice versa $\forall y\in B\ldotp ...
0
votes
2answers
24 views

Relation between the euclidean space and a set of functions.

Let $n$ be an integer. In what sense can $\mathbb{R}^n$ be seen as the collection of functions $\lbrace n\to \mathbb{R}\rbrace$? (-what is $n$ here?) And also, does this (bijection of sets, I guess?) ...
1
vote
0answers
33 views

On $\sigma$-algebra generated by sets

Given $\mathcal{S}$ a collection of subsets of $X$ and $A\subset X$. To show that $\sigma(\mathcal{S}\cap A)=\sigma(S)\cap A$, where for any collection of $\mathcal C$ of subsets of $X$, $\mathcal ...
3
votes
2answers
27 views

Some questions in set theory about belonging

Some questions about set theory: 1.If $a$ is an element of a set $A$, is it a subset of $A$ or not? 2.If not, can $A$ be a subset of $a$ ?
1
vote
1answer
16 views

How can I show that this has a reflexive closure?

Assume R is a relation on A. Show that R ∪ ΔA is the reflexive closure of R. What I thought is, that if R is an union with ΔA, it must mean that all a in A are (a,a). But I don't know if this is ...
1
vote
1answer
57 views

Is it true , if $|A|=|B|$ and $|C|=|D|$, then $|A \times C| = |B \times D|$?

Check my proof, please. Divide into subsets $A \times C$ and $B \times D$ so that , all pairs with the same element belong to the same subset. Each such subset $|A \times C|$ bijective $C$, $|C|=|D|$ ...
0
votes
2answers
39 views

Prove that $f(m,n) = 2^m(2n +1 ) -1 $ is a bijection

Basically this proves that set of natural numbers is equinumerous to its cartesian product with itself. f I have tried proving injectivity and surjectivity.Here is what I have done so far. To prove ...
1
vote
1answer
68 views

Countable union of cartesian product.

Let $I^1_j$ $1$-dimensional intervals( of the form $[a,b)$) and $I^n_j$ be $n$-dimensional interval(of the form $[a_1,b_1)\times \ldots\times [a_n,b_n)$) such that $I_j\times I^n_j$ are pairwise ...
0
votes
1answer
17 views

Describing circles as a indexed family of sets.

I have the following task: "Describe the following as an indexed family of sets. Here $\Pi$ denotes the coordinatized xy-plane: The family of all circles in $\Pi$ of radius 1." the general equation ...
1
vote
2answers
29 views

Proof that the subset relation is reflexive and transitive

I'm teaching myself set theory, and I'm not sure how detailed I should be when asked to prove things. Here is my proof that $A\subseteq A$ (the subset relation is reflexive): $A \subseteq B$ iff ...
3
votes
1answer
40 views

Trying to prove lim inf $(A_n) \subseteq$ lim sup $(A_n)$

I am trying to show that for a sequence of sets $(A_n)$ $$ lim \ inf \ (A_n) \subseteq lim \ sup \ (A_n)$$ I can see why this is true intuitively as follows - $x \in lim \ inf \ (A_n)$ $\implies ...
1
vote
2answers
44 views

Is the powerset of a countably infinite set countable? [duplicate]

I remember having heard that if $S$ is countable infinite, then $\mathcal P(S)$ is uncountably infinite. My intuition, however, tells me it should not be. Since $S$ is countable, you can enumerate it. ...
1
vote
0answers
20 views

A set system generated by a closure operator?

Given a ground set $E$, and a matroid closure operator $\tau$ on $\mathcal P(E)$, we can define a set system $(E,F)$ with $$ F := \{X \in \mathcal P(E): \forall x \in X, x \notin \tau(X-\{x\}) \}$$ ...
2
votes
3answers
92 views

What is the difference between a set that is countable and infinite and one that is countably infinite?

I am rereading my analysis notes and I came on this remark in the section on countability: We have proved that Q is countable, and certainly Q is not finite, because N ⊆ Q. We have not proved that Q ...
0
votes
0answers
45 views

Real Analysis - Proving a function is injective

I just need a nudge in the right direction. I know one-to-one (injective) functions but I have never seen it like this: Let $i\colon \mathbb Z\to \mathbb Q$ be defined by $ i(x)=[(x,1)]$ for all ...
0
votes
1answer
71 views

How can we prove these equivalence relations [closed]

We have this relation $A= (\mathbb Z_{\geq0})\times(\mathbb Z_{\geq0})\times\ldots\times(\mathbb Z_{\geq0})$. And we have the relation $R$ on $A$ such that: $(a , b)R(c , d)\iff a+d=c+b$ and ...
0
votes
2answers
49 views

Axiom of Pairing

Axiom of Pairing states that if $a,b$ are sets, $\exists$ a set $A$ such that $A=\{{a,b\}}$.But why we can't just write the set $A=\{a,b\}$ explicitly so we don't need that axiom?
1
vote
0answers
41 views

bijective function $h:\mathbb{N}\rightarrow A\cup B$ from bijective functions $f:\mathbb{N}\rightarrow A$, $g:\mathbb{N}\rightarrow B$

Let $A,B\subseteq \mathbb{N}$ and let $f:\mathbb{N}\rightarrow A$, $g:\mathbb{N}\rightarrow B$ be bijective functions. What are ways to construct a bijective function $$h:\mathbb{N}\rightarrow A\cup ...