This tag is for elementary questions on set theory, spanning topics usually found in introductory courses in set theory, in addition to review sections of graduate textbooks in the same field. Topics include intersections and unions, de Morgan's laws, Venn diagrams, relations, functions, ...

learn more… | top users | synonyms

1
vote
0answers
23 views

Stating the domain of a function using set notation

I'm trying to write the domain of $f(x+y) = \frac{1}{1+ x + y}$ given $f(x) = \frac{1}{1+ x}$ using set notation. I'm thinking first we'd have something like $Domain[ f(x) ] = \mathbb{R} \setminus ...
0
votes
1answer
22 views

When is the preimage of codomain not equal to domain?

I need to show that For every $X\subseteq A$, $X \subseteq f^{-1}(f(X))$, where $f: A\to B$. I think I understand why this is true. However, under what circumstances are they not equal? When is ...
1
vote
1answer
31 views

On half open and half closed intervals.

Which interval is commonly referred to as half closed? Is there any problem if I refer to it as half open?
-1
votes
2answers
37 views

Can decreasing sequence of sets with $A_i$ containing infinitely less elements than $A_{i-1}$ have finite limit?

An updated question to one I just asked. Can we have a decreasing sequence of sets $A_n$ each a subset of the natural numbers with all members containing countably infinitely many elements such that ...
9
votes
9answers
3k views

Set Interview Question, Any Creative Way to solve?

I ran into a simple question, but I need an expert help me more to understand more: The following is True: $ A - (C \cup B)= (A-B)-C$ $ C - (B \cup A)= (C-B)-A$ $ B - (A \cup C)= (B-C)-A$ and ...
0
votes
1answer
57 views

Proving that $f(W\cap X) \subseteq f(W) \cap f(X)$

I am trying to write the proofs and/or counterexamples to these problems, but I'm not sure if my proofs are right; I have trouble trying to write proofs. Theorem $5.4.2.$ Suppose $f: A \rightarrow ...
2
votes
0answers
23 views

Showing that an intersection of indexed sets is a subset of every individual indexed set

I am required to show that for every $k \in I$, $\bigcap_{i\in I}A_{i}\subseteq A_{k}$ where $I$ is an index for a collection of subsets $A_{i}\subseteq S$, $i \in I$. This seems obvious to me from ...
1
vote
1answer
53 views

When to use $\in$ and $\subseteq$ when talking about bases and topologies

Can someone demonstrate a concrete example of when to use $\in$ and $\subseteq$ when talking about topologies and bases? When is something $\subset$ of a basis or a topology and when is something ...
0
votes
0answers
27 views

Want to disprove $\exists$ an injection from $(A-B) \rightarrow B.$

Prove (or disprove) $\#(A-B) \leq \#B$. Can someone please check my work? Want to show $\exists$ a function $j$ such that for some $x_1,x_2 \in (A-B)$, $j(x_1) = j(x_2) \land x_1 \neq x_2$ ...
-1
votes
2answers
45 views

Prove that $f \circ g = g \circ f$ from A to A [duplicate]

How do I prove that if A is set and each of f and g is a function from A to A, then f o g = g o f? Edit: If this is not true how can I prove that it is false using sets?
1
vote
2answers
25 views

Prove $A\setminus(B \cup C) = (A \setminus B) \cap (A \setminus C)$ using element chasing?

How can I prove $A \setminus(B \cup C) = (A \setminus B) \cap (A \setminus C)$ using element chasing? I need to verify that it is correct and show the steps of element chasing.
6
votes
1answer
173 views

Why can't we order Complex Numbers? [duplicate]

I know this may very well be a silly question. I always hear that Complex numbers cannot be ordered. But there's something I'm missing... Why can't we just compare two complex numbers $z_1,z_2$ as ...
0
votes
2answers
22 views

How to prove this equality about functions over indexed and intersecting sets?

Let $f:A\to B$ be a map of sets, and let $\left\{X_{i}\right\}_{i\in I}$ be an indexed collection of subsets of $A$. I need to prove that $f\left(\bigcap_{i\in I} X_{i}\right) \subset \bigcap_{i\in ...
1
vote
1answer
22 views

Trying to prove $f(n) = |\{n' \in A| n' < n\}|$ is surjective ($A$ is infinite set of integers

As title says, I have some infinite set of integers $A$, a function $f:A \to \mathbb N$ defined by $f(n) = |\{n' \in A| n' < n\}|$ is surjective. I'm having problems proving it. I'm not entirely ...
2
votes
2answers
62 views

Filters on $\omega$

I am currently reading the book "Set theory on the real line" by Bartoszynski and Judah and I do have problems to proof the following statement: Suppose $\mathcal{F}$ is a filter on $\omega$ including ...
0
votes
1answer
25 views

elements of nested sets

I was thinking about elements of the power set, and I know that for a power set $P=\{\{\},\{a\},\{b\},\{a,b\}\}$ that $\{\},\{a\},\{b\},\{a,b\}$ are all elements of $P$. However, if you have another ...
1
vote
1answer
30 views

Concerning families of sets regarded as functions

In the course I am taking of axiomatic set theory we've defined a family of sets $F$ indexed by $I$ as any function satisfying $dom(F)=I$, where there are no assumptions about its image. This ...
0
votes
2answers
52 views

Well-formed formula, systematically rule out

Does the following formula is or is not a well-formed formula of the language of set theory? $a\in (A\subset B)$ and in either case How to systemtically tackle the above question?
1
vote
1answer
60 views

If there is an injection from $A$ to $B$, is there an injection from $A\times C$ to $B\times C$?

UPDATE: Want to show $\exists$ an injection $g:(A \times C) \rightarrow (B \times C)$. We assume $\#A \leq \#B \iff \exists$ an injection $h:A \rightarrow B$ We can let $g(a,c) = (h(a),c)$, where ...
1
vote
1answer
22 views

Prove: the cardinality of the set (A-B) is less than or equal to the cardinality of A

Hi this is my first question so please bear with me. My question is this. If A and B are sets, is $ \#(A-B) \leq \#(A) $ True? I drew some Venn diagrams and intuitively this seems to be true, $ ...
0
votes
0answers
13 views

Order type of a sum ($\bigcup$) of sets

A quick question. Is $$\textrm{ot}(\bigcup\limits_{\gamma <\lambda}\alpha_{\gamma})=\bigcup\limits_{\gamma <\lambda}\textrm{ot}(\alpha_{\gamma})?$$ where $\textrm{ot}$ stands for the order type ...
0
votes
1answer
17 views

I am confused about some specific types of domains and ranges that are provided in questions

There are some specific type of questions based on functions which map from some domain to range which is confusing to me... For example, can someone explain what sort of mapping is this: $g: ...
1
vote
1answer
37 views

Is $f(n)=\begin{cases} \frac{n}{2}&\text{if}~n~\text{is even}\\ \frac{-n-1}{2}&\text{if}~n~\text{is odd}\end{cases}$ a bijection?

let f define by : $$f(n)=\begin{cases} \frac{n}{2}&\text{if}~n~\text{is even}\\ \frac{-n-1}{2}&\text{if}~n~\text{is odd}\end{cases}$$ I would like to show that $f$ is a bijection from ...
0
votes
2answers
31 views

Increasing set or decreasing set

I know this is probably trivial but I am confused on how we determine a set is increasing or decreasing. For example suppose we have a set $\{E_j\}_{1}^{\infty}\subset M$ where $M$ is a ...
0
votes
0answers
40 views

Difficulty in understanding Cantor's diagonal argument

I recently found Cantor's diagonal argument in Wikipedia, which is a really neat proof that some infinities are bigger than others (mind blown!). But then I realized this leads to an apparent paradox ...
2
votes
2answers
68 views

Discrete Math: Multiplying a set by ∅

How would you multiply any set by $\varnothing$? Lets say $A \times \varnothing$. Would that simply be equal to $\varnothing$? or Would I write out $(a, \varnothing ), (a_1, \varnothing), (a_2, ...
2
votes
4answers
63 views

Show that $(A \cup B)-B=A$ is false. Why is my method wrong?

So the textbook uses a counter example to show this which is pretty simple. I tried playing around with the algebra. Ie. $(A \cup B)-B$ is equal to $(A \cup B)\cap \bar{B}$ and associative law says ...
0
votes
0answers
29 views

How does the cardinality of the set of all functions from $A$ to itself relate to that of $A$?

If $A$ is a set with cardinality $c$, what can we say about the cardinality of the set of all functions from $A$ to itself?
2
votes
2answers
30 views

$X$ be a non-empty subset of irrational numbers such that sum of any two elements of $X$ is rational ; then is there any upper bound for $|X|$?

Let $X$ be a non-empty subset of irrational numbers such that sum of any two elements of $X$ is rational ; then is there any possible upper bound for the cardinality of $X$ ? Can $X$ be infinite ?( I ...
0
votes
3answers
24 views

Prove transitivity or not of some relation

I'm trying to prove if this equation is an equivalence relation or not. $R =\{(x,y) \in N\times N: \mbox{There exist }m,n \in N\mbox{ such that } x^m = y^n\}$ It's relatively easy to prove both ...
0
votes
2answers
26 views

Show that if $X= \emptyset$ and $r \in \mathbb{R}$ then $r\emptyset=\emptyset+r=\emptyset$.

Show that if $X= \emptyset$ and $r \in \mathbb{R}$ then $r\emptyset=\emptyset+r=\emptyset$. Defitinions: $X+r=\{x+r:x\in X\}$, $rX=\{rx:x\in X\}$. Can you hint me? I know I will use these ...
-1
votes
0answers
25 views

Let $X$ be a set. Let X be closed under $-$. Then, so, X is closed under $+$.

Prop. Let $X$ be a set. Let X be closed under $-$. Then, so, X is closed under $+$. Proof. If $X$ is closed under $-$, we have $X-X\subseteq X$. Then, we will show that $X+X\subseteq X$. Note: We ...
2
votes
2answers
76 views

Showing the power set is equinumerous to ${}^X2$

I'm trying to prove that the power set of $X$ and the set of functions from $X$ to $2$ are equinumerous. I think the best way to do so is to define a bijection between the two, but I'm not sure how to ...
-1
votes
3answers
48 views

Find a bijection between the set of real numbers and the interval $(−1, 1) ≡ \{\,x ∈ \Bbb R\mid − 1 < x < 1\,\}$.

Find a bijection between the set of real numbers and the interval $(−1, 1) ≡ \{\,x ∈ \Bbb R\mid − 1 < x < 1\,\}$. Hi am I trying to revise for an an exam and I came across this question which I ...
1
vote
3answers
38 views

Use direct proof to prove: If $A \cap B = A \cap C$ and $A \cup B = A \cup C$, then $B = C$

I'm interested in knowing if the method I used is correct. I've been teaching myself proofs lately and I am having difficulties with how to approach a problem so any general tips would be awesome as ...
1
vote
1answer
54 views

Naive set theory really need axiom of power?

given the axioms of extension, pairing, specification, unions, unordered pair, as stated in naive set theory, this do not ensure the existence for each set of a collection of sets containing among its ...
1
vote
4answers
45 views

Use Direct Proof to Prove: If $A\cup B = A$, then $B\subseteq A$

I started with: Assume $A\cup B = A$, then $x\in A \cup B$. Without loss of generality, let $x \in A$. However, at this point I am not sure what to do. Note: In the textbook, they use ...
0
votes
2answers
20 views

Is this proof about equicardinality correct and/or rigorous? Can it be helped?

Here's the proof than a Cartesian product of two countable sets is countable(the proof is used, for example, in C.Pugh's "Real Mathematical Analysis" with one exception: they prove equicardinality of ...
0
votes
2answers
42 views

How do we know “$x$ belongs to $A$” has a truth value?

In the book "Naive Set Theory," by Paul Halmos, 'belongs to' is not defined. So how do we know that the sentence "$x$ belongs to $A$" is a statement, that is , it has a truth value?
1
vote
1answer
25 views

Equivalence between Minimality Conidition, Well-Founded Property, Descending-Chain-Condition, and Noertherin Induction

Let $(M, \preceq)$ denote a partially ordered set $M$ along with a partial order $\preceq$ on it. Proof of the equivalence between: A: Descending Chain Condition If ($\mathcal{C}$ is a decresasing ...
0
votes
0answers
25 views

A certain question about elementary logic and functions.

I need to understand the following detail. Suppose we know the following is true(we know that composition for functions $\theta, \sigma$ and $\tau$ is well-defined): There is a unque isomorphism ...
1
vote
1answer
41 views

Proof of indexed family set

I am stuck at the following exercise in Velleman's How To Prove it: Suppose $\{A_i\mid i \in I\}$ is a family of sets. Prove that if $\mathscr P\left(\bigcup_{i\in I}A_i\right) \subseteq ...
0
votes
0answers
23 views

Well founded tree of height $\omega$

Can someone provide an example of a well-founded tree of height $\omega$. It seems like this would not be possible, as having height $\omega$ would yield an infinite sequence.
3
votes
1answer
48 views

Given bijection between $\mathbb{N}$ and $A$ and $B$, find bijection from $\mathbb{N}$ to $A \cup B$

Let $A$ and $B$ be two countable sets and consider that $f$ is a bijection from $\mathbb{N}$ to $A$ and $g$ is a bijection from $\mathbb{N}$ to $B$. I have to find a bijection from $\mathbb{N}$ to $A ...
0
votes
1answer
17 views

Formula for the characterisc function of a infinite intersections of sets.

Let any characteristic function on set $S$ be denoted by $\mathcal{X}_S$. Note that if $E\cap F=A$ and $E\cup F=B$, then $$ \mathcal{X}_A=\mathcal{X}_E\mathcal{X}_F\hskip 0.4cm \text{and}\hskip0.4cm ...
3
votes
1answer
31 views

Interval notation: infinity, -infinity in closed interval

I was watching a video stream a little bit ago and noticed on an equation without context that had the interval $\left[{-\infty, \infty}\right]$. This was preculiar to me as I've never seen the ...
0
votes
1answer
41 views

Prove that the set of the subsets of N of size n is countable [closed]

How can I prove that the set of subsets of N of size n is countable? X∈P(N) | |X| = n. Where do I go on from here? Also how can I prove that the set of all finite subsets of N is countable.
0
votes
0answers
45 views

Number of connected graphs with multi edges

Given $n$ distinct nodes $1,2...n$, I wish to find the number of connected graphs with these $n$ nodes. I have seen the previous question : How to calculate the number of possible connected simple ...
0
votes
1answer
51 views

Every subset of a finite set is finite (hopefully this would be the last time)

I am so sorry for posting about it more than one time but this is my 4th revision for this proof and I want some feedback.. Note : $[n]$ is $\{1,2,3,4,\ldots,n\}$, a finite set Prop: Every subset of ...
1
vote
0answers
32 views

Verification of proof that the empty set is well ordered

I felt a little weird (stupid) in writing this. I figure that I should just post it here. Claim: $(A,S)$ where $A=\emptyset$ is a linearly ordered set and a well-ordered set. Proof: $S$ is ...