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

0
votes
0answers
25 views

How to show that an $\omega$-sequence is club in a limit ordinal $\gamma$.

Suppose that $\gamma$ is a limit ordinal. We say that a subset $X \subseteq \gamma$ is closed if whenever $\delta < \gamma$ is a limit ordinal and $\sup(X \cap \delta) = \delta$, then $\delta \in ...
1
vote
0answers
34 views

Show a set is countable

Let the set T(8) = {all subsets containing 8 elements of $\mathbb{N}$}. Show that T(8) is countable. Proof: $T(8)=\mathop{\cup}\limits_{n=1}^\infty\{\{n,x_{2},...,x_{8}\}:x_{2},...,x_{8}>n\} = ...
4
votes
0answers
61 views

Deducing the existence of particular functions $\mathbb{N}\longrightarrow\mathbb{Q}$ in the context of Tom Leinster's “Rethinking Set Theory”

This question concerns the set theory given by Tom Leinster in his paper "Rethinking Set Theory," available here: http://arxiv.org/abs/1212.6543 In this paper, axioms for set theory are given in the ...
0
votes
2answers
59 views

How can I prove that these sets are countable infinite?

I am very new to proofs so please excuse any trivial errors. In lecture we were told that: A set $\mathbb S$ is called finite if there exists a one-to-one mapping (bijective mapping) between ...
5
votes
3answers
1k views

Real numbers as element of a universe

defn. A universe is a set $U$ such that: $x\in u\in U\Rightarrow x\in U$ $u\in U$ and $v\in U$ imply $\left\{u,v\right\}, \langle u,v\rangle, u\times v\in U$ $x\in U\Rightarrow \mathcal{P}(x)$ and ...
1
vote
2answers
24 views

Show that $\bigcup_{n=1}^\infty A_n= B_1 \backslash \bigcap_{n=1}^\infty B_n$

Let $\{B_n\}$ be a decreasing set $B_1 \supseteq B_2 \supseteq B_3 \supseteq ....$ Define $A_n = B_1 \backslash B_n$ i.e. $A_1 = \varnothing, A_2 = B_1 \backslash B_2$ If we imagine $\{B_n\}$ as a ...
0
votes
0answers
27 views

Is it possible to define a set $S=\{ x \ |\ 1<x \le 1\}$?

I was wondering what would happen if I defined a set $S$ like this $S=\{ x\ | \ 1<x \le 1\}$. My main question would be if defining $S$ like that would be valid in set theory or if it is ...
1
vote
3answers
31 views

How to phrase a proof of a function from a set A to a set B

Here is a problem: Let $f \subseteq A \times B$ be a function. In many situations you may want to restrict the domain of $f$ or expand its range. If $C \subseteq A$ then define the restriction of $f$ ...
2
votes
2answers
23 views

finding counterexample for identity of sets

Let $A_i,B_i,C_j,D_j$ be sets. I am wondering if the equation $$\bigcup_{i\in I}(A_i\times B_i) \cap \bigcup_{j\in J}(C_j\times D_j)=\bigcup_{i\in I,j\in J}(A_i\cap C_j)\times (B_i\cap D_j) $$ holds. ...
-1
votes
1answer
30 views

set theory simplificaiton (laws of set theory)

I am relatively new to set theory,and I have to simplifiy this $$(Y \setminus X) \cap X $$ I'm stuck, can anyone help me.
0
votes
1answer
25 views

minmum number of subsets of $\{1, 2, 3, … , n\}$, each of cardinality $r$, required such that their intersection is $\{1, 2, 3, … , m\}$

Let $M = \{1, 2, 3, ... , m\}$ and $N = \{1, 2, 3, ... , n\}$ be sets with $m < n$. Let $r \in \{1, ... , n\}$, with $m < r$. What is the minmum number of subsets of $N$, each of ...
0
votes
2answers
29 views

Prove by contradiction that If $R$ is a transitive relation on set $A$ then $R^2$ is transitive.

I saw this problem and read through it but I am still kind of confused as to what $u_1$ and $u_2$ stand for. Prove by contradiction that for a transitive relation $R$ on $A$, $R^2$ is also transitive ...
-2
votes
1answer
32 views

A = { x:x²=1, x is integer} How to get -1?

A = { x:x²=1, x is integer} How to get -1? The answer is -1 and 1. 1² = 1 But where -1 come from?
0
votes
1answer
39 views

How to prove something is an equivalence class?

I don't understand equivalence class and representative function: http://www.cdhmhome.com/uic/math215/S.pdf , I'm looking at examples 37, 1-7 and have already determined which ones are equivalence ...
1
vote
2answers
34 views

Is there a continuous function $f:X\rightarrow Y$ such that $f\big(\cap_{i\in I} A_i) \neq \cap_{i\in I}f\big(A_i)$

Is there a continuous function $f:X\rightarrow Y$ such that $$f\big(\cap_{i\in I} A_i) \neq \cap_{i\in I}f\big(A_i)$$ Where $A_i\subseteq X$ and $I$ is an arbitrary index set. I can easily find a ...
1
vote
0answers
33 views

I'm looking for a good book on FOL and set theory.

I finally decided to really learn some axiomatic set theory, at least the basics. I've studied a bit of FOL, but a review would be nice. In short, I'm looking for a book that focuses on $\sf ZFC$ or ...
2
votes
0answers
56 views

Carother's “certainly” proof about measurable sets

Carother's Real Analysis text has the following Theorem. Can someone check if my proof is correct? $(i \Rightarrow ii)$ Let $E$ be a measurable. Let $I_k$ be open intervals, such that $$m^*(E) ...
0
votes
2answers
25 views

Validity of certain arguments about the countability of infinite sets

I am trying to get an understanding, in layman's terms / on an intuitive level, why some arguments about the countability of infinite sets are valid, and some arguments which seem almost identical on ...
1
vote
1answer
72 views

Should $\bigcap_{n = 1}^\infty (a-\frac{1}{n}, b + \frac{1}{n})$ be $(a,b)$ or $[a,b]$

I am confused about the limiting behavior of as $n \to \infty$, $\bigcap_{n = 1}^\infty (a-\frac{1}{n}, b + \frac{1}{n})$. I have read that it is the case that this set becomes closed, but I can't ...
0
votes
1answer
31 views

Could multiplication be defined as $|A_1 \cup A_2 \cup ..A_n|$?

Taking discrete math which suddenly right now I am thinking of what dividing and multiplication do when it comes to what I learned in this class. But would multiplication be defined as the cardinality ...
0
votes
0answers
30 views

mathematical formula to compute sum of all sub sequences of a number N

We have a number say N and we list down all its sub- sequences and sum them up.SAY for n=123 ,the sum is 177(123+12+23+13+1+2+3). I came across this mathematical formula which computes the sum taking ...
-1
votes
1answer
28 views

Prove set relations without using Venn Diagrams

For sets A and B,(A\B) = A∩B^c show that (A\B)\C ⊆ A(B\C) without using Venn Diagrams show that A∩B and B\A are disjoint without using Venn Diagrams Need explanation to solve this sum. Cheeers!
1
vote
2answers
43 views

Proof of a property of set of all one-to-one mappings

Let $S$ be a nonempty set and $A(S)$ be the set of all one-to-one mappings of $S$ onto itself. I.N. Herstein in Topics in Algebra says (in page 28) that whenever $S$ has three or more elements, we can ...
1
vote
1answer
29 views

How to verify this relationship between area under the graph and the preimage?

Define $h : \mathbb{R} \to [0, \infty)$, Let $H = \{(x,y)| 0 \leq y \leq h(x)\}$ be the area under the graph (including the boundary) I wish to show the following is true: $$H = ...
1
vote
2answers
27 views

Counting number of relations that are symmetric and reflexive.

I've looked at the other two problems similair to mine but I'm having a bit of an issue understanding as their solutions seems a bit more complex. While I for the most part understand my professors ...
0
votes
0answers
31 views

Equivalence Relations and Cardinality

I'm looking at the question below from a past paper: What is an equivalence relation? Say that two sets $X$ and $Y$ are related via the relation $\rho$ if $X$ and $Y$ have the same cardinality. Prove ...
0
votes
1answer
28 views

Clarification needed for a set notation

I have a question with regards to this problem: Let $S = \{1,2,3,4,5,6\}$ and let $P(A): A \cap \{2,4,6\} = \emptyset$ and $Q(A): A \neq \emptyset$ be open sentences over the domain $\mathcal{P}(S)$. ...
0
votes
3answers
86 views

Given $3$ sets if $A \cap B = A \cap C$. Is $B=C$? [closed]

I've been trying to solve this question for a while but I just seem to be missing something. Let $A$, $B$ and $C$ be three sets. If $ A \cap B = A \cap C$ Is $ B=C $ ?
2
votes
1answer
21 views

Why can't we define intersection with all the elements of a filter?

Let's see the definition of a filter with the "$\subset$" order. Let $X$ be a set. We say a non-empty family $\mathcal{F}$ of subsets of $X$ is a filter if: $\emptyset \notin ...
3
votes
1answer
27 views

When is the intersection of $k$ sets non-empty?

Suppose, given a ground set $S$, we have two subsets $A,B \subseteq S$. If we know that $|A|, |B| > \frac{|S|}{2}$, then we know that $A \cap B \neq \emptyset$. Can this be generalized to $k$ ...
1
vote
1answer
41 views

a set $X$ is infinite iff there isn't a bijection from $I_n\subset N$ to it

Consider the set: $$I_n = \{p\in \mathbb{N}; 1<p\le n\}$$ My book says that a set is finite when it's not empty or when there exists, for some $n\in \mathbb{N}$, a bijection: $$\phi: I_n\to X$$ ...
0
votes
1answer
37 views

find an injective function from a finite set to an infinite one, and a surjective inverse

I have to prove that there exists an injective function from $X$ to $Y$, being $X$ a finite set, and $Y$ an infinite set. I must also prove that there exists a surjective function from $Y$ to $X$. My ...
1
vote
1answer
20 views

Notation for arbitrary indexing of summation, integration, and derivation

Suppose I have a multivariate function $f(x_1, x_2, \dots, x_n)$ and I'd like to divide the arguments of this function into two groups. The indices of these groups can be represented by two sets. ...
3
votes
0answers
24 views

Let $A$ be a set with $m$ elements and let $B$ be a set with $n$ elements where $m,n\in \omega$ and $m>n$. If $f:A\to B$, then $f$ is not injective

So I am still learning how to work with infinite sets, and this particular problem is giving me some issues. Right now, I am trying to pick some $x_1,x_2\in A$ such that $f(x_1) = f(x_2)$ to serve as ...
0
votes
1answer
18 views

For a set $A = \{1,3,6,14,18\}$, $x$ relates to $y$, if $y$ is divisible by $x$. Is this set reflexive, symm. antisymm. or transitive?

For a set $A = \{1,3,6,14,18\}$, $x$ relates to $y$, if $y$ is divisible by $x$. Is this set reflexive, symm. antisymm. or transitive? Heres what I have so far for relation $R (1,3), (3,6), (1,6) ...
1
vote
1answer
10 views

Let $A$ be an infinite set and let $B$ be a set such that $A$ is equinumerous to a subset of $B$. Then, $B$ is infinite.

To me, the proof is as simple as this: Let $C\subset B$ such that $A\sim C$. Then, as $A$ is infinite, we have that $C$ is infinite. Thus, as $C\subset B$, it must be that $B$ is infinite. Thus, $B$ ...
1
vote
1answer
24 views

How many antisymmetrical relations are there on a set $B =\{ 1,2,3\}$? [duplicate]

How many antisymmetrical relations are there on Set $B$ if Set $B = \{1,2,3\}$? I believe its three?
0
votes
0answers
28 views

What is meaning of canonical form of a set?

Let A{1,2,3}, B1={1,2}, B2={2,3}. Find minset canonical form of B1 and B2. We know minsets generated by B1 & B2 are A1 = B1 \cap B2^{c} A2 = B1 \cap B2 A3 = B1^{c} \cap B2 A4 = B1^{c}\cap B2^{c} ...
0
votes
2answers
21 views

Is this reflexive, symmetric, antisymmetric or transitive?

Set A contains all points $(x, y)$ on a coordinate plane. The relation $R$ is defined as: point $(x_1,y_1)$ is related to point $(x_2,y_2)$, if $y_1=y_2$. Is this set (A) reflexive, symmetric, ...
0
votes
0answers
39 views

10-Subset Sum: Given a set of integers K and an integer M, is there a subset of exactly 10 elements of K whose sum equals M?

I understand that the more general Subset Sum problem is NP-complete, but I am under the assumption that this more specific version of the problem can be solved in polynomial time. However, I can't ...
1
vote
0answers
22 views

Injective: In what circumstances would there be less than one pre-image of an image?

I am trying to get my head around the different types of function in set theory. In the definition of injective where: if (x',y) is in f and (x'',y) is in f, then x'= x'' in other words y has no ...
1
vote
1answer
34 views

Sets and Universes

A universe is a set $\mathcal{U}$ such that: 1) $x\in\mathcal{U}$ and $y\in x$ implies $y\in\mathcal{U}$ 2) $I\in\mathcal{U}$ and $x_i\in\mathcal{U}$ for every $i\in I$ implies ...
0
votes
0answers
22 views

Can we use the terms 'class of sets' and 'family of sets' interchangeably?

I read in pg-4, Introduction to Topology and Modern Analysis by Simmons that class refers to a set of sets while family refers to a set of classes. I formulated an example for the same - if points are ...
0
votes
2answers
20 views

Is it true that if $cl(S) = int(S) \cup \partial (S)$ and $cl(S) = S \cup \partial (S)$ then $int(S) = S$ which means $S$ is open?

Like the title says, I know: $cl(S) = int(S) \cup \partial (S)$ But also; $cl(S) = S \cup \partial (S)$ But then $S = int(S)$ which is only true if $S$ is an open set. Where is this limitation ...
1
vote
2answers
17 views

Let $X, Y$ be topological spaces and let A ∈ B($X$) (Borel $\sigma$ algebra on $X$), B ∈ B($Y$). How to show that A × B ∈ B($X\times Y$)?

Let X be a topological space. All that I know is Borel $\sigma$ algebra on X is the smallest $\sigma$ algebra generated by $T_X$ i.e. set of all open sets in X. Is there any other characterization of ...
10
votes
1answer
624 views

Is directed set countable, if for each element there are only finitely many smaller ones?

A directed set is a pair $(A,\leq)$ where $\leq$ is a reflexive, transitive relation such that for any $x,y\in A$ we have some $z$ such that $x,y\leq z$. (This comes up when dealing with categorical ...
1
vote
2answers
36 views

Standard notation for 'same' function with different ranges

Does anyone know of a standard notation for the situation when we want to define the 'same' function but on a larger or smaller range. More precisely, if $$f:A \to B$$ is a function and $C$ contains ...
3
votes
1answer
18 views

Comparability of a set and a subset of power set.

It's well known that for any set $A$, $A < P(A)$. But now, I have some question that, WITHOUT AC, can we guarantee that $A \leq X$ or $X \leq A$ whenever $X \subseteq P(A)$? Thank you.
1
vote
2answers
48 views

The number $\binom{8}{4}$ is equal to the number of subsets of size 4 of the set $\{1, \dots, 8\}$

I was asked to proof if is true and give a counter example if it is false. However I prefer True. since all the numbers 1-8 insides the brackets are in the sets. I'm I correct?
0
votes
1answer
21 views

Finding equivalence classes in a set of functions with a condition

I can't seem to work around this problem... Let $n$ and $m$ be two positive integers. $F$ is the set of functions from {1,..,n} to {1,...,m}. We define the relation $R$ as: $f R g$ if and only if ...